算法题（普通数组）

一、题目1、最大子数组和LC 532、合并区间LC 563、轮转数组LC 189二、题解1、最大子数组和LC 531分析本题使用动态规划的方法解决。最终问题求连续子数组的最大和。步骤一定义子问题求以数组中每个元素结尾的子数组的最大和dp[i]。 定义子问题的思考过程和暴力解法类似暴力是求以每个元素开头的连续子数组最大和但是每次都需要再求一遍而求以数组中每个元素结尾的子数组的最大和求出后求下一个还可以再利用。步骤二状态转移方程如果前一个元素结尾的子数组最大和dp[i-1]为负数则当前的dp[i] nums[i]如果前一个元素结尾的子数组最大和dp[i-1]为正数或零当前的dp[i] dp[i-1] nims[i]。步骤三初态dp[0] nums[0]。步骤四输出遍历过程中记录dp[i]的最大值即为所求连续子数组的最大和。2解答class Solution { public int maxSubArray(int[] nums) { int res nums[0]; int[] dp new int[nums.length]; dp[0] nums[0]; if(nums.length1){return dp[0];} for(int i1; inums.length; i){ if(dp[i-1]0){ dp[i] nums[i] dp[i-1]; }else{ dp[i] nums[i]; } res Math.max(res, dp[i]); } return res; } }2、合并区间LC 561分析先依据每个数组的第一个元素大小对所给的二维数组进行排序。创建动态数组list将二维数组intervals中第一个元素放到list中再对intervals的后面元素做以下判断如果和list中的最后一个元素last重叠就与last合并更新last如果不与last重叠就将这个元素添加到list中。最后将list转化为二维数组就是所求的不重叠的区间数组。2解答class Solution { public int[][] merge(int[][] intervals) { ArrayListint[] list new ArrayList(); Arrays.sort(intervals, (a,b)-a[0]-b[0]); list.add(intervals[0]); for(int i1; iintervals.length; i){ int[] last list.get(list.size()-1); int[] curr intervals[i]; if(last[1]curr[0]){ last[1] Math.max(last[1], curr[1]); }else{ list.add(curr); } } return list.toArray(new int[list.size()][]); }}3、轮转数组LC 1891分析将数组看为两部分后k个元素一部分剩余元素一部分。需要将这两部分调换位置。可以先将这个数组翻转假设k为3如“1234|567”翻转后为“765|4321”。在将两个部分分别翻转“567|1234”这就得到了将原数组轮转k个位置后的数组。这种解法空间复杂度仅为O(1)。2解答class Solution { public void rotate(int[] nums, int k) { int n nums.length; k k % n; reverse(nums, 0, n-1); reverse(nums, 0, k-1); reverse(nums, k, n-1); } public void reverse(int[] nums, int i , int j){ while(ij){ int temp nums[i]; nums[i] nums[j]; nums[j] temp; i; j--; } } }