上岸算法LeetCode Weekly Contest 295解题报告

上岸算法 · 发表于 2022-5-30 17:23:18

【 NO.1 重排字符形成目标字符串】
6 _8 i7 {; e6 y. }1 K  q( @5 o
. R  {" a; i0 m% X- c2 U解题思路

统计每种字符的数量，原字符串和目标字符串的对应字符数量之比的最小值即答案。

代码展示

【 NO.2 价格减免】
3 Q1 T; `% B6 r# A0 N' J; Z
" Z3 J# r) i$ V: K4 Y解题思路

按照题意要求解析字符串、计算即可。注意一个 corner case: 单一个 $ 也是单词。

代码展示

【 NO.3 使数组按非递减顺序排列】/ t& Z; w4 G0 y: [

) d8 h4 w1 N1 N解题思路
& w/ ]  O* O% z6 p: k
动态规划 + 单调栈。

设 dp 表示将 i 移除需要操作多少次，若 i 最终不会被移除则 dp = inf。
0 |% E2 X" c+ ~: p8 s6 X) ?9 m7 Z9 @
维护一个单调递减的栈，当前元素入栈时，会有一些元素 (假设为 X) 被它弹出。
! b3 j. d* W3 W
) h! r! p9 J0 Z  J若当前元素入栈前所有元素都会被弹出，说明这个元素就是最大的，不会被删除。否则，它最终将会被当时的栈顶删除，而具体会在第几次被删除，取决于 X 需要经过多少轮才被删除，取 max{dp[x]}。0 S: n' `. d/ V$ |
/ [* o1 r, N1 q  q# P& M8 ?
代码展示* F  s* z1 Z0 j' s+ A8 o4 q1 v

" ?' O- L* i- S" _- z) Q) t! s$ g( l: W6 T, A2 ?9 r
+ N# j# h3 e# u  ^7 b2 P# b
【 NO.4 到达角落需要移除障碍物的最小数目】, q+ \6 q; a" r5 b+ ]; O; ~
2 ^$ n" }. C. ^
解题思路
: O. V1 M0 a) o6 k2 w$ o+ K8 H& ^* B  q. z
最短路。每两个相邻的点之间连边，如果目标点为障碍物，则边权为 1，否则为 0。用 dijkstra 算法求最短路即可。" @, S+ U' b4 I) |' b+ a" O
& E$ Q* R2 R( S2 K0 W
代码展示
$ o5 {+ W, ?+ k- b+ I9 h

帐号		自动登录	找回密码
密码			注册账号

[吹水聊天] 上岸算法LeetCode Weekly Contest 295解题报告

本帖子中包含更多资源