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