Gamer's Show

你知道人生最要紧的事是快乐不停

0%

coding_records

Posted on Edited on In

搜索

二分

35. 搜索插入位置（升序不重复）

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

  • 建议可以复刻一下算法过程，实际上当target < nums[mid] 时，返回值并不需要-1
  • .size()返回的是长度，要-1！
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    class Solution {
    public:
        int searchInsert(vector<int>& nums, int target) {
            int l=0, r=nums.size()-1;    //注意size()
            int flag = 0;
            int mid = (l+r) /2;
            while(l<=r){
                if (nums[mid] == target){
                    return mid;
                }
                if(nums[mid] < target)
                    l = mid + 1;
                else
                    r = mid - 1;
                if(l<=r) mid = (l+r) /2;
            }
            if(nums[mid] > target){
                return mid; //就是这里！画图复现一边代码就能看出来这里不-1！
            }
            else 
                return mid + 1;
        }
    };

34. 搜索指定数的重复区间（上下界bysearch）

常规二分（两遍时间复杂度不变）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        int l = 0,r = nums.size()-1;
        int mid1 = (l+r) / 2;
        int mid2 = (l+r) / 2;
        int f = 0,ans1,ans2;
        while(l<=r){
            if(nums[mid1] == target) ans1 = mid1,f=1;   //需要判定区间边界是否要包含在内
            if( nums[mid1] >= target)
                r = mid1 -1;
            else
                l = mid1 + 1;
            mid1 = (l+r) /2;
        }
        l = 0,r = nums.size()-1;    //重复使用变量需要初始化
        while(l<=r){
            if(nums[mid2]==target)
                ans2 = mid2;
            if( nums[mid2] <= target)
                l = mid2 + 1;
            else
                r = mid2 -1;
            mid2 = (l+r) /2;
        }
        if(f == 1)              //不知道为啥这里判定就是会报错。。
            return {ans1, ans2};
        return {-1,-1};
    }
};

bysearch解法

思路：找到一个大于等于target的最小下标，再找一个大于target的最小下标

  • 把不一样的问题整理成一样的问题可以减少代码量
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    class Solution { 
    public:
        int binarySearch(vector<int>& nums, int target, bool type){
            //bool用来判断是大于等于还是大于,type=1时筛选大于等于
            int l = 0,r = nums.size()-1,ans=-1;
            int mid = (l+r)/2;
            while(l<=r){
                if(nums[mid]==target) ans=mid;//mid是一个中间量，需要ans来记录符合条件的值
                if(nums[mid]>target || (type && nums[mid] >= target)){
                    r = mid -1;
                }
                else 
                    l = mid +1;
                mid =(l+r)/2;
            }
            return  ans;
        }
        vector<int> searchRange(vector<int>& nums, int target) {
            int left = binarySearch(nums,target,1);
            int right = binarySearch(nums,target,0);
            if(left >= 0)
                return {left,right}; //vector类型的返回方式
            else 
                return {-1,-1};
        }
    };

977.有序数组的平方（双指针）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {
        int l = 0, r = nums.size()-1;
        vector<int> ans(nums.size());
        int i = nums.size()-1;
        while(i >= 0){
            int res1 = nums[l]*nums[l];
            int res2 = nums[r]*nums[r];
            if(res1 > res2){
                ans[i] = res1;
                l++;
            }
            else{
                ans[i]=res2;
                r--;
            }
            i--;
        }
        return ans;
    }
};

滑动窗口

209.长度最小的子数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int minSubArrayLen(int s, vector<int>& nums) {
        int result = INT32_MAX;
        int sum = 0; // 滑动窗口数值之和
        int i = 0; // 滑动窗口起始位置
        int subLength = 0; // 滑动窗口的长度
        for (int j = 0; j < nums.size(); j++) {
            sum += nums[j];
            // 注意这里使用while，每次更新 i（起始位置），并不断比较子序列是否符合条件
            while (sum >= s) {
                subLength = (j - i + 1); // 取子序列的长度
                result = result < subLength ? result : subLength;
                sum -= nums[i++]; // 这里体现出滑动窗口的精髓之处，不断变更i（子序列的起始位置）
                //先减随后i自加
            }
        }
        // 如果result没有被赋值的话，就返回0，说明没有符合条件的子序列
        return result == INT32_MAX ? 0 : result;
    }
};
一个我写的的代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int i=0,ans=100001;
        int sum = 0;
        for(int j=0;j<nums.size();j++){
            sum += nums[j];
            while(sum>=target && i<=j){
                int count = j-i+1;
                if(ans>count) ans=count; //注意先判定更新ans再操作
                sum -= nums[i];
                i++;
            }
        }
        if(ans==100001) ans=0;
        return ans;
    }
};

