【 NO.1 重排字符形成目标字符串】. E' I3 h# m2 [1 n
) r, K) M/ Z" M4 E5 G* q4 ^, w ?解题思路* q% G: C% u2 n
1 a( g# p) x ?5 c3 ^: ?: \' V
统计每种字符的数量，原字符串和目标字符串的对应字符数量之比的最小值即答案。
& L, v, ]0 j" b! z' p6 K4 K! B" m% B* {* t
代码展示
, e/ m0 s5 W7 @5 B& F: Q7 N) X$ F$ ? J
, V1 y s$ Y4 O8 ~: m" w
0 V( f3 n. S `% g! X/ e
【 NO.2 价格减免】0 P! L- J/ h1 q5 `9 T+ Q
6 z0 P+ o( N( `8 x/ l' H解题思路
& T5 e+ K+ ^ p, ^; ^. R0 [$ @# z2 [3 m- X
按照题意要求解析字符串、计算即可。注意一个 corner case: 单一个 $ 也是单词。. A$ y1 Z* K/ M. v- t
5 \3 w) X! B+ o9 l' z
代码展示$ x/ ~# O, p) O$ O
2 x3 U9 y. I' M6 _7 v' T& ]8 O$ x
4 x. ]+ |/ k% a: g9 \. j/ T# m
/ V- \* H8 u& F0 S! C" P; i4 M0 c* N
【 NO.3 使数组按非递减顺序排列】
9 f& y1 [. ]. ]* [* [3 z0 |5 D0 ^
' Q0 x% _) ?: R& u2 W解题思路) c8 s! B: M; }) w; C) _: [( L5 t% g
9 j1 w: I0 v1 `" B9 e动态规划 + 单调栈。9 W; H8 X; p5 z8 ^1 s1 S, D6 Q8 |
! ^- t, f& ~0 |设 dp 表示将 i 移除需要操作多少次，若 i 最终不会被移除则 dp = inf。( R# ^ q% P; K4 t! e8 a! l
8 S2 z& S' T! j& W. ^' D$ r
维护一个单调递减的栈，当前元素入栈时，会有一些元素 (假设为 X) 被它弹出。9 ?! Y( s: b9 k2 e
6 n( { q8 D# l$ l Z6 ^' F1 E
若当前元素入栈前所有元素都会被弹出，说明这个元素就是最大的，不会被删除。否则，它最终将会被当时的栈顶删除，而具体会在第几次被删除，取决于 X 需要经过多少轮才被删除，取 max{dp[x]}。7 C7 g7 W/ [* s% J" R+ M
5 ?( S C0 L, y, n# B
代码展示
6 h8 z' f2 x; x% f. O- W+ }' J, z% W& i9 V m1 E
2 W1 y( E6 B" c. s6 K: H$ m7 @* P2 z
【 NO.4 到达角落需要移除障碍物的最小数目】
5 ]$ l; k; u# F6 n8 |3 }4 {5 K& H1 h- N
解题思路' m9 S. q7 `2 g, [0 U" l0 n
7 K) F: Y/ _$ ~4 j! T# f9 m最短路。每两个相邻的点之间连边，如果目标点为障碍物，则边权为 1，否则为 0。用 dijkstra 算法求最短路即可。( a: m8 h% n! L% |' u3 e; y
1 n- Y4 E& J; D- V! i( O/ W5 E0 {! i
代码展示
+ \) b% v& b: ]7 |5 V M |
