普通数组
53.最大子数组和
53. 最大子数组和
给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
子数组是数组中的一个连续部分。
示例 1：
1
2
3
| 输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。
|
示例 2：
示例 3：
1
2
| 输入：nums = [5,4,-1,7,8]
输出：23
|
方法一：
1.使用动态规划，定义**dp[i]：包括下标i（以nums[i]为结尾）的最大连续子序列和为dp[i]**。
2.确定递推公式，dp[i]只有两个方向可以推出来：
- dp[i - 1] + nums[i]，即：nums[i]加入当前连续子序列和
- nums[i]，即：从头开始计算当前连续子序列和
3.初始化：dp[i]是依赖于dp[i - 1]的状态，dp[0]就是递推公式的基础。
4.确定遍历顺序
递推公式中dp[i]依赖于dp[i - 1]的状态，需要从前向后遍历。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| class Solution {
public int maxSubArray(int[] nums) {
if (nums.length == 0) {
return 0;
}
int[] dp = new int[nums.length];
dp[0] = nums[0];
int ans = dp[0];
for (int i = 1; i < nums.length; i++) {
dp[i] = Math.max(dp[i - 1] + nums[i], nums[i]);
ans = Math.max(dp[i], ans);
}
return ans;
}
}
|
56.合并数组
56.合并数组
以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。
示例 1：
1
2
3
| 输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
输出：[[1,6],[8,10],[15,18]]
解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
|
示例 2：
1
2
3
| 输入：intervals = [[1,4],[4,5]]
输出：[[1,5]]
解释：区间 [1,4] 和 [4,5] 可被视为重叠区间。
|
将列表中的区间按照左端点升序排序。然后将第一个区间加入 merged 数组中，并按顺序依次考虑之后的每个区间：
- 如果当前区间的左端点在数组 merged 中最后一个区间的右端点之后，那么它们不会重合，我们可以直接将这个区间加入数组 merged 的末尾；
- 否则，它们重合，我们需要用当前区间的右端点更新数组 merged 中最后一个区间的右端点，将其置为二者的较大值。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| class Solution {
public int[][] merge(int[][] intervals) {
if (intervals.length == 0) {
return new int[0][2];
}
Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
List<int[]> ans = new ArrayList<int[]>();
int num = 0;
for (int i = 0; i < intervals.length; i++) {
int l = intervals[i][0], r = intervals[i][1];
if (i == 0 || ans.get(ans.size() - 1)[1] < l) {
ans.add(new int[]{l, r});
} else {
ans.get(ans.size() - 1)[1] = Math.max(r, ans.get(ans.size() - 1)[1]);
}
}
return ans.toArray(new int[ans.size()][2]);
}
}
|
189.旋转数组
189.旋转数组
给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。
示例 1:
1
2
3
4
5
6
| 输入: nums = [1,2,3,4,5,6,7], k = 3
输出: [5,6,7,1,2,3,4]
解释:
向右轮转 1 步: [7,1,2,3,4,5,6]
向右轮转 2 步: [6,7,1,2,3,4,5]
向右轮转 3 步: [5,6,7,1,2,3,4]
|
方法一：使用额外的数组
我们可以使用额外的数组来将每个元素放至正确的位置。用 n 表示数组的长度，我们遍历原数组，将原数组下标为 i 的元素放至新数组下标为 (i + k) mod n 的位置，最后将新数组拷贝至原数组即可。
1
2
3
4
5
6
7
8
9
10
11
12
| class Solution {
public void rotate(int[] nums, int k) {
int n = nums.length;
int[] tmp = new int[n];
for (int i = 0; i < n; i++) {
tmp[(i + k) % n] = nums[i];
}
System.arraycopy(tmp, 0, nums, 0, n);
}
}
|
方法二：数组反转
我们可以先将所有元素翻转，这样尾部的 k mod n个元素就被移至数组头部，然后我们再翻转[0, k mod n − 1] 区间的元素和 [k mod n, n − 1] 区间的元素即能得到最后的答案。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| class Solution {
public void rotate(int[] nums, int k) {
k = k % nums.length;
reverse(nums, 0, nums.length - 1);
reverse(nums, 0, k - 1);
reverse(nums, k, nums.length - 1);
}
public void reverse(int[] nums, int l, int r) {
while (l < r) {
int temp = nums[l];
nums[l] = nums[r];
nums[r] = temp;
l++;
r--;
}
}
}
|
238. 除自身以外数组的乘积
238. 除自身以外数组的乘积
给你一个整数数组 nums，返回 数组 answer ，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。
题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。
请 不要使用除法，且在 O(*n*) 时间复杂度内完成此题。
示例 1:
1
2
| 输入: nums = [1,2,3,4]
输出: [24,12,8,6]
|
示例 2:
1
2
| 输入: nums = [-1,1,0,-3,3]
输出: [0,0,9,0,0]
|
左侧所有数字的乘积和右侧所有数字的乘积（即前缀与后缀）相乘得到答案。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| class Solution {
public int[] productExceptSelf(int[] nums) {
int n = nums.length;
int[] l = new int[n];
int[] r = new int[n];
l[0] = 1;
for (int i = 1; i < n; i++) {
l[i] = nums[i - 1] * l[i - 1];
}
r[n - 1] = 1;
for (int i = n - 2; i >= 0; i--) {
r[i] = nums[i + 1] * r[i + 1];
}
int[] ans = new int[n];
for (int i = 0; i < n; i++) {
ans[i] = l[i] * r[i];
}
return ans;
}
}
|
41. 缺失的第一个正数
41. 缺失的第一个正数
给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。
请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。
示例 1：
1
2
3
| 输入：nums = [1,2,0]
输出：3
解释：范围 [1,2] 中的数字都在数组中。
|
示例 2：
1
2
3
| 输入：nums = [3,4,-1,1]
输出：2
解释：1 在数组中，但 2 没有。
|
示例 3：
1
2
3
| 输入：nums = [7,8,9,11,12]
输出：1
解释：最小的正数 1 没有出现。
|
我们可以对数组进行一次遍历，对于遍历到的数 x=nums[i]，如果 x∈[1,N]，我们就知道 x应当出现在数组中的 x−1的位置，因此交换 nums[i]和 nums[x−1]，这样 x 就出现在了正确的位置。在完成交换后，新的 nums[i]可能还在[1, N]的范围内，我们需要继续进行交换操作，直到 x∉[1,N]。
注意到上面的方法可能会陷入死循环。如果 nums[i] 恰好与 nums[x−1] 相等，那么就会无限交换下去。此时我们有 nums[i]=x=nums[x−1]，说明 x 已经出现在了正确的位置。因此我们可以跳出循环，开始遍历下一个数。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| class Solution {
public int firstMissingPositive(int[] nums) {
int n = nums.length;
for (int i = 0; i < n; i++) {
while (nums[i] > 0 && nums[i] <= n && 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 < n; i++) {
if (nums[i] != i + 1) {
return i + 1;
}
}
return n + 1;
}
}
|
