SOUSIC

哈库呐玛塔塔

0%

Leetcode每日一题 - 2020年八月

发表于 更新于 分类于 Valine：
本文字数： 17k 阅读时长 ≈ 15 分钟
8月份每日一题

8月3日 415. 字符串相加（简单）

给定两个字符串形式的非负整数 num1 和num2 ，计算它们的和。

注意：

1
2
3
4
num1 和num2 的长度都小于 5100.
num1 和num2 都只包含数字 0-9.
num1 和num2 都不包含任何前导零。
你不能使用任何內建 BigInteger 库， 也不能直接将输入的字符串转换为整数形式。

题解：
两个数字位数不同时，在指针当前下标处于负数的时候返回 0，等价于对位数较短的数字进行了补零操作，这样就可以除去两个数字位数不同情况的处理。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
string addStrings(string num1, string num2){
    int i = num1.length() - 1, j = num2.length() - 1, add = 0;
    string res = "";
    while (i >= 0 || j >= 0 || carry != 0) {
        int x = i >= 0 ? num1[i] - '0' : 0;
        int y = j >= 0 ? num2[j] - '0' : 0;
        int result = x + y + carry;
        res.push_back('0' + result % 10);
        carry = result / 10;
        i -= 1;
        j -= 1;
    }
    // 计算完以后的答案需要翻转过来
    reverse(res.begin(), res.end());
    return res;
}

时间复杂度：O(max{n1,n2})
空间复杂度：O(1)

8月4日 207. 课程表（中等）

你这个学期必须选修 numCourse 门课程，记为 0 到 numCourse-1 。

在选修某些课程之前需要一些先修课程。 例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示他们：[0,1]

给定课程总量以及它们的先决条件，请你判断是否可能完成所有课程的学习？

示例 1:

1
2
3
输入: 2, [[1,0]] 
输出: true
解释: 总共有 2 门课程。学习课程 1 之前，你需要完成课程 0。所以这是可能的。

示例 2:

1
2
3
输入: 2, [[1,0],[0,1]]
输出: false
解释: 总共有 2 门课程。学习课程 1 之前，你需要先完成​课程 0；并且学习课程 0 之前，你还应先完成课程 1。这是不可能的。

提示：

1
2
3
输入的先决条件是由 边缘列表 表示的图形，而不是 邻接矩阵 。详情请参见图的表示法。
你可以假定输入的先决条件中没有重复的边。
1 <= numCourses <= 10^5

题解：

  1. 有向图的dfs遍历。
    visited[i]表示第i和节点的状态，0表示没有被访问过，1表示正在被访问，2表示访问结束的节点。circle表示有向图有环。使用dfs遍历有向图：
  • 当正在访问的节点（visited[i]=1）又被访问时，说明有向图存在环，返回false。
  • 全部节点访问完毕，返回true
    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
    void dfs(int u, vector<vector<int> > &graph, vector<int> &visited){
        visited[u] = 1;//正在访问该节点
        for(int v:graph[u]){
            if(visited[v]==0){
                dfs(v, graph, visited);
                if(circle)
                    return;
            }else if(visited[v]==1){
                circle = true;
                return;
            }
        }
        visited[u] = 2;
    }

    bool canFinish(int numCourses, vector<vector<int> >& prerequisites) {
        if(prerequisites.empty())
            return true;
        vector<vector<int> > graph(numCourses);
        for (auto course : prerequisites)
        {//build graph
            graph[course[1]].push_back(course[0]);
        }

        vector<int> visited(numCourses);
        for (int i = 0; i < numCourses && !circle; i++)
        {
            if(!visited[i])
                dfs(i, graph, visited);
        }
        return !circle;
    }
    时间复杂度：O(m+n)。m是有向图的边，n是有向图的节点。
    空间复杂度：O(m+n)
  1. bfs入度为0的点
    拓扑排序中，起点都是入度为0的点。把所有入度为0的节点放入队列，依次访问队列中的节点。访问的时候把所有从该节点出去的边都删掉，即该节点出发连接的边的入度都减1。再把入度减到0的点加入队列。
    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
    bool canFinish(int numCourses, vector<vector<int> >& prerequisites) {
        if(prerequisites.empty())
            return true;
        vector<vector<int> > graph(numCourses);
        vector<int> inDegree(numCourses, 0);
        for (auto course : prerequisites)
        {//build graph
            graph[course[1]].push_back(course[0]);
            inDegree[course[0]]++;
        }

        queue<int> que;
        for (int i = 0; i < numCourses;i++)
        {
            if(inDegree[i]==0)
                que.push(i);
        }

        int visited = 0;
        while (!que.empty())
        {
            visited++;
            int u = que.front();
            que.pop();
            for(int v:graph[u]){
                inDegree[v]--;
                if(inDegree[v]==0)
                    que.push(v);
            }
        }
        return visited == numCourses;
    }
    时间复杂度：O(m+n)。m是有向图的边，n是有向图的节点。
    空间复杂度：O(m+n)

