目录

1089. 复写零

法一：用栈实现

法二：用双指针

202. 快乐数

11. 盛最多水的容器

611. 有效三角形的个数

LCR 179. 查找总价格为目标值的两个商品

15. 三数之和

18. 四数之和

---

1089. 复写零

题目链接：1089. 复写零 - 力扣（LeetCode）

法一：用栈实现

解题思路：

        ❁ 将遍历到的数据放入栈中

        ❁ 如果放入的数据为0，且栈中数据 < arr.size()，则再放入一个0

        ❁ 如果栈中数据 >= arr.size()，直接结束循环

        ❁ 将栈中的数据逆序（因为栈是先进后出）放入答案数组ans

class Solution {
public:// 用栈来实现void duplicateZeros(std::vector<int>& arr) {int size = arr.size();std::stack<int> st;int top = 0, i = 0;while (top < size) {st.push(arr[i]);top++;if (top < size && arr[i] == 0) {st.push(0);top++;}i++;}for (int i = 0; i < size; i++) {arr[size - 1 - i] = st.top();st.pop();}}
};

法二：用双指针

解题思路：

        ❁ 题目要求：原地操作

        ❁ 我们可以先思考异地的操作，然后发现可以定义一个cur指针和一个dest指针，cur指向原数组，dest指向答案数组，当cur指向的值为非0，则cur++, dest++，否则cur++, dest += 2

        ❁ 再由异地操作思考原地操作，但是发现当dest > cur时，会修改cur后面的值，导致答案错误 ----> 思路转换 ----> 转换为从后向前修改

        ❁ 需要我们先找到最后一个被放入答案数组的位置 -----> 也就是找到cur最后指向的位置

        ❁ 从后向前修改数组，arr[dest] = arr[cur],如果arr[cur] == 0,则arr[dest - 1] = arr[cur]

        ❁ 注意点：dest可能再修改数组前 = size，那将造成越界访问；而dest = size的原因是：cur最后指向的元素为0，因此在修改数组前，应该判断是否dest == size，如果满足，则将arr[size - 1] = 0, cur--, dest -= 2

如下代码用top替代上面的dest,用i替代上面的cur 

class Solution {
public:// 双指针实现void duplicateZeros(vector<int>& arr){int size = arr.size();int top = -1/*因为指向最后位置*/, i = 0;// 注意顺序// 找cur最后的位置// 1、判断cur位置的值// 2、根据cur的值移动dest// 3、判断dest的位置// 4、移动curwhile (i < size){if (arr[i] == 0)top++;top++;if (top >= size - 1)// 已经到达最后一个位置break;i++;}// 越界了，dest = sizeif (top == size){arr[size - 1] = 0;top -= 2;i--;}// 从后向前修改数组while (i >= 0 && top >= 0){arr[top] = arr[i];top--;if (arr[i] == 0){arr[top] = 0;top--;}i--;}}
};

202. 快乐数

题目链接：. - 力扣（LeetCode）

解题思路：       

1、实际上这是一个一定成环的问题，我以2为例，这个例子不会变成1

 

2、如果能变为1，也将陷入循环 

 

3、不管会不会变成1，都会陷入循环，我们只需要判断环内的数是不是为1就好了

4、既然变为环，我们就可以联想到判断链表是否成环的那个问题的解法：快慢指针

，在判断链表是否成环的那个问题中快指针每一次走两步，慢指针每一次走一步，而这一题，我们的慢指针只要计算每一位的平方和一次，而快指针要计算每一位的平方和两次

class Solution {
public:// 快慢指针int GetAns(int a) {int ans = 0;while (a) {ans += ((a % 10) * (a % 10));a /= 10;}return ans;}bool isHappy(int n) {int s = n, f = GetAns(n); // 因为如果s和f相等，则下面的循环进不去，因为一定成环，不用继续判断成环的位置// 获得成环时的入口数据// 如当n = 2时，入口数据为4while (s != f) {s = GetAns(s);f = GetAns(GetAns(f));}// 判断入口数据是否为1return s == 1;}
};

11. 盛最多水的容器

题目链接：. - 力扣（LeetCode）

这题太经典了，OI中的题目也常考 

解题思路：

        ⚀ 该题有点贪心思维，根据贪心的思想，我们容易知道，两边的柱子高度越高，盛的水会更容易多

        ⚁ 因此，我们可以用两个指针，一个指向开头，一个指向最后一个元素，然后每次移动较矮的那个指针即可

class Solution {
public:// 用双指针，一个指向左边，一个指向右边，移动更矮的那个指针int maxArea(vector<int>& height){int ret = 0;int l = 0, r = height.size() - 1;while (l < r){if (height[l] < height[r]){ret = max(ret, (r - l) * height[l]);l++;}else{ret = max(ret, (r - l) * height[r]);r--;}}return ret;}
};

