培训网站建设方案书,电商网站建设如何,在线设计房屋平面图,嘉兴公司的网站设计普通数组 常见的题型有#xff1a; 取模、区间合并、最大子序列和、最长非0子序列等。 一些解题思路很巧妙#xff0c;多练多总结。 Leetcode 53. 最大子数组和 [dp动态查找最大值] 题目理解#xff1a; 给定一个整数数组, 求一个连续的子序列 该子序列满足和最大 要求返回最… 普通数组 常见的题型有 取模、区间合并、最大子序列和、最长非0子序列等。 一些解题思路很巧妙多练多总结。 Leetcode 53. 最大子数组和 [dp动态查找最大值] 题目理解 给定一个整数数组, 求一个连续的子序列 该子序列满足和最大 要求返回最大和 解题思路 动态规划的思路 定义dp数组 dp[i]表示以i为结尾的子序列的最大值 则有递推公式 dp[i]max(dp[i-1]nums[i],nums[i]) 其本质表达的是是需要前面的前缀还是从i位置重新计算 用max维护整个数组中最大的子序列和 1.解题
动态规划版解题
class Solution {public int maxSubArray(int[] nums) {int[] dpnew int[nums.length];dp[0]nums[0];int maxnums[0];for(int i1;inums.length;i){dp[i]Math.max(dp[i-1]nums[i],nums[i]);maxMath.max(max,dp[i]);}return max;}
}
2.复杂度分析 时间复杂度O(n) 遍历数组的时间 空间复杂度O(1) max的存储空间损耗 Leetcode 56. 合并区间 [排序合并] 题意理解 给定多个区间 要求对相互交叠的区间进行合并。 解题思路 为了方便进行合并以所有区间的左边界为准进行排序。 当区间i的右边界i1区间的左边界时两区间交叠——进行合并操作 合并有两种情况 i1的右边界i右边界即i1区间包含在i区间内 将合并的区间更新至i1位置 i1的右边界i的右边界即对i区间的右边界进行更新更新为最远右边界将合并的区间更新至i1位置 当区间i的右边界i1区间的左边界时两区间不交叠 当且仅当下一区间不交叠时将当前合并的区间加入结果集 1.解题
class Solution {public int[][] merge(int[][] intervals) {int lenintervals.length;Arrays.sort(intervals,(a,b)-{return a[0]-b[0];});LinkedListint[] resultnew LinkedList();result.add(new int[]{intervals[0][0],intervals[0][1]});for(int i1;ilen;i){//交叠if(intervals[i-1][1]intervals[i][0]){intervals[i][1]Math.max(intervals[i-1][1],intervals[i][1]);result.getLast()[1]intervals[i][1]; }else{result.add(new int[]{intervals[i][0],intervals[i][1]});}}int[][] resultArrnew int[result.size()][2];for(int i0;iresult.size();i){resultArr[i][0]result.get(i)[0];resultArr[i][1]result.get(i)[1];}return resultArr;}
}
2.复杂度分析 时间复杂度O(nlog) sort排序的时间损耗 空间复杂度O(2n) 区间数组的空间损耗 3.技巧 如何按左边界进行排序 //按照左边界升序排序 Arrays.sort(intervals,(a,b)-Integer.compare(a[0],b[0])); Leetcode 189. 轮转数组 [技巧取模] 题意理解 给定一个数组每次向右旋转轮转k, 求轮转后的结果值 解题思路 将原数组下标为 i的元素放至新数组下标为 (ik) mod n 的位置 其可以想象为在nums前方防止k个空位置则当前的坐标就变成了ik 但是数组大小为n, 则为了将超出数组的元素重新放入对应元素位置则有 index(ik)mod n 取模运算总是在循环0-n-1之间的值 1.解题
class Solution {public void rotate(int[] nums, int k) {int lennums.length;int[] result Arrays.copyOfRange(nums,0,len);for(int i0;ilen;i){nums[(ik)%len]result[i];}}
}
2.复杂度分析 时间复杂度O(n) 遍历数组的时间损耗 空间复杂度O(n) 存储结果的空间损耗
