LeetCode数组题分析与解法（1）

「爱情、让人受尽委屈。」 2023-10-05 12:47 10阅读 0赞

LeetCode上数组题的分析与解法的第一部分。

### 查找中心点 （\#1144） ###

对于一个整数数组，该数组的中心点（pivot）指的是该元素左边的数字之和等于右边的数字之和。比如数组`[1, 7, 3, 6, 5, 6]`的中心点坐标是`3`。

具体的解法是首先计算出数组的总和`sum`，然后依次遍历该数组并累加左边集合`leftSum`，如果数组序号`i`满足`leftSum == sum - nums[i] - leftSum`，这说明`i`就是中心点序号。

public int pivotIndex(int[] nums) {  int sum = 0;  for (int num : nums) {    sum += num;  }  int leftSum = 0;  for (int i = 0; i < nums.length; i++) {    if (leftSum == sum - nums[i] - leftSum) {      return i;    }    leftSum += nums[i];  }  return -1;}

### 至少是其他元素两倍的最大值 （\#1147） ###

对于一个整数数组，总有一个最大值。如果这个最大值至少是其他元素的两倍，就返回该最大值的序号，否则返回`-1`。

在遍历数组的过程中，记录下最大值及其序号，以及第二大值。只需要根据这两个值进行判断即可。

public int dominantIndex(int[] nums) {  int largest = Integer.MIN_VALUE;  int secondToLargest = Integer.MIN_VALUE;  int index = 0;  for (int i = 0; i < nums.length; i++) {    if (nums[i] > largest) {      secondToLargest = largest;      largest = nums[i];      index = i;    } else if (nums[i] > secondToLargest) {      secondToLargest = nums[i];    }  }  if (largest >= 2 * secondToLargest) {    return index;  } else {    return -1;  }}

### 加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`的位置。借助一个辅助数组，可以得到下面的实现。

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`行。

Pascal三角的算法很直接，只需要注意边界情况的处理即可。

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;}