611. 有效三角形的个数

题目链接：. - 力扣（LeetCode）

解题思路:

    双指针

    三角形的判断条件是：a + b > c

    所以我们可以先排序，然后固定c，a、b为双指针

    1、如果a + b > c:那么说明a和a到b之间的所有数据都满足a + b > c，因此 ret += b - a;

    同时移动b指针

    2、如果a + b <= c:那么说明a太小了，因此要找一个能满足a + b > c的a，因此要移动a指针

    当a和b指针重叠时，移动c,a定位到0位置，b定位为c的前面一个位置

// 判断是否为三角形：两个小边的和 > 第三边
class Solution {
public:int triangleNumber(vector<int>& nums){if (nums.size() < 3)return 0;int ret = 0;sort(nums.begin(), nums.end());int size = nums.size();int l = 0, r = size - 2;int ptr = size - 1;while (l < r){if (nums[l] + nums[r] > nums[ptr]){ret += r - l;r--;}else{while (l < r && nums[l] + nums[r] <= nums[ptr])l++;}if (l == r){ptr--;l = 0;r = ptr - 1;}}return ret;}
};

LCR 179. 查找总价格为目标值的两个商品

题目链接：LCR 179. 查找总价格为目标值的两个商品 - 力扣（LeetCode）

原剑指offer：和为s的两个数

// 数组已经是升序了// 解法1 哈希：存数据 
// 解法2 双指针：查找
class Solution {
public:vector<int> twoSum(vector<int>& price, int target){int l = 0, r = 1;vector<int>ans(2);int size = price.size();while (r < size && price[l] + price[r] != target){if (price[l] + price[r] > target){l++;r = l + 1;continue;}r++;if (r == size){l++;r = l + 1;}}ans[0] = price[l];ans[1] = price[r];return ans;}
};

15. 三数之和

题目链接：. - 力扣（LeetCode）

解法汇总：

1、使用map，固定两个数，查找第三个数

超时超内存

2、排序 + 暴力枚举 + set去重

3、有序算法要想到：二分  或者 双指针

如果可以用双指针，就用双指针（可以降低时间复杂度）

可以运用两数之和 = target的做法，将三数之和转化为：固定一个数值nums[i]，在其他元素中找和为target3 - nums[i]

这个固定的数值就可以用循环遍历数组来实现

class Solution {
public:// 3、双指针// 先排序，再遍历i，固定i，先判断nums[i] == nums[i - 1]，等于就要continue跳过（去重操作）// 另外l指针为i + 1，r为size - 1，// 1、如果和 > 0，l++// 2、如果和 < 0，r--// 如果和 = 0，加入答案数组，并去重vector<vector<int>> threeSum(vector<int>& nums) {sort(nums.begin(), nums.end());vector<vector<int>>ans;if (nums.size() < 3)return ans;int size = nums.size();for (int i = 0; i < size - 2; i++){if (nums[i] > 0)return ans;// 去重if (i > 0 && nums[i] == nums[i - 1])continue;int l = i + 1, r = size - 1;while (l < r){int sum = nums[i] + nums[l] + nums[r];if (sum > 0)r--;else if (sum < 0)l++;else{ans.push_back({nums[i], nums[l], nums[r]});// 去重while (l < r && nums[l + 1] == nums[l])l++;while (l < r && nums[r - 1] == nums[r])r--;l++;r--;}}}return ans;}
};

18. 四数之和

题目链接：. - 力扣（LeetCode）

解题思路：

        四数之和 转化为 三数之和，三数之和 转化为 两数之和

//注意：不重复/*法一：双指针法，l,r,i,j*/
// 与三数之和类似，无非多了一层循环
class Solution {
public:vector<vector<int>> fourSum(vector<int>& nums, int target) {vector<vector<int>>ans;if (nums.size() < 4)return ans;sort(nums.begin(), nums.end());int size = nums.size();for (int i = 0; i < size - 3; i++){if (i > 0 && nums[i] == nums[i - 1])continue;for (int j = i + 1; j < size - 2; j++){if (j > i + 1 && nums[j] == nums[j - 1])continue;int l = j + 1, r = size - 1;while (l < r){long long sum = (long long)/**/nums[i] + nums[j] + nums[l] + nums[r];if (sum < target)l++;else if (sum > target)r--;else{ans.push_back({nums[i], nums[j], nums[l], nums[r]});while (l < r && nums[l + 1] == nums[l])l++;while (l < r && nums[r - 1] == nums[r])r--;l++;r--;}}}}return ans;}
};