leetcode4.10-16

Leetcode 4.10-4.16

4.10

994 腐烂的橘子

广度优先搜索，多源

方法和01矩阵相似，但是不知道为什么出现了bug,代码基本完全一样但是运行报错，找问题找了2个小时还是没有找到问题

4.11

70.爬楼梯

dp

这两天开始接触DP相关的题目

4.12

198 偷房子

120 三角形最小路径和

4.13

今天开始按照代码随想录的顺序进行刷题，争取6月前完成1刷

二分

69.平方根

不愧是经典题目，用二分法以为能过，但是没有考虑整数溢出

1. mid前面加long long

class Solution {
public:
    int mySqrt(int x) {
        int left=0;
        int right=x;
        while(left<=right){
            int mid=(right-left)/2+left;
            if((long long)mid*mid==x)
            return mid;
            else if((long long)mid*mid<x){
                left=mid+1;
            }
            else if((long long)mid*mid>x){
                right=mid-1;
            }
        }
        return right;
    }
};

2.没有想到的解法，还是二分做了一个变式，然后用了除法防止溢出

class Solution {
    public int mySqrt(int x) {
        int i = 1;
        int j = x;
        int ans = 0;
        while (i <=j){
            int mid = i + (j-i)/2;
            // upper bound的形式，因为我们要找的ans要是最接近于x的最大的数，利用upper bound
            if (mid <= x/mid){
                i = mid +1;
                ans = mid; // 只要mid <= x/mid，left左边界就会一直向右移动，ans就会一直更新（变大），直到不在满足mid <= x/mid的条件为止，ans就会停止更新，永远停在满足mid<=x/mid条件下面的最后一次更新，即满足ans * ans <= mid的最大值。
            }
            else
                j = mid-1;
        }
        
        return ans;
    }
}

双指针

367

双指针法，自己想到的是头尾双指针

if(nums[left] == val) { //left位置的元素需要移除
                //将right位置的元素移到left（覆盖），right位置移除
                nums[left] = nums[right];
                right--;
            }
            left++;
            while(right >= 0 && nums[right] == val) right--;

题解算法，自己的头尾双指针写的有漏洞，样例不能全过

4.16

双指针

844 比较含退格的字符串

双指针，对双指针的理解还是不够，这道题在昨天看了评论区的一个方法后，排除了一个越界的bug后成功复现。

思路

快指针FAST去遍历，如果没有遇到’#’,将当前的值赋值给SLOW指向的值，然后快慢指针各自向前移动一步；

如果遇到了’#‘，==这里非常巧妙也是关键==，将slow–,也就是slow后退一格，那么本来slow指向的值会被后面的新值覆盖，相当于把这个值消除了。还有要注意SLOW=0时按上面的逻辑消去会越界的问题，因此要单独讨论。

class Solution {
public:
    bool backspaceCompare(string s, string t) {
        int slow1=0,fast1=0;
        while(fast1<s.size()){
            if(s[fast1]!='#'){
                s[slow1++]=s[fast1++];
            }
            else{
                fast1++;
                if(slow1>0){
                 slow1--;
                }
            }
        }
        int slow2=0,fast2=0;
        while(fast2<t.size()){
            if(t[fast2]!='#'){
                t[slow2++]=t[fast2++];
            }
            else{
                fast2++;
                if(slow2>0){
                slow2--;
                }                /*这里很重要，slow=0时，是没有字符给你消除的，slow--会造成
                				 越界的问题*/
            }
        }
        if(slow2!=slow1){
            return false;
        }
        for(int i=0;i<slow1;i++)
        {
            if(s[i]==t[i]){
                continue;
            }
            else
                return false;
        }
        return true;
    }
};

双指针的题碰到过不少，但是有时候还是没有想到很好的解法，先继续往下刷，后续持续训练

滑动窗口

这个点当时也是很迷，希望有所进步。

也可以说是双指针的一种（还是逃不过双指针），但是解法过程像一个窗口的移动。

209.长度最小的子数组

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int result=INT32_MAX;
        int i=0;
        int sum=0;
        int length=0;
        for(int j=0;j<nums.size();j++){
            sum+=nums[j];
            while(sum>=target){
                length=j-i+1;
                result=result>length?length:result;
                sum=sum-nums[i];
                i++;
            }
        }
        return result==INT32_MAX?0:result;
    }
};