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

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

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

UWCSSA提醒您:

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

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

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

【 NO.1 重排字符形成目标字符串】# j4 w' t0 M  A, W2 e

4 b* Q" _9 Q4 E* y解题思路

. F) Q: U, v6 e* L$ \& O5 P. [
# h+ k* u! ?" _# n, ^+ K统计每种字符的数量,原字符串和目标字符串的对应字符数量之比的最小值即答案。' m% P+ h# C4 o4 w1 N  G
/ y) m+ d) @* P9 p6 T7 q
代码展示" a6 e1 m9 q: E6 ~/ \1 L, [

5 y: Q* X9 {/ Q; P+ ]# |& X, b, F3 |- F( }& ]7 N3 B" X

; S) a( b% S% M1 k2 I+ P8 `【 NO.2 价格减免】
1 f; h0 ]+ i# b2 ~5 ~2 W2 h* x7 O# E2 K+ ]0 A
解题思路

1 x7 S) b. A2 o% F% f0 f
; q  G. P6 q9 ^1 S, Y+ k按照题意要求解析字符串、计算即可。注意一个 corner case: 单一个 $ 也是单词。
/ B# }5 g9 ?/ a2 N
7 A" {' `* ^0 U% H# C& o2 E代码展示
" Y) z; u) K: M& I& g; u
5 t& f) |+ b/ K- T! O3 C4 \7 [# q6 p1 V6 a# R1 |: j

7 r9 m/ x5 ]( t0 @【 NO.3 使数组按非递减顺序排列】/ S/ k* Y3 ~# g" ]2 o

- a4 I9 t9 X+ y! H" f* o% }解题思路5 i* W5 s* z5 G$ W: r. ~5 _
8 @- K7 V, O7 q3 c+ K. m
动态规划 + 单调栈。9 n) C5 h0 Y$ R) G

, H% U4 v9 c- d: z设 dp 表示将 i 移除需要操作多少次,若 i 最终不会被移除则 dp = inf。% Z! i' o; I$ a: ^
) A, \3 d* j8 a4 r; h
维护一个单调递减的栈,当前元素入栈时,会有一些元素 (假设为 X) 被它弹出。0 F, j/ |, \' h- P) z* {, H
! v* ?' Z. o2 @: h, e( W! i  k
若当前元素入栈前所有元素都会被弹出,说明这个元素就是最大的,不会被删除。否则,它最终将会被当时的栈顶删除,而具体会在第几次被删除,取决于 X 需要经过多少轮才被删除,取 max{dp[x]}。0 M2 U# R& ]# }" m6 R4 k
! p8 }2 B" G2 M, l4 o7 B& f9 R
代码展示
# p. C& {9 t' D" y
) ?3 M8 l9 i& g' Y& J1 C
$ n( Q; h; _) W1 {* ~/ E0 v9 c- b

& s& \0 D( y# L: W, R【 NO.4 到达角落需要移除障碍物的最小数目】- o) T. f) G- \  S: w$ l) F

* l5 o" P7 r! H0 |( ~解题思路% Q& }% M5 P9 s( i+ _+ {

2 Z& ?) B' s1 s: d" ~0 j) P/ e最短路。每两个相邻的点之间连边,如果目标点为障碍物,则边权为 1,否则为 0。用 dijkstra 算法求最短路即可。8 l8 w* b+ J: K; B0 l

# N, I5 q% q& g% Q7 M- B代码展示  _2 L8 n1 w0 i9 P

本帖子中包含更多资源

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

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

本版积分规则

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