真题

模版匹配

前面给一个词做模版，看后面的多个词是否能和前面的模版匹配。

示例1：

1
2
输入：pattern = "noon", str = "big star star big"
输出：true

示例2:

1
2
输入：pattern = "noon", str = "big star star not"
输出：false

题解：

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
bool testMatch(string pattern, string str) {
    map<string,char> wordMap;
    char used[128] = {0};
    string word;
    int pos = 0;
    str.push_back(' ');
    for (int i = 0; i < str.size();i++){
        if(str[i]==' '){
            if(pos==pattern.size())
                return false;
            if(wordMap.find(word)==wordMap.end()){
                if(used[pattern[pos]])
                    return false;
                wordMap[word] = pattern[pos];
                used[pattern[pos]] = 1;
            }else{
                if(wordMap[word]!=pattern[pos])
                    return false;
            }
            word = "";
            pos++;
        }else{
            word += str[i];
        }
    }
    if(pos!=pattern.size())
        return false;
    return true;
}

找到最小的排列组合数

找到比原数字位数排列组合后，比原数字大的，最小的数。没有就输出-1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//80%  比如 2231就不对了
int findGreaterNum(int N) {
    string s = to_string(N);
    for (int i = s.size() - 1; i > 0; i--)
    {
        if (s[i] > s[i - 1])
        {
            swap(s[i], s[i - 1]);
            break;
        }
    }
    int res = atoi(s.c_str());
    if (res == N)
        cout << -1 << endl;
    else 
        cout << res;
    return 0;
}

1477. 找两个和为目标值且不重叠的子数组

给你一个整数数组 arr 和一个整数值 target。

请你在 arr 中找两个互不重叠的子数组 且它们的和都等于 target。可能会有多种方案，请你返回满足要求的两个子数组长度和的 最小值 。

请返回满足要求的最小长度和，如果无法找到这样的两个子数组，请返回 -1 。

题解：
dp[i]表示i后面和等T的最小子数组长度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int minSumOfLengths(vector<int>& arr, int target){
    int sum = 0, r = arr.size() - 1, res = 200000; 
    vector<int> dp(arr.size() + 1, 200000);//后面子数组的最小长度
    for (int l = r; l >= 0; --l) { //l,r是滑动区间的左右坐标
        sum += arr[l];
        while (sum > target)
            sum -= arr[r--];
        if (sum == target) {
            int curLen = r - l + 1; //子数组长度
            res = min(res, curLen + dp[r + 1]); //子数组长度 + r后面子数组的最小长度
            dp[l] = min(dp[l + 1], curLen); //更新l后面子数组的最小长度
        }else
            dp[l] = dp[l + 1]; //更新子数组的最小长度
    }
    return res == 200000 ? -1 : res;
}

16进制和10进制的互转

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
string convert_10_to_16(int num)
{
    vector<int> ivec;
    int Num = num;
    while (num != 0)
    {
        ivec.push_back(num % 16);
        num = num / 16;
    }
 
    vector<int>::size_type sz = ivec.size();
    vector<string> ivec2;
    int m = 0;
    string s;
    for (vector<int>::size_type index = 0; index != sz; ++index)
    {
        if (ivec[sz - 1 - index] > 9)
        {   
            m = ivec[sz - 1 - index] + 55;
            s = m+'0'-'0';
            ivec2.push_back(s);
        }
        else
        {
            s = ivec[sz - 1 - index] + '0';
            ivec2.push_back(s);
 
        }         
    }

    string res = "";
    for (auto item : ivec2)
        res += item;
    return res;
}

