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

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

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

UWCSSA提醒您:

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

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

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

登录后可回复主题

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

x
关注我们:杭州上岸算法网络科技有限公司  B- E1 c! u+ ^" Y- ]( P
【 NO.1 可以输入的最大单词数】  E1 c- H7 R" ]) [8 ?0 ^

8 y/ I. Y+ K  ~4 x0 `( N解题思路
; L, F" y7 c* O4 W; w, O签到题,循环遍历判断即可。
. w3 ~$ d# N+ x/ ~/ |4 c$ E) K3 e: U/ d& ?- k- {4 z6 v
代码展示+ G5 S& o( |1 Z

; F: P" n% |& Kclass Solution {
2 V! {6 i  J) k& N4 N0 j    public int canBeTypedWords(String text, String brokenLetters) {9 N5 a( {7 E) I: M* o4 W7 R* p
        if (text == null || text.length() == 0) {! Z5 M% V. o% X
             return 0;( v! M* h. F; t; D4 S" w9 D
        }
3 n: O9 a. w/ p8 ^        String[] texts = text.split(" ");
. h9 m0 C, D% Y3 F7 `" e2 R        Set<Character> set = new HashSet<>();
* Y/ u8 p% u- [4 M        for (char c : brokenLetters.toCharArray()) {
8 N. ]5 S( F# D! D            set.add(c);3 l: R# `4 ?0 j; I* N9 M  p
        }
, }- y7 E& y  A. W1 M& D3 J        int ans = 0, flag = 0;3 }1 w2 e+ x: F: H
        for (String word : texts) {8 l9 i, ]" M! t5 G8 k
            for (char c : word.toCharArray()) {1 o, f. }0 b; E0 q2 Y8 D% y7 I7 x
                if (set.contains(c)) {% U3 f' @$ }" |. G
                    flag = 1;
$ I3 u  _# _! u; @2 n: g                    break;+ f( Z$ \0 {( z1 j) A% z8 q; Z( V
                }( t% D# s" I  T" s% J4 b* o; w3 y! O
            }
