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

[吹水聊天] 上岸算法LeetCode Weekly Contest 286解题报告

上岸算法 回复:0 | 查看:1374 | 发表于 2022-3-27 16:58:22 |阅读模式 |复制链接

UWCSSA提醒您:

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

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

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

登录后可回复主题

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

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
您需要登录后才可以回帖 登录 | 注册账号

本版积分规则

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