登录后可回复主题
您需要 登录 才可以下载或查看,没有帐号?注册账号
x
关注我们:杭州上岸算法网络科技有限公司
* y0 ?3 v3 Z9 I8 ]! W0 k( B【 NO.1 可以输入的最大单词数】0 a. P/ k, Z" o* e
" k7 V4 v, n3 I- f$ u解题思路
. h/ S5 d. n5 S( s5 f% V签到题,循环遍历判断即可。
$ T& g* B* `7 h: d* c/ J4 F9 a
2 L8 l5 L$ e2 T4 ` e代码展示
: b- {2 y# w0 `. v7 d& n% W' N% B$ _2 @) u( {& e. M
class Solution {
( U. V7 r9 W& {! w- P- s! g- p2 l public int canBeTypedWords(String text, String brokenLetters) {
) q+ e% O9 e2 u2 k4 Q if (text == null || text.length() == 0) {
B* \# r8 {# c# g! L' \- g return 0;
# d& k2 }$ @/ n }
& S# h, W/ `9 Z9 A m9 N( W, ^3 B' \ String[] texts = text.split(" ");! H; c) g7 _# P6 p- W
Set<Character> set = new HashSet<>();
1 N5 W' y/ u; S5 [! [; G# m8 I for (char c : brokenLetters.toCharArray()) {4 c; V4 z+ ]* d$ N; H1 q
set.add(c);
9 t% L, c. R& l2 d }5 E; G( P' }! e& g
int ans = 0, flag = 0;
! `- \- H4 I+ I8 D! { for (String word : texts) {+ P/ A* B* H; Q/ ^
for (char c : word.toCharArray()) {
' u3 `# Z5 S [4 I+ t" J$ v. \ if (set.contains(c)) {
3 w' K4 Q( ^ a' T flag = 1;& h4 r! x/ I7 z' c/ y8 b" H' b3 I3 m
break;, U' M5 g6 G! t W: }0 ~* c
}
! k/ v @- G( p6 S' O5 ^) Q }) [9 V6 u5 Y |6 w' V
if (flag == 0) {$ c8 l* p: t+ ~
ans++;
3 Q* l! v$ `7 R/ Y8 r2 c }
* l3 N- D) N: u" X& P& ] flag = 0;
! n4 P# e9 i5 l3 m' P
# e, w5 @& `& z }
& Y$ E8 U& F8 b/ C$ V) I8 k return ans;
5 m% H9 a$ H" h& [3 Z } W( `6 y( X8 z
}
8 e5 Z& N4 ^: S$ ^# `
9 o% o- n0 k" ?' ?5 m1 w2 n+ _! N【 NO.2 新增的最少台阶数】
8 |: [! f s. P N! g- f# n8 ?+ ~) Z) d L
解题思路
. T/ T% m2 Z! M第二道签到题,两两计算差值,需要判断一下是否可以整除。
* Y/ z- a% N% P9 d! x/ u7 G+ d
0 f% J, Y7 n; G ~1 p* J代码展示
: p2 k( ^9 {. z, i
A0 P# H; g5 gclass Solution {
" c# L$ E& k! D4 y, v+ p public int addRungs(int[] rungs, int dist) {
$ O+ t+ H/ P7 Q- T5 }4 y2 J if (rungs == null || rungs.length == 0) {/ v. k8 v9 _. `$ Q# J, s5 F
return 0;! s7 T2 l3 M* ]
}: Q- L2 G; r* e
int ans = 0;
7 ]3 ^! a& q& N8 b6 Y int preRun = 0;
. ?" ~; B" H4 a! b3 r O' N for (int rung : rungs) {/ C4 ^7 m1 T$ ^+ @& A% h0 J
int diff = rung - preRun;
/ y; w! N, n6 P5 F9 H1 b) r // 整除的情况可梯子少一个5 i) N9 _- o: c% K+ W
if (diff % dist == 0) {) X1 j. B2 u6 b) v' a
ans += diff / dist - 1;
5 y. f1 o8 R, i) ^4 }: k) O$ J }
0 ` o' e% i9 F& Y else {' _: J' ~; L, s V6 O; ~
ans += diff / dist;
( n& x ~6 c: g' g& [9 e' w) C. E }
7 ~+ U+ W- M# w* f8 H3 ?" d. [ preRun = rung;# p( d$ v# J- E! |- Y0 l7 K. x9 R
}
r7 I* S2 _8 J$ O# w# t9 o2 B, U return ans;7 p$ V; N5 l( ]1 d' n
}
8 S4 D( e4 @ H( w+ S4 F}
) G- E& W4 Z' y1 d7 A4 k* U, `7 |( E. v
& y( p2 ~# C" n【 NO.3 扣分后的最大得分】0 A g1 U7 y8 i7 g
, B5 k# w* l! a- C
解题思路1 e h" n, Y. S* J
坐标型动态规划
. u; e/ n8 M0 w% K! W, [( r- X- ]* J
. e* p- }' S! a; ?dp[i][j]表示处于坐标 i j 的位置的最大收益% e* T5 o k9 M0 G: t! R
" y ?- U. E: `
普通的坐标转化会超时
& z2 g* {. F) ~. {. O2 B' K- q4 S" v( d q
考虑针对每一个j,会从 j的左侧和右侧转移过来,我们只想要一个收益最大的0 z _- {3 g4 v: y
( g6 G( f4 H- L9 ?; a- z l9 r7 p
因此在遍历 j 的时候记录这个左侧和右侧最大的收益,给下一层用4 ~$ W, D7 z( e$ m' U, s( \
. U+ Q# S T( I% e+ a3 |" g* J7 _& h
还有优化的空间,i 可以压缩成两行& I8 v9 V" O. C* X& s( S1 {
, H0 j# p' U6 R9 l* I9 [" E m& V/ E代码展示
0 \3 Q6 j; K1 [1 U# c4 C+ I- y
6 ?& D& z6 R) l# V# b3 M7 l- ~: `class Solution {2 U# b( Q& }1 m7 k, I2 s
public long maxPoints(int[][] points) {
' k7 W# q6 F9 p2 |& w; ] if (points == null || points.length == 0 || points[0].length == 0) {
" T9 I" {9 B, E5 B2 j5 { return 0;
5 s+ _, B8 {7 |+ Q }
: v0 Q' |: {! o2 v int n = points.length;
* Y: F6 N( b2 e9 b9 o int m = points[0].length;
1 Q, K, o1 J2 n& r, S! h8 h long[][] dp = new long[n][m];
& a4 u" S3 c; @- f // 首行初始化2 ^- D5 u9 r, i8 X5 d
for (int j = 0; j < m; j++) {
' _7 T. ^& F. j0 C, O! U, o$ S! y dp[0][j] = points[0][j];
; j/ ^- |$ f; @) M4 Q }) T1 F O& Z: D, p# A
for (int i = 1; i < n; i++) {- l) F& |2 y6 ?0 q7 Q8 x6 j
// 对于所有上一行左边的数,都是加上它的坐标减去自己的坐标;
0 x: C; |/ K3 W& C* Y M" n // 对于上一行所有右边的数,都是减去它的坐标加上自己的坐标;
( u, |5 ?6 H! M) J9 p long leftMax = Integer.MIN_VALUE;
5 K1 k3 |3 ~: g4 I4 b) b( e) X8 f long rightMax = Integer.MIN_VALUE;$ v* Z A( b6 W" {$ H( K1 W q
for (int j = 0; j < m; j++) {
/ i# u% X, I* ]' G" s leftMax = Math.max(leftMax, dp[i - 1][j] + j);: F* s: p- G* c
rightMax = Math.max(rightMax, dp[i - 1][m - 1 - j] - (m - 1 - j));! R" t0 `$ ^" C4 T5 F5 d, ~* Z
dp[i][j] = Math.max(dp[i][j], points[i][j] + leftMax - j);7 d2 o! U4 H2 y- h" k+ L( G4 D
dp[i][m - 1 - j] = Math.max(dp[i][m - 1 - j], points[i][m - 1 - j] + rightMax + m - 1 - j);* z8 s- H6 W; V9 G
}9 w n& j" ~0 I6 U! k
}
5 d5 n' @, l+ P long ans = 0;! r# T- V: p" ~3 k
for (int j = 0; j < m; j++) {. N7 t% L2 W9 v) l* G
ans = Math.max(ans, dp[n - 1][j]);5 W8 D6 s9 D* B3 N& S
}
1 V/ `, W9 A: s: W8 E/ H; M! [( E5 E; X return ans;9 ?$ o9 Y9 | Z
}
* j* Y2 |; n4 z6 C}+ x9 d0 @1 }$ _# V5 d" C
0 d" M' X. B, L+ D
9 |# d& U; J! @+ m, E' r
【 NO.4 查询最大基因差】
3 |, M9 O2 D) A- \. ~+ `' o2 c' Z1 f% k. n
解题思路
: {9 W7 \, E; v* T: X. B3 e二进制的字典树:将数字转化成二进制记录在字典树当中
1 Y7 M. {; \4 q2 Y H) q* k; K: b4 t4 W) [0 X
构建树,方便做DFS+ k! B+ Q8 R3 g' u
! E9 T6 x4 Q- Q% Q# Z每搜索一个数字,将该数字更新到字典树当中7 d+ c; W3 }: G1 s1 o+ L
6 M% u6 M; G1 D o. N" y1 u0 W1 F在字典树上计算最终最大的异或值' Q$ V9 U& y$ o, \3 K5 u
. j/ s/ W/ I; {
代码展示* r0 M6 ]6 I2 H4 ?* |6 b8 ~. ~* M
6 Z& y# I6 N4 s5 k; u% l7 |1 q4 ~
class Trie {3 h$ i/ u2 W( A8 o t
Trie left; // 1/ f! x/ o0 k1 b
Trie right; // 08 b' c% M( K5 x! X0 P7 ?
int[] count = new int[2];
/ ^; w4 B6 u9 V u, o public Trie() {}
; y' A/ G1 f+ k' X) v$ u6 Y1 t% e
' F( h" I. _1 j, P; c2 x0 l // s == 1 添加, s == -1 删除6 _0 t6 l& L, a
public void insert(int val, int s) {' O Z1 U& R/ Z
int flag = (1 << 30);
5 H2 b+ s) I/ f6 N) t" H0 g Trie node = this;! a% W$ s. w3 h; f' s
while (flag > 0) {
- z: i5 ^% _( ~5 G0 R int bit = (flag & val);3 W/ v( Q2 D: D( D% t. Z g( }
if (bit > 0) {
1 H. Z' ?# }+ C: B7 M // 1 走左边
5 y1 b m2 ^8 S4 Z8 H3 P8 }- ` if (node.left == null) {
+ q3 `) U! ?) T" E1 d node.left = new Trie();( n8 O' W x! |7 c
}
4 z# ^/ o2 x; H9 Q7 ` node.count[1] += s;
, t4 n# O6 Q% a node = node.left;; }$ j9 F' @* D4 u, ~
} else {* { ]$ ?6 |9 l. V. n& k c
// 0 走右边* N( \9 H. x, Q) b3 s5 A
if (node.right == null) {) h/ d X7 V- H0 _+ T' U
node.right = new Trie();* L7 G8 a1 S) G
}
! \) z8 s( ?, |$ {( Q# T node.count[0] += s;2 q: S7 D1 b+ h' r
node = node.right;
% G9 v& N% D/ y- ]- q }4 M6 M. r' Z' P2 }3 U" i+ \
flag >>>= 1;
) [3 A' u& v$ T# K7 O }: {1 {/ ~9 \, _6 T
}( B3 u3 Q6 y* Q/ A+ ^" e
! f/ H. s2 @2 e5 O8 G
public int getMax(int val) {
3 O S1 ]8 I; l Trie node = this;
. |: k! c$ u8 C# L. h" U9 G int flag = (1 << 30);
. |& J% Y/ l, d# y; ?% K: k8 U) _5 C7 u2 \ int res = 0;
0 l" G: b& z T4 g while (flag > 0) {
# r4 k: U8 u. M int bit = (flag & val);! @' w5 t, z* o) |+ M
// 贪心算法,1 的话走右边,0 的话走左边. v- e8 X: K; x5 X
if (bit > 0) {! q( H& O2 y6 ]7 a% u1 d! w/ h! a
// 走右边,右边不行走左边0 r! e1 x; H6 ?2 u2 E% ~7 I9 d
if (node.right != null && node.count[0] > 0 ) {% ~* q: o0 {+ a5 g2 R# d
node = node.right;4 y0 Y: u" H6 i+ q' m0 f, j. K
res |= flag;
8 z% c' A6 B. V: g3 Z } else if (node.left != null && node.count[1] > 0) {
$ u# W1 h* k- b5 T) P5 @& ]) h4 _ node = node.left;4 ~/ Q# L: f8 B9 l: G9 M4 ~; r
} else {
4 G! {1 W9 J) C% Q return -1;$ d% ?0 D6 M4 w9 V
}7 p+ e; C7 r- ?/ `' R) x
} else {) }$ R" `# r6 x
// 优先走左边
8 Q/ w. l ~! ~7 l& @! ?3 d if (node.left != null && node.count[1] > 0) {
{7 D: i9 j9 Y node = node.left;
, W0 L+ _1 f6 ~8 _9 H! z8 z+ A res |= flag;
, q- t* h8 y4 ^! U! C } else if (node.right != null && node.count[0] > 0) {7 J( @, m+ F+ w1 r9 @) {
node = node.right;
( i! c* i( }2 A9 b0 Q6 l } else {, k" L1 Z3 f+ p
return -1;
! F' J8 L2 t' R6 O% G }) R9 e9 U1 R7 O' e, b
}$ ~5 N, Y! n; i5 y( `5 \
flag >>>= 1;
8 z! I5 H, R( q0 k- o O2 k: X0 E }
; B& C) R4 s! L# { return res;# a( M' b% _; k$ M8 L/ ^8 h1 B1 X/ d
}
( O- Z- l1 S# S+ n s! o0 q2 ^}
/ P+ q9 J6 X6 r6 Fpublic class Solution2 {
8 y5 q; p8 `8 A+ X' Y6 N static class TreeNode {
+ ?+ q3 R4 X7 q2 x List<TreeNode> son = new ArrayList<>();
9 Z Q" B) b8 D int val;9 e" U B9 h; A/ a1 k# Z
public TreeNode(int val) {
0 V: p5 c! C5 B this.val = val;
4 z- f; t8 c" n3 l' L, f } k8 u2 N! C, `' z
}( s! O8 D* S3 T. C4 F" \
Map<Integer, List<int[]>> map = new HashMap<>();
2 K6 r E5 @+ w Trie trie;1 x! V; i& i9 g; S5 k8 q' F
public int[] maxGeneticDifference(int[] parents, int[][] queries) {
: b5 V: T. c- B; P( y. o0 ] int n = parents.length, m = queries.length;
* ]3 M. \6 Z: e // 封装查询的信息) V L6 y" m& p# \" \
for (int i = 0; i < m; i++) {$ ^2 ~2 B/ G3 O
int node = queries[i][0], val = queries[i][1];" i, P" I) e$ P4 q! p8 v" ]$ e* s
if (!map.containsKey(node)) {
5 L g2 n+ X! N& T, I" f map.put(node, new ArrayList<>());: c7 S( ~+ ?; d: H0 [
}
$ x2 o4 h! ~% h7 Y% {7 s8 u1 \ map.get(node).add(new int[]{val, i});
6 U$ Z/ M& Q* f+ K% K }
. c# J" j, ]) c% |+ r2 g6 q' j9 d2 t Map<Integer, TreeNode> nodeMap = new HashMap<>(); Z3 J5 } e6 B" M* a" \: q
// 构建树
8 P, I V- ?! w0 w1 K, b5 k TreeNode root = null;
* m8 j8 r3 j- Y8 b+ n% `& e for (int i = 0; i < parents.length; i++) {
$ O1 \9 e3 g2 {8 L int p = parents[i];
% F# L% V" Q- y if (!nodeMap.containsKey(i)) {
7 l; e! j: S: n. g7 t0 A! t nodeMap.put(i, new TreeNode(i));
* C9 u! o3 C/ R$ X2 J( o5 m x }
- s1 @" d+ J' Q$ U8 { if (p != -1) {
- N* P5 }, \; B+ d- M if (!nodeMap.containsKey(p)) {6 a. P; U2 b1 o: v3 }
nodeMap.put(p, new TreeNode(p));
3 G9 M! f) \, ~$ D; t D }
- N. V- w+ P1 Z& N4 H$ A nodeMap.get(p).son.add(nodeMap.get(i));% P s4 B8 B; R6 n# X3 H- q- t9 ` S
} else {; e8 f4 @3 \* c6 W/ s2 X2 O' P
root = nodeMap.get(i);, A+ ^. U5 y# l; o, U E0 K- a
}! O6 `6 X+ d8 L7 E# M6 J
}1 D" e2 d) V" X$ Y, O+ y. S
trie = new Trie();
T9 f/ I* r6 |5 a- h int[] res = new int[m];
4 n/ M0 I4 b7 l8 V; z7 t // 在树上进行DFS
5 O0 T9 e. G: q& f4 w- t0 t dfs(root, res, map, trie);
5 U- g! b7 j5 g7 ` k3 S/ A4 w return res;! H6 f+ W9 F) t" V* f
/ |: w$ d: Q% G0 ^9 I5 ]$ k
}
$ K' |, m! K2 c& m3 T' M/ l2 P! ]7 |6 k- p W
private void dfs(TreeNode root, int[] res, Map<Integer, List<int[]>> map, Trie t) {) B/ e5 R/ ` Y. Q
if (root == null) {
4 r+ h c# d S$ |$ d( E return;
! m6 m) d2 u, W } v$ o% n. g4 C2 X3 G0 O& `# Z( K
t.insert(root.val, 1);
8 h- e: f( C) |2 M4 r# H5 K if (map.containsKey(root.val)) {1 d" q5 k) M$ e$ X; @9 P
for (int[] each : map.get(root.val)) {4 ^& F3 P: G% g1 ~( k, _- ^0 Z. y. _+ ]
int idx = each[1], v = each[0];* A* x6 Y* r* C% Q) R2 X
res[idx] = t.getMax(v);
$ p' |; b- o3 H9 A+ @; R, i }
' }6 I% |* c4 Q }
2 l: \0 q: T0 h" Q% R: ^ for (TreeNode s : root.son) {
* s2 X+ s! E) v/ V* S O dfs(s, res, map, t);
& _1 u- f D% r c' _1 m, Z# m; G }
8 v: |% \) X6 F+ {7 S // delete! H8 ^) |0 x( U" c! B
t.insert(root.val, -1);
. a A& h* L/ q" d+ E2 H1 H }5 G0 g, S, O. D4 \8 u; {
}
9 k6 e- `' i$ W$ n% b x; D( m7 @5 A7 q( r
9 [0 H, g. Q, b4 a |