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

[吹水聊天] LeetCode Weekly Contest 250解题报告

上岸算法 回复:0 | 查看:2203 | 发表于 2021-7-19 18:02:58 |阅读模式 |复制链接

UWCSSA提醒您:

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

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

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

登录后可回复主题

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

x
关注我们:杭州上岸算法网络科技有限公司! H" n; K0 r- c+ t& P- @$ U  F
【 NO.1 可以输入的最大单词数】5 I- P8 a6 H: o4 c- o( b
% S& X( Q: d( a, b5 u' P
解题思路9 b( z& d, y' j1 r, S
签到题,循环遍历判断即可。
; j2 l3 T# A( l+ o4 Z$ x
7 V/ J) g& n$ f  A代码展示8 _* h: Y5 M% m! d* n1 v" E1 M8 ~

/ ?, ~! G: Q+ `. z4 c  |' Gclass Solution {
! ^% z, q! C: c5 I    public int canBeTypedWords(String text, String brokenLetters) {2 B# i4 w2 `- A4 s" B
        if (text == null || text.length() == 0) {* c# Y3 H" c' }
             return 0;. h4 |; H' C3 e& ?
        }  L  n1 I6 r$ Z; x" A
        String[] texts = text.split(" ");1 s( ^$ Q7 y" g1 T, h' d
        Set<Character> set = new HashSet<>();2 |+ v, c. P5 V3 @: g0 ~) ~
        for (char c : brokenLetters.toCharArray()) {
6 _2 g0 k! c- h0 U& x. a            set.add(c);
+ G: V8 D! z# R6 J1 |& N" Q        }7 w) O! p# X9 n9 l& u/ p
        int ans = 0, flag = 0;
4 G4 l( V" Y9 l8 ?6 c( j        for (String word : texts) {$ ^3 |* o$ z$ V' y" M
            for (char c : word.toCharArray()) {, }' T3 p; T7 N, ?+ h  N0 r
                if (set.contains(c)) {1 M) k  D% e. m+ S1 m- S3 Q: z
                    flag = 1;) Z" q' g) r7 r0 V; R+ y
                    break;
9 b; p1 f$ {4 l3 h# _+ a3 t                }$ |0 p+ L; o" }
            }
; Y1 {0 l) N1 s, \( v            if (flag == 0) {
6 J: w6 E3 c8 t                ans++;- u, X5 v3 M6 I2 Q2 i) |
            }& X; i6 C! ~5 W8 ?. J) p
            flag = 0;/ J5 s9 j3 M" p- E) V! h
            
8 a( ~7 V4 e, j6 o  W' F        }0 ^6 W% c" ?: T" g& T: w
        return ans;- N) D  d$ X9 h* q2 S/ R4 W; k
    }3 |% \" |3 X) n4 k( ^; e, |$ U' Z
}0 Z# @" G# l$ {1 e- R
3 ?; R* R6 q0 V
【 NO.2 新增的最少台阶数】
  d6 _9 \& r3 x, h$ ~! A  m- }8 }
9 A% [; o6 Q* ]) }- B" C, @2 {解题思路
9 K& F$ n2 o7 ]& G6 _第二道签到题,两两计算差值,需要判断一下是否可以整除。# u5 @6 Z5 }3 d
. x  F& G8 c1 h
代码展示9 Y) L* c7 K' v5 y

