周赛传送门

掉大分咯~

重排字符形成目标字符串

思路：统计字符数量

时间复杂度：$O(n+m)$

分别统计 s 和 target 中每种字符的数量，分别使用一维数组 cs 和 ct 存储，那么答案可表示为：
$$\underset{i\in [a,z],c{t}_i\ne 0}{\min }\frac{c{s}_i}{c{t}_i}$$

class Solution {
public:
    int rearrangeCharacters(string s, string target) {
        
        int cs[26] = {0}, ct[26] = {0};
        std::for_each(s.begin(), s.end(), [&cs](char c) {cs[c-'a']++;});
        std::for_each(target.begin(), target.end(), [&ct](char c) {ct[c-'a']++;});
        
        int anw = 100;
        for (int i = 0; i < 26; i++) {
            if (ct[i]) {
                if (ct[i] == 0) {
                    return 0;
                }
                anw = min(anw, cs[i]/ct[i]);
            }
        }
        
        return anw;
    }
};

价格减免

思路：模拟

时间复杂度：$O(n)$

标准的模拟题啦，还挺简单的，我只交了七遍就过了 ?。

小数点精度可以借助 sprintf 控制。

class Solution {
public:
    pair<int, int64_t> cal(const std::string &s, int p) {
        if (p >= s.size()) {
            return make_pair(s.size(), -1);
        }
        int64_t price = 0;
        int n = s.size();
        for (int i = p; i < n; i++) {
            if ('0' <= s[i] && s[i] <= '9') {
                price *= 10;
                price += s[i]-'0';
            } else if (s[i] == ' ' && i != p) {
                return make_pair(i-1, price);
            } else {
                return make_pair(-1, -1);
            }
        }
        
        return make_pair(n-1, price);
    }
    string discountPrices(string s, int d) {
        string anw;
        int n = s.size();
        for (int i = 0; i < n; i++) {
            if ((i == 0 && s[i] == '$') || (s[i] == ' ' && i+1 < n && s[i+1] == '$')) {
                auto [pos, price] = cal(s, i ? i+2 : i+1);
                if (price == -1) {
                    anw += s[i];
                    continue;
                }
                char tmp[20] = {0};
                sprintf(tmp, i ? " $%.2f" : "$%.2f", price * (100-d) / 100.0);
                anw += tmp;
                i = pos;
            } else {
                anw += s[i];
            }
        }
        return anw;
    }
};

使数组按非递减顺序排列

思路：数组模拟

时间复杂度：$O(n)$

设 $cos{t}_i$ 为每个数字被删除的时间(在第几轮操作被删掉)，最大的 $cos{t}_i$ 即为答案。

考虑第 $i$ 个数字 $nu{m}_i$，如果在区间 $[0,i-1)$ 中不存在比它大的数字，则 $cos{t}_i=0$，表示永远不会被删除。

接下来，只考虑区间 $[0,i-1)$ 中存在 $m$ 个数字大于 $nu{m}_i$ 的情形，设 $m$ 个数字中最大下标为 $j$，则有：

• 如果 $j+1=i$，即相邻，则 $cos{t}_i=1$。
• 反之，$cos{t}_i=\max (cos{t}_k)+1,k\in (j,i)$。

第一个结论是显然的。

第二个结论，因为区间$(j,i)$中的数字不会删除 $nu{m}_i$，因此当且仅当 $(j,i)$ 都被删除后，下一轮操作就会删除 $nu{m}_i$。

class Solution {
public:
    int totalSteps(vector<int>& nums) {
        // prev[i] 记录前一个比 nums[i] 大的数字的下标。
        // prev[i] = -1，表示前面没有比他大的数字。
        vector<int> prev(nums.size());
        // cost[i] 表示第几轮删除 nums[i]。
        vector<int> cost(nums.size());

        // 第一个数字，显然前面没有比它大的了
        prev[0] = -1;

        // 记录最大的 cost[i]
        int anw = 0;

        for (int i = 1; i < nums.size(); i++) {
            if (nums[i-1] > nums[i]) {
                // 前一个数组就比自己大，必然第一轮就被删了。
                prev[i] = i-1;
                cost[i] = 1;
            } else if (nums[i-1] == nums[i]) {
                // 前一个数组和自己一样大，显然删完前一个就会删到自己。
                prev[i] = prev[i-1];
                cost[i] = (prev[i-1] == -1 ? 0 : cost[i-1]+1);
            } else {
                // 通过 prev 向前跳若干次，直到跳出边界或者找到比自己大的值。
                // 向前跳跃期间，记录若干个区间 (prev[tp],tp] 中的最大值，即 cost[tp] 中的最大值。
                int tp = i-1, tc = 0;
                while (tp >= 0) {
                    if (nums[tp] > nums[i]) {
                        break;
                    }
                    tc = max(tc, cost[tp]);
                    tp = prev[tp];
                }
                // 如果存在 prev[i]，则 tc 即为 cost[prev[i]+1, i-1] 中的最大值。
                prev[i] = tp;
                cost[i] = (tp == -1 ? 0 : tc+1);
            }
            anw = max(anw, cost[i]);
        }

        return anw;
    }
};

到达角落需要移除障碍物的最小数目

思路：最短路

时间复杂度：$O(n\ast m)$

首先构图，点对应单元格，并设置点权：

• 无障碍为 0
• 有障碍为 1

相邻两单元格对应的点，连一条边，边权为 0。

在图上找出起始点和目标点的最短路(点权之和最小的路径)，该路径的点权之和即为答案。

class Solution {
public:
    int minimumObstacles(vector<vector<int>>& grid) {
        // 优先队列
        // second 表示单元格位置
        // first 表示从起始点到 second 的路径的点权之和。
        priority_queue<pair<int, pair<int, int>>, std::vector<pair<int, pair<int, int>>>, std::greater<pair<int, pair<int, int>>>> queue;
        // 初始化
        queue.push(make_pair(0, make_pair(0, 0)));

        int n = grid.size(), m = grid[0].size();

        // cost[i][j] 用来记录 [0,0] 到 [i,j] 的最短路的点权之和。
        vector<vector<int>> cost(n, vector<int>(m, n+m));

        // 求最短路
        while (!queue.empty()) {
            auto f = queue.top();
            queue.pop();

            int x = f.second.first;
            int y = f.second.second;
            int c = f.first;

            if (x == n-1 && y == m-1) {
                return c;
            }
            
            if (c > cost[x][y]) {
                continue;
            }

            int dx[] = {-1,  0,  1,  0};
            int dy[] = { 0,  1,  0, -1};

            for (int i = 0; i < 4; i++) {
                int nx = dx[i] + x;
                int ny = dy[i] + y;

                if (0 <= nx && nx < n && 0 <= ny && ny < m) {
                    int nc = c + grid[nx][ny];
                    if (cost[nx][ny] > nc) {
                        cost[nx][ny] = nc;
                        queue.push(make_pair(nc, make_pair(nx,ny)));
                    }
                }
            }
        }

        return cost[n-1][m-1];
    }
};