基础知识：重温数据结构（基础知识）
C++算法语法：[[算法中C++ & C常用的语法回顾]]

数组

数组模拟

2909. 元素和最小的山形三元组 II

🛫2909. 元素和最小的山形三元组 II
👑MID
🔔 相关主题：数组

题目I即数据量稍小，可以暴力

给你一个下标从 0 开始的整数数组 nums 。

如果下标三元组 (i, j, k) 满足下述全部条件，则认为它是一个 山形三元组 ：

  • i < j < k
  • nums[i] < nums[j] 且 nums[k] < nums[j]
    请你找出 nums 中 元素和最小 的山形三元组，并返回其 元素和 。如果不存在满足条件的三元组，返回 -1 。

示例 1：

输入：nums = [8,6,1,5,3]
输出：9
解释：三元组 (2, 3, 4) 是一个元素和等于 9 的山形三元组，因为：

  • 2 < 3 < 4
  • nums[2] < nums[3] 且 nums[4] < nums[3]
    这个三元组的元素和等于 nums[2] + nums[3] + nums[4] = 9 。可以证明不存在元素和小于 9 的山形三元组。

【思路】：最小的数肯定在山的一端，所以先找最小的，记录为后缀suf；然后遍历找前缀，记录前缀（山的另一端）为0号元素，从1~数组末尾 （注意：不是1~后缀，因为这里的后缀是相对概念，前缀还是可以超过后缀，比如[1,3,2]，这里1是suf） 逐个哦按段可否构成山形，如果可以，则判断是否最小

hl:13
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:
    int minimumSum(vector<int>& nums) {
        int n = nums.size();
        vector<int> suf(n); // 后缀最小值
        suf[n - 1] = nums[n - 1];
        for (int i = n - 2; i > 1; i--) {
            suf[i] = min(suf[i + 1], nums[i]);
        }// 找出后缀最低的

        int ans = INT_MAX;
        int pre = nums[0]; // 前缀最小值
        for (int j = 1; j < n - 1; j++) {
            if (pre < nums[j] && nums[j] > suf[j + 1]) { // 是否山形
                ans = min(ans, pre + nums[j] + suf[j + 1]); // 更新答案
            }
            pre = min(pre, nums[j]);// 把更小的设置为左底
        }
        // 注意：前后缀只是相对概念，pre的指向可以超过suf
        return ans == INT_MAX ? -1 : ans;
    }
};

283. 移动零

🛫283. 移动零
👑SIMPLE
🔔 相关主题：数组

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
请注意 ，必须在不复制数组的情况下原地对数组进行操作。

示例 1:
输入: nums = [0,1,0,3,12]
输出: [1,3,12,0,0]

【思路】

  1. 初始化两个指针
  2. 左指针永远逐个累加，右指针较快，会指向非0的数
  3. 交换左右指针的值，继续
  4. 当右指针到末尾，说明左侧全是非0值
  5. 右侧赋0值
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:
    void moveZeroes(vector<int>& nums) {
        int len = nums.size();
        int rt=0;
        int lf=0;
        if(len==1) return;
        while(rt<len){
            if(nums[rt]==0){
                rt++;
            } else {
                nums[lf] = nums[rt];//左指针累加，右指针是快指针，指向非0的数
                lf++;
                rt++;
            }
        }// 右指针遍历完后，说明所有非0数都在左边了，只需要把右边的数字全部置零即可
        while(lf<len){
            nums[lf] = 0;
            lf++;
        }
    }
};

前缀和与差分

统计子矩阵

蓝桥杯2109题，点击跳转

棋盘反转

🛫蓝桥杯-棋盘反转
👑MID
🔔 相关主题：差分

问题描述：小蓝拥有n×n大小的棋盘，一开始棋盘上全都是白子。小蓝进行了次操作，每次操作会将棋盘上某个范围内的所有棋子的颜色取反（也就是白色棋子变为黑色，黑色棋子变为白色）。请输出所有操作做完后棋盘上每个棋子的颜色。

输入格式：输入的第一行包含两个整数n，m,用一个空格分隔，表示棋盘大小与操作数。接下来m行每行包含四个整数x1,y1,x2,y2,相邻整数之间使用一个空格分隔，表示将在x1至x2行和y1至y2列中的棋子颜色取反。输出格式输出n行，每行个0或1表示该位置棋子的颜色。如果是白色则输出0，否则输出1。

1
2
3
4
5
6
7
8
9
10
 输入：
 3 3 
 1 1 2 2 
 2 2 3 3 
 1 1 3 3
输出：
001 
010 
100
 
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
#include <iostream>
using namespace std;
const int N=2010;
int n,m;
int b[N][N];
void insert(int x1,int y1,int x2,int y2,int c){//向所有矩阵中元素同时加上c
  b[x1][y1]+=c;
  b[x1][y2+1]-=c;
  b[x2+1][y1]-=c;
  b[x2+1][y2+1]+=c;
 }