438.找到字符串中所有字母异位词

啊啊啊啊啊啊啊啊啊啊啊啊为什么不对啊啊啊啊啊啊啊啊啊啊啊啊
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        int m=s.length(),n=p.length();
        int pp=0;
        vector<int> ans;
        while(pp<(m-n)){
            int a[30]={0},flag=1;
            for(int i=0;i<m;i++){
                a[p[i]-'a']++;
            }
            for(int i=pp;i<pp+n-1;i++){
                a[p[i]]--;
            }
            for(int i=0;i<26;i++){
                if(a[i]!=0) {
                    flag=0;
                    break;
                }
            }
            if(flag){
                ans.push_back(pp);
            }
        }
        return ans;
    }
};

904.水果成篮(好难捏)

官方解

我们可以使用滑动窗口解决本题，$\textit{left}$ 和 $\textit{right}$ 分别表示满足要求的窗口的左右边界，同时我们使用哈希表存储这个窗口内的数以及出现的次数。

我们每次将 right\textit{right}right 移动一个位置，并将 fruits[right]$\textit{fruits}$[$\textit{right}$]fruits[right] 加入哈希表。如果此时哈希表不满足要求（即哈希表中出现超过两个键值对），那么我们需要不断移动 left\textit{left}left，并将 $fruits[left]\textit{fruits}[\textit{left}]fruits[left]$ 从哈希表中移除，直到哈希表满足要求为止。

需要注意的是，将 $fruits[left]\textit{fruits}[\textit{left}]fruits[left]$ 从哈希表中移除后，如果 $fruits[left]\textit{fruits}[\textit{left}]fruits[left]$ 在哈希表中的出现次数减少为 000，需要将对应的键值对从哈希表中移除。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
    int totalFruit(vector<int>& fruits) {
        int n = fruits.size();
        unordered_map<int, int> cnt;

        int left = 0, ans = 0;
        for (int right = 0; right < n; ++right) {
            ++cnt[fruits[right]];
            while (cnt.size() > 2) {
                auto it = cnt.find(fruits[left]);
                --it->second;
                if (it->second == 0) {
                    cnt.erase(it);
                }
                ++left;
            }
            ans = max(ans, right - left + 1);
        }
        return ans;
    }
};

作者：力扣官方题解
链接：https://leetcode.cn/problems/fruit-into-baskets/solutions/1893352/shui-guo-cheng-lan-by-leetcode-solution-1uyu/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
详解

无注释版

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int totalFruit(vector<int>& fruits) {
        if(fruits.size()<3) return fruits.size();
        int mn=0;
        for(int j=0,f1=0,f2=0,t=0;j<fruits.size();j++){
            if(fruits[j]!=fruits[f1]&&fruits[j]!=fruits[f2]){
                if(f1!=f2) f1=t;
                f2=j;
            }
            if(fruits[t]!=fruits[j]) t=j;
            mn=mn>(j-f1+1)?mn:(j-f1+1);
        }
        return mn;
    }
};