double convert_16_to_10(string str)
{
    double sum = 0, times;
    double m;
    string::size_type sz = str.size();
    for (string::size_type index = 0; index != sz; ++index)
    {
        str[index] = tolower(str[index]);
        if (str[index] >= 'a' && str[index] <= 'f')
        {
            m = str[index] - 'a' + 10;
            times = pow(16, (sz - 1 - index));
            sum += m * times;
 
        }
        else if (isdigit(str[index]))
        {
            m= str[index] - 48;
            times = pow(16, (sz - 1 - index));
            sum += m * times;
            
        }
        else
        {
            break;
        }
    }
    return sum;
}

8月10日 696. 计数二进制子串

给定一个字符串 s，计算具有相同数量0和1的非空(连续)子字符串的数量，并且这些子字符串中的所有0和所有1都是组合在一起的。

重复出现的子串要计算它们出现的次数。

示例 1 :

1
2
3
4
5
6
7
输入: "00110011"
输出: 6
解释: 有6个子串具有相同数量的连续1和0：“0011”，“01”，“1100”，“10”，“0011” 和 “01”。

请注意，一些重复出现的子串要计算它们出现的次数。

另外，“00110011”不是有效的子串，因为所有的0（和1）没有组合在一起。

示例 2 :

1
2
3
输入: "10101"
输出: 4
解释: 有4个子串：“10”，“01”，“10”，“01”，它们具有相同数量的连续1和0。

注意：

1
2
s.length 在1到50,000之间。
s 只包含“0”或“1”字符。

题解：

  1. 把每个相同的字符分组，比如“00111011” 就可以分为subs={2,3,1,2}，表示2个0，3个1，1个0，2个1。每一对相邻的能有min{subs[i],subs[i+1]}个字串。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    int countBinarySubstrings(string s) {
        vector<int> subs;
        
        int i = 0;
        while(i<s.size()){
            int mark = i;
            char cur = s[i];
            while(i<s.size() && s[i]==cur)
                i++;
            subs.push_back(i-mark);
        }

        int res = 0;
        for(int i = 0;i<subs.size()-1;i++){
            res += min(subs[i],subs[i+1]);
        }
        return res;
    }

    时间复杂度：O(n)
    空间复杂度：O(n)

  2. 优化。空间复杂度优化到O(1)。也只用到subs的上一个状态量，所以可以不用保存整个subs数组。

    1
    （代码略）

8月11日 130. 被围绕的区域（中等）

给定一个二维的矩阵，包含 ‘X’ 和 ‘O’（字母 O）。

找到所有被 ‘X’ 围绕的区域，并将这些区域里所有的 ‘O’ 用 ‘X’ 填充。

示例:

1
2
3
4
5
6
7
8
9
10
X X X X
X O O X
X X O X
X O X X
运行你的函数后，矩阵变为：

X X X X
X X X X
X X X X
X O X X

解释:
被围绕的区间不会存在于边界上，换句话说，任何边界上的 ‘O’ 都不会被填充为 ‘X’。 任何不在边界上，或不与边界上的 ‘O’ 相连的 ‘O’ 最终都会被填充为 ‘X’。如果两个元素在水平或垂直方向相邻，则称它们是“相连”的。
题解：
dfs。也可以用bfs，但是需要自己用队列实现，还是递归方便一点。

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
vector<vector<int> > dirs = {{1,0},{-1,0},{0,1},{0,-1}};

void dfs(vector<vector<char> >& board,vector<int> & s,vector<vector<bool> > &marked){
    int x=s[0],y=s[1];
    if(board[x][y]=='X' || marked[x][y])
        return;
    marked[x][y] = true;
    for(auto d:dirs){
        int next_i = x+d[0], next_j = y+d[1];
        vector<int> tmp = {next_i,next_j};
        if((next_i > 0 && next_i < board.size())
        && (next_j > 0 && next_j < board[0].size()))
            dfs(board,tmp,marked);
    }
    return;
}

