LeetCode 数组经典题型解析与实现

加 1（#1148）

给定一个表示数字值的数组，对其进行加 1 操作。例如数组 [1, 2, 3] 代表数字 123，加 1 后结果为 [1, 2, 4]。

解法很直观，关键在于处理好进位。难点在于类似 [9, 9, 9] 的情况，此时需要改变数组长度。

public int[] plusOne(int[] digits) {
    for (int i = digits.length - 1; i >= 0; i--) {
        if (++digits[i] <= 9) {
            return digits;
        } else {
            digits[i] = 0;
        }
    }
    int[] result = new int[digits.length + 1];
    result[0] = 1;
    return result;
}

旋转数组（#1182）

给定一个数组，将其元素往右移动 k 个位置。对于数组 [1, 2, 3, 4, 5, 6, 7] 和 k=3，得到的结果是 [5, 6, 7, 1, 2, 3, 4]。

这个问题并不复杂。原来在位置 i 的元素，旋转后会移动到 (i + k) % nums.length 的位置。借助一个辅助数组，可以清晰地实现这一逻辑。

public void rotate(int[] nums, int k) {
    int[] result = new int[nums.length];
    for (int i = 0; i < nums.length; i++) {
        result[(i + k) % nums.length] = nums[i];
    }
    System.arraycopy(result, 0, nums, 0, result.length);
}

Pascal 三角（#1170）

生成 Pascal 三角的前 n 行。

算法逻辑很直接，只需要注意边界情况的处理即可。每一行的首尾都是 1，中间的值等于上一行相邻两数之和。

public List<List<Integer>> generate(int numRows) {
    List<List<Integer>> result = new ArrayList<>(numRows);
    if (numRows == 0) {
        return result;
    }
    result.add(Collections.singletonList(1));
    for (int i = 1; i < numRows; i++) {
        List<Integer> row = new ArrayList<>(i + 1);
        row.add(1);
        List<Integer> lastRow = result.get(i - 1);
        for (int j = 1; j < i; j++) {
            row.add(lastRow.get(j - 1) + lastRow.get(j));
        }
        row.add(1);
        result.add(row);
    }
    return result;
}