彩票创建网站,广州新塘做网站,庆阳在线网,商务网站开发作业终于有时间刷刷力扣#xff0c;求实习中。。。。
目录
1.最大子数组和
2.合并区间
3.轮转数组
4.除自身以外数组的乘积 1.最大子数组和
class Solution {public int maxSubArray(int[] nums) {//就是说可以转换为计算左边的最大值#xff0c;加上中间的值#xff0c…终于有时间刷刷力扣求实习中。。。。
目录
1.最大子数组和
2.合并区间
3.轮转数组
4.除自身以外数组的乘积 1.最大子数组和
class Solution {public int maxSubArray(int[] nums) {//就是说可以转换为计算左边的最大值加上中间的值加上右边的最大值//这样的话就可以使用递归了int nnums.length;if(n0){return 0;}return maxSub(nums,0,n-1);}//计算常规连续的数组最大和public int maxSub(int [] nums,int left,int right){if(leftright){return nums[left];}int mid(leftright)/2;return Math.max(maxSub(nums,left,mid),Math.max(maxSub(nums,mid1,right),maxCross(nums,left,mid,right)));}//计算跨越mid元素的最大和public int maxCross(int [] nums,int left,int mid,int right){//s1为临时求和int s10;//左边的最大值int max_left0;int start_leftmid-1;while(start_leftleft){s1nums[start_left];max_leftMath.max(s1,max_left);start_left--;}int s20;int max_right0;int start_rightmid1;while(start_rightright){s2nums[start_right];max_rightMath.max(s2,max_right);start_right;}//最终结果return max_leftnums[mid]max_right;//不理解为什么max_left设置为0}
} 2.合并区间
class Solution {public int[][] merge(int[][] intervals) {//按照第一个元素进行排序Arrays.sort(intervals,(a,b)-a[0]-b[0]);Listint[] retnew 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 nnums.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(ij){int tmpnums[i];nums[i]nums[j];nums[j--]tmp;}}
} 4.除自身以外数组的乘积
class Solution {public int[] productExceptSelf(int[] nums) {//pre表示前缀积suf表示后缀积ret两者之积即可int nnums.length;int[] prenew int[n];pre[0]1;for(int i1;in;i){pre[i]nums[i-1]*pre[i-1];}int[] sufnew int[n];suf[n-1]1;for(int in-2;i0;i--){suf[i]nums[i1]*suf[i1];}int[] ret new int[n];for(int i0;in;i){ret[i]pre[i]*suf[i];}return ret;}
}