void solve(vector<vector<char> >& board) {
    if(board.empty())
        return;
    int m = board.size(),n = board[0].size();
    vector<vector<bool> > marked(m,vector<bool>(n, false));
    vector<vector<int> > side;
    for(int i=0;i<n;i++){
        if(board[0][i]=='O'){
            side.push_back({0,i});
            //marked[0][i] = true;
        }
        if(board[m-1][i]=='O'){
            side.push_back({m-1,i});
            //marked[m-1][i] = true;
        }
    }
    for(int i=1;i<m-1;i++){
        if(board[i][0]=='O'){
            side.push_back({i,0});
            //marked[i][0] = true;
        }
        if(board[i][n-1]=='O'){
            side.push_back({i,n-1});
            //marked[i][n-1] = true;
        }
    }

    for(auto s:side){
        dfs(board,s,marked);
    }

    for(int i=0;i<m;i++){
        for(int j=0;j<n;j++){
            if(!marked[i][j] && board[i][j]=='O')
                board[i][j] = 'X';
        }
    }
    return;
}

时间复杂度：O(mn)
空间复杂度：O(mn)

8月12日 133. 克隆图（中等）

给你无向 连通 图中一个节点的引用，请你返回该图的 深拷贝（克隆）。

图中的每个节点都包含它的值 val（int） 和其邻居的列表（list[Node]）。

1
2
3
4
class Node {
    public int val;
    public List<Node> neighbors;
}

题解：

  1. bfs

    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
    Node* cloneGraph(Node* node) {
        if (node == nullptr) {
            return node;
        }

        unordered_map<Node*, Node*> visited;

        // 将题目给定的节点添加到队列
        queue<Node*> que;
        que.push(node);
        // 克隆第一个节点并存储到哈希表中
        visited[node] = new Node(node->val);

        // 广度优先搜索
        while (!que.empty()) {
            // 取出队列的头节点
            auto curNode = que.front();
            que.pop();
            // 遍历该节点的邻居
            for (auto& neighbor: curNode->neighbors) {
                if (visited.find(neighbor) == visited.end()) {
                    // 如果没有被访问过，就克隆并存储在哈希表中
                    visited[neighbor] = new Node(neighbor->val);
                    // 将邻居节点加入队列中
                    que.push(neighbor);
                }
                // 更新当前节点的邻居列表
                visited[curNode]->neighbors.emplace_back(visited[neighbor]);
            }
        }

        return visited[node];
    }

    时间复杂度：O(n)
    空间复杂度：O(n)

  2. dfs

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    unordered_map<Node*, Node*> visited;

    Node* cloneGraph(Node* node) {
        if (node == nullptr) {
            return node;
        }

        if(visited.find(node) != visited.end())
            return visited[node];

        Node *cloneNode = new Node(node->val);
        visited[node] = cloneNode;

        for(auto &neighbor:node->neighbors){
            cloneNode->neighbors.push_back(cloneGraph(neighbor));
        }

        return visited[node];
    }

    时间复杂度：O(n)
    空间复杂度：O(n)

8月13日 43. 字符串相乘（中等）

给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。

示例 1:

1
2
输入: num1 = "2", num2 = "3"
输出: "6"

示例 2:

1
2
输入: num1 = "123", num2 = "456"
输出: "56088"

说明：

1
2
3
4
num1 和 num2 的长度小于110。
num1 和 num2 只包含数字 0-9。
num1 和 num2 均不以零开头，除非是数字 0 本身。
不能使用任何标准库的大数类型（比如 BigInteger）或直接将输入转换为整数来处理。

题解：
大数相乘问题。

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
string multiply(string num1, string num2){
    int m = num1.size(), n = num2.size();
    vector<long long> num(m + n - 1, 0);

    for (int i = 0; i < m;i++){//前面是高位，后面是低位
        int a = num1[i] - '0';
        for (int j = 0; j < n; j++)
        {
            int b = num2[j] - '0';
            num[i + j] += a * b;
        }
    }

    int carry = 0;
    for (int i = num.size() - 1; i >= 0;i--){//前面是高位，后面是低位
        int cur = num[i] + carry;
        num[i] = cur % 10;
        carry = cur / 10;
    }
    while(carry!=0){
        int cur = carry % 10;
        carry /= 10;
        num.insert(num.begin(), cur);
    }

    string res = "";
    for (auto a : num)
    {
        res += to_string(a);
    }
    return res;
}

