张可的博客

[LeetCode]-1，字符串相乘/跳跃游戏2/螺旋矩阵/简化路径

计算机

·

January 18, 2024

·

by

张可

今年打算重新开始刷题了，会保持每周至少两题，我会隔段时间写一篇文章记录最近刷的题和题解思路。

字符串相乘

https://leetcode.cn/problems/multiply-strings/description/

给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。

注意：不能使用任何内置的 BigInteger 库或直接将输入转换为整数。

示例 1:

输入: num1 = "2", num2 = "3"
输出: "6"

示例 2:

输入: num1 = "123", num2 = "456"
输出: "56088"

提示：

解

由于字符串长度最大是 200，所以肯定不能用 int/long 来表示，且题目要求不能使用 BigInteger，那么只能将字符串转成 char 数组使用了。

因此，我们还需要模拟乘法的计算过程来计算两个 char 数组的乘积。

这里我用的是小学时学过的竖式乘法过程。

将 char 转成对应的 int 的方式是：char - 48, 因为 0 的 ASCII 编码是 48.

过程中还会用到另外一个题目的解答，就是字符串相加，因为需要讲每一层乘法的结果相加。

public String multiply(String num1, String num2) {
    if (num1.equals("0") || num2.equals("0")) return "0";
    String sum = "0";
    char[] num1Array = num1.toCharArray();
    char[] num2Array = num2.toCharArray();
    for (int i = num2Array.length - 1; i >= 0; i--) {
        int factory = num2Array[i] - 48;
        StringBuilder sumBuilder = new StringBuilder();
        int zeroCount = num2Array.length - 1 - i;
        for (int c = 0; c < zeroCount; c++) {
            sumBuilder.append('0');
        }
        int plusNumber = 0;
        for (int j = num1Array.length - 1; j >= 0; j--) {
            int num1Factory = num1Array[j] - 48;
            int thisTimeSum = plusNumber + factory * num1Factory;
            sumBuilder.insert(0, thisTimeSum % 10);
            plusNumber = thisTimeSum / 10;
        }
        if (plusNumber > 0) {
            sumBuilder.insert(0, plusNumber);
        }
        sum = addStrings(sum, sumBuilder.toString());
    }
    return sum;
}

public String addStrings(String num1, String num2) {
    int maxLength = Math.max(num1.length(), num2.length());
    char[] num1CharArray = num1.toCharArray();
    char[] num2CharArray = num2.toCharArray();
    List<Integer> result = new ArrayList<>(maxLength + 1);
    int num1Space = maxLength - num1.length();
    int num2Space = maxLength - num2.length();
    boolean hasPlus = false;
    for (int i = maxLength - 1; i >= 0; i--) {
        int num1Item = getIntFromArray(num1CharArray, i, num1Space);
        int num2Item = getIntFromArray(num2CharArray, i, num2Space);
        int sum = num1Item + num2Item;
        if (hasPlus) {
            sum++;
        }
        hasPlus = sum > 9;
        result.add(0, sum % 10);
    }
    if (hasPlus) result.add(0, 1);
    StringBuilder builder = new StringBuilder();
    for (Integer integer : result) {
        builder.append(integer);
    }
    return builder.toString();
}

private int getIntFromArray(char[] array, int index, int space) {
    if (index - space < 0) return 0;
    return array[index - space] - 48;
}

跳跃游戏2

https://leetcode.cn/problems/jump-game-ii/description/

给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。

每个元素 nums[i] 表示从索引 i 向前跳转的最大长度。换句话说，如果你在 nums[i] 处，你可以跳转到任意 nums[i + j] 处:

返回到达 nums[n - 1] 的最小跳跃次数。生成的测试用例可以到达 nums[n - 1]。

示例 1:

