首页 > 其他分享 >「LeetCode Top100」之双指针

「LeetCode Top100」之双指针

时间:2024-08-10 20:49:51浏览次数:12  
标签:right nums int height ans 之双 Top100 LeetCode left

283. 移动零

题目链接:https://leetcode.cn/problems/move-zeroes/description/?envType=study-plan-v2&envId=top-100-liked
题目难度:简单
标签:数组双指针
题目状态:AC

思路:

两个指针,i 用来找 0,j 用来找 非0。当nums[i] == 0 && nums[j] != 0时,将两者交换。

代码:

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int i = 0;
        for(int j = 1; j < nums.size(); ++j) {
            if(nums[i] == 0 && nums[j] != 0) {
                swap(nums[i], nums[j]);
            }
            if(nums[i] != 0) i++;
        }
    }
};

11. 盛最多水的容器

题目链接:https://leetcode.cn/problems/container-with-most-water/description/?envType=study-plan-v2&envId=top-100-liked
题目难度:中等
标签:贪心数组双指针
题目状态:ChatGPT协助

思路:

前后指针,依次遍历,直到前后指针交叉了,每次遍历的时候记录当前遍历得到的最大容量。

代码:

class Solution {
public:
    int maxArea(vector<int>& height) {
        int max = 0;
        int left = 0;
        int right = height.size() - 1;
        while(left < right) {
            if(height[left] < height[right]) {
                max = std::max(max, (right - left) * height[left]);
                left++;
            } else {
                max = std::max(max, (right - left) * height[right]);
                right--;
            }
        }
        return max;
    }
};

15. 三数之和

题目链接:https://leetcode.cn/problems/3sum/description/?envType=study-plan-v2&envId=top-100-liked
题目难度:中等
标签:数组双指针排序
题目状态:AC

思路:

首先对数组进行排序,然后用一个指针来固定第一个元素,之后使用双指针来遍历数组后面的其他元素,寻找三数之和为目标值的三个数,具体细节看代码。

代码:

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> res;
        sort(nums.begin(), nums.end());
        for(int i = 0; i < nums.size(); ++i) {
            if(nums[i] > 0 ) break;
            if(i > 0 && nums[i] == nums[i - 1]) continue;
            int left = i + 1;
            int right = nums.size() - 1;
            while(left < right) {
                int sum = nums[i] + nums[left] + nums[right];
                if(sum > 0) right--;
                else if(sum < 0) left++;
                else {
                    res.push_back({nums[i], nums[left], nums[right]});
                    while(right > left && nums[right] == nums[right - 1]) right--;
                    while(right > left && nums[left] == nums[left + 1]) left++; 
                    left++;
                    right--;
                } 
            }
        }
        return res;
    }
};

42. 接雨水

题目链接:https://leetcode.cn/problems/trapping-rain-water/description/?envType=study-plan-v2&envId=top-100-liked
题目难度:困难
标签:数组双指针动态规划单调栈
题目状态:看题解

题解中给了三种思路,一种动态规划、一种单调栈,一种双指针,个人认为动态规划的方式更好理解,其次是双指针方法,最难是单调栈。

思路一:动态规划

这道题记录了两个动规数组leftMax[i]、rightMax[i],leftMax[i]表示当前位置i的左边最大的值是多少,rightMax[i]表示当前位置i的右边最大的值是多少。当全部记录下来之后,再次遍历数组,判断位置i记录的leftMax和rightMax的最小值,将这个最小值减去i的值,这个值就是积攒的雨水,下图(来自LeetCode官方题解)更好理解:

image

代码一:

class Solution {
public:
    int trap(vector<int>& height) {
        int n = height.size();
        if (n == 0) {
            return 0;
        }
        vector<int> leftMax(n);
        leftMax[0] = height[0];
        for (int i = 1; i < n; ++i) {
            leftMax[i] = max(leftMax[i - 1], height[i]);
        }

        vector<int> rightMax(n);
        rightMax[n - 1] = height[n - 1];
        for (int i = n - 2; i >= 0; --i) {
            rightMax[i] = max(rightMax[i + 1], height[i]);
        }

        int ans = 0;
        for (int i = 0; i < n; ++i) {
            ans += min(leftMax[i], rightMax[i]) - height[i];
        }
        return ans;
    }
};

思路二:单调栈

  1. 初始化变量:
    • ans:用于存储总的雨水量。
    • stk:一个栈,用于存储柱子的索引。
    • n:高度数组的大小。
  2. 遍历高度数组:
    • 对于每个柱子高度height[i]:
      • 检查栈顶元素:如果当前高度大于栈顶的高度,说明可以形成一个“洼地”。
      • 计算雨水量:
        • 弹出栈顶元素,作为当前洼地的底部。
        • 如果栈为空,说明没有左边界,无法形成洼地,继续下一个。
        • 否则,计算当前洼地的宽度 currWidth 和高度 currHeight:
        • currWidth 是当前索引 i 与新的栈顶 left 之间的距离减一。
        • currHeight 是形成洼地的左右边界的最小高度减去底部高度。
      • 将洼地的雨水量加到 ans 中。
  3. 将当前索引压入栈:
    • 继续处理下一个柱子。
  4. 返回结果:
    • 最终返回累计的雨水量 ans。

代码二:

class Solution {
public:
    int trap(vector<int>& height) {
        int ans = 0;
        stack<int> stk;
        int n = height.size();
        for (int i = 0; i < n; ++i) {
            while (!stk.empty() && height[i] > height[stk.top()]) {
                int top = stk.top();
                stk.pop();
                if (stk.empty()) {
                    break;
                }
                int left = stk.top();
                int currWidth = i - left - 1;
                int currHeight = min(height[left], height[i]) - height[top];
                ans += currWidth * currHeight;
            }
            stk.push(i);
        }
        return ans;
    }
};

