【 NO.1 重排字符形成目标字符串】 H$ H6 V4 `# g& d. S
" @: b- \% r' w% P; i: K: z3 w
解题思路# Y( z# j3 x4 U( g. j- y' a+ Q
3 l2 ?3 ~, N5 t" v8 M
统计每种字符的数量，原字符串和目标字符串的对应字符数量之比的最小值即答案。
/ }9 z- y1 S1 [+ x3 g( \: ~8 T+ m! C! H# T) P0 j3 {
代码展示
9 t2 X# m0 A, ~- r# l- o' E2 I7 u+ J0 D7 G1 |! v3 y% k
8 [; b3 q) `& `9 O/ V8 n) S
9 z* b0 y! ]5 U【 NO.2 价格减免】
7 |( K- J0 W' {2 s# O( Q9 E
) r2 C6 E5 T0 D0 j2 v解题思路" O' z* v7 J- H% G/ k X$ x
' [ |$ q" Z" s0 X7 |
按照题意要求解析字符串、计算即可。注意一个 corner case: 单一个 $ 也是单词。
9 b( T$ d4 V N/ u0 Y+ d W8 E; o( V1 r: y# m1 o: W# T) Q
代码展示4 s* {% P- t; H0 }& V4 h
5 F3 V/ Q4 c' Z/ Q# T% Y
4 Z. ~1 f& B4 n* p3 z
$ n/ G# a$ E8 `# ?4 N! u6 c+ b' o8 h【 NO.3 使数组按非递减顺序排列】
! G/ k7 Z& C- l) P/ I+ ]1 \- g9 G% c9 ~- A! M
解题思路( ^ u+ X6 `% X0 ]- N5 h' N
2 Z* y0 Q" _4 Q
动态规划 + 单调栈。
9 N: {, D' D& A% G) _4 v
( T N. M, F0 f4 s Z设 dp 表示将 i 移除需要操作多少次，若 i 最终不会被移除则 dp = inf。
7 T) \8 G2 G$ q" s9 Q W0 q3 T7 f( l
9 i, N8 ~. ~, @' F9 a# E9 S维护一个单调递减的栈，当前元素入栈时，会有一些元素 (假设为 X) 被它弹出。
; \. Y/ V) F4 |- Z7 A
Z/ `9 v' m# q( ?% g若当前元素入栈前所有元素都会被弹出，说明这个元素就是最大的，不会被删除。否则，它最终将会被当时的栈顶删除，而具体会在第几次被删除，取决于 X 需要经过多少轮才被删除，取 max{dp[x]}。5 Z3 l2 m" `* i# K- @" p! [
, ?0 f* }8 L3 [: d9 s代码展示8 }% f. o3 Z& \
! P3 w! G2 ^8 X5 L, E
+ o& q* t5 h# g- i( ]! @9 w) w% A% u- [
【 NO.4 到达角落需要移除障碍物的最小数目】: N8 D6 c: L- U) N& C: \9 N
0 ?6 L( w2 [" q# E2 e' N解题思路; Q: r3 a! C, l" Y
! S H* p8 Q. W6 {. d最短路。每两个相邻的点之间连边，如果目标点为障碍物，则边权为 1，否则为 0。用 dijkstra 算法求最短路即可。! w2 h, k1 Y0 ]
) [9 I: a0 X* o. x% h代码展示
* M0 T* u( u. I9 \1 w/ n$ Z |
