【LeetCode第 295 场周赛】

传送门

• 1. 重排字符形成目标字符串
• • • 题目
    • 样例
    • 代码
• 2. 价格减免
• • • 题目
    • 样例
    • 代码
• 3. 使数组按非递减顺序排列
• • • 题目
    • 样例
    • 代码
• 4. 到达角落需要移除障碍物的最小数目
• • • 题目
    • 样例
    • 代码

class Solution:
    def rearrangeCharacters(self, s: str, target: str) -> int:
        x = Counter(s)
        y = Counter(target)
        cnt = inf
        for k, v in y.items():
            cnt = min(cnt, x[k] // v)
        return cnt
        

class Solution:
    def discountPrices(self, sentence: str, discount: int) -> str:
        s = []
        for i in sentence.split():
            try:
                assert i[0] == '$'
                val = float(i[1:])
                val *= (100 - discount) / 100
                s.append("$%.2f" % round(val, 2))
            except:
                s.append(i)
        return " ".join(s)

• 观察一个性质：

  • 对于一串非降的序列（序列前有个更大的元素），该序列每个元素被删除的时间是单调递增的。
  • 利用这一单调性，我们只需要存储这串非降序列的最后一个元素被删除的时间，这些时间的最大值就是所需要计算的最大值。

用一个单调递减栈存储元素及其被删除的时间，当遇到一个不小于栈顶的元素 x {x} x 时，就不断弹出栈顶元素，并取弹出元素被删除时间的最大值。

class Solution {
public:
    int totalSteps(vector& nums) {
        int res = 0;
        stack> s;
        for (auto &x: nums) {
            int maxT = 0; // 当前x应该删除的时间
            // 栈不空 & x>=top
            while(!s.empty() && s.top().first <= x) {
                maxT = max(maxT, s.top().second);
                s.pop();
            }
            if(!s.empty()) ++maxT;
            res = max(maxT, res);
            s.push({x, maxT});
        }
        return res;
    }
};

• 0-1 BFS：

  • 把障碍物当作可以经过的单元格，经过它的代价为 1 {1} 1，空单元格经过的代价为 0 {0} 0。
  • 问题转化成从起点到终点的最短路。
  • 我们可以用 Dijkstra（priority_queue），但还可以用 0-1 BFS 来将时间复杂度优化至 O ( m n ) {O(mn)} O(mn)。
  • 对于队列里头的元素，很显然的是，同一时间最多只会相差点权为 1 {1} 1.
    于是通过堆来排序的思路可以换作双端队列来手动排序， + 0 {+0} +0 的排到队头， + 1 {+1} +1 的排到队尾。

class Solution {
public:
    static constexpr int walk[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
    static constexpr int inf = 0x3f3f3f3f;
    int minimumObstacles(vector>& grid) {
        int n = grid.size(), m = grid[0].size();
        vector> dis(n, vector(m, inf));
        deque> q;
        q.emplace_front(0, 0);
        dis[0][0] = 0;

        while(q.size()) {
            auto [x, y] = q.front(); q.pop_front();
            for (auto &[fx, fy]: walk) {
                int dx = fx + x, dy = fy + y;
                if(dx >= 0 && dx < n && dy >= 0 && dy < m) {
                    int f = grid[dx][dy];
                    if(dis[x][y] + f < dis[dx][dy]) {
                        dis[dx][dy] = dis[x][y] + f;
                        f == 0 ? q.emplace_front(dx, dy) : q.emplace_back(dx, dy);
                    }
                }
            }
        }
        return dis[n - 1][m - 1];
    }
};