8 v" a) E) N6 l, @  {            if (flag == 0) {
( {) J3 \+ p1 }9 v                ans++;
9 c  _2 j( Y  v            }/ R% Z( A2 |, t5 S- @7 x+ x2 I$ O
            flag = 0;
! o2 c  K( J- ~- z            
- m, i0 ^- V. |0 E" k5 q        }
& E- [9 m# o# n. w/ {3 a/ p6 a        return ans;
: u4 j9 x; {1 Z' f" d+ M. M  u    }- I( G! F, b$ C  u) [$ k/ m* {1 `
}! K$ E3 ~& D4 v% T- ?& b, ?

: z# ]' i6 K+ J& ]4 N/ b( K& x【 NO.2 新增的最少台阶数】1 Y4 F6 v0 T% y& w4 S
4 K" e" E$ m2 D& O: c
解题思路# n# ~7 O9 T, F, ~( p% x  `
第二道签到题,两两计算差值,需要判断一下是否可以整除。
# {' D2 I& v; n% M5 `
; W, W% E+ I2 C  c, _代码展示# E3 K( T+ l$ [7 w( h& L0 }7 q

, H$ }1 Q3 K) }9 Eclass Solution {
; K% M5 H% r0 j/ ~2 G7 Q    public int addRungs(int[] rungs, int dist) {% z0 j* ^- [1 e2 m* j, k
        if (rungs == null || rungs.length == 0) {
- i" H3 `/ R8 e  W( m& V            return 0;& w3 {) N4 x0 u4 G' h7 ~
        }
; O* t2 i# i/ B% s% ^5 _        int ans = 0;! P$ W, Y, ~& [& `2 W: T8 ?0 |
        int preRun = 0;
+ t9 f! v- z! D        for (int rung : rungs) {
. O( S, b8 n, A) O            int diff = rung - preRun;: L( u( I5 M5 |% B. D* a
            // 整除的情况可梯子少一个* h5 W0 T2 ^9 v) ~7 o! V: `. l
            if (diff % dist == 0) {
9 m8 e' {. \7 Q6 f: b2 o& [8 ?4 m' g                ans += diff / dist - 1;4 Q! R* n1 A" S) H) r7 C
            }  i, ?4 f7 t8 u2 N1 A
            else {
- x5 f& W8 E% C$ u9 \/ W                ans += diff / dist;
  ]. ~, X" k" D: R  \# B2 g& H4 ?) j( C            }$ k5 E3 }  s3 T3 @+ `% H
            preRun = rung;
2 c1 ~; J4 I0 G        }
/ C2 ~! O% s8 D        return ans;3 d2 w9 J& e+ L% O: P
    }
' @1 a8 A  |2 i2 r+ \& Z8 @9 e) J}. v) v" j# O# F+ p" b

7 Z/ a) \% ], g; q" O. |; e0 x3 i& c( e6 ]  W# C: v/ k2 `# A% s
【 NO.3 扣分后的最大得分】
; e( u0 x3 n$ T" _+ G8 o( [+ ^5 {7 G5 L
解题思路, T$ b" W. ]6 g
坐标型动态规划
% t7 R" a$ Y2 K" X' f
% }: N9 h. f. Ndp[i][j]表示处于坐标 i j 的位置的最大收益
# M( N: c% |; }' N' S9 t4 v3 O- M% F( T# [
普通的坐标转化会超时( Z5 T  ~) F7 {: T, G
0 H* C, Y% o; X! |
考虑针对每一个j,会从 j的左侧和右侧转移过来,我们只想要一个收益最大的; \. ]! ?2 z7 `1 L, q/ {9 v
3 M0 B& A) @( V2 u6 q& I7 E* t% l: t
因此在遍历 j 的时候记录这个左侧和右侧最大的收益,给下一层用) Z" a. ^2 S/ L$ c8 g0 b/ @/ ~
5 b/ {, n2 V  L9 l( o
还有优化的空间,i 可以压缩成两行' [9 a  P) |6 X  W# v1 i# E

; G0 u" Z% I8 m( \: X5 N  R代码展示
, @4 @' x, ]2 p2 L0 I2 P( {4 s( m% M6 q% H1 ~* D3 d+ O8 [
class Solution {
3 S; G* Z( F, k" z8 W* e7 p( [    public long maxPoints(int[][] points) {
2 y8 @+ v, g, w  v' F9 F        if (points == null || points.length == 0 || points[0].length == 0) {" x+ ]4 W* E7 x5 A# z
            return 0;
4 U" A6 a! f% Y, e, W$ m' \. [        }
, }$ q0 w4 z/ U0 m: a7 {        int n = points.length;
3 z4 f3 t7 A. I7 \        int m = points[0].length;$ S  Q& P* e+ I; L* P/ `
        long[][] dp = new long[n][m];
) H. t% d; Q! r; }+ j# M+ [: X6 \5 v        // 首行初始化$ n' v$ ?2 ~; T6 h+ u, b. L
        for (int j = 0; j < m; j++) {
8 D  R' o2 R  Y0 Y6 X            dp[0][j] = points[0][j];* k0 @$ y" d; d
        }% x/ `$ R8 o8 J9 x; K( E7 b. ]8 I
        for (int i = 1; i < n; i++) {
" ]* O8 i& m" b, }) F* d+ h            // 对于所有上一行左边的数,都是加上它的坐标减去自己的坐标;
* P  T# }5 `7 x* ]+ k            // 对于上一行所有右边的数,都是减去它的坐标加上自己的坐标;- A) R2 p4 N# R6 V! b7 ?" p& ]2 q+ n
            long leftMax = Integer.MIN_VALUE;
