山东省建设部网站,网站降权不更新文章可以吗,md风格的wordpress主题,专业做展会网站283.移动零
题目#xff1a;
给定一个数组 nums#xff0c;编写一个函数将所有 0 移动到数组的末尾#xff0c;同时保持非零元素的相对顺序。
请注意 #xff0c;必须在不复制数组的情况下原地对数组进行操作。
示例 1:
输入: nums [0,1,0,3,12] 输出: [1,3,12,0,0] …283.移动零
题目
给定一个数组 nums编写一个函数将所有 0 移动到数组的末尾同时保持非零元素的相对顺序。
请注意 必须在不复制数组的情况下原地对数组进行操作。
示例 1:
输入: nums [0,1,0,3,12] 输出: [1,3,12,0,0] 示例 2:
输入: nums [0] 输出: [0]
思路
使用双指针i和j。第一遍遍历i从左到右遍历数组遇到非零元素即赋值给j所在的位置。因为j的数量一方面等于非零元素的个数另一方面等于最终形态数组的左边最后一个非零元素的下标-1。相当于一个数组长度是4最后一个元素的下标就是4-1为3 第二遍再从j下标开始遍历一直到数组结尾都赋值为0即相当于从最终形态数组的左边最后一个非零元素的下一个即零元素一直到数组结尾都赋值为0.
java代码
class Solution {public void moveZeroes(int[] nums) {int lennums.length;if(nums null||len0) return;int j0;for(int i0;ilen;i){if(nums[i]!0){nums[j]nums[i];}}for(int ij;ilen;i)nums[i]0;}
}效率
时间上为1ms击败了99%的用户。不用再优化了。
11.盛最多水的容器
题目
给定一个长度为 n 的整数数组 height 。有 n 条垂线第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。
找出其中的两条线使得它们与 x 轴共同构成的容器可以容纳最多的水。
说明你不能倾斜容器。 n height.length 2 n 10^5 0 height[i] 10^4
思路
暴力做法从左到右遍历每次都固定左边界然后再从左边界开始遍历右边界。这样可以涵盖所有面积的情况。但是因为是双重循环所以时间复杂度为ON。
双指针做法针对这种两边边界都会移动的情况下我们优化时首先需要考虑的就是双指针。暴力循环的做法每次固定左边界右边界移动会让底和高同时变化。这样就让我们无法提前判断是否某些情况是无需遍历的可以被优化的。基于此我们要思考的就是如何移动能只有一个因素影响面积。 我们发现如果不是固定左边界然后右边界从左边界处从左到右遍历。而是左右边界都各自放在坐标的左右边界这样就确保了移动的过程中底是越来越小的只有高变化时才有可能出现面积更大的可能。那么就只有一个因素影响面积。 接下来我们需要判断什么时候移动左边界什么时候移动右边界。同理我们只需要移动高度较小的那边。因为高度较小的那边限制了面积只有移动他才有可能出现面积更大的情况。 这个题力扣官方讲解的很好建议还是不明白的话去看下官方讲解视频。
java代码
class Solution {public int maxArea(int[] height) {int lenheight.length;int ans0;int i0;int jlen-1;while(ji){int mminMath.min(height[i], height[j])*(j-i);ansMath.max(ans, mmin);//考虑移动左指针还是右指针//如果左指针的高度比右指针小那么此时移动左指针才有可能找到面积更大的区域if(height[i]height[j]){//移动左指针i;}else j--;}return ans;}
}效率
4ms击败 61.80%使用 Java 的用户还行没啥需要优化的空间了。