int main()
{
  // 请在此输入您的代码
cin>>n>>m;
while(m--){//每进行一次操作，所有元素加一
  int x1,y1,x2,y2;
  cin>>x1>>y1>>x2>>y2;
  insert(x1,y1,x2,y2,1);// 构造差分数组
}
for(int i=1;i<=n;i++){
  for(int j=1;j<=n;j++){
    b[i][j]+=b[i-1][j]+b[i][j-1]-b[i-1][j-1];//计算新的前缀和，即每个元素操作了多少次
    cout<<b[i][j]%2;//输出每个元素操作次数除以2的余数，奇数是黑棋，偶数为白棋
  }
  cout<<"\n";
}
  return 0;
}

字符串

简单字符串模拟

2810. 故障键盘

🛫2810. 故障键盘
👑SIMPLE
🔔 相关主题：字符串、模拟

你的笔记本键盘存在故障，每当你在上面输入字符 ‘i’ 时，它会反转你所写的字符串。而输入其他字符则可以正常工作。

给你一个下标从 0 开始的字符串 s ，请你用故障键盘依次输入每个字符。

返回最终笔记本屏幕上输出的字符串。

示例 1：

输入：s = “string”
输出：”rtsng”
解释：

输入第 1 个字符后，屏幕上的文本是：”s” 。
输入第 2 个字符后，屏幕上的文本是：”st” 。
输入第 3 个字符后，屏幕上的文本是：”str” 。
因为第 4 个字符是 ‘i’ ，屏幕上的文本被反转，变成 “rts” 。
输入第 5 个字符后，屏幕上的文本是：”rtsn” 。
输入第 6 个字符后，屏幕上的文本是： “rtsng” 。
因此，返回 “rtsng” 。

没啥难度，关注一下反转的写法reverse(t.begin(), t.end())

hl:reverse
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    string finalString(string s) {
        string t;
        for (char c : s) {
            if (c == 'i') {
                reverse(t.begin(), t.end());
            } else {
                t.push_back(c);
            }
        }
        return t;
    }
};

滑动窗口与尺取法

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

🛫438. 找到字符串中所有字母异位词
👑MID
🔔 相关主题：尺取法

给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。

异位词 指由相同字母重排列形成的字符串（包括相同的字符串）。

示例 1:

输入: s = “cbaebabacd”, p = “abc”
输出: [0,6]
解释:
起始索引等于 0 的子串是 “cba”, 它是 “abc” 的异位词。
起始索引等于 6 的子串是 “bac”, 它是 “abc” 的异位词。

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

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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
class Solution {
public:
    vector<int> findAnagrams(string s, string p) {

        vector<int> ans;
        // // 特殊判断【对字符串s="a",p="a"的判断方式1】
        // if (s.size() == p.size())
        // {
        //     if (s == p)
        //     {
        //         ans.push_back(0);
        //         return ans;
        //     }
        //     else
        //     {
        //         return ans;
        //     }
        // }
        int map_len = p.size();
        unordered_map<char, int> map;
        for (int i = 0; i < p.size(); i++) {
            if (map.find(p[i]) != map.end()) {
                map[p[i]]++;
            } else {
                map.insert(make_pair(p[i], 1));
            }
        }
        int count = 0;
        int s_len = s.size();
        s = '#' + s;
        int l = 1;
        int r = 1;
        for (;;) {
            while (r <= map_len && r <= s_len)
            // 这里不能再用s.size了因为是修正过的。
            {
                if (map.find(s[r]) != map.end()) {
                    if (map[s[r]] > 0)
                    // 如果在移动过程中发现新加入的元素恰好需要，那么直接加入
                    {
                        count++;
                    }
                    map[s[r]]--;
                }
                r++;
            }

            if (count == map_len && r > s_len)
            // // 特殊判断【对字符串s="a",p="a"的判断方式2】
            {
                ans.push_back(l - 1);
            }
            if (r > s_len) {
                return ans;
            }

            // 左右一起移动
            while (r <= s_len + 1) {
                if (count == map_len) {
                    ans.push_back(l - 1);
                }

                if (map.find(s[r]) != map.end()) {
                    if (map[s[r]] >
                        0) // 此时还没纳入map，判断是否还需要这个元素
                    // 只有>0才算需要的有效的，=0或者小于0都是多余的
                    {
                        count++;
                    }
                    map[s[r]]--; // 若此时变成0，则是刚好的
                }
                r++;

                if (map.find(s[l]) != map.end()) {
                    if (map[s[l]] >= 0) // 此时还没删除这个元素
                    // =0时标识刚好已经有一个了，但是这个就是刚好的哪一个，需要减去
                    {
                        count--;
                    }
                    map[s[l]]++;
                }
                l++;
            }
            return ans;
        }
    }
};

