53最大子数组和

题目

思路解析

我们用一个dp数组来收集我们从左往右，加起来的最大的和

也就是我们的节点不是负数，那我们直接收集就好了

如果是负数，我们就用Max（）比较是这个节点大还是当前节点大（这个情况是为了避免前面的和为-3，而这个节点为-1的这种情况，就是这个节点比前面的最大和还大，那我们就优先用这个节点）

然后Arrays.sort（）排序我们的搜集结果的数组，然后返回结果

代码

class Solution {public int maxSubArray(int[] nums) {int n = nums.length;int dp[] = new int[n + 1];dp[0] = Integer.MIN_VALUE;for (int i = 1; i <= n; i++) {if (dp[i - 1] >= 0) {dp[i] = dp[i - 1] + nums[i - 1];} else {dp[i] = Math.max(nums[i - 1], dp[i - 1]);}}Arrays.sort(dp);return dp[n];}
}

---

56合并区间 

题目

思路解析

根据元素的左短点从小到大进行排序

Arrays.sort(intervals,(a,b)->Integer.compare(a[0],b[0]));

如果当前节点的左边界，小于上一个节点的有边界，说明存在重叠区间，那么就可以合并区间

当我们为最后一个节点或者当前节点的右边界小于下一个节点的左边界，说明不会出现重叠区间了

代码

我的垃圾代码

