第 196 场周赛

Posted on | In , | |
Words count in article: 420 | Reading time ≈ 2

5452. 判断能否形成等差数列

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    bool canMakeArithmeticProgression(vector<int>& arr) {
        if(arr.size() <= 2) return true;
        sort(arr.begin(), arr.end());
        int cur = arr[1]-arr[0];
        for(int i=1; i<arr.size()-1; i++) {
            if(arr[i+1]-arr[i] != cur) return false;
        }
        return true;
    }
};

5453. 所有蚂蚁掉下来前的最后一刻

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int getLastMoment(int n, vector<int>& left, vector<int>& right) {
        int curmax = 0;
        for(auto& l: left) {
            curmax = max(curmax, l);
        }
        for(auto& r: right) {
            curmax = max(curmax, n-r);
        }
        return curmax;
    }
};

5454. 统计全 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
class Solution {
public:
    int numSubmat(vector<vector<int>>& mat) {
        int n = mat.size();
        int m = mat[0].size();
        vector<vector<int> > left(n,vector<int>(m));
        int now = 0;
        for(int i=0;i<n;i++){
            now = 0;
            for(int j=0;j<m;j++){
                if(mat[i][j] == 1) now ++;
                else now = 0;
                left[i][j] = now;
            }
        }
        int ans = 0,minx;
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                minx = 0x3f3f3f3f;
                for(int k=i;k>=0;k--){
                    minx = min(left[k][j],minx);
                    ans += minx;
                }
            }
        }
        return ans;
    }
};

5455. 最多 K 次交换相邻数位后得到的最小整数

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
class Solution {
public:
    string minInteger(string num, int k) {
        if (k == 0)
            return num;
        //special return
        if (num.size() * num.size() < k) {
            sort(num.begin(), num.end());
            return num;
        }
        for (int i = 0; i < num.size(); i++) {
            char tem = num[i];
            int flag = 0;
            int index;
            //find minChar
            for (int j = i + 1; j < i + 1 + k && j < num.size(); j++) {
                if (num[j] < tem) {
                    //update
                    tem = num[j];
                    flag = 1;
                    index = j;
                }
            }
            if (flag) {
                //loop swap update
                for (int t = index; t >= i + 1; t--) {
                    char temp = num[t];
                    num[t] = num[t - 1];
                    num[t - 1] = temp;
                }
                flag = 0;
                k = k - (index - i);
            }
            //return
            if (k == 0)
                break;
        }
        return num;
    }
};
Donate? comment?