& T* e" H) r2 d8 b2 N' F& M            long rightMax = Integer.MIN_VALUE;
- Z8 Y2 i# l' O4 k1 H: h, p            for (int j = 0; j < m; j++) {
) \7 k# \! C/ L  A5 i7 ~% }! Q                leftMax = Math.max(leftMax, dp[i - 1][j] + j);% f" T/ c& Z- [) B
                rightMax = Math.max(rightMax, dp[i - 1][m - 1 - j] - (m - 1 - j));- |6 B, g& _3 X1 v" f, [  z2 ]
                dp[i][j] = Math.max(dp[i][j], points[i][j] + leftMax - j);9 @) L( b  g, l1 b0 b% n9 B" x+ N
                dp[i][m - 1 - j] = Math.max(dp[i][m - 1 - j], points[i][m - 1 - j] + rightMax + m - 1 - j);/ [" y& o( d4 }8 \
            }
# q" A: S; M6 L' [6 l4 c0 k        }
/ M0 |! Q. L! p( r; A7 }        long ans = 0;
  j* N; a/ |/ j1 O: X* O* s        for (int j = 0; j < m; j++) {1 J) h) t( Y9 ?6 f* a
            ans = Math.max(ans, dp[n - 1][j]);
: q5 @& |* m/ c; ^5 z  z        }0 C7 f& G* X* e$ H* C9 _1 H; M
        return ans;2 m' p$ z! [! ^8 k$ T5 B8 y. [* M
    }
; T( e# W1 X" j2 b: C6 o6 w" X9 L}2 c9 s5 p- x" @# }# s! {
/ ^) u9 o+ G6 r: I  j

( M$ X, P5 s$ b【 NO.4 查询最大基因差】
# D4 k) f  {. Z! {
1 y( y' P( H5 T* b' t2 I解题思路; y# p& R1 m) c# x
二进制的字典树:将数字转化成二进制记录在字典树当中
- u: u# c  d: O6 E8 H+ i% a8 H
构建树,方便做DFS
$ A* o' d) p+ C3 k
2 v4 X7 B* X5 Z1 h. r每搜索一个数字,将该数字更新到字典树当中
0 n1 o6 ^2 U- ]( b8 b: l% L4 S4 n* N  R9 ^: `8 F6 R
在字典树上计算最终最大的异或值
" }# q: _( n2 m& t' U
! @6 N# w% c4 c7 b* ~0 v6 l代码展示
4 A# @3 _2 \) k/ L3 ^: ?- Y2 }7 r. C& Q
class Trie {! n+ L8 o. g3 n. \& C+ S. J. W
    Trie left;      // 15 O! |! s3 z% i$ X! O5 l2 i( W
    Trie right;     // 0
5 ?* B" O# n) s7 [1 d9 P    int[] count = new int[2];" w2 a4 k, G. ]; l
    public Trie() {}1 o& }& p7 D0 T/ D
# f3 u$ C6 [) h$ H- h6 r) V
    // s == 1 添加, s == -1 删除
7 q3 k6 @% S3 x# t1 N9 D8 E( Y    public void insert(int val, int s) {9 P6 i1 Q& h+ T0 u
        int flag = (1 << 30);
% E9 u# l( \, t! Q5 ~% p        Trie node = this;
2 G: \$ z' e7 X6 u8 L- @        while (flag > 0) {4 |3 n5 t* k' v% [( j6 w
            int bit = (flag & val);2 b; ]& a' \* N8 V
            if (bit > 0) {/ J- b' O, v7 M& ]7 v% a
                // 1 走左边4 r- h! P! K' _. m3 f! k
                if (node.left == null) {) _+ V/ N8 c1 B+ I2 i6 o6 ~
                    node.left = new Trie();/ H5 J/ @5 }3 K7 Y) f1 k6 i! u
                }3 M- B# h. c! x
                node.count[1] += s;
0 C5 Z" G3 n2 V6 g                node = node.left;8 J9 f8 G7 @; K6 R4 b7 P' N3 i
            } else {- e( n  u6 H3 b+ A* e9 b
                // 0 走右边- g0 k& ], y/ b! r9 B
                if (node.right == null) {; P- \* F& l* ^  }
                    node.right = new Trie();! @$ U+ N1 P0 ^" p9 P: ?
                }
. ]3 J7 s9 }# I6 C3 k                node.count[0] += s;/ F# a( m: H# n5 `
                node = node.right;
) h  z1 V" E/ m+ G1 k  K            }
) L6 a  ~% S' {: f, L            flag >>>= 1;
. u5 o5 c- j. i: f( ^        }
  _; w3 Z  {5 B9 p! e5 z    }
