【 NO.1 重排字符形成目标字符串】# j4 w' t0 M A, W2 e
4 b* Q" _9 Q4 E* y解题思路
. F) Q: U, v6 e* L$ \& O5 P. [
# h+ k* u! ?" _# n, ^+ K统计每种字符的数量，原字符串和目标字符串的对应字符数量之比的最小值即答案。' m% P+ h# C4 o4 w1 N G
/ y) m+ d) @* P9 p6 T7 q
代码展示" a6 e1 m9 q: E6 ~/ \1 L, [
5 y: Q* X9 {/ Q; P+ ]# |& X, b, F3 |- F( }& ]7 N3 B" X
; S) a( b% S% M1 k2 I+ P8 `【 NO.2 价格减免】
1 f; h0 ]+ i# b2 ~5 ~2 W2 h* x7 O# E2 K+ ]0 A
解题思路
1 x7 S) b. A2 o% F% f0 f
; q G. P6 q9 ^1 S, Y+ k按照题意要求解析字符串、计算即可。注意一个 corner case: 单一个 $ 也是单词。
/ B# }5 g9 ?/ a2 N
7 A" {' `* ^0 U% H# C& o2 E代码展示
" Y) z; u) K: M& I& g; u
5 t& f) |+ b/ K- T! O3 C4 \7 [# q6 p1 V6 a# R1 |: j
7 r9 m/ x5 ]( t0 @【 NO.3 使数组按非递减顺序排列】/ S/ k* Y3 ~# g" ]2 o
- a4 I9 t9 X+ y! H" f* o% }解题思路5 i* W5 s* z5 G$ W: r. ~5 _
8 @- K7 V, O7 q3 c+ K. m
动态规划 + 单调栈。9 n) C5 h0 Y$ R) G
, H% U4 v9 c- d: z设 dp 表示将 i 移除需要操作多少次，若 i 最终不会被移除则 dp = inf。% Z! i' o; I$ a: ^
) A, \3 d* j8 a4 r; h
维护一个单调递减的栈，当前元素入栈时，会有一些元素 (假设为 X) 被它弹出。0 F, j/ |, \' h- P) z* {, H
! v* ?' Z. o2 @: h, e( W! i k
若当前元素入栈前所有元素都会被弹出，说明这个元素就是最大的，不会被删除。否则，它最终将会被当时的栈顶删除，而具体会在第几次被删除，取决于 X 需要经过多少轮才被删除，取 max{dp[x]}。0 M2 U# R& ]# }" m6 R4 k
! p8 }2 B" G2 M, l4 o7 B& f9 R
代码展示
# p. C& {9 t' D" y) ?3 M8 l9 i& g' Y& J1 C
$ n( Q; h; _) W1 {* ~/ E0 v9 c- b
& s& \0 D( y# L: W, R【 NO.4 到达角落需要移除障碍物的最小数目】- o) T. f) G- \ S: w$ l) F
* l5 o" P7 r! H0 |( ~解题思路% Q& }% M5 P9 s( i+ _+ {
2 Z& ?) B' s1 s: d" ~0 j) P/ e最短路。每两个相邻的点之间连边，如果目标点为障碍物，则边权为 1，否则为 0。用 dijkstra 算法求最短路即可。8 l8 w* b+ J: K; B0 l
# N, I5 q% q& g% Q7 M- B代码展示 _2 L8 n1 w0 i9 P
|
