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

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

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

UWCSSA提醒您:

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

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

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

登录后可回复主题

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

x
关注我们:杭州上岸算法网络科技有限公司
1 u# T2 W" ]3 ]4 N( H; P【 NO.1 可以输入的最大单词数】
' a4 p0 @( ~4 h" t* z+ d5 g3 f
5 x9 _6 |/ A7 ^/ r+ Q* i# `解题思路5 c" u; f6 X7 w$ k9 @
签到题,循环遍历判断即可。
/ k+ q& x+ _6 A9 u5 I
! u; u$ A/ @( r0 E  W代码展示4 ~& u( G* b; a- I8 o9 h9 r) W8 @

7 S! g& p6 [! t2 P7 U" q# [class Solution {4 V% v! V) ?2 \& O8 v! J1 i
    public int canBeTypedWords(String text, String brokenLetters) {
8 @1 m0 r3 |5 Y' z) w* m        if (text == null || text.length() == 0) {' v8 g" {- F$ n8 K
             return 0;  e: B( R8 w1 z3 {
        }
6 r5 D) {0 }  x- H/ ]        String[] texts = text.split(" ");  M3 B4 [3 o" l) j, Y" B1 y
        Set<Character> set = new HashSet<>();2 B4 p( k" u* E4 d" E7 w! n& E7 J6 w+ s
        for (char c : brokenLetters.toCharArray()) {
# V! @& _7 l7 ]6 i) t            set.add(c);
3 V* S' g5 Y/ E7 h( \$ r0 k# O        }' I5 W! U+ U. N  k
        int ans = 0, flag = 0;' t6 R* d& j8 n; _, E
        for (String word : texts) {9 a' g! ?# ~/ ?% W7 c, U
            for (char c : word.toCharArray()) {, E: f* A- Y8 o4 f, M' R
                if (set.contains(c)) {
2 q- C+ }" @5 x! o                    flag = 1;
# |8 G" i5 w% E' D                    break;
) J6 v  M: v8 }+ s9 Q                }1 ?/ A3 n2 Q% a9 G
            }
% G* t( {# }3 y9 S- C            if (flag == 0) {0 C/ d5 b7 ]% O2 @- d8 X% A1 D
                ans++;* J- v$ C! B5 L: X! @
            }
) q% x7 i) {1 Y& M( {; {. W            flag = 0;
# F' D! ~2 F9 v# K% V            
0 ?+ I+ n9 Z) a- k        }
6 d0 K* Q8 ~8 G4 d4 v$ Z1 d        return ans;
  {+ H% I9 |+ m! H    }6 G- s, k( O) c* j. i% `  a
}; ]3 b' N) g" Y2 {7 \* S. [

6 O6 b) @4 N' i' D8 E+ G" C【 NO.2 新增的最少台阶数】' z3 G& _4 z; c

  D6 ~5 d1 ^# p3 E- j+ w4 N解题思路
9 Y3 S! P+ c) e- k+ v  A0 T4 v第二道签到题,两两计算差值,需要判断一下是否可以整除。1 l* Z7 E; k' M6 {2 i) o9 ]
- b3 ~0 j5 M' O" K
代码展示3 C' J! ^2 l( e3 d
# A4 X0 K* b+ @; u) c  Y
class Solution {2 J  _0 `+ w1 b! f4 J5 T6 j
    public int addRungs(int[] rungs, int dist) {, J& f1 ^/ }; P5 A9 ^
        if (rungs == null || rungs.length == 0) {7 D; `6 p2 A" N5 g6 V
            return 0;0 p8 ?1 F4 B+ ]$ k/ V% c" i9 E" x
        }
  p  \  H# N; u2 c        int ans = 0;
) J" i, c' e+ {. P5 k" p        int preRun = 0;
% x& R& ^0 L- D& g$ Z+ t3 H        for (int rung : rungs) {' [/ z# b6 n  x4 A
            int diff = rung - preRun;
6 h! k5 c9 l7 r) [8 x' A            // 整除的情况可梯子少一个3 D2 `- m* ], h) _7 V! Y
            if (diff % dist == 0) {
9 v8 F* ?" ?: w8 g, ~* p) |                ans += diff / dist - 1;3 I$ g: h' ?6 I+ \6 n. l
            }& ?" g' ^, N5 i# s
            else {8 R' Q; d8 d) i( o( \
                ans += diff / dist;
. T. _# R: ~' U) ]! S            }
! x7 {) K7 e+ G, _+ |9 d            preRun = rung;
, ^. L$ w( d: J# T        }  L2 L& b: V- z0 b( u) |. f
        return ans;, e; N$ P4 z8 O) F$ i
    }
* u/ v( p! g' I8 I7 Y! T' C0 L}
. G: j- W) i5 N2 b
: `# T0 f5 c# e; t/ ^1 B
* s1 H( k6 c' w" i【 NO.3 扣分后的最大得分】3 ^1 V& D; c" h' T& }8 a
' f! ]; f# D# [8 o' J4 y9 V. x
解题思路1 ?6 X( ]0 e  V- z$ U9 h
坐标型动态规划
" M/ y/ D( s( l+ l- d7 F$ t; i  t. \( r& n( P" d2 A+ e$ h
dp[i][j]表示处于坐标 i j 的位置的最大收益8 x+ i& d( k* h; Z9 M! D4 L6 j
% J( A' y1 Y4 q$ }9 _
普通的坐标转化会超时& Y  c* g0 g# L! |# f+ m" f" z

9 `; k* l2 g/ b考虑针对每一个j,会从 j的左侧和右侧转移过来,我们只想要一个收益最大的8 G& d; H9 ]3 {
1 p3 n3 O; C; R7 \& V* m
因此在遍历 j 的时候记录这个左侧和右侧最大的收益,给下一层用( F, t% g8 ^: D( k( u
% C; W. L, Y/ I; y5 n! J6 w
还有优化的空间,i 可以压缩成两行
3 o: |- y1 q# c* R* ?5 ?# j0 Y# _6 z- u8 F! j
代码展示
$ Q9 L  I) z7 r* m
1 G, m/ Q2 i; `8 aclass Solution {8 `+ p. D, n! E6 C  v4 V- q6 R8 E
    public long maxPoints(int[][] points) {
- a4 k4 u9 z! N- Q! G4 n; j, f        if (points == null || points.length == 0 || points[0].length == 0) {
, H: G0 t8 U, d' j& t( ^! `0 a            return 0;
  J) U0 j' y) O' `        }
% B2 l4 S9 F3 w, v        int n = points.length;
9 W( U2 x( G7 Y' g$ {        int m = points[0].length;  u, I* y8 D6 p5 G
        long[][] dp = new long[n][m];( m( w6 \# ^% c* @
        // 首行初始化
8 h# |% [" [5 a, `7 |5 O4 h        for (int j = 0; j < m; j++) {
2 o1 J2 o& w0 B) k            dp[0][j] = points[0][j];
+ m* `) x; l6 X        }
9 w7 d4 P7 E' r* b8 q5 h3 @        for (int i = 1; i < n; i++) {; D$ R# T+ u  {+ P* c- C( U% p% m  C
            // 对于所有上一行左边的数,都是加上它的坐标减去自己的坐标;
- \! N( V: i: T            // 对于上一行所有右边的数,都是减去它的坐标加上自己的坐标;, \. G+ ]2 q3 t; e$ v
            long leftMax = Integer.MIN_VALUE;+ L: Y" ?( N3 N, u* k! u
            long rightMax = Integer.MIN_VALUE;) ^; c# m$ q% p- }- A" E7 R
            for (int j = 0; j < m; j++) {  o# G3 E" J8 I  }% ^
                leftMax = Math.max(leftMax, dp[i - 1][j] + j);
4 X/ W' R( ]9 K* m3 t$ k                rightMax = Math.max(rightMax, dp[i - 1][m - 1 - j] - (m - 1 - j));6 Y+ X$ X7 E7 c2 n
                dp[i][j] = Math.max(dp[i][j], points[i][j] + leftMax - j);2 u8 X2 l  V0 r2 w( [
                dp[i][m - 1 - j] = Math.max(dp[i][m - 1 - j], points[i][m - 1 - j] + rightMax + m - 1 - j);
: h4 s7 z( |; M+ x2 B- ~            }9 `4 J  {" H# d3 i
        }, S9 G) ]8 y" P, p# h8 y
        long ans = 0;
* G/ D. B& B: e; p        for (int j = 0; j < m; j++) {' c1 H) l6 A2 ?! K7 E7 t) h
            ans = Math.max(ans, dp[n - 1][j]);
: ?- h- s  y: v9 P$ }6 S3 p        }3 N! F8 j  Q$ s5 C% @! j. ^' [
        return ans;
; v* j/ b" R. p) b! R( O- C    }( i( k" G% y. e/ u- Q' `; c7 F
}# t, W* Q( E8 n

* f9 V9 ^* V6 ~! |1 |$ e) C+ Z
. z: i3 {7 @" R* R【 NO.4 查询最大基因差】& [0 k+ s5 U1 p% R

. ]9 E# a8 t' q* C解题思路
4 L* D; f" w1 T: x- V二进制的字典树:将数字转化成二进制记录在字典树当中( l+ @2 r: ?+ y( K* [5 O+ B