有注释版

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
public:
    int totalFruit(vector<int>& fruits) {
        //当fruits数组长度≤2，则直接返回fruits数组长度
        if(fruits.size()<3) return fruits.size();
//ans为结果，即fruits数组中包含两个不同水果类型的最大子序列长度
        int ans=0;
/*j为遍历fruits数组的指针，也是滑动窗口的右边界，f1,f2分别为第一个和第二个篮子
的起始索引，f1同时也是滑动窗口的左边界，t为未来两个篮子里的第一个篮子的起始索
引*/
        for(int j=0,f1=0,f2=0,t=0;j<fruits.size();j++)
        {
/*当f1=f2时，fruits[j]!=fruits[f1]&&fruits[j]!=fruits[f2]说明遇到的是第二个篮子
要装的第二种水果；当f1!=f2时，fruits[j]!=fruits[f1]&&fruits[j]!=fruits[f2]说明
遇到的是第三种水果*/
            if(fruits[j]!=fruits[f1]&&fruits[j]!=fruits[f2])
            {
/*当f1=f2时，说明第一个篮子已经装了一种水果，第二个篮子里还没有装，不更新f1，
只更新f2，即往第二个篮子里装第二种水果；
当f1!=f2时，fruits[j]!=fruits[f1]&&fruits[j]!=fruits[f2]说明遇到的是第三种水果，
则更新f1和f2，即当前两个篮子的两种水果已装满，更新f1和f2为未来两个篮子里的两种
水果*/
                if(f1!=f2) f1=t;
                f2=j;
            }
/*t寻找未来两个篮子中第一个篮子要装的一种水果的起始索引，每次t与当前的j作对比，
当fruits[t]!=fruits[j]时，更新t=j*/
            if(fruits[t]!=fruits[j]) t=j;
/*更新当前子序列的长度，即每次计算装入两个篮子中的水果总数目*/
            ans=ans>(j-f1+1)?mn:(j-f1+1);
        }
        return ans;//返回最终结果ans
    }
};
一个部分错误的代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
public:
    int totalFruit(vector<int>& fruits) {
        int tr1,tr2,i=0;
        int ans=0;
        for(int j=1;j<fruits.size();j++){
            int count=1;
		    tr1 = fruits[i]; 
		    while(1){
                if(fruits[j]!=tr1){
                    count++;//用两个数表示两个果很容易错
                    if(count == 2) 
                        tr2 = fruits[j];
                    else{
                        if(fruits[j]!=tr2)
                            break;
                    }
                }
                if(j==fruits.size()-1)
                    break;
                j++;
		    }
        int length = j-i+1;
        if(length>ans) 
            ans=length;
        i++;    //j在到达最后一位时自动退出循环了，但是有可能j不动i后移一位时会得到最长
                //这个故事告诉我们要在while窗口中更新i
        }
    return ans;
    }
};

76.最小覆盖字串

哈希表

判断集合中某个元素存在性

49.字母异位词分组

官方题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        unordered_map<string, vector<string>> mp;
        for (string& str: strs) {
            string key = str;
            sort(key.begin(),key.end());
            mp[key].emplace_back(str);
        }
        vector<vector<string>>ans;
        for(auto it=mp.begin();it!=mp.end();++it){
            ans.emplace_back(it->second);
        }
        return ans;
    }
};

438. 找到字符串中所有的字母异位词

啊啊啊啊啊改了无数次

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        int m=s.size(),n=p.size();
        int pp=0,count=0;
        vector<int> ans;
        while(pp<(m-n+1)){  //都是循环条件没找好
            int a[30]={0},flag=1;
            for(int i=0;i<n;i++){
                a[p[i]-'a']++;
            }
            for(int i=pp;i<pp+n;i++){
                a[s[i]-'a']--;
            }
            for(int i=0;i<26;i++){
                if(a[i]!=0) {
                    flag=0;
                    break;
                }
            }
            if(flag){
                ans.push_back(pp);
            }
            pp++;
        }
        return ans;
    }
};

模拟

##循环

螺旋矩阵

  1. 循环不变量，区间左右开闭的选择守恒
  2. 注意边界限定，以及lr同时赋begin值
  3. 如果n为奇数的话，需要单独给矩阵最中间的位置赋值
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    class Solution {
    public:
        vector<vector<int>> generateMatrix(int n) {
            vector<vector<int>> a(n, vector<int>(n, 0));    // vector类型创建方法
            int l=0,r=0,i=1;
            int begin=0,end=n-1;    //
            int loop=n/2;
            while(loop--){  //
                l=begin,r=begin;    //
                for(;r<end;r++){
                    a[l][r] = i;
                    i++;
                }
                for(;l<end;l++){
                    a[l][r] = i;
                    i++;
                }
                for(;r>begin;r--){
                    a[l][r] = i;
                    i++;
                }
                for(;l>begin;l--){
                    a[l][r] = i;
                    i++;
                }
                begin++;
                end--;
            }
            int mid=n/2;    
            if (n % 2) {    //
                a[mid][mid] = i;
            }
            return a;
        }
    };