【 NO.1 重排字符形成目标字符串】
& \+ i1 i; b3 _, E: i' o- _3 a9 q" Z5 a7 A
解题思路" G- e5 w' F2 x; H. |/ K" @* n& B9 K
0 t% _: f4 U/ l8 }# A: D
统计每种字符的数量，原字符串和目标字符串的对应字符数量之比的最小值即答案。
$ i4 p5 w+ v4 `$ z" {. C) k% p2 g) A* j) ?7 `8 ?: ~0 a0 q
代码展示) ]5 R* m: `* s P2 z
: S) R5 L* d1 n& B' \: T, L- ]: g, Y3 @( O% m9 C7 j
+ T F% k( }- h( L7 s2 z5 @【 NO.2 价格减免】3 A- W: @, z& V; |- I7 c0 X
8 g u9 _% S4 z; G" `; O
解题思路
( [6 [) x9 ]( ^2 F9 w2 s* D4 [: _! q8 e5 z: ]6 `
按照题意要求解析字符串、计算即可。注意一个 corner case: 单一个 $ 也是单词。
w8 |! O* S8 F+ j' }4 n$ \9 B0 C* C }$ T7 R
代码展示
8 [4 ^) [, z2 X
, ^) t* K3 |% y0 Y/ Z% m9 y# t6 I! m2 e4 O& o1 O
# e+ H9 A8 c$ a) ?" I
【 NO.3 使数组按非递减顺序排列】
. B! I- I! k E, G9 s! v
2 [" h3 z: t, |/ r9 R. o解题思路+ G0 u' ~ D' }! T" H
+ Y- }( w( ^0 e. b动态规划 + 单调栈。
5 x9 D% {. ]# @1 K# d
/ m8 a' V3 q# Z4 d8 `设 dp 表示将 i 移除需要操作多少次，若 i 最终不会被移除则 dp = inf。
+ m( W- P( t1 R8 b
0 k& {4 O+ Q; }& E) }维护一个单调递减的栈，当前元素入栈时，会有一些元素 (假设为 X) 被它弹出。
4 I+ Z( a5 A. f; D. w4 _! H6 w, R( K3 f9 g& a1 u
若当前元素入栈前所有元素都会被弹出，说明这个元素就是最大的，不会被删除。否则，它最终将会被当时的栈顶删除，而具体会在第几次被删除，取决于 X 需要经过多少轮才被删除，取 max{dp[x]}。
& c3 i+ s- J/ A6 v8 s% X% g* C0 j1 l; ^+ T) ~- E: b$ H, d
代码展示
6 E" P+ V5 v W4 y4 d- B
' E7 ]. Q6 H; e% |0 M% `$ k1 e7 Z% s A+ d
; \( X: A" L( F, ^- m【 NO.4 到达角落需要移除障碍物的最小数目】+ \+ F, O8 ~6 W6 J0 L) L
- \4 E0 C: `0 I% |* q
解题思路 L) B; D. I/ A$ q3 O1 K! H5 D4 j* T
+ h+ C1 `& g; p最短路。每两个相邻的点之间连边，如果目标点为障碍物，则边权为 1，否则为 0。用 dijkstra 算法求最短路即可。
7 Y5 d4 d2 S& f" e/ A# d1 C
1 h' S" x3 w1 }/ Y" J1 U代码展示
$ Q; U2 ~* u8 [: N# J/ n |
