上周周赛。

双题选手。

2287. Rearrange Characters to Make Target String

Analysis

统计 s 中和 target 相同的字符次数，然后模拟构成 target 子串即可。

Code

这是当时提交通过的代码：

class Solution {
public:
    int rearrangeCharacters(string s, string target) {
        vector<int> cnt(26);
        int len = s.length();
        for(int i = 0; i < len; i++) {
            cnt[s[i] - 'a']++;
        }
        int ret = 0;
        bool flag = true;
        while(true) {
            len = target.length();
            for(int i = 0; i < len; i++) {
                cnt[target[i] - 'a']--;
                if(cnt[target[i] - 'a'] < 0) {
                    flag = false;
                    break;
                }
            }
            if(!flag) break;
            ret++;
        }
        return ret;
    }
};

实际上，这个题可以通过维护两个哈希表做除法来确定最多能组成几个 target。

class Solution {
public:
    int rearrangeCharacters(string s, string target) {
        vector<int> cnt1(26), cnt2(26);
        int len = s.length();
        for(char c: s) {
            cnt1[c - 'a']++;
        }
        for(char c: target) {
            cnt2[c - 'a']++;
        }
        int min_val = INT_MAX;
        for(char c: target) {
            min_val = min(min_val, cnt1[c - 'a'] / cnt2[c - 'a']);
        }
        return min_val;
    }
};

2288. Apply Discount to Prices

Analysis

这个题实际上算是个披着中等题外衣的简单题，难点在于对不同情况的分类，所以很容易 WA（WA 了 5 次😓）。

Code

这是当时提交通过的代码：

class Solution {
public:
    string discountPrices(string sentence, int discount) {
        int len = sentence.length();
        string ret = "";
        for(int i = 0; i < len; i++) {
            if(sentence[i] != '$') ret.push_back(sentence[i]);
            else {
                ret.push_back(sentence[i]);
                if(i > 0 && sentence[i - 1] != ' ') continue;
                i++;
                if(i == len) break;
                if(!isdigit(sentence[i])) {
                    ret.push_back(sentence[i]);
                    continue;
                }
                double tmp = 0;
                bool flag = true;
                int pos = i;
                while(i < len && sentence[i] != ' ') {
                    if(!isdigit(sentence[i]) && sentence[i] != ' ') {
                        flag = false;
                        break;
                    }
                    tmp = tmp * 10 + sentence[i] - '0';
                    i++;
                } 
                if(flag) {
                   tmp = tmp * (1 - discount / 100.0) + 0.005;
                    string t = to_string(tmp);
                    int j = 0;
                    while(j < t.length() && t[j] != '.') {
                        ret.push_back(t[j]);
                        j++;
                    }
                    ret.push_back(t[j]);
                    ret.push_back(t[j + 1]);
                    ret.push_back(t[j + 2]);
                    if(i != len) {
                        ret.push_back(sentence[i]);
                    }
                } else {
                    ret += sentence.substr(pos, i - pos + 1);
                }
            }
        }
        return ret;
    }
};

被那几个用例来回折磨...
稍微改一下：

class Solution {
public:
    string discountPrices(string sentence, int discount) {
        int len = sentence.length();
        string ret = "";
        for(int i = 0; i < len; i++) {
            if(sentence[i] != '$') ret.push_back(sentence[i]);
            else {
                ret.push_back(sentence[i]);
                if(i > 0 && sentence[i - 1] != ' ') continue;
                i++;
                if(i == len) break;
                if(!isdigit(sentence[i])) {
                    ret.push_back(sentence[i]);
                    continue;
                }
                double tmp = 0;
                bool flag = true;
                int pos = i;
                while(i < len && sentence[i] != ' ') {
                    if(!isdigit(sentence[i]) && sentence[i] != ' ') {
                        flag = false;
                        break;
                    }
                    tmp = tmp * 10 + sentence[i] - '0';
                    i++;
                } 
                if(flag) {
                   tmp = tmp * (1 - discount / 100.0) + 0.005;
                    string t = to_string(tmp);
                    int j = 0;
                    while(j < t.length() && t[j] != '.') {
                        ret.push_back(t[j]);
                        j++;
                    }
                    for(int k = j; k < j + 3; k++) {
                        ret.push_back(t[k]);
                    }
                    if(i != len) ret.push_back(sentence[i]);
                } else {
                    ret += sentence.substr(pos, i - pos + 1);
                }
            }
        }
        return ret;
    }
};