思路三:双指针

  1. 初始化变量:
    • ans:用于存储总的雨水量。
    • left 和 right:分别指向数组的左右两端。
    • leftMax 和 rightMax:分别记录从左到右和从右到左的最大高度。
  2. 双指针遍历:
    • 当 left 小于 right 时,进行以下操作:
      • 更新 leftMax 和 rightMax,分别为当前指针位置的最大高度。
      • 比较 height[left] 和 height[right]:
      • 如果 height[left] 小于 height[right]:
        • 计算左边可以储水的量 leftMax - height[left],并加到 ans。
        • 移动左指针 left 向右。
      • 否则:
        • 计算右边可以储水的量 rightMax - height[right],并加到 ans。
        • 移动右指针 right 向左。
  3. 返回结果:
    • 最终返回累计的雨水量 ans。
class Solution {
public:
    int trap(vector<int>& height) {
        int ans = 0;
        int left = 0, right = height.size() - 1;
        int leftMax = 0, rightMax = 0;
        while (left < right) {
            leftMax = max(leftMax, height[left]);
            rightMax = max(rightMax, height[right]);
            if (height[left] < height[right]) {
                ans += leftMax - height[left];
                ++left;
            } else {
                ans += rightMax - height[right];
                --right;
            }
        }
        return ans;
    }
};

标签:right,nums,int,height,ans,之双,Top100,LeetCode,left
From: https://www.cnblogs.com/frontpen/p/18348465

相关文章

  • Leetcode 206. 反转链表
    给你单链表的头节点 head ,请你反转链表,并返回反转后的链表。示例1:输入:head=[1,2,3,4,5]输出:[5,4,3,2,1]示例2:输入:head=[1,2]输出:[2,1]示例3:输入:head=[]输出:[]提示: 链表中节点的数目范围是 [0,5000]-5000<=Node.val<=5000方法一: //双指......
  • LeetCode | 20 ValidParentheses
    分析括号成对出现,键值对类型括号字符序列嵌套出现,不能错位,顺序具有对称性为什么不用数组这种数据结构来记录数量?因为这种方法不能保证括号的正确顺序。例如,字符串'({[)}]'会被认为是有效的。栈解决有效括号问题当遇到一个左括号时,我们需要记住它,以便在后续遇到相应的右括......
  • LeetCode | 225 Implement Stack Using Queues
    分析阻塞(Blocking)阻塞操作指的是在调用一个函数或方法时,如果该操作不能立即完成(例如,因为需要等待某个事件的发生,如数据达到或资源可用),那么当前线程或进程会被挂起(暂停执行),直到操作完成为止。在这个等待期间,线程或进程无法执行其他任务。等待:调用方必须等待操作完成独......
  • leetcode-12 字符串
    12.2字符串比较242有效的字母异位词给定两个字符串s和t,编写一个函数来判断t是否是s的字母异位词。注意:若s和t中每个字符出现的次数都相同,则称s和t互为字母异位词。//解法1:排序后逐个比较字符boolisAnagram(strings,stringt){if(s.length()......
  • *算法训练(leetcode)第四十七天 | 并查集理论基础、107. 寻找存在的路径
    刷题记录*并查集理论基础107.寻找存在的路径*并查集理论基础讲解107.寻找存在的路径题目地址直接套模板。结点编号从1开始,因此定义father数组时需要n+1个空间,否则会越界。时间复杂度:O(......
  • LeetCode | 541 Reverse String II
    分析以2k作为游标步长,反转游标前半部分的字符串,后半部分保留;尾部部分余留长度,如果在[k,2k)直接处理情况跟前述一样,如果不是则直接返回。在这道题里面,还是回到数组部分提到的循环不变量法则,在2k长度这个游标移动过程中,处理完全一致:2k步长移动,只处理[2i,2i+k]部分,即便是尾部也是如......
  • 151. 反转字符串中的单词【 力扣(LeetCode) 】
    一、题目描述  给你一个字符串s,请你反转字符串中单词的顺序。  单词是由非空格字符组成的字符串。s中使用至少一个空格将字符串中的单词分隔开。  返回单词顺序颠倒且单词之间用单个空格连接的结果字符串。注意:输入字符串s中可能会存在前导空格、尾......
  • LeetCode | 344 Reverse String
    分析字符数组本质上还是数组,双指针本质上是遍历,遍历过程只处理两个独立数据,移动过程将问题分为已经解决和未解决的两部分。在这个题目中值得注意的是,关于字符数组进行数据原地交换采用的是异或^的方式主类packagecom.github.dolphinmind.string;/***@authordolphinmind......
  • LeetCode | 383 RanSom Note
    分析赎金信在侦探系列是容易出现的场景,为了不暴露自己的笔迹,利用一本杂志里面已有的字符来组装自己的信。倘若这本杂志的字符不够,那么赎金信就无法完成。这道题与Valid-Anagram本质上是一致的。Anagram要求字符类型和数量完全一致,本题要求杂志里面所有的字符串类型和数量是赎金信......
  • 【Leetcode 169 】 多数元素——投票算法要把我迷倒了
     给定一个大小为 n 的数组 nums ,返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊n/2⌋ 的元素。你可以假设数组是非空的,并且给定的数组总是存在多数元素。示例 1:输入:nums=[3,2,3]输出:3示例 2:输入:nums=[2,2,1,1,1,2,2]输出:2提示:n==nums......