算法练习04——数组问题

本文介绍: 【代码】算法练习04——数组问题。

53. 最大子数组和（动态规划）

https://leetcode.cn/problems/maximum-subarray/

class Solution {
    public int maxSubArray(int[] nums) {
        int len=nums.length;
        int dp[]=new int[len];
        dp[0]=nums[0];
        int res=nums[0];
        for(int i=1;i<len;i++){
                dp[i]=Math.max(dp[i-1]+nums[i],nums[i]);
                res=Math.max(res,dp[i]);
        }
        return res;
    }
}

56. 合并区间（贪心）

https://leetcode.cn/problems/merge-intervals/

class Solution {
    public int[][] merge(int[][] intervals) {
        List<int[]> res = new LinkedList<>();
        //按照左边界排序
        Arrays.sort(intervals,(x,y)->Integer.compare(x[0],y[0]));
        //initial start 是最小左边界
        int start = intervals[0][0];
        //mostRightIndex是最大右边界
        int mostRightIndex = intervals[0][1];
        for(int i=1;i<intervals.length;i++){
            //如果左边界大于最大右边界
            if(intervals[i][0]>mostRightIndex){
                res.add(new int[]{start,mostRightIndex});
                start=intervals[i][0];
                mostRightIndex=intervals[i][1];
            }else{//如果左边界小于最大右边界
                //更新最大右边界
                mostRightIndex=Math.max(mostRightIndex,intervals[i][1]);
            }
        }
        res.add(new int[]{start,mostRightIndex});
        return res.toArray(new int[res.size()][]);
    }
}

189. 轮转数组

https://leetcode.cn/problems/rotate-array/

class Solution {
    public void rotate(int[] nums, int k) {
        int len=nums.length;
        if(k>len){
            k=k%len;
        }
        reverse(nums,0,len-1);
        reverse(nums,0,k-1);
        reverse(nums,k,len-1);
    }
    public void reverse(int[] nums, int start,int end){
        while(start<end){
            int t=nums[start];
            nums[start++]=nums[end];
            nums[end--]=t;
        }
    }
}