登录后可回复主题
您需要 登录 才可以下载或查看,没有帐号?注册账号
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 |