力扣刷题记录10.11

今天主要复习双指针法和贪心算法

2024/10/11

（1） 接雨水

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

（刷过一遍的题果然比较好上手🙂‍↕️🙂‍↕️）

1、动态规划法

思路：遍历数组，得到两个向量数组left和right，left[i]和right[i]分别存储左边、右边的最大值（包括自己本身）。然后再遍历一次数组，在i处两个向量数组的最小值减去本身的高度就是这一格能接到的雨水量。（思路理清了这道题就变得十分简单了）

至于哪里需要动态规划，那就是在找最大值的时候了，需要用一个数组来维护。

注意：边界判断、下标处理

class Solution {
public:
    int tmp,cnt;
    int trap(vector<int>& h) {
        int n=h.size();
        vector<int> left(n),right(n);
        left[0]=h[0],right[n-1]=h[n-1];
        for(int i=1;i<n;i++){
            left[i]=max(left[i-1],h[i]);
            right[n-i-1]=max(right[n-i],h[i]);
        }
        for(int i=1;i<n-1;i++){
            tmp=min(left[i],right[i])-h[i];
            cnt+=tmp;
        }
        return cnt;
    }
};

2、单调栈法

单调栈：单调栈内存储的是下标。如果该下标高度小于栈顶，入栈；否则开始计算两个下标之间可以接的雨水量。

看着代码我能理解，但是我肯定是想不到的。。。。。不想干了。

int cnt;
int trap(vector<int>& h) {
   stack<int> r;
   for(int i=0;i<h.size();i++){
      while(!r.empty()&&h[r.top()]<h[i]){
         int cur=r.top();
         r.pop();
         if(r.empty())
            break;
         cnt+=(min(h[r.top()],h[i])-h[cur])*(i-r.top()-1);
      }
      r.push(i);
   }
   return cnt;
}

3、双指针法

（这又是什么天才的构思。。。）

使用双指针法的目的是降低空间复杂度，思路和动态规划差不多，但是更加聪明。

首先维护两个指针，left从0开始，right从n-1开始；

再维护两个最大值：leftMax和rightMax，分别表示左边的最大值和右边的最大值。

上面动态规划之所以要使用数组去维护最大值，是因为还要进行一次遍历去得到能接到的总雨水值，所以需要比较各个位置的左边最大值和右边最大值。但是双指针法的思路是：

指针从两边往中间靠拢，在没有相遇的时候：

• 如果h[left]<h[right]，那么这个位置的左边最大值就一定小于右边最大值。因此这里可以接到的雨水量就一定是leftMax-h[left]。
• 相反，h[left]>=h[right]，这里接到的雨水量就一定是rightMax-h[right]。

注意：

• 如果算的是左边的雨水量，left++，反之right--。
• 注意维护leftMax和rightMax
• 如果指针相遇，说明已经计算完了雨水量

class Solution {
public:
    int cnt;
    int trap(vector<int>& h) {
        int n=h.size();
        int left=0,right=n-1;
        int leftMax=h[0],rightMax=h[n-1];
        while(left<right){
            leftMax=max(leftMax,h[left]);
            rightMax=max(rightMax,h[right]);
            if(h[left]<h[right]){
                cnt+=leftMax-h[left];
                left++;
            }
            else{
                cnt+=rightMax-h[right];
                right--;
            }
        }        
        return cnt;
    }
};

（2）双指针法

1、合并两个有序数组

给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。

m、n分别从两个数组中最后一个（非零）数字向前遍历，比较大小，选取大的数字放在nums1数组末尾。记得更新指针。

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
            int i=m+n-1;
            m--,n--;
            while(n>=0){
                if(m>=0&&nums1[m]>nums2[n]){
                    nums1[i--]=nums1[m--];
                }
                else{
                    nums1[i--]=nums2[n--];
                }
            }
        }
};

2、移除元素

给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素。元素的顺序可能发生改变。然后返回 nums 中与 val 不同的元素的数量。

假设 nums 中不等于 val 的元素数量为 k，要通过此题，您需要执行以下操作：

• 更改 nums 数组，使 nums 的前 k 个元素包含不等于 val 的元素。nums 的其余元素和 nums 的大小并不重要。
• 返回 k。

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int left=0;
        for(int right=0;right<nums.size();right++){
            if(nums[right]!=val){
                nums[left]=nums[right];
                left++;
            }
        }
        return left;
    }
};