7 f6 z& y+ O% hclass Solution {9 X: q6 @( A% n9 j& F6 c  F2 K9 |$ b
    public int addRungs(int[] rungs, int dist) {! Y& r0 O5 u" t5 z# }; p# Q
        if (rungs == null || rungs.length == 0) {, E0 @" C+ r7 M" N
            return 0;" y7 l, Q. B0 S) s
        }; A4 J+ a0 M" N  V' W1 s' d
        int ans = 0;. u8 s5 Q2 B1 X. @* x! ?
        int preRun = 0;7 U- S4 m$ n2 N- J
        for (int rung : rungs) {* p. P6 y" C2 W! w6 A
            int diff = rung - preRun;
* d+ ?% h' K! z  K) l) C' ~  Z% c            // 整除的情况可梯子少一个" v9 ?. F6 r, T' S' T% `
            if (diff % dist == 0) {9 Q! a8 k9 L/ B: F
                ans += diff / dist - 1;
* W% ^4 X. O# D& r- q, d            }
$ F. Z6 x+ B  \) m5 R, |            else {3 |" z6 R0 L9 ~# d" ^
                ans += diff / dist;
+ q& \% ]1 y0 p1 j0 h9 h( Z% N& f            }
8 p2 _# e, H) M  B: q" B            preRun = rung;
7 o5 {- ?$ N) O$ N: C. n        }( j6 k9 f0 L$ H" a( {3 ?7 o
        return ans;
) o+ \! n/ h3 P% k; n    }
2 g8 ~3 e% D1 q3 j}: Z& x! o0 @  `! y
! j6 U# m( w3 F0 ~" Y2 }
6 G" [" Q8 K, ^  {, j# u. T1 O+ }
【 NO.3 扣分后的最大得分】
1 \( t# _! P% R/ S$ W
9 _9 e7 r. o! }8 L+ N. J解题思路( L- x" w  [% |) A/ {
坐标型动态规划
+ p6 O7 g& s6 n$ H
! @  |" M; Q2 odp[i][j]表示处于坐标 i j 的位置的最大收益5 f' ]5 v$ L/ {) t6 w1 |

1 }6 ?2 ], p9 y7 F; a2 f普通的坐标转化会超时- T) v. g- J" x1 P

2 P0 M5 ~: _2 {+ N3 S3 Q2 X3 z考虑针对每一个j,会从 j的左侧和右侧转移过来,我们只想要一个收益最大的
: R' G% @* E/ u' M) ~7 U. y* s& p( u: _5 k' F" l
因此在遍历 j 的时候记录这个左侧和右侧最大的收益,给下一层用
) |0 I8 v3 ]7 w  C, k6 p+ T' }9 K) j- ]% |: P
还有优化的空间,i 可以压缩成两行
, G; [8 ?5 n4 X% U- e5 ~
/ ^/ d' I* v8 t( k4 T代码展示
# v: h! O3 O# K8 u$ B0 C3 C. X+ O8 I0 ^4 c
class Solution {
& X+ |/ d( r4 i/ l8 h; }- m1 A    public long maxPoints(int[][] points) {
! M2 G. v; R9 ^4 P: |        if (points == null || points.length == 0 || points[0].length == 0) {2 `! m& N- O' F
            return 0;
. T, {( V7 S2 ?9 p1 J$ c        }
  U% @/ Q; v% X( p- j# s2 x2 ~        int n = points.length;
8 ~. b$ K6 \. s6 w0 B        int m = points[0].length;/ G$ ^* Z9 J+ u- p3 D
        long[][] dp = new long[n][m];. T* T5 M5 T2 `6 A2 B( K  i! ?
        // 首行初始化3 e6 v; ?% x# c
        for (int j = 0; j < m; j++) {
4 p( R: E3 K0 \% `! }! [. v            dp[0][j] = points[0][j];& B( p7 c3 I+ B5 G' A1 ?
        }7 _2 A- \* f: N5 @' w" k
        for (int i = 1; i < n; i++) {  J- I+ c; B. v; a
            // 对于所有上一行左边的数,都是加上它的坐标减去自己的坐标;
6 o" D+ Q, e( {9 o            // 对于上一行所有右边的数,都是减去它的坐标加上自己的坐标;
" C" {' P# G8 W2 i$ G/ g1 t            long leftMax = Integer.MIN_VALUE;
, h: P/ \2 ]4 A' _0 @" D            long rightMax = Integer.MIN_VALUE;) a0 e' c, ]+ ?5 b' `* @
            for (int j = 0; j < m; j++) {& v( D, Q' y6 L. B6 G! q
                leftMax = Math.max(leftMax, dp[i - 1][j] + j);
/ |2 Y' H  |, N3 i% U                rightMax = Math.max(rightMax, dp[i - 1][m - 1 - j] - (m - 1 - j));2 V' o% g/ r: ]8 q; s# D
                dp[i][j] = Math.max(dp[i][j], points[i][j] + leftMax - j);- e' L8 J9 r; d/ z1 S* q
                dp[i][m - 1 - j] = Math.max(dp[i][m - 1 - j], points[i][m - 1 - j] + rightMax + m - 1 - j);
+ j8 `8 t  e1 G% o. ?5 y            }
1 U, r( {) V7 x- f2 t; q  \& u9 S2 Q" S        }3 {" l# K6 S! D0 Z0 T  w
        long ans = 0;
0 v' p4 w- q4 u8 S        for (int j = 0; j < m; j++) {
' H. u* ^! ^# M2 b" y            ans = Math.max(ans, dp[n - 1][j]);
0 J1 L& J( ^# Q' N1 ^/ w( e$ u' {        }
" Q# K" N" x' [- \& ~4 C. s        return ans;- n# P# j1 X$ |8 t) G6 ?
    }
) g+ ~% _/ n) e+ K% o}
. z! h" l# u# |, v+ Q, j9 o
8 ]( C( t0 ?2 B, S0 O- L+ c" R2 z0 l- @- C& v
【 NO.4 查询最大基因差】
- x- X) i& L. e& B' M+ x4 H* K0 ]5 n4 O; o9 H0 R0 w
解题思路
$ j4 h) x* H/ `3 l/ n) R二进制的字典树:将数字转化成二进制记录在字典树当中
/ ?- b$ N% V+ F4 J& L- g6 E* B2 M7 x$ x" j: g* E
构建树,方便做DFS
2 i# w7 S5 |9 S9 D& c
9 {* X' b& A5 z+ a每搜索一个数字,将该数字更新到字典树当中
0 H  i1 d5 ~/ _. c
5 r9 X/ }$ y- z$ l( i在字典树上计算最终最大的异或值1 e' K0 B7 t5 k& e5 D
! n, [. P2 U9 G1 v. m5 p
代码展示
5 n' d% ~; l  V$ p9 l, ^  v8 J, W: T3 R( d1 e; g" a
class Trie {! ~. E- f: Y7 j/ ?; p
    Trie left;      // 1
! d+ I8 z& J! ]. O( C" i; c    Trie right;     // 0# X3 ^2 C2 e5 @4 @2 F8 _( K* g$ I
    int[] count = new int[2];
6 C; v; y. b& K1 G) F% ^7 Q$ m7 l* @    public Trie() {}
1 _& A- S! z' d2 [/ B+ h7 d1 C! I$ c( r
    // s == 1 添加, s == -1 删除
, O9 h3 Y; P0 p    public void insert(int val, int s) {
( J: X6 Z( \* O        int flag = (1 << 30);) D# L9 _. [+ L6 r& A
        Trie node = this;
% |1 m1 o2 e3 C" Q0 Z$ F; f        while (flag > 0) {
& ]: c7 N% E; s/ X% K1 I: @& b            int bit = (flag & val);2 w  F# M. g+ ^5 G
            if (bit > 0) {
$ p) U1 r9 J' h                // 1 走左边
5 w+ t+ q9 F" g( |& w' J                if (node.left == null) {+ A5 W6 S0 @: L8 R  i
                    node.left = new Trie();( V' @6 {7 t3 W& U( L
                }  \9 o7 e- o8 ?; [3 [- O9 T
                node.count[1] += s;
! I# \1 e0 E3 k9 x                node = node.left;  e, q8 j0 t* j- }) i
            } else {6 E. a3 M% v; {5 e
                // 0 走右边
+ [; @$ ^2 \" W( K                if (node.right == null) {
+ g/ ?2 H, j$ [5 C/ i; P' H+ A- A) P                    node.right = new Trie();: H0 _# {1 S8 C
                }( R: L5 q' A2 u
                node.count[0] += s;, m. \5 M9 v& |! }, x9 b# z
                node = node.right;  r7 V  X# @* K: d
            }- {' q& G4 C. S& B( b
            flag >>>= 1;5 s9 _6 b% o' ~
        }6 o' u; Y5 ~( Q* l6 t
    }
1 W0 b& c4 }, e2 Z* u& ^, h; [7 Z  u
    public int getMax(int val) {& M, B" a8 R. A  r6 s4 ^9 `7 n
        Trie node = this;/ q" u, q" [7 u. N
        int flag = (1 << 30);
. }/ ^4 V) {: a% H8 n        int res = 0;( |- S2 q/ [# ]" N6 P$ H4 S/ K  L
        while (flag > 0) {
' r1 Z5 P4 H6 ~$ ]7 `            int bit = (flag & val);
. m/ L( Q; S0 {) k            // 贪心算法,1 的话走右边,0 的话走左边
8 Y3 D: a+ I" q: S/ B% {            if (bit > 0) {4 X6 Z' w; l5 W5 F
                // 走右边,右边不行走左边
& a4 M% h" h3 l5 R7 _; d' K4 |                if (node.right != null && node.count[0] > 0 ) {* A, n1 d' Y- X( a7 o
                    node = node.right;
2 {( V: x1 k2 ^! _- T2 \                    res |= flag;9 b* i' o% d8 K8 a1 _" `
                } else if (node.left != null && node.count[1] > 0) {/ u) p6 t$ X, Q! a. W
                    node = node.left;/ k4 n, a1 J( ?8 h1 e+ h" c
                } else {: O& _, o4 x* K( ?
                    return -1;
2 _; S  G# z, V# Q                }4 }2 R- s. u* @5 ?" v: a
            } else {" [4 d: V) K/ e: I9 L' ^
                // 优先走左边
$ F+ b$ x/ e3 d  s8 d                if (node.left != null && node.count[1] > 0) {
8 A+ V# s/ A. v# K% F                    node = node.left;( {" y# b( v, S( {
                    res |= flag;- H5 U. H5 B& G( i0 n
                } else if (node.right != null && node.count[0] > 0) {
% @! J6 _# y, h0 a# C6 F. {5 |                    node = node.right;3 w7 f1 b( |  ?* @& X
                } else {$ U, ~4 {4 X0 _$ Q- j7 E
                    return -1;
3 @" F$ D+ N9 m/ z5 E                }
# T0 E. L- u2 ]            }
/ I1 O: B# Z+ {3 u  o            flag >>>= 1;
6 {( T; ^. i/ }0 ]. s! B1 A        }' w- t7 e- e, u4 ?1 ?
        return res;
* D& h4 p  N1 ^* H% S6 ~( ?    }! r8 y0 F& _8 G. u- X% ?
}0 i: {' W: P5 }5 m* }4 R4 P2 w
public class Solution2 {2 z* @6 \2 Y! [5 _3 R$ L& [- q
    static class TreeNode {% ~7 q+ W0 {) [5 E* W
        List<TreeNode> son = new ArrayList<>();' g( |' f$ P- C! D# N  [$ W3 B+ M
        int val;
' r# L1 M  w9 v' z+ Z* W        public TreeNode(int val) {: e2 l( V8 l' q5 |, w& J; D  {- T+ h
            this.val = val;/ s2 m# F4 X: j5 ^& M  B
        }
1 j1 X8 [% \2 G) A4 t    }
6 a9 I' ~# ~3 f# \    Map<Integer, List<int[]>> map = new HashMap<>();
2 v( t9 }+ O0 P( k/ S    Trie trie;
( u. L- d- d9 _8 ~) ?! O    public int[] maxGeneticDifference(int[] parents, int[][] queries) {
0 V, g& E: J( b7 a        int n = parents.length, m = queries.length;9 K* X6 s7 ?$ ^$ A6 y1 u$ G
        // 封装查询的信息: ^: B9 h( H* w$ c# r) l
        for (int i = 0; i < m; i++) {' b# g: G% K; w% y/ I: y2 N
            int node = queries[i][0], val = queries[i][1];
( W( w! C6 b- g6 ^3 ?% A            if (!map.containsKey(node)) {
1 E- V1 n; q- ?! Z: k( A& D5 P$ k                map.put(node, new ArrayList<>());' ?7 ~/ \8 u1 `' y! F; {
            }
5 N. n5 t6 ?' b( r+ I0 J4 b0 A            map.get(node).add(new int[]{val, i});
3 ~: q2 y6 ~6 M7 E5 p" \, \, l7 _. c( o        }
8 ?8 U! e6 i3 k* c: j        Map<Integer, TreeNode> nodeMap = new HashMap<>();
" E! j2 Y+ U3 y8 ^( U1 }        // 构建树
% ^$ c* M, Q& a7 E! Z1 a9 a        TreeNode root = null;
% w# J$ I" ]* m1 C        for (int i = 0; i < parents.length; i++) {8 Q0 B! i0 L9 k  A
            int p = parents[i];4 U( t& E* g  U" x5 F+ O
            if (!nodeMap.containsKey(i)) {
# D+ w# x" g* `+ [                nodeMap.put(i, new TreeNode(i));5 _. s9 F# m7 j/ ?3 N4 l# _
            }8 t7 W( [0 |5 m' G
            if (p != -1) {- b7 A" e- T3 L% X, z4 C5 ~8 V
                if (!nodeMap.containsKey(p)) {' Q+ g2 s8 |- f6 E7 M7 K
                    nodeMap.put(p, new TreeNode(p));
9 Y2 o2 q# [# f- l( U                }
5 s- |  U+ M9 ?' P1 r                nodeMap.get(p).son.add(nodeMap.get(i));
4 F/ d4 W# w5 M            } else {4 A  G) Z  f. _1 o: M+ j
                root = nodeMap.get(i);5 [: F* `$ ]5 U) Y7 ^/ N
            }
3 {5 C; M+ {& B8 Z5 |1 j* K        }
( ?. V! f8 t! l1 h        trie = new Trie();! g4 x# L1 @: h/ Y: E
        int[] res = new int[m];
6 K1 M# V) ^8 O% j        // 在树上进行DFS- I0 Z8 _% G, n! \$ ?  L* I- y8 p
        dfs(root, res, map, trie);
! O& z/ p& ]- E: W        return res;) q8 T$ i7 d4 k1 p: p6 A

3 L4 d2 o0 T" g    }# X" b% i4 k4 |5 `. d( ~; Z
+ r4 x( w# X* M
    private void dfs(TreeNode root, int[] res, Map<Integer, List<int[]>> map, Trie t) {" [9 ?6 L( E! n5 V8 u
        if (root == null) {; M- ?5 _1 U5 ~! p8 _
            return;
9 n& b; Q" `- I& v3 x6 C        }$ m& F# r# U" s' R0 P$ I
        t.insert(root.val, 1);: l7 v) g$ t' S% w6 X
        if (map.containsKey(root.val)) {
) P+ Q+ W2 R1 O. c7 h3 C6 g            for (int[] each : map.get(root.val)) {
" [& ~2 e$ ^: B# |, k& p  v2 D                int idx = each[1], v = each[0];
% x* n% Z8 p# k7 X, Q2 e' f# T8 t                res[idx] = t.getMax(v);
) j! |4 Z) L/ `2 q4 z" E5 _" N            }
( q  P" t6 g3 a9 f        }
+ @# ?& _0 h# ]  L, B        for (TreeNode s : root.son) {
; `7 @5 s$ q4 [& f/ U& e7 n3 w% |- [            dfs(s, res, map, t);
9 V( ^/ G; f# Z1 Z! f6 n, p2 |& ~3 Y; I        }
" `4 R- e! V6 l8 U' O+ p  f  F        // delete
1 M5 b$ O* O/ |+ b+ ^1 k9 X" n        t.insert(root.val, -1);! ?* S, i7 \/ D
    }1 E. h  q" j5 I7 P6 m' _7 C1 }
}
, _! l% G2 s' i' |) X
3 Y" o- M$ X( ]) v& V
- j. b+ i4 ^# r) J+ f. u, D
您需要登录后才可以回帖 登录 | 注册账号

本版积分规则

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