时间复杂度：O(m*n)
空间复杂度：O(m+n)

8月19日 647. 回文子串（中等）

给定一个字符串，你的任务是计算这个字符串中有多少个回文子串。

具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。

示例 1：

1
2
3
输入："abc"
输出：3
解释：三个回文子串: "a", "b", "c"

示例 2：

1
2
3
输入："aaa"
输出：6
解释：6个回文子串: "a", "a", "a", "aa", "aa", "aaa"

题解：
枚举每一个字串，再判断是不是回文。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
bool isPalindrome(string str){
    int L = 0, R = str.size() - 1;
    while(L<R){
        if(str[L]!=str[R])
            break;
        L++;
        R--;
    }
    return L>=R;
}

int countSubstrings(string s) {
    int n = s.size();
    if(n==0) return 0;
    int res = n;
    for(int m=2;m<=n;m++){
        for(int i=0;i<=n-m;i++){
            string cur_str = s.substr(i,m);
            if(isPalindrome(cur_str))
                res++;
        }
    }
    return res;
}

时间复杂度：O(n^2)
空间复杂度：O(1)

8月20日 529. 扫雷游戏（中等）

让我们一起来玩扫雷游戏！

给定一个代表游戏板的二维字符矩阵。 ‘M’ 代表一个未挖出的地雷，’E’ 代表一个未挖出的空方块，’B’ 代表没有相邻（上，下，左，右，和所有4个对角线）地雷的已挖出的空白方块，数字（’1’ 到 ‘8’）表示有多少地雷与这块已挖出的方块相邻，’X’ 则表示一个已挖出的地雷。

现在给出在所有未挖出的方块中（’M’或者’E’）的下一个点击位置（行和列索引），根据以下规则，返回相应位置被点击后对应的面板：

如果一个地雷（’M’）被挖出，游戏就结束了- 把它改为 ‘X’。
如果一个没有相邻地雷的空方块（’E’）被挖出，修改它为（’B’），并且所有和其相邻的未挖出方块都应该被递归地揭露。
如果一个至少与一个地雷相邻的空方块（’E’）被挖出，修改它为数字（’1’到’8’），表示相邻地雷的数量。
如果在此次点击中，若无更多方块可被揭露，则返回面板。

示例 1：

1
2
3
4
5
6
7
8
9
10
11
12
13
输入: 
[['E', 'E', 'E', 'E', 'E'],
 ['E', 'E', 'M', 'E', 'E'],
 ['E', 'E', 'E', 'E', 'E'],
 ['E', 'E', 'E', 'E', 'E']]

Click : [3,0]

输出: 
[['B', '1', 'E', '1', 'B'],
 ['B', '1', 'M', '1', 'B'],
 ['B', '1', '1', '1', 'B'],
 ['B', 'B', 'B', 'B', 'B']]

示例 2：

1
2
3
4
5
6
7
8
9
10
11
12
13
输入: 
[['B', '1', 'E', '1', 'B'],
 ['B', '1', 'M', '1', 'B'],
 ['B', '1', '1', '1', 'B'],
 ['B', 'B', 'B', 'B', 'B']]

Click : [1,2]

输出: 
[['B', '1', 'E', '1', 'B'],
 ['B', '1', 'X', '1', 'B'],
 ['B', '1', '1', '1', 'B'],
 ['B', 'B', 'B', 'B', 'B']]

