[数据结构与算法]Leetcode第 259 场周赛

总结：

本次比赛难度适中，第三题这种题目边界分情况讨论清楚，比如说：枚举的是边长，依次枚举正方形四个顶点…
第四题的话，稍难，观察数据范围，发现长度最长的子序列为7，这是这道题的出发点，暴力枚举答案，并且在$O(n)$的时间判断重复的次数，从大到小枚举，保证字典序最大，细节还是比较多的

5875. 执行操作后的变量值

class Solution {
public:
    int finalValueAfterOperations(vector<string>& operations) {
        int x = 0;
        for (auto& str : operations)
            if (str[1] == '+') x ++ ;
            else x -- ;

        return x;
    }
};

5876. 数组美丽值求和

思路：维护前缀最大值和后缀最小值

class Solution {
public:
    int sumOfBeauties(vector<int>& a) {
        int n = a.size();
        vector<int> minn(n + 1);
        minn[n - 1] = a[n - 1];
        for (int i = n - 2; i >= 1; i -- ) 
            minn[i] = min(a[i], minn[i + 1]);
        
        int s = 0, pre = a[0];
        for (int i = 1; i <= n - 2; i ++ ) {
            if (a[i] > pre && a[i] < minn[i + 1]) s += 2;
            else if (a[i] > a[i - 1] && a[i] < a[i + 1]) s += 1;
            pre = max(pre, a[i]);
        }
        return s;
    }
};

5877. 检测正方形

大模拟：枚举边长

class DetectSquares {
public:
    int f[1001][1001];
    DetectSquares() {
        memset(f, 0, sizeof f);
    }
    
    void add(vector<int> point) {
        f[point[0]][point[1]] ++ ;
    }
    
    int count(vector<int> point) {
        int res = 0, x = point[0], y = point[1];
        for (int i = 1; i <= min(x, 1000 - y); i ++ )
            res += f[x - i][y] * f[x][y + i] * f[x - i][y + i];
        for (int i = 1; i <= min(1000 - x, 1000 - y); i ++ )
            res += f[x + i][y] * f[x][y + i] * f[x + i][y + i];
        for (int i = 1; i <= min(x, y); i ++ )
            res += f[x - i][y] * f[x][y - i] * f[x - i][y - i];
        for (int i = 1; i <= min(1000 - x, y); i ++ )
            res += f[x + i][y] * f[x][y - i] * f[x + i][y - i];
        return res;
    }
};

/**
 * Your DetectSquares object will be instantiated and called as such:
 * DetectSquares* obj = new DetectSquares();
 * obj->add(point);
 * int param_2 = obj->count(point);
 */

最后一题不会…

5878. 重复 K 次的最长子序列

class Solution {
public:
    vector<string> v[8];

    bool check(string t, string s, int k) {
        int cnt = 0;
        for (int i = 0, j = 0; i < s.size(); i ++ ) {
            if (s[i] == t[j]) {
                j ++ ;
                if (j == t.size()) {
                    cnt ++ ;
                    j = 0;
                }
            }
        }
        return cnt >= k;
    }

    string longestSubsequenceRepeatedK(string s, int k) {
        v[0].push_back("");
        int l = 1;
        for (; l < 8; l ++ ) {
            for (auto str : v[l - 1]) {
                for (char ch = 'z'; ch >= 'a'; ch -- ) {
                    if (check(str + ch, s, k))
                        v[l].push_back(str + ch);
                }
            }
            if (v[l].empty()) break;
        }
        l -- ;
        return v[l][0];
    }
};