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

目录

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;
    }
}