LeetCode -- 108场双周赛-526互联

利用差分和动态规划进行求解。首先求出差分数组d[i]，f[i]表示从0-i - 1中选，且包含d[i]所有交替子数组的最大长度。

条件中有s1 = s0 + 1 所以如果d[i] == 1 将 f[i]初始化为1

d[i - 1] == 1 && d[i] == -1 或者 d[i - 1] == -1 && d[i] == 1 都有 f[i] = max(f[i], f[i - 1] + 1)

c ++class Solution {
public:
    int alternatingSubarray(vector<int>& nums) {
        int n = nums.size();
        vector<int> d(n + 10, 0);
        vector<int> f(n + 10, 0);
        
        for(int i = 1; i < n; i ++ ) {
            d[i] = nums[i] - nums[i - 1];
        }
        
        for(int i = 1; i < n; i ++ ) {
            if(d[i] == 1) f[i] = 1;
            if(d[i - 1] == 1 && d[i] == -1 || d[i - 1] == -1 && d[i] == 1) {
                f[i] = max(f[i], f[i - 1] + 1);
            }
        }
        
        int res = 0;
        for(int i = 1; i < n; i ++ ) res = max(res, f[i]);
        
        return res != 0 ? res + 1: -1;
    }
};

一个简单的哈希，注意每次操作要把某位置全部的石子进行移动

c ++ 
class Solution {
public:
    vector<int> relocateMarbles(vector<int>& nums, vector<int>& moveFrom, vector<int>& moveTo) {
        int n = nums.size();
        int m = moveFrom.size();
        
        unordered_map<int, int> mp;
        
        for(int i = 0; i < n; i ++ ) {
            mp[nums[i]] ++ ;
        }
        
        for(int i = 0; i < m; i ++ ) {
            if(moveFrom[i] == moveTo[i]) continue;
            mp[moveTo[i]] += mp[moveFrom[i]];
            mp[moveFrom[i]] = 0;
        }
        
        vector<int> res;
        for(auto it : mp) {
            if(it.second) res.push_back(it.first);
        }
        
        sort(res.begin(), res.end());
        
        return res;
        
    }
};

本题中s的范围比较小，O(n^2)进行子序列动态规划即可。

c ++ 
class Solution {
    int f[20];
    bool check(string s) {
        if(s[0] == '0') return false;
        int n = s.size();
        int sum = 0;
        for(int i = 0; i < n; i ++ ) {
            sum = sum * 2 + s[i] - '0';
        }
        while(sum % 5 == 0) {
            sum /= 5;
        }
        return sum == 1;
    }
    
public:
    int minimumBeautifulSubstrings(string s) {
        int n = s.size();
        int res = 0x3f3f3f3f;
        memset(f, 0x3f, sizeof f);
        
        f[0] = 0;
        for(int i = 0; i < n; i ++ ) {
            for(int j = i; j < n; j ++ ) {
                string tmp = s.substr(i, j - i + 1);
                if(check(tmp)) {
                    f[j + 1] = min(f[j + 1], f[i] + 1);
                }               
            }
        }
        
        return f[n] <= n ? f[n]: -1;
    }
};

本题采用逆向思维，我们不去正向枚举每个2*2矩阵中的黑白格子数目，而是通过黑格子去进行逆推。

每个黑格子会使其周围的2 * 2矩阵黑格子数目加一，我们遍历所有黑格子，来对答案进行统计。

c ++ 
class Solution {
    typedef long long LL;
public:
    vector<long long> countBlackBlocks(int m, int n, vector<vector<int>>& coordinates) {
        map<pair<int, int>, int> cnt;
        int dx[4] = {0, -1, -1, 0};
        int dy[4] = {-1, -1, 0, 0};

        for(auto &p : coordinates) {
            for(int k = 0; k < 4; k ++ ) {
                int nx = p[0] + dx[k], ny = p[1] + dy[k];
                if(nx < 0 || nx >= m - 1 || ny < 0 || ny >= n - 1) continue;
                cnt[{nx, ny}] ++ ;
            }
        }

        vector<LL> res(5);
        for(auto &[_, v] : cnt) {
            res[v] ++ ;
        }

        res[0] = 1LL * (m - 1) * (n - 1) - accumulate(res.begin() + 1, res.end(), 0);

        return res;
    }
};