题目要保留 2 位小数，那么第 3 位小数就要四舍五入，一个解决办法是直接加上 0.005，另外一个解决办法是用long double。
PS：C++ 的字符串能力确实不如其他语言...这个题写的有点折磨人。

2289. Steps to Make Array Non-decreasing

Analysis

这个题想了挺久的，可惜没想出来...
当时把第二个题改好，就已经毫无耐心了，看了两眼后面两个题就溜了😂。
现在再回来倒腾一下。

Code

em，先琢磨一下暴力解法。

class Solution {
public:
    int totalSteps(vector<int>& nums) {
        int cnt = 0;
        while(true) {
            int n = nums.size();
            vector<int> tmp;
            bool flag = true;
            tmp.push_back(nums[0]);
            for(int i = 1; i < n; i++) {
                if(nums[i] < nums[i - 1]) flag = false;
                else tmp.push_back(nums[i]);
            }
            if(!flag) cnt++;
            else break;
            nums = tmp;
        }
        return cnt;
    }
};

暴力解法还算是比较容易想到（好像前几周的周赛的第一道跟这个差不多），思路就是暴力模拟，时间复杂度是 $O(n^2)$，死在第 79 个用例了。
参考了一下大佬的题解：等价转换 + 利用单调性（Python/Java/C++/Go）。
原来这是个单调栈的题，但是想到用单调栈来处理不算容易。
首先要能想到的是将问题是一个数字能否“活到”最后，只取决于这个数字的左边有没有比它更大的数字。如果有，那这个数字一定会被拿掉；反之，这个数字一定会出现在结果序列中。
然后需要考虑的是被拿掉的数字会在那一轮筛选中被拿掉。观察用例可以发现，被拿掉的数字肯定是这个数字与其左边第一个大于它的数字中间的数被拿掉之后才会被拿掉（我在说什么呢？😂）。以5, 3, 4, 5, 7, 3, 6, 11, 8, 5, 11为例，6一定会被拿掉，但是6一定是在其前面的3被拿掉后的下一轮筛选中被拿掉。换句话说，拿掉6需要的操作数就是拿掉3需要的操作数加 1。

按照这样的思路，可以使用一个单调递减栈来存储元素及其对应被拿掉的轮次（用时刻来表示也是可以的）。当栈顶元素小于当前元素时，就弹出栈顶元素，同时取被弹出元素轮次的最大值maxt，然后将当前元素与maxt + 1入栈。如果此时栈为空，说明当前元素不会被拿掉，maxt = 0，然后入栈。

class Solution {
public:
    int totalSteps(vector<int>& nums) {
        int ans = INT_MIN;
        stack<pair<int, int>> st;
        for(int i: nums) {
            int maxt = 0;
            while(!st.empty() && st.top().first <= i) {
                maxt = max(maxt, st.top().second);
                st.pop();
            }
            maxt = st.empty() == true ? 0 : maxt + 1;
            st.emplace(i, maxt);
            ans = max(ans, maxt);
        }
        return ans;
    }
};

难点在思路上，本身的实现过程其实并不复杂。

2290. Minimum Obstacle Removal to Reach Corner

Analysis

第一眼看到这个题的时候，就意识到了这是个与图相关的走迷宫的题目。跟图相关的内容，已经是忘的差不多...

Code

实际上这是个最短路的问题，grid可以直接当作这个图的邻接矩阵，那么整个题的求解过程就可以直接用 bfs 来完成。

class Solution {
public:
    int dirs[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
    int minimumObstacles(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        vector<vector<int>> dist(m, vector<int>(n, INT_MAX));
        queue<pair<int, int>> q;
        q.emplace(0, 0);
        dist[0][0] = 0;
        while(!q.empty()) {
            auto u = q.front(); q.pop();
            for(int i = 0; i < 4; i++) {
                int newx = u.first + dirs[i][0];
                int newy = u.second + dirs[i][1];
                if(0 <= newx && newx < m && 0 <= newy && newy < n &&
                 dist[newx][newy] > dist[u.first][u.second] + grid[u.first][u.second]) {
                    dist[newx][newy] = dist[u.first][u.second] + grid[u.first][u.second];
                    q.emplace(newx, newy);
                }
            }
        }
        return dist[m - 1][n - 1];
    }
};