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

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

上岸算法 回复:0 | 查看:116 | 发表于 2022-5-9 19:43:39 |阅读模式 |复制链接

UWCSSA提醒您:

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

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

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

【 NO.1 字符串中最大的 3 位相同数字】
  X, W! s" q5 U$ k3 N0 c' p& v& n, C
解题思路% }" @3 d1 d; p  a

( n# D2 o- D( G枚举即可。
: P6 X& z+ @1 f6 d) l) b( a# l
. A" {2 k7 H. S6 X7 q! P1 U# C7 @! R代码展示& g: }& P9 j5 W4 U9 ?% ~

* K) f5 {7 }% W$ s( N$ }# _6 L& `2 T* P4 C
【 NO.2 统计值等于子树平均值的节点数】
, d  i; j& Z5 c, P" ~
7 u0 d' w6 r1 c解题思路) a* C( d; \( v3 d4 F! X8 l
2 z" H$ @, M5 K
一次递归遍历即可。+ S/ x/ b7 b7 c+ x3 h7 l8 r
0 I3 a2 j+ u8 m$ T, \; t9 A  ^
代码展示
* g4 ?( s9 l0 x% ]3 T, v0 Y( v& W0 L* H, u& {7 L+ q2 ]
* ^: Z  x; s$ P
【 NO.3 统计打字方案数】6 B% x2 q1 K+ B3 _, y- Y
& o& U( Q& P, [. V
解题思路: z; n0 s' x# `) H

% q2 e* N1 ~  i# ?) |  @1 E我们需要关心的是每一种按键连续按下了多少次。7 i2 G2 g: v( F8 W+ E

2 @3 [( K/ X  R* ~: K比如 “232323345” 这一输入,每种按键没有被连续按下过,所以代表的可能性只有 1 种。! s0 X% S* z/ n) L- o
  i5 `# l/ ~, q6 N: K9 ~. j
按键 2 被连续按下 2 次则有 2 种可能,被连续按下 3 次则有 4 种可能。
" Y" E- D( ?# |  p3 f- E# F
- l3 }  T; P; c# [" N. v/ j3 f2 t我们使用动态规划求出连续按 x 次有多少种可能,详见注释。
5 f+ M5 U& x' ~3 X5 `* u* a' ^, Z! v/ ]. X
代码展示5 F) L* z! m4 m3 O" U( {

9 E/ f( ]( ^7 @  C. z
& Q1 G* ?$ w, h, y& F【 NO.4 检查是否有合法括号字符串路径】" ^# u7 j5 g' k' |9 I

. ^* c7 k: J7 i5 F- R' J' X/ s解题思路
4 ]1 F8 ?5 m( z: y) ]* j6 E' B+ c6 @/ e% t
记忆化搜索即可。详见注释。
4 Y7 ~2 e" {  _* |* |
7 {% D9 P/ b. q8 O代码展示
& y" x( M8 I* _# L% @' w& Z. G8 U
3 A+ B: F: `: A3 r8 O( o

本帖子中包含更多资源

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

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

本版积分规则

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