! F0 v1 Q2 x7 V: k5 S/ X
( U, F& H" c( _$ R    public int getMax(int val) {6 ?+ y) @6 U1 y/ X
        Trie node = this;6 |/ ]& L5 O& g; ?6 i9 N/ q% a
        int flag = (1 << 30);
8 @, p- W7 ?2 c        int res = 0;
" ~1 N2 c/ ^6 p- T! q. g1 M        while (flag > 0) {4 k) B  _- H% \- @# y( M
            int bit = (flag & val);
3 l- @0 u+ S4 {6 `8 Q* j            // 贪心算法,1 的话走右边,0 的话走左边2 ?! u; Y; H' e/ z" r) K
            if (bit > 0) {8 H8 N1 L7 Z# Y0 W) p, u
                // 走右边,右边不行走左边
! C- j6 _6 Y( @; c                if (node.right != null && node.count[0] > 0 ) {0 G& \( T4 }; Y* L: z" v1 X
                    node = node.right;
& f) l# i/ o/ \$ f6 q" p4 G                    res |= flag;; C) s: ^+ Q* l1 }8 a7 G, B
                } else if (node.left != null && node.count[1] > 0) {
: d9 R0 l1 @5 `& ?                    node = node.left;5 l: U1 a$ J: l; ]- C6 G9 f) Z
                } else {
6 d# v! {; E% p                    return -1;
+ r0 v4 o/ E  i. c' I5 i4 B                }
" {3 P5 f& W5 @' L% h            } else {3 |1 j& K+ |( I2 h4 O" y1 X; y
                // 优先走左边
. t$ I) O* h" U3 ~                if (node.left != null && node.count[1] > 0) {; \( j- S, M$ z+ x$ q6 E
                    node = node.left;
4 H# o% t% q1 i, _5 F: j5 G                    res |= flag;
/ [: u+ O$ I3 r, Z8 f                } else if (node.right != null && node.count[0] > 0) {& c9 d# f/ L" n/ E9 C! \1 [
                    node = node.right;
1 A& u! }) b; R2 b" A                } else {. W- h0 ]& o# F8 o4 c
                    return -1;# W: `- ?' e: P( _, N& d  ?4 Q
                }
