由()承担_重庆seo霸屏_常州seo排名收费_百度一下网页首页

53.最大子数组合

贪心，和小于0就抛弃

class Solution {public int maxSubArray(int[] nums) {int count = 0;int res = Integer.MIN_VALUE;for(int i = 0 ; i<nums.length ; i++ ){count += nums[i];if(count > res) res = count;if(count <= 0) count = 0;}return res;}
}

56.合并区间

注意：

1. 使用两个指针记录当前需要对比的区间左右边界，初始化为第一个区间，遍历结束还要放入一次。
2. 注意出现重合时，左右边界都需要比较极值。
3. 注意sort的比较规则，结果为负数a在b前面。
4. 注意LinkedList为链表适合插入操作，toArray方法可以传入转换成的目标数组。

class Solution {public int[][] merge(int[][] intervals) {Arrays.sort(intervals , (a,b) -> a[0]-b[0]);List<int[]> res = new LinkedList<>();int left = intervals[0][0];int right = intervals[0][1];for(int i = 1 ; i<intervals.length ; i++){if(right>=intervals[i][0]){left = Math.min(left,intervals[i][0]);    //注意right = Math.max(right,intervals[i][1]);  //注意}else{res.add(new int[]{left,right});left = intervals[i][0];right = intervals[i][1];}}res.add(new int[]{left,right});return res.toArray(new int[res.size()][0]);}
}

189.轮转数组

使用新数组：

1. 注意新数组和原数组的位置对应关系
2. 注意System.arraycopy( 原数组，复制起始位置，新数组 ，终止位置，复制长度）

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

不使用新数组：

通过三次翻转数组实现，向右移动k以后，最后k个元素会到头部，先将整体数组翻转，再将前面k个元素翻转，和后面元素翻转即可。

class Solution {public void rotate(int[] nums, int k) {reverse(nums,0,nums.length-1);reverse(nums,0,k-1);reverse(nums,k,nums.length-1);}private void reverse(int[] nums, int start , int end){int left = start;int right = end;while(left<right){int temp = nums[right];nums[right] = nums[left];nums[left] = temp;left++;right--;}}
}

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

计算出当前元素左边元素乘积和，和右边元素乘积，相乘即可

class Solution {public int[] productExceptSelf(int[] nums) {int len = nums.length;int[] left = new int[len];int[] right = new int[len];left[0] = 1;for(int i = 1 ; i<len ; i++){left[i] = nums[i-1]*left[i-1];}right[len-1] = 1;for(int i = len-2 ; i>=0 ; i--){right[i] = nums[i+1]*right[i+1];}int[] res = new int[len];for(int i = 0 ; i<len ; i++){res[i] = right[i]*left[i];}return res;}
}

优化，左边乘积和可以在结果计算过程中用常数保存。

class Solution {public int[] productExceptSelf(int[] nums) {int len = nums.length;int[] right = new int[len];right[len-1] = 1;for(int i = len-2 ; i>=0 ; i--){right[i] = nums[i+1]*right[i+1];}int[] res = new int[len];int left = 1;for(int i = 0 ; i<len ; i++){res[i] = left*right[i];left *= nums[i];}return res;}
}

41.缺失的第一个正数

为了满足时间复杂度为O(N)，空间复杂度为O(1)，需要利用题目给定的数组。

1. 数组长度为n，所以数组最多出现n个顺序正整数，此时结果为n+1；
2. 因为负数值是无意义的，所以首先将负数值设为n+1（不影响对数组做标记）；
3. 遍历数组，将绝对值处于1-N之间的数，在对应 num-1位置处增加负号；
4. 遍历数组如果出现正数则说明出现缺失，输出该位置+1，否则遍历结束输出N+1。

class Solution {public int firstMissingPositive(int[] nums) {int len = nums.length;for(int i = 0; i<len ; i++){if(nums[i]<=0){nums[i] = len+1;}}for(int i = 0; i<len ; i++){int num = Math.abs(nums[i]);if(num<=len ){nums[num-1] = -Math.abs(nums[num-1]);   }}for(int i = 0; i<len ; i++){if(nums[i]>0){return i+1;}}return len+1;}
}