1. 重排字符形成目标字符串
题目
样例
代码
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
2. 价格减免
题目
样例
代码
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)
3. 使数组按非递减顺序排列
题目
样例
代码
观察一个性质：
对于一串非降的序列（序列前有个更大的元素），该序列每个元素被删除的时间是单调递增的。
利用这一单调性，我们只需要存储这串非降序列的最后一个元素被删除的时间，这些时间的最大值就是所需要计算的最大值。
用一个单调递减栈存储元素及其被删除的时间，当遇到一个不小于栈顶的元素 x 时，就不断弹出栈顶元素，并取弹出元素被删除时间的最大值。
class Solution { public: int totalSteps(vector<int>& nums) { int res = 0; stack<pair<int, int>> 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; } };
4. 到达角落需要移除障碍物的最小数目
题目
样例
代码
0-1 BFS：
把障碍物当作可以经过的单元格，经过它的代价为 1 ，空单元格经过的代价为 0 。
问题转化成从起点到终点的最短路。
我们可以用 Dijkstra（priority_queue），但还可以用 0-1 BFS 来将时间复杂度优化至 O(mn)。
对于队列里头的元素，很显然的是，同一时间最多只会相差点权为 1.
于是通过堆来排序的思路可以换作双端队列来手动排序， + 0 的排到队头， + 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<vector<int>>& grid) { int n = grid.size(), m = grid[0].size(); vector<vector<int>> dis(n, vector<int>(m, inf)); deque<pair<int, int>> 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]; } };
