【 NO.1 重排字符形成目标字符串】
& I4 w( N. L) X
% V5 Q% c) d$ h0 X3 A0 [$ F解题思路
0 C9 w* y" x+ Q. h- b$ |3 ^
9 h7 o8 {8 [! a+ i- g( w4 ` N统计每种字符的数量，原字符串和目标字符串的对应字符数量之比的最小值即答案。
. b4 m! V6 f, X, t1 o3 M6 A; s% U
代码展示
- a1 _, K' [# h) o W2 X; ]" P' u1 k# q
% E5 _8 w( d6 [* D1 d4 j9 D3 f
8 v( y" B9 F" I: `2 C' M【 NO.2 价格减免】
- ?2 q; q B- \% s/ ?9 h* _ Q! a/ V0 k" j
解题思路
* m% Q7 A9 r' x3 h+ }
b3 w3 U, \; T2 r; G按照题意要求解析字符串、计算即可。注意一个 corner case: 单一个 $ 也是单词。
0 s1 |, ?, x# J4 @) U. {! B- m# Z" T$ [& @! [
代码展示) N3 c, W/ r. q* Z1 F
! g5 D& V G" O4 R+ l6 r
2 m# }+ r0 w0 \% G) @* w8 {7 J$ Q8 }* Z; C
【 NO.3 使数组按非递减顺序排列】$ f# M: n2 F8 k4 w; @
3 X2 w+ V4 L- P
解题思路6 Q6 }1 K% W, Z. E. y1 S
' z/ v8 x( C8 d! O
动态规划 + 单调栈。
6 P0 {' ^/ j. ?+ ?! K3 e! q- k1 H' v1 f6 n4 \
设 dp 表示将 i 移除需要操作多少次，若 i 最终不会被移除则 dp = inf。" i& D8 v( `/ G; V9 S) J2 ^
3 J, i) K- [6 ?* i, r维护一个单调递减的栈，当前元素入栈时，会有一些元素 (假设为 X) 被它弹出。: P" h# f& f$ L v$ ] O
. V. I5 o! {9 G9 W9 B& t6 L8 v* Z
若当前元素入栈前所有元素都会被弹出，说明这个元素就是最大的，不会被删除。否则，它最终将会被当时的栈顶删除，而具体会在第几次被删除，取决于 X 需要经过多少轮才被删除，取 max{dp[x]}。
7 m3 H/ b8 i0 @
5 W6 l5 ^. k" ~+ e- f0 ]代码展示
8 S: }$ ]- C2 C
, _) t3 {! D1 y8 k2 _8 D: g5 r
2 B) ?# C0 A! @0 k% J* w Q; x
3 O$ l) Q. W, F+ k1 t【 NO.4 到达角落需要移除障碍物的最小数目】) [/ v3 e' b- n: [
4 q; ~, F3 s7 `, f4 N
解题思路9 |, G5 h& R* c
3 @) K9 j7 m9 O4 F7 U" |4 p最短路。每两个相邻的点之间连边，如果目标点为障碍物，则边权为 1，否则为 0。用 dijkstra 算法求最短路即可。
9 b& G$ c& V4 u8 E/ p5 v$ W. h
# p; o W# ^ A0 ^- A5 z1 ]代码展示0 C+ E2 l& [4 T/ ^
|
