【二刷hot100】day 4

终于有时间刷刷力扣，求实习中。。。。

目录

1.最大子数组和

2.合并区间

3.轮转数组 

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

1.最大子数组和

class Solution {public int maxSubArray(int[] nums) {//就是说可以转换为计算左边的最大值，加上中间的值，加上右边的最大值；//这样的话，就可以使用递归了；int n=nums.length;if(n==0){return 0;}return maxSub(nums,0,n-1);}//计算常规连续的数组最大和public int maxSub(int [] nums,int left,int right){if(left==right){return nums[left];}int mid=(left+right)/2;return Math.max(maxSub(nums,left,mid),Math.max(maxSub(nums,mid+1,right),maxCross(nums,left,mid,right)));}//计算跨越mid元素的最大和public int maxCross(int [] nums,int left,int mid,int right){//s1为临时求和int s1=0;//左边的最大值int max_left=0;int start_left=mid-1;while(start_left>=left){s1+=nums[start_left];max_left=Math.max(s1,max_left);start_left--;}int s2=0;int max_right=0;int start_right=mid+1;while(start_right<=right){s2+=nums[start_right];max_right=Math.max(s2,max_right);start_right++;}//最终结果return max_left+nums[mid]+max_right;//不理解为什么max_left设置为0}
}

2.合并区间

class Solution {public int[][] merge(int[][] intervals) {//按照第一个元素进行排序Arrays.sort(intervals,(a,b)->a[0]-b[0]);List<int[]> ret=new ArrayList<>();for(int [] p:intervals){//当前区间左端点<=最后一个区间右端点，可以合并if(!ret.isEmpty()&&p[0]<=ret.get(ret.size()-1)[1]){ret.get(ret.size()-1)[1]=Math.max(ret.get(ret.size()-1)[1],p[1]);}else{//不能合并，添加区间ret.add(p);}}return ret.toArray(new int[ret.size()][]);}
}

3.轮转数组 

class Solution {public void rotate(int[] nums, int k) {int n=nums.length;k%=n;reverse(nums,0,n-1);reverse(nums,0,k-1);reverse(nums,k,n-1);}private void reverse(int[] nums,int i,int j){while(i<j){int tmp=nums[i];nums[i++]=nums[j];nums[j--]=tmp;}}
}

 

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

class Solution {public int[] productExceptSelf(int[] nums) {//pre表示前缀积；suf表示后缀积；ret=两者之积即可；int n=nums.length;int[] pre=new int[n];pre[0]=1;for(int i=1;i<n;i++){pre[i]=nums[i-1]*pre[i-1];}int[] suf=new int[n];suf[n-1]=1;for(int i=n-2;i>=0;i--){suf[i]=nums[i+1]*suf[i+1];}int[] ret = new int[n];for(int i=0;i<n;i++){ret[i]=pre[i]*suf[i];}return ret;}
}