leetcode(数组板块)

LeetCode 189. 轮转数组方法一每次取出最后一个元素放到数组头部不推荐运行超时空间复杂度O(n)时间复杂度O(nk)思路每次弹出最后一个插入最前面。import java.util.ArrayList; import java.util.List; class Solution { public void rotate(int[] nums, int k) { int n nums.length; //避免多余循环 k k % n; //数组转ArrayList方便增删 ListInteger arrList new ArrayList(); for (int num : nums) { arrList.add(num); } //循环k次找到并移除最后一个元素将它插入最前面 for (int i 0; i k; i) { int last arrList.remove(arrList.size() - 1); arrList.add(0, last); } //将List结果写回原数组 for (int i 0; i n; i) { nums[i] arrList.get(i); } } }方法二使用翻转的方法空间复杂度O(1)时间复杂度O(n)思路进行三次反转第一次翻转整个数组第二次翻转前k个元素第三次翻转剩余元素例如nums [1,2,3,4,5,6,7] k 3第一次翻转后 [7,6,5,4,3,2,1]第二次翻转后 [5,6,7,4,3,2,1]第三次翻转后 [5,6,7,1,2,3,4]但是是怎样想到这样的解决方案的呢对于这个题我们看到后的第一想法应该是移动元素例如方法一将每个元素从最后面移到前面。如果你想到这一步了那么可以再多想一点像那样的移动是一次只能移一个元素那么我们是否可以一次移动多个元素呢例如nums [1,2,3,4,5,6,7] k 3我们可以将[5,6,7]这个整体一起移到最开头。就变成了[5,6,7,1,2,3,4]。那么问题又来了我们怎样移动一个整体呢可以想到利用翻转操作先把他从最后面翻转到最前面但与此同时也会改变其内部的顺序[x,x,x,...,5,6,7]---[7,6,5,x,x,x,...]所以我们自然的就会想到再进行一次内部的翻转[7,6,5,x,x,x,...]---[5,6,7,x,x,x,...]。处理完[5,6,7]这部分后数组剩下的元素也不能忽略。我们可以发现其他元素其实和移动[5,6,7]的思路一致他们实际上就是整体从最前面移到了最后面这样我们仍然可以用两次翻转来移动。分开单独看两段区块每一段都需要 “全局翻转 自身内部翻转” 两次操作两段理论上需要四次翻转但全局翻转是两段共用的公共步骤可以合并执行一次最终只需要三次翻转就能完成整体轮转。我们可以总结到在数组中移动某一段连续的元素可以利用两次翻转来解决仅考虑这一段元素是两次翻转整体是三次翻转无需额外开辟数组占用空间。那么我们可以拓展一下思路将数组中某段连续的元素移动到某一位置不仅是从最前移动到最后是否也可以使用翻转解决呢class Solution { public void rotate(int[] nums, int k) { int n nums.length; if(n0){return;} //避免多余循环 kk%n; //首先翻转整个数组 reverse(nums,0,n-1); //其次翻转前k个元素 reverse(nums,0,k-1); //最后翻转剩余的元素 reverse(nums,k,n-1); } public void reverse(int[] nums,int l,int r){ while(lr){ int temp nums[l]; nums[l]nums[r]; nums[r]temp; l; r--; } } }Leetcode 56.合并区间思路拿到这道题就会想到先按照左侧元素进行排序再比较右侧的元素是否可以合并。依次考虑不同的结果即可。class Solution { public int[][] merge(int[][] intervals) { //先根据左侧进行排序 int nintervals.length; Arrays.sort(intervals,(a,b)-a[0]-b[0]); int[] current intervals[0];//current代表intervals的第一个数组 Listint[] listnew ArrayList(); //拿左边的第二个数和右边的第一个数比较 for(int i1;in;i){ //如果左边的第二个数右边的第一个数,说明他们可以合并 if(current[1] intervals[i][0]){ //再拿左边的第二个数和右边的第二个数比较 if(current[1]intervals[i][1]){ //如果左边的第二个数右边的第二个数,则更新当前区间的右边界 current[1] intervals[i][1]; } } //如果左边的第二个数右边的第一个数,说明他们不可以合并直接加入集合里 else{ list.add(current); currentintervals[i]; } } list.add(current); return list.toArray(new int[0][]); } }更简洁的写法class Solution { public int[][] merge(int[][] intervals) { // 先根据左侧进行排序 int n intervals.length; Arrays.sort(intervals, (a, b) - a[0] - b[0]); Listint[] list new ArrayList(); // 先将第一个区间加入 list.add(intervals[0]); for (int i 1; i n; i) { int[] last list.get(list.size() - 1); int[] curr intervals[i]; // 如果当前区间的左边界 上一个区间的右边界说明有重叠 if (curr[0] last[1]) { // 合并更新右边界为两者的最大值 last[1] Math.max(last[1], curr[1]); } else { // 没有重叠直接加入 list.add(curr); } } return list.toArray(new int[0][]); } }LeetCode 53. 最大子数组和方法一前缀和维护最小值思路看到这道题要求一个具有最大和的连续子数组根据求和和连续这两个词我们可以想到用前缀和的方法。区间[l, r]的和 preSum[r1] - preSum[l],要让这个差值最大则固定右端r找到当前最小的 preSum [l]这样他们的差值就是最大的。那么我们就需要找出在每个右端点r下的最小的前缀和的值。因此我们的任务可以继续缩减在遍历到每个右端点 i 时如何得到它之前的所有前缀和中的最小值--- 定义一个变量min_persum在遍历过程中不断更新。class Solution { public int maxSubArray(int[] nums) { //定义一个数组 int nnums.length; int[] presumnew int[n1]; //先求出所有的前缀和放入数组中 for(int i 0; i n;i){ presum[i1]nums[i]presum[i]; } // min_presum[i]表示确定右端i后找出的最小前缀和 int[] min_presum new int[n 1]; int maxSum Integer.MIN_VALUE; for (int i 1; i n; i) { //最大值presum[i]-min_presum[i] maxSum Math.max(maxSum, presum[i]-min_presum[i-1]); //求出确定右端点i后找出的最小前缀和 min_presum[i] Math.min(min_presum[i-1], presum[i]); } return maxSum; } }方法二动态规划 DP核心存下子问题答案避免重复算两个条件重叠子问题 最优子结构思路把大问题拆小小问题结果存数组后面直接复用特点求全局最优解会考虑两种选择再取最大值 例最大子数组、背包、打家劫舍class Solution { public int maxSubArray(int[] nums) { int n nums.length; // dp[i] 表示以 i 为右端点时能够得到的最大子数组和 int[] dp new int[n]; dp[0] nums[0]; // ans 记录所有 dp[i] 中的最大值 int ans nums[0]; for (int i 1; i n; i) { // 如果前面的最大子数组和接上当前数更大就接上 // 否则从当前 nums[i] 重新开始一段 dp[i] Math.max(dp[i - 1] nums[i], nums[i]); // 更新最终答案 ans Math.max(ans, dp[i]); } return ans; } }LeetCode 238. 除自身以外数组的乘积思路由于不能用除法所致只能通过乘法来解决那么我们可以通过求得该元素的前面元素相乘的值×后面元素相乘的值来计算。class Solution { public int[] productExceptSelf(int[] nums) { int nnums.length; int[] snew int[n]; //先用一个整数1作为第一个元素的左边的乘积 int pre_s 1; //求出左边元素的乘积 for(int i0;in;i){ s[i]pre_s; pre_s*nums[i]; } //求出右边元素的乘积 int suffix 1; for (int i n - 1; i 0; i--) { //左边乘积×右边乘积 s[i] * suffix; //更新后缀积把当前元素乘进去 suffix * nums[i]; } return s; } }