A. Rearrange Characters to Make Target String (opens new window)

DETAILS

class Solution {
public:
    int rearrangeCharacters(string s, string t) {
        map<char, int> ss, tt;
        for (auto ch : s)
            ss[ch]++;
        for (auto ch : t)
            tt[ch]++;
        int ans = s.size() / t.size();
        for (auto const &x : tt) 
            ans = min(ans, ss[x.first] / x.second);

        return ans;
    }
};

B. Apply Discount to Prices (opens new window)

Split string, find the valid word and multiply the number by discount.

DETAILS

class Solution:
    def discountPrices(self, S: str, d: int) -> str:
        S = S.split(" ")
        for i, s in enumerate(S):
            if s[0] == '$' and s[1:].isdigit():
                S[i] = '$' + "{:.2f}".format(int(s[1:]) * (100 - d) / 100)
        return " ".join(S)

C. Steps to Make Array Non-decreasing (opens new window)

Please refer to This LC Discussion (opens new window) for my solutions in English.

维持一个递减栈。 我们这么想：一个数字(我们假设它的下标是i)，如果最终被消灭，那一定是被它左边的某个大于它的数(我们假设它的下标是j)消灭的，在此之前，数字i必须等待所有位于i, j之间的数都被消灭掉，之后的下一秒它才会被消灭。这个时间，就等于所有这些中间数的被消灭时间中的最大值再加1。

DETAILS

def totalSteps(self, A: List[int]) -> int:    
        st = [[A[0], 0]]
        ans = 0
        
        for a in A[1:]:
            t = 0
            while st and st[-1][0] <= a:
                t = max(t, st[-1][1])
                st.pop()
            if st: 
                t += 1
            else:
                t = 0
            ans = max(ans, t)
            st.append([a, t])
            
        return ans

D. Minimum Obstacle Removal to Reach Corner (opens new window)

Dijkstra

DETAILS

#define vi vector<int>
#define vvi vector<vi>
#define pi pair<int, int>
#define vpi vector<pi>

class Solution {
public:
    int minimumObstacles(vector<vector<int>>& A) {
        int m = A.size(), n = A[0].size();
        //auto cmp = [](const auto &a, const auto &b) { return a[0] > b[0]; };
        priority_queue<pair<int, pi>, vector<pair<int, pi>>, std::greater<pair<int, pi>> > pq;
        vvi C(m, vi(n, 100000));
        C[0][0] = 0;
        vi dirs = {0, 1, 0, -1, 0};
        
        pq.push({0, {0, 0}});
        while (!pq.empty()) {
            auto cur = pq.top();
            pq.pop();
            int c = cur.first, cx = cur.second.first, cy = cur.second.second;
            if (cx == m - 1 && cy == n - 1) 
                return c;
            for (int i = 0; i < 4; ++i) {
                int x = cx + dirs[i], y = cy + dirs[i + 1];
                if (x < 0 || x >= m || y < 0 || y >= n) continue;
                int cc = A[x][y];
                if (c + cc < C[x][y]) {
                    C[x][y] = c + cc;
                    pq.push({C[x][y], {x, y}});
                }
            }
        }
        return -1;
    }
};