2020-06-22

题目汇总

LeetCode 43. Multiply Strings

算法思路

乘法直接计算

这道题怎么说呢，做过不难，但是有很多细节，见代码注释。

这里我们先对num1[i]和num2[j]进行乘积，将其暂时存到一个初始化长度为m + n的int数组num中，其中num1[i]和num2[j]相乘我们存储到num[i + j]中，对于i + j相同的值我们加起来存到num[i + j]上。因为长度m的数和长度为n的数字相乘，最多也不过m + n - 1的长度，因此我们不必担心溢出的问题。

然后再进行进位操作，一位位进行计算，细节注释如下:

class Solution {
    public String multiply(String num1, String num2) {
        if (num1.equals(zero) || num2.equals(zero)) {
            return zero;
        }

        // 这道题很巧妙，我们不需要每次乘一次就去运算各种进位什么的，不划算，直接记录每一位的进位值，画个图就懂了。
        int m = num1.length(), n = num2.length();
        int[] numA = new int[m];
        int[] numB = new int[n];
        int[] num= new int[m + n];

        // 从低位到高位存储每一位数字，计算的时候低位运算结果也要写在前面，为了防止和没用到的0相冲突！！！
        for (int i = m - 1; i >= 0; i--) {
            numA[m - 1 - i] = num1.charAt(i) - '0';
        }

        for (int i = n - 1; i >= 0; i--) {
            numB[n - 1 - i] = num2.charAt(i) - '0';
        }

        // res从低位到高位存储，index从0开始
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                num[i + j] += numA[i] * numB[j];
            }
        }

        // 从前向后计算进位
        int temp = 0;
        for (int i = 0; i < m + n; i++) {
            temp += num[i];
            num[i] = temp % 10;
            temp = temp / 10;
        }

        // 从后向前遍历，去掉多余的0，也就是多余的高位0不要
        int end = m + n - 1;
        while (end >= 0 && num[end] == 0) {
            end--;
        }

        // 从后向前依次append每一位
        StringBuilder sb = new StringBuilder();
        for (int i = end; i >= 0; i--) {
            sb.append(Integer.toString(num[i]));
        }

        return sb.toString();
    }
}

LeetCode 48. Rotate Image

算法思路

翻转做法（很tricky）

这道题算是脑筋急转弯，直接背解法即可。

将数组先沿着左上角到右下角的轴线进行对折翻转，然后沿着竖轴中线进行翻转，即可得到答案。

其实这道题还有多种对折方式，画一下，尝试一下！！！顺时针转90度，逆时针转90度等等。

class Solution {
    public void rotate(int[][] matrix) {
        // 先沿着对角线翻转，左上角到右下角的那条线；然后再沿着中轴竖着翻转；
        // 或者沿着左下角到右上角的线进行翻转，然后再沿着横中轴进行翻转。
        int n = matrix.length;

        // 注意不要翻转两遍！！！
        for (int i = 0; i < n; i++) {
            for (int j = 0; j <= i; j++) {
                int temp = matrix[i][j];
                matrix[i][j] = matrix[j][i];
                matrix[j][i] = temp;
            }
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n / 2; j++) {
                int temp = matrix[i][j];
                matrix[i][j] = matrix[i][n - 1 - j];
                matrix[i][n - 1 - j] = temp;
            }
        }
    }
}