有时候真的很嫉妒别人的彩花。

3、删除有序数组中的重复项

原地删除，顺序保持一致，数组非严格递增排序。

真让我学到东西了😁

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int left=1;
        for(int right=1;right<nums.size();right++){
            if(nums[right]>nums[right-1]){
                nums[left++]=nums[right];
            }
        }
        return left;
    }
};

4、删除有序数组中的重复项 II

给你一个有序数组 nums ，请你** 原地** 删除重复出现的元素，使得出现次数超过两次的元素只出现两次 ，返回删除后数组的新长度。

（脑子，你醒醒啊脑子！！！！！！）

（一开始蠢头瓜脑地真的删元素了。。。于是就跳不出循环了。）

思路：快慢指针。啊啊啊啊讲不清楚，为什么双指针这么令人小脑萎缩。

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int left=0,right=2;
        int n=nums.size();
        if(nums.size()<3) return nums.size();
        while(right<n){
            if(nums[right]!=nums[left]){
                nums[left+2]=nums[right];
                left++;
            }
            right++;
        }
        return left+2;
    }
};

为什么别人的算法如此优雅：

class Solution {
   public int removeDuplicates(int[] nums) {
       int i = 0;
       for (int num : nums) {
           if (i < 2 || num > nums[i - 2]) {
               nums[i++] = num;
           }
       }
       return i;
   }
}

因为||是短路操作符，所以才不会担心i<2时导致nums[i-2]发生数组越界错误。

（3）贪心

1、跳跃游戏

给你一个非负整数数组 nums ，你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。判断你是否能够到达最后一个下标，如果可以，返回 true ；否则，返回 false 。

我的做法：

思路是维护一个数组表示每一格是否能达到；如果前一格能达到且能跳跃的格数大于0，就说明能跳到这一格。然后要更新这一格能跳到的最大格数。

有空间复杂度！！！！！！！！！！！！！！！！！！！！！

而且最后那个三元运算符根本不需要。。。max就行了。。

class Solution {
public:
    bool canJump(vector<int>& nums) {
        int n=nums.size();
        vector<bool> dp(n,false);
        dp[0]=true;
        for(int i=1;i<n;i++){
            dp[i]=dp[i-1]&&nums[i-1]>0;
            nums[i]=nums[i]<nums[i-1]-1?nums[i-1]-1:nums[i];
        }
        return dp[n-1];
    }
};

官方做法：

维护两个值：

• i：表示走到的长度；k：表示目前能达到的最大长度。

现在的位置加上现在能跳跃的距离与k比较取最大值赋给k。

如果i<k，则说明无法达到，直接返回false，循环结束后返回true。

class Solution {
public:
    bool canJump(vector<int>& nums) {
        int n=nums.size();
        int i=0,k=0;
        for(i;i<n;i++){
            if(k<i)
                return false;
            k=max(nums[k]+i,k);
        }
        return true;
    }
};

2、跳跃游戏 II

求到达最后位置的最小跳跃次数

笑死，用dp做怎么反而简单点。。就是性能好差啊，时间复杂度和空间复杂度都击败5%的人。。。😅😅😅😅😅有点离谱了哈。

class Solution {
public:
    int jump(vector<int>& nums) {
        int n=nums.size();
        vector<int> dp(n,INT_MAX);
        dp[0]=0;
        for(int i=1;i<n;i++){
            for(int j=0;j<i;j++){
                if(nums[j]>=i-j){
                    dp[i]=min(dp[j]+1,dp[i]);
                    nums[i]=max(nums[i],nums[j]-i+j);
                }       
            }
        }
        return dp[n-1];
    }
};

看了一眼贪心算法的解法幡然醒悟！！！！！！！！（果然够贪心）

有一个人的比喻我觉得很贴切，就是把起点和终点比喻成河的两岸，从这边到对岸，需要搭桥，维护两个值：上次搭的桥能到达的最大距离；在到达最大距离之前能搭的桥的最大距离。

3、划分字母区间

给你一个字符串 s 。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。

注意，划分结果需要满足：将所有划分结果按顺序连接，得到的字符串仍然是 s 。

返回一个表示每个字符串片段的长度的列表。

为什么为什么这居然能够转换成和上道题几乎一样的思路！！！！！！

