【 NO.1 重排字符形成目标字符串】; M9 d5 p, o" ^% m: c/ f; I! j
$ s: H" ^9 X e6 d" q
解题思路
3 p+ c5 Z2 r4 ~ b! p7 ?7 Q$ n7 e; U! d( j" k$ V
统计每种字符的数量，原字符串和目标字符串的对应字符数量之比的最小值即答案。1 u" U2 V0 p7 x
+ p5 C4 I3 a! k
代码展示3 p/ D. e% e) R- v' G X
: t3 Y% A/ J% p( V8 p3 ~- }" ?- l* ~1 H) s" }
/ Y! N1 }6 @$ N" t【 NO.2 价格减免】2 { g( Z" I7 E# K
( \1 g; t6 w, T, T. C3 ~: J' N
解题思路
9 g) n5 ^8 F/ q Q" H4 P2 a7 G6 {
4 S- B4 B9 B2 o: r4 q; p按照题意要求解析字符串、计算即可。注意一个 corner case: 单一个 $ 也是单词。
' s' `( n- _% q, S" h# y/ w# H7 N: n9 o9 u( I0 W3 R/ \
代码展示
7 s: R8 t) E3 I: Q1 r7 O+ Z0 b. R" ~! W: Q( i: |6 T
3 _2 g' N) \" O' p# |2 P$ z. L6 s' C
【 NO.3 使数组按非递减顺序排列】' m9 G/ E; D6 {/ \: A
) w4 z0 r' H8 F3 @ X- K( }! B" u# g解题思路
! h* T" Y2 L; c& X P$ d: X
/ M9 D2 I$ @6 h动态规划 + 单调栈。. A* S6 Y b' y) e, L
- V' L( z) ?$ a' D! `
设 dp 表示将 i 移除需要操作多少次，若 i 最终不会被移除则 dp = inf。* y2 u. q7 J n0 [ m1 [
4 ]2 q1 a. X: e% X$ {; }维护一个单调递减的栈，当前元素入栈时，会有一些元素 (假设为 X) 被它弹出。
4 m @. Y; P- n+ h- ?
5 M/ Y$ d; ?+ L, P若当前元素入栈前所有元素都会被弹出，说明这个元素就是最大的，不会被删除。否则，它最终将会被当时的栈顶删除，而具体会在第几次被删除，取决于 X 需要经过多少轮才被删除，取 max{dp[x]}。% @5 L7 h$ }+ I2 [' E0 F
0 x. A2 h: f C0 A) o( ^代码展示% t& I: r3 ?8 z0 g) D3 p$ C
+ D! o5 r+ M4 t$ S$ V5 \: }. G( s( W) X X6 I- V, P
; |# H4 {2 [) {+ ?/ @! l( \) T$ T
【 NO.4 到达角落需要移除障碍物的最小数目】8 U" z1 D# d, ~; l
0 W9 q8 K% f( u P$ p
解题思路+ Y% j5 t6 n7 e* F' \% f a' {5 D
R7 I* I5 @# N# a
最短路。每两个相邻的点之间连边，如果目标点为障碍物，则边权为 1，否则为 0。用 dijkstra 算法求最短路即可。
1 k5 w Z7 L! s" N8 {3 q6 O) b8 c1 r! ~! d
代码展示( b7 `; R# k! H
|
