LeetCode周赛#225

传送门

T1替换隐藏数字得到的最晚时间

思路

签到题，注意一些细节就行。

代码

class Solution {
public:
    string maximumTime(string time) {
        if (time[0] == '?' && time[1] >= '4' && time[1] != '?')
            time[0] = '1';
        else if (time[0] == '?')
            time[0] = '2';
        
        if (time[1] == '?' && time[0] == '2')
            time[1] = '3';
        else if (time[1] == '?' && time[0] != '2')
            time[1] = '9';
        
        if (time[3] == '?')
            time[3] = '5';
        
        if (time[4] == '?')
            time[4] = '9';
        
        return time;
    }
};

T2满足三条件之一需改变的最少字符数

思路

枚举，对于三种要求，求出它们分别的步数，然后求三者最小值作为答案。

对于情况3，最简单，直接用i枚举26个字母，然后统计a串b串全部置为i所需要的步数就是情况3下的步数。

对于情况1与2，其实可以看做同一个过程，即把a(b)串中所有字符置为不小于b(a)串的字符。对于这个过程，依然是用i枚举26个字母，以i作为一个“中间字符”，统计前者串中小于i的字符数与后者串中大于等于i的字符数，加起来就是这种情况下的步数。

值得注意的是，因为不存在比a更小的字符，所以情况1、2时i应该从b枚举到z，而非从a开始。至于为什么z可以取，因为题干要求是“严格小于”，即左闭右开。

代码

class Solution {
public:
    // 处理情况1、2,因为本质上是一种操作，所以
    // 只需要交换ab串的位置就可以用一个函数实现
    int solve(string& a, string& b, char x) {
        int res = 0;
        for (char c : a) if (c >= x) res++;
        for (char c : b) if (c < x) res++;

        return res;
    }

    int minCharacters(string a, string b) {
        int ans = a.size() + b.size();

        for (char i = 'a'; i <= 'z'; i++) {
            int tmp = 0;
            for (char c : a) if (c != i) tmp++;
            for (char c : b) if (c != i) tmp++;
            ans = min(tmp, ans);
        }

        for (char i = 'b'; i <= 'z'; i++) {
            int tmp = min(solve(a, b, i), solve(b, a, i));
            ans = min(ans, tmp);
        }

        return ans;
    }
};

T3找出第 K 大的异或坐标值

思路

赛时想出来用数组预存前缀和了，居然没往dp想，只差临门一脚，太可惜了…

周赛经典第三题比第二题简单，这题只要看出来是dp基本上就a了，状态方程不难想。设dp[i][j]表示从(0,0)到(i,j)区域内所有元素的异或和，如下图：

dp[i][j]的值应该等于(0,0)到(i-1,j-1)这个小正方形的异或和再异或上图示中蓝色细长矩形与红色细长矩形。

但根据异或的性质，同一个数奇数次异或还是等于他自己，所以状态方程dp[i][j] = dp[i-1][j]^dp[i][j-1]^dp[i-1][j-1]^m[i][j]是可以正确表示上述求解思路的。

值得注意的是，因为题设下标从 0 开始计数 ，但 k 的值从 1 开始计数 ，所以在代码中应该异或的并非是matrix[i][j]而是 matrix [i-1][j-1].

代码

class Solution {
public:
    int kthLargestValue(vector<vector<int>>& matrix, int k) {
        int h = matrix.size();
        int w = matrix[0].size();
        vector<int> arr;
        vector<vector<int>> dp(h + 1, vector<int>(w + 1, 0));

        for (int i = 1; i <= h; i++) {
            for (int j = 1; j <= w; j++) {
                dp[i][j] = dp[i-1][j] ^ dp[i][j-1] ^ dp[i-1][j-1] ^ matrix[i-1][j-1];
                arr.push_back(dp[i][j]);
            }
        }
        sort(arr.begin(), arr.end(), [](int a, int b) -> bool {
            return a > b;
        });

        return arr[k-1];
    }
};

这里我用的是向量+排序来维护答案，事实上可以直接用一个大根堆来维护，当堆大小大于k时pop，使堆大小适中小于等于k，这样堆顶的元素就直接是答案了。