乐子人，C++的数组可以直接比较

hl:"sCount 
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
36
class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        int sLen = s.size(), pLen = p.size();

        if (sLen < pLen) {
            return vector<int>();
        }

        vector<int> ans;
        vector<int> sCount(26);
        vector<int> pCount(26);
        for (int i = 0; i < pLen; ++i) {
            ++sCount[s[i] - 'a'];
            ++pCount[p[i] - 'a'];
        }

        if (sCount == pCount) {
            ans.emplace_back(0);
        }

        for (int i = 0; i < sLen - pLen; ++i) {
            --sCount[s[i] - 'a'];
            ++sCount[s[i + pLen] - 'a'];

            if (sCount == pCount) {
                ans.emplace_back(i + 1);
            }
        }

        return ans;
    }
};

//作者：力扣官方题解

76.最小覆盖子串

🛫76. 最小覆盖子串
👑Hard
🔔 相关主题：滑动窗口 尺取

给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 “” 。

注意：

对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
如果 s 中存在这样的子串，我们保证它是唯一的答案。

示例 1：

输入：s = “ADOBECODEBANC”, t = “ABC”
输出：”BANC”
解释：最小覆盖子串 “BANC” 包含来自字符串 t 的 ‘A’、’B’ 和 ‘C’。

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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
string minWindow(string s, string p)
{

    string ans;
    int map_len = p.size();
    unordered_map<char, int> map;
    for (int i = 0; i < p.size(); i++)
    {
        if (map.find(p[i]) != map.end())
        {
            map[p[i]]++;
        }
        else
        {
            map.insert(make_pair(p[i], 1));
        }
    }
    int count = 0;
    int s_len = s.size();
    s = '#' + s;
    int l = 1;
    int r = 1;

    int ansstart = 0;
    int anslen = 0;

    for (;;)
    {

        while (r <= s_len && count < map_len)
        {
            if (map.count(s[r]) != 0)
            {
                // 加入窗口
                if (map[s[r]] > 0)
                {
                    // 大于0表明是还有需求的，所以累加
                    count++;
                }
                map[s[r]]--; // 更新剩余出现次数
            }
            r++;
        }

        if (count < map_len)
        {
            break;
        }

		/* 
		   下面这种写法会爆内存，因为每次substr都会用一次内存
		*/
        // if (anslen != 0 && r - l <= ans.size())
        // {
        //     // ans = s.substr(l, r - l);
        //     
        // }
        // else if (ans.size() == 0)
        // {
        //     // ans = s.substr(l, r - l);
        //    
        // }

        if (anslen != 0 && r - l <= anslen)
        {
            // ans = s.substr(l, r - l);
            ansstart = l;
            anslen = r - l;
        }
        else if (anslen == 0)
        {
            // ans = s.substr(l, r - l);
            ansstart = l;
            anslen = r - l;
        }

        if (map.count(s[l]) != 0)
        {
            // 移除窗口
            if (map[s[l]] >= 0)
            {
                count--;
            }
            map[s[l]]++; // 更新剩余出现次数
        }

        l++;
    }
    ans = s.substr(ansstart, anslen);
    return 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
32
33
34
35
36
37
38
39
40
41
class Solution {
public:
    unordered_map <char, int> ori, cnt;

    bool check() {
        for (const auto &p: ori) {
            if (cnt[p.first] < p.second) {
                return false;
            }
        }
        return true;
    }

    string minWindow(string s, string t) {
        for (const auto &c: t) {
            ++ori[c];
        }

        int l = 0, r = -1;
        int len = INT_MAX, ansL = -1, ansR = -1;

        while (r < int(s.size())) {
            if (ori.find(s[++r]) != ori.end()) {
                ++cnt[s[r]];
            }
            while (check() && l <= r) {
                if (r - l + 1 < len) {
                    len = r - l + 1;
                    ansL = l;
                }
                if (ori.find(s[l]) != ori.end()) {
                    --cnt[s[l]];
                }
                ++l;
            }
        }

        return ansL == -1 ? string() : s.substr(ansL, len);
    }
};

链表

142. 环形链表 II

🛫142. 环形链表 II
👑SIMPLE
🔔 相关主题：哈希

给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
不允许修改 链表。


输入：head = [3,2,0,-4], pos = 1
输出：返回索引为 1 的链表节点
解释：链表中有一个环，其尾部连接到第二个节点。

hl:unor
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        unordered_set<ListNode *> visited;
        // 注意：这里哈希存储的是结点而非结点值，所以在结点值相等的情况下仍然适用
        while (head != nullptr) {
            if (visited.count(head)) {
                return head;
            }
            visited.insert(head);
            head = head->next;
        }
        return nullptr;
    }
};