LeetCode 热题 100 | 普通数组

普通数组基础

动态规划五部曲：
1.确定dp数组的含义
2.递推公式
3.dp数组初始化
4.遍历顺序
5.模拟dp数组
合并区间提前排序好数组
轮转数组先翻转全部元素，再根据k % nums.length来翻转不同区间。
前缀和，后缀和的提前计算。如果想省空间，可以把输出数组当作前缀和先存储着，然后动态计算后缀和。
在原数组上进行哈希可以用置换或者负号+下标

53. 最大子数组和

题目讲解：LeetCode
重点：

确定递推公式。dp[i]是必须选取下标i的子数组的最大和。

思路：

确定dp数组的含义
dp[i]是必须选取下标i的子数组的最大和
递推公式
dp[i]=max(nums[i], dp[i-1]+nums[i])
dp数组初始化
dp[0] = nums[0]
遍历顺序
从头到尾
模拟dp数组
-2, 1, -2, 4, 3, 5, 6, 1, 5

复杂度：

n 是数组长度
时间复杂度：O(n)
空间复杂度：O(1)

public int maxSubArray(int[] nums) {int[] dp = new int[nums.length];dp[0] = nums[0];int result = dp[0];for (int i = 1; i < nums.length; i++) {// 重点: 递推公式, 必须取下标i的元素dp[i] = Math.max(nums[i], dp[i - 1] + nums[i]);result = Math.max(result, dp[i]);}return result;
}

56. 合并区间

题目讲解：LeetCode
重点：

提前按照start从小到大排序好数组

思路：

提前按照start从小到大排序好数组
把intervals[0]加入到result中，然后开始遍历intervals。如果当前区间跟result中的最后一个区间重叠了，则更新result中的最后一个区间。如果没有重叠，则直接加入到result中。

复杂度：

n 是intervals数组长度
时间复杂度：O(nlogn)。排序的时间
空间复杂度：O(n)

public int[][] merge(int[][] intervals) {List<int[]> result = new ArrayList<>();// 重点: 提前排序数组Arrays.sort(intervals, Comparator.comparingInt(o -> o[0]));result.add(intervals[0]);for (int i = 1; i < intervals.length; i++) {// 重点: 出现重叠时取最大区间if (result.get(result.size() - 1)[1] >= intervals[i][0]) {result.get(result.size() - 1)[1] = Math.max(result.get(result.size() - 1)[1], intervals[i][1]);} else {result.add(intervals[i]);}}return result.toArray(new int[result.size()][]);
}

189. 轮转数组

题目讲解：LeetCode
重点：

使用额外数组：%nums.length根据新数组位置取模看在旧数组哪个位置
数组翻转：先将所有元素翻转，再翻转[0, k % n − 1]和[k % n, n − 1]

思路：

使用额外数组
初始化新数组，旧数组元素索引+k对旧数组长度取模就是在新数组的位置。
数组翻转
先将所有元素翻转，这样尾部的 k % n 个元素就被移至头部。再翻转[0, k % n − 1]的元素和[k % n, n − 1]的元素就能得到答案

复杂度：

n 是数组长度
使用额外数组
时间复杂度：O(n)
空间复杂度：O(n)
数组翻转
时间复杂度：O(n)
空间复杂度：O(1)

// 使用额外数组
public void rotate(int[] nums, int k) {int[] newNums = new int[nums.length];for (int i = 0; i < nums.length; i++) {// 重点: i+k是新数组的位置, %nums.length根据新数组位置取模看在旧数组哪个位置newNums[(i + k) % nums.length] = nums[i];}System.arraycopy(newNums, 0, nums, 0, nums.length);
}

// 数组翻转
public void rotate(int[] nums, int k) {// 重点: 先将所有元素翻转, 这样尾部的 k % n 个元素就被移至头部// 再翻转[0,k%n−1]的元素和[k%n,n−1]的元素就能得到答案reverse(nums, 0, nums.length - 1);reverse(nums, 0, k % nums.length - 1);reverse(nums, k % nums.length, nums.length - 1);
}
public void reverse(int[] nums, int start, int end) {while (start < end) {int temp = nums[start];nums[start] = nums[end];nums[end] = temp;start++;end--;}
}

238. 除自身以外数组的乘积

题目讲解：LeetCode
重点：

左右乘积列表：提前计算好每个元素左侧和右侧所有数字的乘积。
动态构造R数组：先把输出数组当作 L 数组来计算，然后再动态构造 R 数组得到结果。

思路：

左右乘积列表

两个数组分别存储每个元素左侧和右侧所有数字的乘积。然后遍历数组，左右相乘就可以得到每个位置的答案。

动态构造R数组

先把输出数组当作 L 数组来计算，然后再动态构造 R 数组得到结果。

复杂度：

N 是数组长度
左右乘积列表
时间复杂度：O(N)
空间复杂度：O(N)
动态构造R数组
时间复杂度：O(N)
空间复杂度：O(1)

// 左右乘积列表
public int[] productExceptSelf(int[] nums) {int[] result = new int[nums.length];int[] L = new int[nums.length];// 重点: 存储每个元素左侧所有数字的乘积L[0] = 1;for (int i = 1; i < nums.length; i++) {L[i] = L[i - 1] * nums[i - 1];}int[] R = new int[nums.length];// 重点: 存储每个元素右侧所有数字的乘积R[nums.length - 1] = 1;for (int i = nums.length - 2; i >= 0; i--) {R[i] = R[i + 1] * nums[i + 1];}for (int i = 0; i < nums.length; i++) {result[i] = L[i] * R[i];}return result;
}

// 动态构造R数组
public int[] productExceptSelf(int[] nums) {int[] result = new int[nums.length];// 重点: 先把输出数组当作 L 数组来计算result[0] = 1;for (int i = 1; i < nums.length; i++) {result[i] = result[i - 1] * nums[i - 1];}// 重点: 然后再动态构造 R 数组得到结果int curR = nums[nums.length - 1];for (int i = nums.length - 2; i >= 0; i--) {result[i] = result[i] * curR;curR *= nums[i];}return result;
}

41. 缺失的第一个正数

题目讲解：LeetCode
重点：

对于一个长度为 N 的数组, 其中没有出现的最小正整数只能是[1,N+1]

思路：

负号+下标哈希法
1.把不在[1,N]范围内的数修改成N+1，这样削减所有废数。
2.再把小于等于N的元素当作下标，把对应位置(1就是索引0)改为负数。
3.这时还是正数的元素对应的下标加一就是缺失的最小正数，说明这个下标从来没当作元素出现过。
置换法
1.每次遍历都把该位置上的元素放到它对应的位置上，这样再遍历的时候，如果某个元素不是下标加一说明我们缺失这个正数。

复杂度：

N 是数组的长度
负号+下标哈希法
时间复杂度：O(N)
空间复杂度：O(1)
置换法
时间复杂度：O(N)
空间复杂度：O(1)

// 负号+下标哈希法
public int firstMissingPositive(int[] nums) {// 重点: 把不在[1,N]范围内的数修改成N+1, 这样削减所有废数for (int i = 0; i < nums.length; i++) {if (nums[i] <= 0 || nums[i] >= nums.length + 1) nums[i] = nums.length + 1;}// 重点: 把小于等于N的元素对应的位置(1就是索引0)改为负数for (int i = 0; i < nums.length; i++) {int num = Math.abs(nums[i]);if (num <= nums.length) {nums[num - 1] = -Math.abs(nums[num - 1]);}}// 重点: 这时还是正数的对应下标+1就是缺失的最小正数, 说明这个下标数字从来没出现过for (int i = 0; i < nums.length; i++) {if (nums[i] > 0) return i + 1;}return nums.length + 1;
}

// 置换法
public int firstMissingPositive(int[] nums) {// 重点: 每次遍历都把该位置上的元素放到它对应的位置上for (int i = 0; i < nums.length; i++) {while (nums[i] >= 1 && nums[i] <= nums.length && nums[nums[i] - 1] != nums[i]) {int temp = nums[nums[i] - 1];nums[nums[i] - 1] = nums[i];nums[i] = temp;}}for (int i = 0; i < nums.length; i++) {if (nums[i] != i + 1) return i + 1;}return nums.length + 1;
}