找回密码
 注册账号
置顶:如何加入2024届新生微信群

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

上岸算法 回复:0 | 查看:2018 | 发表于 2022-5-30 17:23:18 |阅读模式 |复制链接

UWCSSA提醒您:

警惕网络诈骗与盗号,不要在他人发送的网站中输入密码,换汇或付款时请小心诈骗。

为了避免个人信息泄漏,建议在帖子中使用不常用的邮箱,或使用私信发送联系方式(点击对方的头像,然后“发送消息”)。

帖子通过审核只代表内容不违规,CSSA 不会验证内容的真实性。请谨防诈骗。

【 NO.1 重排字符形成目标字符串】
& I4 w( N. L) X
% V5 Q% c) d$ h0 X3 A0 [$ F解题思路

0 C9 w* y" x+ Q. h- b$ |3 ^
9 h7 o8 {8 [! a+ i- g( w4 `  N统计每种字符的数量,原字符串和目标字符串的对应字符数量之比的最小值即答案。
. b4 m! V6 f, X, t1 o3 M6 A; s% U
代码展示
- a1 _, K' [# h) o  W2 X; ]" P' u1 k# q

% E5 _8 w( d6 [* D1 d4 j9 D3 f
8 v( y" B9 F" I: `2 C' M【 NO.2 价格减免】
- ?2 q; q  B- \% s/ ?9 h* _  Q! a/ V0 k" j
解题思路

* m% Q7 A9 r' x3 h+ }
  b3 w3 U, \; T2 r; G按照题意要求解析字符串、计算即可。注意一个 corner case: 单一个 $ 也是单词。
0 s1 |, ?, x# J4 @) U. {! B- m# Z" T$ [& @! [
代码展示) N3 c, W/ r. q* Z1 F
! g5 D& V  G" O4 R+ l6 r

2 m# }+ r0 w0 \% G) @* w8 {7 J$ Q8 }* Z; C
【 NO.3 使数组按非递减顺序排列】$ f# M: n2 F8 k4 w; @
3 X2 w+ V4 L- P
解题思路6 Q6 }1 K% W, Z. E. y1 S
' z/ v8 x( C8 d! O
动态规划 + 单调栈。
6 P0 {' ^/ j. ?+ ?! K3 e! q- k1 H' v1 f6 n4 \
设 dp 表示将 i 移除需要操作多少次,若 i 最终不会被移除则 dp = inf。" i& D8 v( `/ G; V9 S) J2 ^

3 J, i) K- [6 ?* i, r维护一个单调递减的栈,当前元素入栈时,会有一些元素 (假设为 X) 被它弹出。: P" h# f& f$ L  v$ ]  O
. V. I5 o! {9 G9 W9 B& t6 L8 v* Z
若当前元素入栈前所有元素都会被弹出,说明这个元素就是最大的,不会被删除。否则,它最终将会被当时的栈顶删除,而具体会在第几次被删除,取决于 X 需要经过多少轮才被删除,取 max{dp[x]}。
7 m3 H/ b8 i0 @
5 W6 l5 ^. k" ~+ e- f0 ]代码展示
8 S: }$ ]- C2 C

, _) t3 {! D1 y8 k2 _8 D: g5 r
2 B) ?# C0 A! @0 k% J* w  Q; x
3 O$ l) Q. W, F+ k1 t【 NO.4 到达角落需要移除障碍物的最小数目】) [/ v3 e' b- n: [
4 q; ~, F3 s7 `, f4 N
解题思路9 |, G5 h& R* c

3 @) K9 j7 m9 O4 F7 U" |4 p最短路。每两个相邻的点之间连边,如果目标点为障碍物,则边权为 1,否则为 0。用 dijkstra 算法求最短路即可。
9 b& G$ c& V4 u8 E/ p5 v$ W. h
# p; o  W# ^  A0 ^- A5 z1 ]代码展示0 C+ E2 l& [4 T/ ^

本帖子中包含更多资源

您需要 登录 才可以下载或查看,没有帐号?注册账号

x
您需要登录后才可以回帖 登录 | 注册账号

本版积分规则

登录 发布 快速回复 返回顶部 返回列表