6 z$ `! }6 s5 \- D构建树,方便做DFS
4 ~) ]# `8 u, O/ m: \* ?& n$ M( X4 E1 R% S* x) q
每搜索一个数字,将该数字更新到字典树当中
7 ]( J: V$ F) ~; |; U" d4 v$ j7 ~- f7 r
在字典树上计算最终最大的异或值+ R% H- l1 X' C; B
7 F+ l9 U* ?( S3 N! n+ f3 {& a
代码展示4 H& Z; s% X# l  Y; Y4 b
5 g- {0 i1 _8 j
class Trie {$ q' Z: r) a, v4 M
    Trie left;      // 1) d5 C2 p1 a0 }' p
    Trie right;     // 09 {4 Y' P2 U! e" K9 n/ L
    int[] count = new int[2];
7 g8 {4 c' b* Y  v" y/ @    public Trie() {}) F+ u6 d  ?6 q4 [# E

' |. _6 `1 t1 Q9 b* r/ u    // s == 1 添加, s == -1 删除
7 ~. B2 G& T3 E8 U' f( w( N    public void insert(int val, int s) {
, \! f' ^  B* ?9 m        int flag = (1 << 30);& x7 w3 `* P3 G! k/ }
        Trie node = this;+ o9 X" Y7 T- x7 W: _$ [1 u
        while (flag > 0) {
1 z0 k/ J6 J+ V- y9 f7 ]            int bit = (flag & val);
- O! q9 _/ Z$ f* M3 T            if (bit > 0) {
1 M" i9 `, h. W2 }" k" C                // 1 走左边
* W) d. A( B- r# Z( ~4 ~' j                if (node.left == null) {
2 R- o, C& d2 F( B4 }                    node.left = new Trie();* b# S; u( c4 W- g: N
                }* [7 k( j3 ?/ U
                node.count[1] += s;
* W3 n+ d! V' ^  A" m                node = node.left;6 V: a$ h# K, X4 _/ \! w
            } else {5 H# ~" X; `- p; B2 E, M
                // 0 走右边( h7 Q2 w4 S- j6 j# ^; W
                if (node.right == null) {
+ `0 a; l9 z( C% d2 A: z$ R4 V; }                    node.right = new Trie();4 b" ~. o+ e2 ?3 O9 Q6 R
                }
, I- m& O" z) z- W* A8 t                node.count[0] += s;5 P: J+ D& u" ~# m( w- P6 u
                node = node.right;2 p# R" l% m2 t! f. |3 X) C: s
            }5 F1 a6 ~9 ~& ~9 [
            flag >>>= 1;5 G2 ~! l, L% [" i3 g" E: }
        }% t, O" f3 f0 \
    }
6 S! o3 x/ `( p  B' N# f( V3 B5 d, A0 m% }9 D1 T" F
    public int getMax(int val) {
6 x! r1 Y2 f+ M( B! x/ `        Trie node = this;1 ]% r( q  j! x% u
        int flag = (1 << 30);9 X, i9 O  W7 O+ |' u; X
        int res = 0;
4 `) M4 x& Q- s2 I. n        while (flag > 0) {! O2 q% ^/ v! W8 p7 ~2 A& z
            int bit = (flag & val);
! P+ A3 a+ i. u; v! P* z* ]$ i            // 贪心算法,1 的话走右边,0 的话走左边
" S  H" ^3 I1 [% i' Z            if (bit > 0) {$ S6 x1 o8 N# C* s
                // 走右边,右边不行走左边
0 q" q9 u9 N) ^- G4 j) O! X5 S. |                if (node.right != null && node.count[0] > 0 ) {, X& H5 {7 l7 D( l$ W, I( r% {# z
                    node = node.right;
. J/ G* ?; j% P  B                    res |= flag;
, `7 y2 D+ _( a! G/ l                } else if (node.left != null && node.count[1] > 0) {4 t% f. q: }$ }, J0 K+ a' F
                    node = node.left;
& K0 Q1 o8 N# \& j: T                } else {' J' y1 a9 m1 \2 i" O+ f& i/ L
                    return -1;. F, ]" J4 Z: H* H9 y) N
                }% X7 K3 {1 c% Q$ ]& Q
            } else {" b8 b( P# `9 r; s' J
                // 优先走左边
% H8 W) o" [; c& z2 U) g                if (node.left != null && node.count[1] > 0) {! e7 H! d4 [' }$ s  `5 r0 ^
                    node = node.left;
$ Q+ h7 n! f6 m9 m$ g                    res |= flag;+ c3 h* Y- K6 ^/ d" {8 u& U
                } else if (node.right != null && node.count[0] > 0) {
" ?: Z5 t$ E) f, M/ h4 E  m" @                    node = node.right;
1 w( o' {- b* ]$ k  j                } else {+ C- w% g- ?0 @8 Y9 E
                    return -1;
; d+ {4 @3 A4 l. H- i3 A# r  a                }
0 G) a2 O1 n7 d- X" f6 \            }
9 v# o( k( T- X. f& h, o: ^2 K6 ~            flag >>>= 1;
  R" @  u- |8 H2 T8 E        }
" G9 T' y$ o* n3 }3 b) \        return res;9 R. n( `" E0 i$ D
    }. ?: o6 Q3 K6 ~& j
}
0 o* \9 x2 _) {public class Solution2 {
$ l) k% \9 y2 c/ Q; Z3 w& o" U    static class TreeNode {/ f& ^% d& t$ _" x
        List<TreeNode> son = new ArrayList<>();, U3 K8 \$ U0 H- W  e7 T( v3 g8 g
        int val;
# d% H' a& N2 j+ |        public TreeNode(int val) {
2 t: `/ I3 n7 V1 _# o            this.val = val;9 U4 [+ ^2 c; n8 {8 g2 v1 P
        }
( a7 z3 k" \9 b4 m% b  B$ X- ]2 m" c    }
) b/ K; O; j) ?9 c1 t7 W* O% p    Map<Integer, List<int[]>> map = new HashMap<>();# ^* W( K- o# J, P$ `& S0 ]: `' W
    Trie trie;3 A4 u/ t# e: E1 _# q  u/ J2 P
    public int[] maxGeneticDifference(int[] parents, int[][] queries) {3 C6 h% v' }2 Q) i/ R. P1 C
        int n = parents.length, m = queries.length;
4 E3 g! j" ^; z# D* O/ T6 f        // 封装查询的信息) a- {3 j6 Y* r/ S: J! |8 P  ~
        for (int i = 0; i < m; i++) {
" L5 O8 G1 i' T) @6 U0 y1 o            int node = queries[i][0], val = queries[i][1];; R/ c+ C* J4 `4 R7 c  d/ Z
            if (!map.containsKey(node)) {1 `  D# D5 Y3 y9 Q' d
                map.put(node, new ArrayList<>());6 `) K1 X$ i+ x3 i! [4 P; K8 e
            }0 `' V8 _( T5 j
            map.get(node).add(new int[]{val, i});
: }: r5 T+ \. q) ~' s        }
* u  v. d1 @' }7 q! J        Map<Integer, TreeNode> nodeMap = new HashMap<>();* L9 [8 B, M6 {
        // 构建树
1 p4 P& @' I$ ?* L        TreeNode root = null;1 j: c+ `5 r3 a! A$ y; o
        for (int i = 0; i < parents.length; i++) {
6 ?4 R* v9 J, P4 h% o" G- q            int p = parents[i];: y! i$ x0 E! s# D2 E* ~
            if (!nodeMap.containsKey(i)) {
  A6 B* V6 i( D1 H' t( g                nodeMap.put(i, new TreeNode(i));( V, A- N5 G& N
            }
% {" T8 e+ v" K9 [6 \8 }! z            if (p != -1) {
- g& `* W; [8 D1 r                if (!nodeMap.containsKey(p)) {
: E) s! Y" f$ ]3 n7 l" L: q                    nodeMap.put(p, new TreeNode(p));/ ~' X7 a# q0 w  ~7 u- C
                }5 s% S8 m* `: `: a$ q
                nodeMap.get(p).son.add(nodeMap.get(i));
7 `. D* o# f! N            } else {
3 P  A' G/ m$ @" L3 ~                root = nodeMap.get(i);
7 h' k3 ^( q: e: k            }
: w' s" K9 c: I& }9 w        }
; d: p0 f) y* c, w" e4 O* h        trie = new Trie();) H1 o+ n5 [9 q/ Y8 o
        int[] res = new int[m];
( R. _7 ?$ m# J8 s, g        // 在树上进行DFS; h7 S0 X9 O0 P6 r
        dfs(root, res, map, trie);
' `$ F* _5 y+ i- m6 J# u$ k        return res;
- ^9 h( k) K! O# b' e: i; x$ E. ?# E& ?+ D& k& b0 A6 ?- k
    }
9 r1 i% G' H. Z7 Q% `" Y) ^- X. @1 m9 X0 y
    private void dfs(TreeNode root, int[] res, Map<Integer, List<int[]>> map, Trie t) {
9 j9 }( k6 N2 V3 J        if (root == null) {) A7 E3 U4 Z  E& n
            return;, C# y; R+ A/ |2 Z! w$ J& P2 k+ ~
        }
! @3 d0 `! B# S' k) s1 G8 Q6 U        t.insert(root.val, 1);' J" l; a! D+ }
        if (map.containsKey(root.val)) {& ]. Y2 }! R, \( `" I2 }
            for (int[] each : map.get(root.val)) {
3 @, `# Z0 @* Q% z; e                int idx = each[1], v = each[0];
8 F; c- \( o' m" y                res[idx] = t.getMax(v);
% M) s; f: q: l- m            }
/ j! _% f6 B+ S% R) h        }+ C. X( T- B) m
        for (TreeNode s : root.son) {4 O, I9 {! j9 C  D9 \4 N3 i$ P
            dfs(s, res, map, t);" i9 Q0 s' K0 ^5 W
        }8 |! G1 C, k2 W* d, B, U
        // delete# u4 l; I1 [( u% r* H8 L
        t.insert(root.val, -1);
6 x9 _/ n7 a: X3 c    }
/ o- q" o8 |% x2 x0 \& u}- o  H& q  P8 V9 V. l3 e
! U8 V6 F% c8 c, S/ T; _

$ F* q+ M& s- s/ k0 e1 V3 u: m
您需要登录后才可以回帖 登录 | 注册账号

本版积分规则

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