合并区间类：

• 首先！有一个天才的思路，就是找到每个字母它最后出现的位置，维护一个数组。
• 然后维护两个值：1、start：这次区间开始的地方；2、这次区间结束的地方。
• 结束的区间怎么算？由于一个字符必须集中在同一个区间，因此结束的位置是，还没到结束位置时，每个字符结束位置的最大值，等到i真的走到了这个最大值，这个区间才算真的结束了。
• 根据这样的算法计算，最后得到的就是能划分的最多的数量。

class Solution {
public:
    vector<int> partitionLabels(string s) {
        vector<int> word(26,0);
        vector<int> num;
        for(int i=0;i<s.size();i++){
            word[s[i]-'a']=max(word[s[i]-'a'],i);
        }
        int end=0,start=0;
        for(int i=0;i<s.size();i++){
            end=max(end,word[s[i]-'a']);
            if(i==end){
                num.push_back(end-start+1);
                start=i+1;
            }
        }
        return num;
    }
};

（4）栈

1、 简化路径

简化后的路径以/作为分隔，开头有/结尾无。..表示返回上一级，.表示此文件。

感觉好多题都是纸老虎呀，看着难但是理清思路后就很简单。

不过我一般都理不清。。😅

stringstream好好用！！！

这道题的思路是，得到所有需要的路径的文件名。

于是第一步我们要把文件名提取出来：

• 如果遇到..就需要返回上一级，也就是弹栈（需保证栈非空）
• 遇空值和“.”可以直接跳过（消除多个/）
• 其他情况，也就是需要入栈的情况

然后从右到左依次连接起来即可。

注意如果没有路径就是返回根路径/。

class Solution {
public:
    string simplifyPath(string path) {
        stack<string> s;
        stringstream ss(path);
        string item;
        while(getline(ss,item,'/')){
            if(item==""||item==".")
                continue;
            else if(item==".."){
                if(!s.empty())
                    s.pop();
            }
            else 
                s.push(item);
        }
        string ans;
        while(!s.empty()){
            ans="/"+s.top()+ans;
            s.pop();
        }
        return ans.size()?ans:"/";
    }
};

2、基本计算器

只涉及+、-、（、）四种符号。

题解较为复杂的有使用双栈去分别存储符号和数字的值，但是感觉这个解法更简练一点。

思路：

• 怎么解决括号内的符号：用一个栈st存储运算符号。初始的运算符号是1，表正值。一旦遇到左括号，就把当前的运算符号压栈，使得括号中的数字按照当前的括号去计算。遇到右括号就出栈，回到原来的运算符号。
• 如何处理计算逻辑：由于栈顶存储的是当前的运算符号，所以如果遇到+号，表示当前运算符号等于栈顶，遇到-号就是栈顶的负值。
• 如何进行数字的计算：这里有一个很巧妙的解决方案，是每次进行运算后，就将num清零。如果遇到的是符号说明或许该进行运算了，可以使用当前运算符*num加上当前的ans值。如果连续遇到数字，就按照十进制赋值。
• ⭐最后的数字没有机会运算，所以要在结果上再运算一下。jiu’jiang

class Solution {
public:
    int calculate(string s) {
        stack<char> st; // 存储正负号
        int ans = 0, num = 0, op = 1;
        st.push(op);

        for (char c : s) {
            if (c == ' ') continue;
            else if (c >= '0') num = num * 10 - '0' + c;
            else {
                ans += op * num;
                num = 0;

                if (c == '+') op = st.top();
                else if (c == '-') op = -st.top();
                else if (c == '(') st.push(op); // 将括号前符号放入栈顶
                else st.pop();
            }
        }
       
        return ans + op * num;
    }
}

（5）滑动窗口

1、长度最小的子数组

给定一个含有 n 个正整数的数组和一个正整数 target 。找出该数组中满足其总和大于等于 target 的长度最小的 子数组[numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int left=0,right=0,cnt=nums.size()+1,ans=0;
        while(right<nums.size()){
            ans+=nums[right];
            if(ans>=target){
                while(ans-nums[left]>=target){
                    ans-=nums[left];
                    left++;     
                }
                cnt=min(cnt,right-left+1);
            }
            if(cnt==1)
                break;
            right++;
        }
        return cnt==nums.size()+1?0:cnt;
    }
};