题解：

  1. dfs

    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
    vector<vector<int> > dirs = {{0,1},{0,-1},{1,0},{-1,0},{1,1},{-1,-1},{1,-1},{-1,1}};

    void dfs(vector<vector<char> > &res, int row, int col, vector<vector<bool> > &hasVisited){
        if(hasVisited[row][col])
            return;
        
        //处理当前格子
        int boom = 0;
        for(auto d:dirs){
            int next_i=row+d[0];
            int next_j=col+d[1];
            if(next_i < 0 || next_i >= res.size() || next_j < 0 || next_j >= res[0].size())
                continue;
            if(res[next_i][next_j]=='M')
                boom++;
        }
        hasVisited[row][col] = true;
        if(boom==0)
            res[row][col] = 'B';
        else{
            res[row][col] = to_string(boom)[0];
            // res[cur_i][cur_j] = boom + '0';
            return;
        }

        //处理下一个格子
        for(auto d:dirs){
            int next_i=row+d[0];
            int next_j=col+d[1];
            if(next_i < 0 || next_i >= res.size() || next_j < 0 || next_j >= res[0].size())
                continue;
            dfs(res,next_i,next_j,hasVisited);
        }
    }

    vector<vector<char>> updateBoard(vector<vector<char>>& board, vector<int>& click) {
        if(board.empty())
            return board;
        int row = click[0],col=click[1];
        vector<vector<char> > res = board;
        if(board[row][col]=='M'){
            res[row][col] = 'X';
            return res;
        }

        vector<vector<bool> > hasVisited(board.size(), vector<bool>(board[0].size(),false));
        dfs(res,row,col,hasVisited);
        return res;
    }

    时间复杂度：O(mn)
    空间复杂度：O(mn)

  2. bfs。

    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
    vector<vector<int> > dirs = {{0,1},{0,-1},{1,0},{-1,0},{1,1},{-1,-1},{1,-1},{-1,1}};
    void bfs(vector<vector<char> > &res, int row, int col, vector<vector<bool> > &hasVisited){
        queue<vector<int> > que;
        que.push({row,col});
        hasVisited[row][col] = true;
        while(!que.empty()){
            int sizeq = que.size();
            while(sizeq-->0){
                int cur_i = que.front()[0];
                int cur_j = que.front()[1];
                que.pop();
                
                int boom = 0;
                for(auto d:dirs){
                    int next_i=cur_i+d[0];
                    int next_j=cur_j+d[1];
                    if(next_i < 0 || next_i >= res.size() || next_j < 0 || next_j >= res[0].size())
                        continue;
                    if(res[next_i][next_j]=='M')
                        boom++;
                }
                
                if(boom==0){
                    //处理当前格子
                    res[cur_i][cur_j] = 'B';
                    //下一个格子
                    for(auto d:dirs){
                        int next_i=cur_i+d[0];
                        int next_j=cur_j+d[1];
                        if(next_i < 0 || next_i >= res.size() || next_j < 0 || next_j >= res[0].size()
                        || hasVisited[next_i][next_j])
                            continue;
                        if(res[next_i][next_j]=='E'){
                            que.push({next_i,next_j});
                            hasVisited[next_i][next_j] = true;
                        }
                    }
                }
                else
                    res[cur_i][cur_j] = to_string(boom)[0];
            }
        }
    }

    vector<vector<char> > updateBoard(vector<vector<char> >& board, vector<int>& click) {
        if(board.empty())
            return board;
        int row = click[0],col=click[1];
        vector<vector<char> > res = board;
        if(board[row][col]=='M'){
            res[row][col] = 'X';
            return res;
        }

        vector<vector<bool> > hasVisited(board.size(), vector<bool>(board[0].size(),false));
        bfs(res,row,col,hasVisited);
        return res;
    }

    时间复杂度：O(mn)
    空间复杂度：O(mn)

元素平衡

A，B，C，D四个数，每次可以任意减少2个单位然后增加1各单位，问当四个数相等时，最大和为多少。

题解：
笔试真题。

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
int main(){
    vector<long> nums(4);
    cin >> nums[0] >> nums[1] >> nums[2] >> nums[3];
    
    sort(nums.begin(), nums.end());

    long long sumn = nums[0] + nums[1] + nums[2] + nums[3];
    long maxn = sumn / 4;
    while(maxn>0){
        int sumL = 0, sumR = 0, idx = 0;
        while(idx<4 && nums[idx]<maxn){
            sumL += (maxn - nums[idx]);
            idx++;
        }
        while(idx<4 && nums[idx]==maxn)
            idx++;
        while(idx<4 && nums[idx]>maxn){
            sumR += (nums[idx] - maxn);
            idx++;
        }
        if(sumL*2 <= sumR){
            cout << maxn * 4 << endl;
            return 0;
        }
        maxn--;
    }
    cout << -1 << endl;

    return 0;
}