输入: nums = [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是2。
     从下标为 0 跳到下标为 1 的位置，跳1 步，然后跳3 步到达数组的最后一个位置。

示例 2:

输入: nums = [2,3,0,1,4]
输出: 2

解

这题我最开始想到的是用贪心算法，但是显然是不对的，连给的示例都过不了。

然后我考虑到，既然目的是跳跃到最后一个元素，那么我可以从后往前开始计算，我只需要找到 n-2 → 0 中所有能一步跳到 n-1 位置的 index 最小的那个元素即可。

然后再从这个元素开始，重复上述步骤。

public int jump(int[] nums) {
    int count = 0;
    int index = nums.length - 1;
    while (index > 0) {
        index = findMinIndex(nums, index);
        count++;
    }
    return count;
}

private int findMinIndex(int[] nums, int index) {
    if (index == 0) return 0;
    int minIndex = index;
    for (int i = index - 1; i >= 0; i--) {
        if (nums[i] + i >= index) {
            minIndex = i;
        }
    }
    return minIndex;
}

螺旋矩阵

https://leetcode.cn/problems/spiral-matrix/description/

给你一个 m 行 n 列的矩阵 matrix ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素。

输入：matrix = [[1,2,3],[4,5,6],[7,8,9]] 输出：[1,2,3,6,9,8,7,4,5]

解

这题还是挺简单的（或者有什么更好的方法我没想到），我的办法比较简单直接，就是按照顺时针的方向步进即可。

然后我还需要一个 state 表示上一次的方向：上/下/左/右。这个 state 用来控制转向。

然后还需要四个 edge 变量表示上下左右的已经扫描完了的边界。

public List<Integer> spiralOrder(int[][] matrix) {
    List<Integer> result = new ArrayList<>(matrix.length * matrix[0].length);
    int leftEdge = -1, topEdge = -1;
    int rightEdge = matrix[0].length;
    int bottomEdge = matrix.length;
    // 0-idle, 1-to right, 2-to bottom, 3-to left, 4-to top.
    int state = 0;
    int i = 0, j = 0;
    while (i > leftEdge && i < rightEdge && j > topEdge && j < bottomEdge) {
        System.out.println(i + ":" + j + ":" + state);
        if (state == 0 || state == 4) {
            for (i = leftEdge + 1; i < rightEdge; i++) {
                result.add(matrix[j][i]);
            }
            i--;
            state = 1;
            topEdge++;
            if (j == topEdge) j++;
        } else if (state == 1) {
            for (j = topEdge + 1; j < bottomEdge; j++) {
                result.add(matrix[j][i]);
            }
            j--;
            state = 2;
            rightEdge--;
            if (i == rightEdge) i--;
        } else if (state == 2) {
            for (i = rightEdge - 1; i > leftEdge; i--) {
                result.add(matrix[j][i]);
            }
            i++;
            state = 3;
            bottomEdge--;
            if (j == bottomEdge) j--;
        } else {
            for (j = bottomEdge - 1; j > topEdge; j--) {
                result.add(matrix[j][i]);
            }
            j++;
            state = 4;
            leftEdge++;
            if (i == leftEdge) i++;
        }
    }
    return result;
}

简化路径

https://leetcode.cn/problems/simplify-path/description/

给你一个字符串 path ，表示指向某一文件或目录的 Unix 风格 绝对路径 （以 '/' 开头），请你将其转化为更加简洁的规范路径。

在 Unix 风格的文件系统中，一个点（.）表示当前目录本身；此外，两个点 （..） 表示将目录切换到上一级（指向父目录）；两者都可以是复杂相对路径的组成部分。任意多个连续的斜杠（即，'//'）都被视为单个斜杠 '/' 。 对于此问题，任何其他格式的点（例如，'...'）均被视为文件/目录名称。

请注意，返回的 规范路径 必须遵循下述格式：

返回简化后得到的 规范路径 。

解

首先创建一个 List 用来存放每一级的文件名，存放进入的文件名一定是规范的，有了这个 List，我们就可以最后方便格式化，以及遇到 '..' 时退回上一级。

然后，用 '/' 分割字符串，得到每一级的文件名，接着按照规则处理即可。

public String simplifyPath(String path) {
    List<String> dirNameList = new ArrayList<>();
    String[] array = path.split("/");
    for (String name : array) {
        if (name.isBlank() || name.isEmpty()) continue;
        StringBuilder builder = new StringBuilder();
        for (char c : name.toCharArray()) {
            if (c != '/') {
                builder.append(c);
            }
        }
        String finalName = builder.toString();
        if (finalName.equals(".")) continue;
        if (finalName.equals("..")) {
            if (!dirNameList.isEmpty()) {
                dirNameList.remove(dirNameList.size() - 1);
            }
            continue;
        }
        dirNameList.add(finalName);
    }
    StringBuilder pathBuilder = new StringBuilder();
    pathBuilder.append('/');
    for (int i = 0; i < dirNameList.size(); i++) {
        pathBuilder.append(dirNameList.get(i));
        if (i < dirNameList.size() - 1) {
            pathBuilder.append("/");
        }
    }
    return pathBuilder.toString();
}

我在 Github 上创建了个仓库用来保存平时的刷题，也可以过去查看全部代码。

https://github.com/0xZhangKe/Algorithms