找回密码
 注册账号
img_loading
智能检测中
置顶:如何加入2024届新生微信群

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

上岸算法 回复:0 | 查看:1474 | 发表于 2022-5-23 20:41:34 |阅读模式 |复制链接

UWCSSA提醒您:

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

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

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

【 NO.1 字母在字符串中的百分比】$ G& G/ r) e+ ^* M! H# `0 m
! [( H! h* g5 ]2 r; R( _
解题思路

7 S. ^, l* U% g0 u8 \7 u- W& ~1 t2 p
签到题,循环统计即可。+ i, k/ ^1 a$ W1 t+ K
! T; H, G$ U  I" h; A6 K5 Z- M# i
代码展示* q# l: _; U# l/ n  t5 a
5 e. X# h  O0 _. P

" J" a2 Y! _1 o* E' f1 r( n/ O/ R【 NO.2 装满石头的背包的最大数量】
& T$ C/ x8 _$ X: {- I/ Q5 W  P# z! K* @" s1 |) L
解题思路

" `. G8 O4 \/ {/ L% ^* ~8 ]* k/ J  ]3 e3 P- P% b
贪心,先装容易装满的。
3 Z7 p; Z$ P* J. a
& N1 ?) z5 y+ Q% E2 ]代码展示8 P; c1 U% |3 T1 r/ T. }2 B' g

5 k1 A0 l7 I$ A; A# X3 b' @$ o$ z3 \
【 NO.3 表示一个折线图的最少线段数】0 V1 d0 i; V( T( m2 @( q

7 C4 s, }1 N4 P8 t解题思路
0 i# d/ c# m* X  \0 l8 W1 ]
' p1 \' W% w  J
横坐标之差除以纵坐标之差即斜率,相邻两对点之间如果斜率相同,那么就可以用一条折线表示。
; e6 T8 D* k( Z; B8 q5 B
4 \, I0 q7 p, V/ F) k/ V# p( F# ~代码展示- Y+ |; P3 b% k1 l# o+ a0 q/ U
$ x. b- C5 s, P. T3 ]

8 ?6 D. S( A6 R) p【 NO.4 巫师的总力量和】
, F6 I- X5 x, \1 k/ F9 [3 X. p/ K# Y0 ?6 H
解题思路

1 e/ Z" m& u: K- }, M, L* ~; c- m# \, ?8 i  Q/ b' O
前缀和 + TreeSet. 依次求出每个巫师作为最弱巫师时贡献的乘积。) R# I' Z+ C5 P. h" |

% ]6 ^+ J  R, b当一个巫师作为最弱巫师时,他能贡献的乘积就是左右两侧比他更弱的巫师之间的这段数组的所有包含他自己的子数组。
; [! h7 z! I2 \  p9 s4 P" X+ B& n  U6 r% p: n. P7 @; }2 o7 a
可以利用 TreeSet 快速找到一个巫师左右两侧距离他最近的比他弱的巫师;然后利用前缀和求出所有这些子数组的和。0 g8 K* G6 H" w8 C" J# n1 d: y
( M0 d% P( h, _; _: E# q7 v
代码展示6 q* L+ S" C; b& q$ V( r& t

, q; U* q% Y/ H4 m; Q% [* y" i3 G* z' N0 m

本帖子中包含更多资源

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

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

本版积分规则

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