3 s  X) @6 c% s3 c# c9 Y+ ?            }
! P7 N& M/ x$ Q4 H; A* N            flag >>>= 1;
% C7 j1 l2 I8 V0 c) Z, d8 v        }
7 h) t. N) R* K7 }* n/ ]7 c        return res;
1 i6 t' R5 s( m# t    }
+ m5 z3 D5 D& _5 u2 G' x}( R5 m5 ^1 |% ^! o; \0 q4 X/ p
public class Solution2 {8 }% p; ]8 [4 I. D* h6 }
    static class TreeNode {
5 G; T/ f: \( b; D) O/ i        List<TreeNode> son = new ArrayList<>();! K- u& M6 V, t+ n
        int val;! }' p' E' |! G2 C+ F4 ?8 e* O6 D6 W
        public TreeNode(int val) {8 T4 u2 U0 z' a! s0 a' N9 G
            this.val = val;
0 Z& o. O+ d% [' W4 ~        }6 c, r+ G, b" d# i& Q- D
    }+ I- q5 o  n5 u* F2 i9 \; p
    Map<Integer, List<int[]>> map = new HashMap<>();7 K& K5 b$ f4 l3 b
    Trie trie;. z2 v4 M! x3 x8 h( `
    public int[] maxGeneticDifference(int[] parents, int[][] queries) {
) l" c( f, k, s- C5 H! j        int n = parents.length, m = queries.length;
4 h3 J3 |8 q; w. a  g        // 封装查询的信息3 V4 V8 S3 Z9 _/ T3 m8 ^/ j: h
        for (int i = 0; i < m; i++) {
' Y7 S0 X( \- z9 k3 N, [9 v- z/ f5 ]            int node = queries[i][0], val = queries[i][1];
  I6 x3 [8 m; C7 B            if (!map.containsKey(node)) {8 q. N" W0 l. P: Q
                map.put(node, new ArrayList<>());
% W! b$ o3 w6 _" Z: z" ]. \. u            }% r5 J4 J7 O) C2 S5 G) Q
            map.get(node).add(new int[]{val, i});* w7 p$ d' t. b' j! P( V) ~; @
        }
  n5 D6 G/ E, |8 U0 I$ D        Map<Integer, TreeNode> nodeMap = new HashMap<>();* |" s, i+ Y$ T' R6 D
        // 构建树
6 h. W( u/ C" \" }        TreeNode root = null;
2 q" h+ ]$ Z; @6 g0 L1 [( d! |, H        for (int i = 0; i < parents.length; i++) {' ?3 _' c2 `: K/ [/ Q8 k  B
            int p = parents[i];/ V8 i& U+ ?9 V
            if (!nodeMap.containsKey(i)) {
5 r( \& ~5 z; K3 g% `% Q6 i  C                nodeMap.put(i, new TreeNode(i));. K2 Y1 B1 N3 T3 g+ t% T. m2 R
            }4 e9 J! I7 E9 a* M8 T, I/ Z6 Y( Z
            if (p != -1) {" h$ ?# f6 d8 B! s
                if (!nodeMap.containsKey(p)) {
. G' ~, M- h1 u& {9 a2 D+ R                    nodeMap.put(p, new TreeNode(p));# u. W0 i7 n1 z; v- d) K
                }) b# q& ~, ^; C
                nodeMap.get(p).son.add(nodeMap.get(i));
. J9 z; E- Y! u& B& x+ b            } else {
2 Z0 M% ~! u5 ]                root = nodeMap.get(i);5 g" i6 S5 u) q  W
            }
4 X" G0 L# k! U- C* i' ^, E        }
3 }# C5 K' ~, V* T) T2 q        trie = new Trie();
9 V  A: _6 b0 ~3 c! L3 p" Z        int[] res = new int[m];
. o) _0 K# V9 v0 T$ K9 E        // 在树上进行DFS
1 w( `$ d! v( }  x        dfs(root, res, map, trie);
2 M: x! S9 R/ }6 o( `2 l/ w        return res;
3 t# F5 Z  i3 c$ s, d3 d
  \, R1 Z/ |' @7 }! j5 Q: S# y    }
7 c5 U3 Y# p4 U* Q/ h8 n& d' w4 f  z! }- i% I( h
    private void dfs(TreeNode root, int[] res, Map<Integer, List<int[]>> map, Trie t) {
$ }' c+ ^; l. s, D" J$ K        if (root == null) {
. M% |) l8 k  D! I7 E+ o1 }            return;  P0 h& [" X' i3 [+ b2 I
        }
' M( X" Y3 _* Q: v8 a- _        t.insert(root.val, 1);
( q( i6 j7 j, I0 z) N: G' A        if (map.containsKey(root.val)) {
1 g: _, Q+ Q5 j            for (int[] each : map.get(root.val)) {8 o! g' M1 r7 ~* u
                int idx = each[1], v = each[0];( Z5 p/ ~$ T! [8 e7 R- O
                res[idx] = t.getMax(v);
. F5 q+ s- T- k) s7 g8 P            }
* C9 z$ W8 D. N+ j% f        }: x+ W8 B! u  Q- U+ h3 e' U
        for (TreeNode s : root.son) {
* Z4 k4 z( H% o5 M            dfs(s, res, map, t);
9 N$ \! Q) W9 ^( q        }
0 p0 v/ a' m+ t; E        // delete
* x) A% O* q9 h8 `& A0 j. R0 [        t.insert(root.val, -1);
; G  u( f0 o. r) W: f    }
8 K8 h# U* ^' [5 ?: Q}  O* `7 P8 {/ F% {1 L: I
2 J1 F, g; x4 y0 {

; `( a9 F, V4 a# R
您需要登录后才可以回帖 登录 | 注册账号

本版积分规则

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