【 NO.1 重排字符形成目标字符串】
& M. F; ~5 L$ Q7 b+ s9 q% [
2 a& k. {" {% \解题思路( F7 }- E1 b' _. Q
6 _3 t! d4 K& h1 A) |! w统计每种字符的数量，原字符串和目标字符串的对应字符数量之比的最小值即答案。
0 _9 ^7 E; Y7 e# }* e6 Y! {4 Z; Y6 d7 j0 u& e- H2 Q' a' J; F
代码展示
* e3 q* P( t! _+ s, Y2 b5 J
. ]9 f& i) g7 x" d0 a& v- s. ]" p4 h8 ]+ e* d' p6 s- M
' e8 G% b! V6 m( g【 NO.2 价格减免】2 ~# m3 c! t5 p: I; U. F% _+ W8 u4 `
8 y8 [0 Y& U1 a2 A0 h# ? j解题思路0 L5 v0 m$ |; h. i9 q
5 a' r' D' }' F: s按照题意要求解析字符串、计算即可。注意一个 corner case: 单一个 $ 也是单词。
* [: u! Z( Y4 n
h- u' Q, N' N" P& Q+ E# w1 ?7 @. |代码展示3 \* z& h- p; Q) r
- t* J/ E! z9 I+ s9 y' A) \: x, Y
# P( F l6 X5 X6 w3 {
7 d. V0 w" C/ _/ J【 NO.3 使数组按非递减顺序排列】
4 j0 u/ o- X# f& _2 {% _: u/ d" O% k$ _( M1 X Y0 [
解题思路
6 O! s# u1 l' Q. L, `" ], r6 [: f- [* z: U) [
动态规划 + 单调栈。 w8 K' \5 D6 }& r- M1 Z
7 |3 ?" z* v# n$ A- w
设 dp 表示将 i 移除需要操作多少次，若 i 最终不会被移除则 dp = inf。+ d$ y3 t1 T# j" r, i3 M
" Y8 t+ _* H8 E! I, R$ @5 l. }* F维护一个单调递减的栈，当前元素入栈时，会有一些元素 (假设为 X) 被它弹出。
/ \+ j& \9 D9 A7 l1 ?4 ]; \( i. W& t. O/ @0 I0 h7 N8 Z3 r
若当前元素入栈前所有元素都会被弹出，说明这个元素就是最大的，不会被删除。否则，它最终将会被当时的栈顶删除，而具体会在第几次被删除，取决于 X 需要经过多少轮才被删除，取 max{dp[x]}。7 @* C! D7 r H9 X
R- Z( y- _8 u. P/ ]5 s代码展示0 P( w* B3 n0 [3 z
- l1 s7 P( r% k* b( r# `
+ z( T! a5 Y1 L9 y! Q( m! g4 E+ ?; L/ F5 J* B' _6 ?6 f
【 NO.4 到达角落需要移除障碍物的最小数目】
B+ ^1 ]# Q4 C1 M, C! o. e0 l ]5 M4 ^. J1 I& T% U/ n
解题思路
3 n/ \; R. n% P! @- |9 p x; x$ t
' P/ Q, A* c" {, |+ J" h最短路。每两个相邻的点之间连边，如果目标点为障碍物，则边权为 1，否则为 0。用 dijkstra 算法求最短路即可。
7 F8 u2 v' ~: |) `* d' s4 S+ r& H9 A; z1 ~0 s: u0 d! A
代码展示# \% f/ }/ t7 c ]# X5 h
|