class Solution {public int[][] merge(int[][] intervals) {List<int[]> list = new LinkedList<>();if (intervals.length <= 0) {return null;}if (intervals.length == 1) {list.add(intervals[0]);return list.toArray(new int[list.size()][]);}// 根据数组元素的左边界来进行排序,然后将排序好的数组放到List里面Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));if (intervals[0][1] < intervals[1][0]) {list.add(intervals[0]);}for (int i = 1; i < intervals.length; i++) {// 如果当前节点的左边界小于上一个节点的右边界,我们添加节点if (intervals[i][0] <= intervals[i - 1][1]) {intervals[i][0] = Math.min(intervals[i - 1][0], intervals[i][0]);intervals[i][1] = Math.max(intervals[i - 1][1], intervals[i][1]);// 该节点为最后一个元素,或者该节点的右边界小于下一个节点的左边界，说明不会出现重叠节点了if (i == intervals.length - 1 || intervals[i][1] < intervals[i + 1][0]) {list.add(intervals[i]);}} // 该节点为最后一个元素,或者该节点的右边界小于下一个节点的左边界，说明不会出现重叠节点了else if (i == intervals.length - 1 || intervals[i][1] < intervals[i + 1][0]) {list.add(intervals[i]);continue;} else {continue;}}return list.toArray(new int[list.size()][]);}
}

灵神的代码

class Solution {public int[][] merge(int[][] intervals) {Arrays.sort(intervals, (p, q) -> p[0] - q[0]); // 按照左端点从小到大排序List<int[]> ans = new ArrayList<>();for (int[] p : intervals) {//ans是目前已经合并的区间，ans.size()是目前已经合并区间的数量int m = ans.size();// 可以合并if (m > 0 && p[0] <= ans.get(m - 1)[1]) { //更新ans里面的区间ans.get(m - 1)[1] = Math.max(ans.get(m - 1)[1], p[1]); // 更新右端点最大值} else { // 不相交，无法合并ans.add(p); // 新的合并区间}}return ans.toArray(new int[ans.size()][]);}
}

---

189轮转数组

 

题目

思路解析

写一个翻转函数

然后整体翻转

再对两个区间分别翻转，这样就好了

特定的翻转位置 k=k%n;

代码

class Solution {public void rotate(int[] nums, int k) {int n = nums.length;k = k % n;//先全体翻转reverse(nums, 0, n - 1);//我们向右轮转了k次，那么就是我们的末尾向右移动了k次//因为我们反转后，我们的末尾变成了我们的头//那么就相当于我们向右移动了1次//然后我们在0->(k-1)这个位置翻转//和k->n-1这个位置翻转，就得到我们的结果了reverse(nums, 0, k - 1);reverse(nums, k, n - 1);}private 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除自身以外数组的乘积

 

题目

思路解析

前后缀分解解法

一个L[]存前面的乘积

一个R[]存后面的乘积

代码

class Solution {public int[] productExceptSelf(int[] nums) {int n = nums.length;int answer[] = new int[n];int L[] = new int[n];int R[] = new int [n];//先初始化为1L[0] = 1;R[n - 1] = 1;for (int i = 1; i < n; i++) {L[i] = nums[i - 1] * L[i - 1];}for (int i = n - 2; i >= 0; i--) {R[i] = R[i + 1] * nums[i + 1];}for (int i = 0; i < n; i++) {answer[i] = L[i] * R[i];}return answer;}
}

---

41缺失的第一个正数

题目

思路解析

哈希表解法（空间复杂度不满足要求）

我们把所有数都放到Map里面

因为我们要找到是整数

所以我们for循环从1开始，来找我们的Map是否包含这个正数

第一个不包含的就是我们的答案

将数组视为Hash表

由于题目要求我们「只能使用常数级别的空间」，而要找的数一定在 [1, N + 1] 左闭右闭（这里 N 是数组的长度）这个区间里。因此，我们可以就把原始的数组当做哈希表来使用。事实上，哈希表其实本身也是一个数组；

我们要找的数就在 [1, N + 1] 里，最后 N + 1 这个元素我们不用找。因为在前面的 N 个元素都找不到的情况下，我们才返回 N + 1；

那么，我们可以采取这样的思路：就把 1 这个数放到下标为 0 的位置， 2 这个数放到下标为 1 的位置，按照这种思路整理一遍数组。

然后我们再遍历一次数组

第 1 个遇到的它的值不等于下标的那个数，就是我们要找的缺失的第一个正数。

这个思想就相当于我们自己编写哈希函数

这个哈希函数的规则特别简单，那就是数值为 i 的数映射到下标为 i - 1 的位置

如何判断该数没有放到正确的位置上（条件判断）

我们是通过某些条件，判断该数没有放到正确的位置上

那我们该如何判断这个数没有放到正确的位置上然后进行两个数之间的交换呢？

for (int i = 0; i < len; i++) {while (nums[i] > 0 && nums[i] <= len && nums[nums[i] - 1] != nums[i]) {// 满足在指定范围内、并且没有放在正确的位置上，才交换// 例如：数值 3 应该放在索引 2 的位置上swap(nums, nums[i] - 1, i);}}

nums【i】>0

因为我们要找正数，所以我们遇到大于0的正数我们就要把他放到正确的位置

nums【i】<=length

数组的有效索引范围是 0 到 len - 1，而缺失的正整数必须在 1 到 len 的范围内

如果 nums[i] 大于 len，那么它不会影响缺失的正整数，因为任何大于 len 的正整数都不可能是缺失的第一个正整数

如果没有这个条件会怎么样？

考虑 nums = [1，5，7]

因为我们的交换条件是nums[nums[i] - 1] != nums[i]

如果我们使用到5的时候，我们的nums[nums[i] - 1]就会出现越界错误

nums[nums[i] - 1] != nums[i]

我们要交换的是数字1到下标为0的位置，数字2到下标为1的位置

也就是nums【i】的值到nums【i】-1的位置

for循环遍历查找第一个不满足的值

我们要找到的值是nums【i】=i+1

当遇到的第一个不满足条件的值，该下标（i+1）就是我们要找的答案

// [1, -1, 3, 4]// [1,2,0]for (int i = 0; i < len; i++) {if (nums[i] != i + 1) {return i + 1;}}// 都正确则返回数组长度 + 1return len + 1;

代码

哈希表解法（空间复杂度不满足要求）

import java.util.HashSet;
import java.util.Set;public class Solution {public int firstMissingPositive(int[] nums) {int len = nums.length;Set<Integer> hashSet = new HashSet<>();for (int num : nums) {hashSet.add(num);}for (int i = 1; i <= len ; i++) {if (!hashSet.contains(i)){return i;}}return len + 1;}
}

将数组视为Hash表

public class Solution {public int firstMissingPositive(int[] nums) {int len = nums.length;for (int i = 0; i < len; i++) {while (nums[i] > 0 && nums[i] <= len && nums[nums[i] - 1] != nums[i]) {// 满足在指定范围内、并且没有放在正确的位置上，才交换// 例如：数值 3 应该放在索引 2 的位置上swap(nums, nums[i] - 1, i);}}// [1, -1, 3, 4]// [1,2,0]for (int i = 0; i < len; i++) {if (nums[i] != i + 1) {return i + 1;}}// 都正确则返回数组长度 + 1return len + 1;}private void swap(int[] nums, int index1, int index2) {int temp = nums[index1];nums[index1] = nums[index2];nums[index2] = temp;}
}