ui做的好的网站有哪些,做华为网站的还有哪些,如果做淘宝网站,杭州物流公司目录
1 283. 移动零
2 11. 盛最多水的容器
3 15. 三数之和 菜鸟做题第一周#xff0c;语言是 C 1 283. 移动零
解题思路#xff1a;
两个指针一前一后遍历数组前者永远指向 0#xff0c;后者永远在寻找非 0 数的路上后者找到一个非 0 数就和前者进行一个数值交换
…目录
1 283. 移动零
2 11. 盛最多水的容器
3 15. 三数之和 菜鸟做题第一周语言是 C 1 283. 移动零
解题思路
两个指针一前一后遍历数组前者永远指向 0后者永远在寻找非 0 数的路上后者找到一个非 0 数就和前者进行一个数值交换
思路说明图 上图并没有画出每一步请自行脑补由上图可见i 始终指向 0j 的作用就是寻找非 0 数一旦找到就进行交换
思考过程
本菜鸟一开始交换两数还用的是最传统的 temp 三步法结果被 swap 函数一把子秒了对于双指针既然 i 和 j 必须是一前一后地移动毕竟自己没有和自己交换的必要那为什么初始化的时候要令 j 等于 i 呢这是因为 nums 的长度可能为 1你初始化 j 1 就越界了。
class Solution {
public:void moveZeroes(vectorint nums) {int i 0, j 0;while (j nums.size()) {if (nums[j] ! 0) {swap(nums[i], nums[j]);i;}j;}}
}; 每完成一次交换i 就要向右移动一格毕竟之前的序列已经处理好了。无论交不交换j 都要向右移动一格。若交换则代表 j 当前指向 0若没交换则还是代表 j 当前指向 0 。而 j 是用来寻找非 0 数的因此必须向右移动。 2 11. 盛最多水的容器
解题思路
两个指针一头一尾遍历数组若左侧更低则左边的指针移动若右侧更低则右边的指针移动每次移动完就计算新的面积并和历史最大面积做比较
思路说明图 这里我们的移动标准是 “哪侧的边矮我们就移动哪侧”。为什么这样做呢难道不会遗漏更好的组合吗举个例子对于初始组合 1 和 9面积的高度等于 1 这个矮边又因为 9 离 1 最远所以面积的宽度已经取到了极值这就是针对 1 这个矮边的最大面积了我们再怎么移动右侧的边也不能使面积增大。
同样地当左侧的边移动到 2 时9 成了矮边。在保证 9 是矮边的条件下2 又是离 9 最远的所以面积的宽度已经取到了极值这就是针对 9 这个矮边的最大面积了我们再怎么移动左侧的边也不能使面积增大。
class Solution {
public:int maxArea(vectorint height) {int i 0, j height.size() - 1;int area min(height[i], height[j]) * (j-i);while (i ! j) {if (height[i] height[j]) {i;} else if (height[i] height[j]) {--j;} else {i;}area max(area, min(height[i], height[j]) * (j-i));}return area;}
}; 3 15. 三数之和
解题思路
为数组排序进行三层循环每层循环针对三数中的一个第二层和第三层体现了双指针一个从头开始一个从尾开始
思路说明图
1双指针 传统的三层循环如 method1 所示即 i、j 和 k 都是从左至右遍历数组。但是因为排序后的数字是按从小到大的顺序排序的并且要求 nums[i] nums[j] nums[k] 0 。又由于 i 和 j 是从左至右遍历的nums[i] nums[j] 会变得越来越大因此 nums[k] 应该越来越小这就要求 k 从右至左进行遍历如 method2 所示。
2避免重复 if (i 0 nums[i] nums[i - 1]) continue;
这行代码是为了避免三元组出现重复。如上图所示我们只看第一层循环。
当 i 等于第一个 -4 的时候j 和 k 屁颠屁颠地给 i 找满足要求的组合它们考虑的数字包含 {-4, -1, -1, 0, 1, 2, 2} 。当 i 等于第二个 -4 的时候j 和 k 还是屁颠屁颠地给 i 找满足要求的组合它们考虑的数字包含 {-1, -1, 0, 1, 2, 2} 。
这里少考虑了一个 -4 会影响结果吗答案是并不会。只能说为第二个 -4 找的三元组可能比为第一个 -4 找的少一个罢了如果数组里还有个 8 的话就会少一个 {-4, -4, 8}但这并不影响啊题目要求的就是不能重复所以我们索性跳过第二个 -4反正为它找的三元组已经存在了。
类似地针对 j 也有这样的 if 语句。
if (j i 1 nums[j] nums[j - 1]) continue;
3第三层循环
按理说第三层循环也拿 for 做不就好了吗条件为 j k只要 --k 就好了呀但会超时…… 还是那个思路 “能少循环就少循环”。
while (j k nums[i] nums[j] nums[k] 0) --k;
这里有两个条件。一个是 j 不能遇上 k它避免了 nums[k] 和 nums[i]、nums[j] 取到同一个位置的值另一个是 nums[i] nums[j] nums[k] 0它避免了 nums[i] nums[j] nums[k] 0 以后k 还在一个劲儿地往左移。
class Solution {
public:vectorvectorint threeSum(vectorint nums) {vectorvectorint result;sort(nums.begin(), nums.end());// 第一层循环for (int i 0; i nums.size(); i) {if (i 0 nums[i] nums[i - 1]) continue;int k nums.size() - 1;// 第二层循环for (int j i 1; j nums.size(); j) {if (j i 1 nums[j] nums[j - 1]) continue;// 第三层循环while (j k nums[i] nums[j] nums[k] 0) --k;// 处理循环结果if (j k) break;if (nums[i] nums[j] nums[k] 0) {result.push_back({nums[i], nums[j], nums[k]});}}}return result;}
}; 这道题最离谱的是把 int k nums.size() - 1; 改写到第二层循环里也会超时啊
