登录后可回复主题
您需要 登录 才可以下载或查看,没有帐号?注册账号
x
【 NO.1 找出两数组的不同】9 c9 Y4 Q1 [& E1 J; `* r2 I
+ v+ W6 Z5 o3 {! `3 g+ C5 Y6 P. l解题思路& ^9 ^; b2 ]' C9 k+ O3 C: s
可以使用 sort + binary search 求差集。
0 r- a' g5 U y L! V2 l2 ^
% s# L* w& P7 e2 N5 {代码展示
! l/ ?9 x2 z* C& V+ r
3 ~7 x4 d. w2 {" hclass Solution {, m6 y+ n& S( x6 I
public List<List<Integer>> findDifference(int[] nums1, int[] nums2) {
( E+ P8 E4 ?) O& m l% t$ M5 a, @ Arrays.sort(nums1);0 v& Q9 V. t7 d, A, i# s
Arrays.sort(nums2);
7 e3 }- |& g: U$ Q& J8 p List<Integer> res0 = Arrays.stream(nums1).: Z4 K; X6 e2 u3 k) @7 u# i
filter(i -> Arrays.binarySearch(nums2, i) < 0).; H: h# p; { Q% m. A& F; {9 x+ R9 g
distinct().boxed().collect(Collectors.toList());
. r7 X0 a. D; L0 a a- g List<Integer> res1 = Arrays.stream(nums2).: `6 r. {) ?/ F& I; N, O
filter(i -> Arrays.binarySearch(nums1, i) < 0).
6 X) b! Q& U1 Q$ j distinct().boxed().collect(Collectors.toList());* z2 y7 s3 J! d
return List.of(res0, res1);
6 T6 {: w8 j8 P2 [% T }
. d Q* p* |- u9 e, j+ K' E& z* i}
8 a# X6 d/ C& `) V8 ^% r G8 t' |* v7 C8 g9 ?1 C. `. y) f- W2 R
5 P, m# m/ Z+ \# F3 ]9 v5 \! K
【 NO.2 美化数组的最少删除数】
" F; J. a( Q# G0 o' T5 Z5 ~/ }$ D
( p. o7 J) l: j9 z9 b$ X) M! O解题思路8 D* U4 T, G2 t8 o8 J9 l
从左到右遍历即可。
9 J$ I' ^: `4 E9 @9 E9 p( G1 ~$ D# u# |; ?, w* @ Y0 {
代码展示
) p! ?# C* g+ q" r3 x) O5 o" j' L; l$ ]" F6 r
class Solution { F" U$ c2 S- L. m" I. T3 L2 j; P6 G* f
public int minDeletion(int[] nums) {$ i" Q! B. ?, c) t: x3 i: i/ e, A
int res = 0;
" _' O/ L Q/ S } Y. S0 b c for (int i = 0; i < nums.length; ) { // i 应当和 i + 1 不同+ ]+ N0 h6 G# E+ y( M) ~ l, G
if (i == nums.length - 1) { // i 是最后一个,应当删除6 C7 u& W6 _( k" u
res++;
; c4 D1 O+ V$ {) M; w3 Q: y7 p break;( Q. p1 D: B$ r. c) Y
}
; j' Y" T) y" K! Y+ y& T' o4 V8 `# e8 S if (nums[i] == nums[i + 1]) { // i 和 i + 1 相同,应当删除,相当于 i++
A3 G8 m; p: {# R+ x' K i++;
7 e, ~0 K! R- O7 l res++; q m7 K/ k( d
} else { // i 和 i + 1 不同,可以保留,i += 2 以判断下一组
8 r8 I6 u0 s$ z/ l2 H- r; `$ | i += 2;' G% ^ \+ m& L9 {
}
# \# g. z5 ~: V2 K; r8 D }
% ^" @) y B( ~" J/ [* L) Z- n return res;. X$ ^! {+ Y5 S1 N, y, r2 z
}5 `. P, }/ l% r! u( H
}5 R) p; o0 Z( K7 T( b
! R1 C$ r& e- X6 E! J- }6 A9 t' O
! z/ q! W+ o L
【 NO.3 找到指定长度的回文数】
$ X$ W" g, h5 D$ p7 ]( o& {
/ u' a# ^) l2 u6 J2 R解题思路
5 J) s3 p. w# o2 _6 x0 _举个例子:长度为 6 的第 k 大的回文数的前半边其实就是 100 + k - 1,由前半边复制出后半边即可。+ k8 K0 W0 B" n
) _: R$ ?% T: C1 x% p9 @( U奇数长度的回文数在复制出后半边前去掉末尾数即可。
7 ~3 d; a9 U# k- G* R0 `" f
`3 r# X5 h8 g9 \代码展示
1 x, E1 J& m# @2 }* M1 }- l: c/ g, {0 E* T' U% ^' ~. C0 H
class Solution {/ h/ N; V& N5 m) o
public long[] kthPalindrome(int[] queries, int intLength) {8 r2 ~8 D/ |, E' f6 |8 C4 ^8 a v* O
long[] res = new long[queries.length];
9 u" w F: D) d7 l/ L9 V( A for (int i = 0; i < queries.length; i++) {2 K( P; e1 L/ [
res[i] = kthPalindrome(intLength, queries[i]);
e& r8 B5 u1 e/ n) n" U }
' P% i s0 C, k. [0 { return res;
+ N6 Q. U( M8 I { R2 ` }
7 c* w0 C6 e# u, R
D& l. Q- u8 ] @ // 返回长度为 intLength 的第 k 小的回文数" X4 I, h" F1 e
private long kthPalindrome(int intLength, int k) {
# t" l" A2 s# h% h // 处理偶数" ?1 T+ o7 e, r, B
if (intLength % 2 == 0) {7 F$ k2 Y0 \; \) s3 g& V% r% L
long half = pow10(intLength / 2 - 1) + k - 1;# J6 Z w" y% @; p( y2 [
if (length(half) * 2 > intLength) {
9 D: a) m% I/ U8 d return -1;
# [4 i6 D# i1 [- ` ]: C" z2 ~ }6 r! d3 _$ j' j Z. @/ t- ]5 V, z
long res = half;
( L8 C6 y+ h" R" E# u# \& M while (half > 0) {! y y) c. W; l* T/ N5 h" |1 H
res = res * 10 + (half % 10);
' Q0 G* Z* `9 F: D4 ~ half /= 10;
/ o* E$ T [, a& z% y# Y }
. ^. X; J3 }( \- m* m2 w3 ?' z% J return res;
3 O$ F' X8 ]( `+ C( J- e& o/ G' n } z1 m- z9 M; ~4 H" r3 \+ ]
# g) D) @ l H: i0 p, I! F if (intLength == 1) {9 h6 b p* X, W4 u ], C
return k > 9 ? -1 : k;
$ ]9 E9 p0 g t y }% C7 T2 h: t+ Y5 j; x2 L
# E/ ~! ]9 U! {! m: }- ?6 \
// 处理奇数& s2 v5 M [) \4 o# f& I" ?
long half = pow10(intLength / 2) + k - 1;8 P& F6 o! J8 y% e8 J. A0 s
if (length(half) * 2 - 1 > intLength) {7 v0 G5 L ~1 I8 s; y) V2 h
return -1;) o0 B8 x6 z' v9 m( U. H9 H/ x+ r
}( Z% r V7 I3 F& O0 i) t
long res = half;. Z& U& \* b" |. X- i9 y! o y) v0 }
half /= 10; // 去掉末尾数
- F, t& i: v* a while (half > 0) {/ h( ~& {3 J# @/ X/ h8 I
res = res * 10 + (half % 10);
/ n$ U6 A. C2 v! b half /= 10;
, l) k8 R$ g1 a- z) i8 M$ B$ l }
) R; ^/ `: W6 _0 ? return res;
) ^( L% e' r( F' H }
7 S. u3 E( _$ e3 w
0 X+ N( x4 Y( S$ I2 I: u private int length(long n) {! H2 n" c7 Q' d7 Q' n. {$ K5 l) D
int res = 0;; h* n, J0 y5 Q3 g1 g) x
while (n > 0) {. s6 F" ^6 H) S+ U
n /= 10;) y+ o8 C5 C; b0 Y
res++;+ m+ k) U" c, E. o, m
}$ A) I) G: c2 i" h2 g2 a
return res;. l1 y0 v" X/ _( p, o. k
}7 }+ o) F& j9 `! E6 R; _# h0 g
/ j4 t/ V' i6 F1 i L/ W private long pow10(int n) {
: s$ v F6 ?3 o long res = 1;3 ?4 ^: `0 O- x: x2 j" V. k
for (int i = 0; i < n; i++) {
2 o n& g2 a2 L, d5 S res *= 10;4 }( X+ b7 I/ \( ?: h1 m" C* m( | ^; U
}7 z1 i- ?& a$ W0 x; J* G
return res;
7 s3 s5 d+ S, b }1 s$ _5 l5 Y$ H1 B& u0 J1 c
}( z9 V2 c% V% l6 i) f6 a
/ |: N$ S/ A1 T! V. @7 j* W
& N+ i( C" W' g3 q" F) e* ]" |【 NO.4 从栈中取出 K 个硬币的最大面值和】0 h+ l5 s W2 m5 M# |9 k
7 _$ H1 ?! w* [# G- v解题思路' T; s; ]' m, A: v
典型的动态规划问题。
( @$ D; _8 _" c6 e# p `
8 j- n) p0 z% m定义状态:dp[i][j] 表示前 i 个栈取 j 次得到的最大和。
: X! l, r( b% {8 S$ J+ B9 e& W! P( V- _6 r6 g$ ?# g" V7 ~' S
状态转移:在第 i 个栈取几个,即 dp[i][j] = max{dp[i-1][j-t] + sum(i, t)},其中 sum(i, t) 表示在第 i 个栈取 t 个硬币得到的和。& `$ q/ q9 X- H% ]- s
1 x: }( P5 M5 \1 {9 c L
代码展示/ O; N7 |5 k8 H: x" x+ `
% r r8 f3 f& j: |7 C
class Solution {5 y+ |* W/ H# } F9 ]4 b
public int maxValueOfCoins(List<List<Integer>> piles, int k) {8 c O8 I. v- }: j( `
int[][] dp = new int[1001][2001];& o9 [( m! }9 ?. x2 H' D
for (int j = 1; j <= k; j++) {2 k {8 o" {/ I' I1 E
for (int i = 1; i <= piles.size(); i++) {
* ^* R1 B, E2 e var p = piles.get(i - 1);
1 j! t! f. q' f& W' L; U2 b int sum = 0;3 ~$ u0 \' _, Z" c
for (int t = 0; t <= j && t <= p.size(); t++) { // 枚举在 i 取 t 个 s( s3 e/ R2 M4 Z8 T7 S
dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - t] + sum);8 I7 d$ \3 U2 R, T* z
if (t < p.size()) {
- w1 f. ^/ \6 b3 s: U! }: t! {. L sum += p.get(t);: e- J! o4 A8 U( u: f; O( y5 y" X
}
6 A/ b( w8 ~( i F; ~' l- R4 F6 U, I) ]& D; q+ Q
}/ ~1 ]5 n$ M$ X# g, X3 C4 U( j3 t
}
1 m$ ?' Y) y: T2 V# {; [ }# b) c d8 S3 u* h" c% K5 m
return dp[piles.size()][k];( c$ q; v" x S& f
}4 G6 z# P& T6 R# }. Q& ^: j9 M# U( x* k
}
2 o! v( a. w' k |