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

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

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

UWCSSA提醒您:

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

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

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

登录后可回复主题

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

x
【 NO.1 找出两数组的不同】
# e' g7 B$ I8 P. R# I& k8 U; H, N  q  z
解题思路8 Q, j1 n- v& s1 s5 g  e2 a; _; s$ U
可以使用 sort + binary search 求差集。! w# X6 C8 |: _6 I: e
! D5 |  s! O+ h/ S1 I8 Z; u
代码展示
1 z" T  f- c( L3 n2 y/ g1 [" m  I! W6 I' P% R. h# u: b: N
class Solution {# I4 m$ w, t! b# X
   public List<List<Integer>> findDifference(int[] nums1, int[] nums2) {
) d2 W, N  F% u5 E/ Q( r5 i       Arrays.sort(nums1);
8 |0 w3 z) D0 a1 p: s8 h       Arrays.sort(nums2);
) ?1 t; W8 _! ~4 x4 }( F       List<Integer> res0 = Arrays.stream(nums1).
/ }. [. ~$ H6 V0 c               filter(i -> Arrays.binarySearch(nums2, i) < 0).
* C2 L2 V7 O3 q0 \$ x, o% k               distinct().boxed().collect(Collectors.toList());4 t: @& n& \1 a7 q* f, n: C
       List<Integer> res1 = Arrays.stream(nums2).) ]0 \) p9 ~  {# t& C& X5 K: T
               filter(i -> Arrays.binarySearch(nums1, i) < 0).
/ t4 a; b+ o  ]6 p* S1 D: m/ N2 S3 @               distinct().boxed().collect(Collectors.toList());
% z1 g2 I5 z7 g1 ^5 t- n       return List.of(res0, res1);
2 X& p' |" _3 G1 [& Y/ B$ B  }
& Z% x  A8 U! G1 R' Z# N( b, l}
* P- S9 h3 c% W4 q( k3 B8 D  v% k+ J7 ~6 w3 B& n
* k+ o3 f1 M7 V% l3 r
【 NO.2 美化数组的最少删除数】
& w/ f$ U# A0 U- G- ?3 u* {& O9 \% C1 {
解题思路. H8 }8 j1 T7 }( j4 |1 l5 B
从左到右遍历即可。
0 e1 B( l8 i- f8 \" b9 p# }: w( ]/ g9 |7 m/ |
代码展示
3 q. K: y2 k* L: Z3 K5 H! Y
/ H) D  t! y* P3 y$ `class Solution {
( b/ _8 k2 g; ]! P) s; ]& M- i5 Q   public int minDeletion(int[] nums) {$ e8 ~  a7 |0 `: a
       int res = 0;) v, b5 u, M, H3 Z6 y. c9 m
       for (int i = 0; i < nums.length; ) { // i 应当和 i + 1 不同
8 e+ T5 h" I* y/ b1 }           if (i == nums.length - 1) {     // i 是最后一个,应当删除7 y! E9 K3 i6 O# k$ I0 a
               res++;
8 |/ o: A4 g9 a* @# i; q               break;
4 v* T5 I1 N$ J8 l8 p9 S2 Z* }1 P          }$ S: G; b  S: P& H
           if (nums[i] == nums[i + 1]) {   // i 和 i + 1 相同,应当删除,相当于 i++  s( u: `: C3 @( \
               i++;
) C" o7 R  E6 \; {* K7 s6 D: I               res++;
' Q  ?$ a# ~( n1 m# |. h2 Z          } else {                        // i 和 i + 1 不同,可以保留,i += 2 以判断下一组
, F$ N  I4 k% f/ J+ O               i += 2;
- Z. f+ ?! v) }6 ~# D          }
) U; ]# C6 E' Q$ G9 e% \4 A      }
' T( H5 {4 d8 F- L4 b) L1 n       return res;
2 k6 @4 a5 t* O! E4 e  }
4 y" V+ s; `7 Z6 N: O# j; q}
: _8 _0 ~9 M7 c9 n  P8 J$ }0 C% K" u

, ^; k6 M1 V6 p& r) p: P7 I【 NO.3 找到指定长度的回文数】: F6 G! Y, {5 P6 ]

+ T6 E& u9 v7 w( o解题思路
" K/ O. g& M1 B举个例子:长度为 6 的第 k 大的回文数的前半边其实就是 100 + k - 1,由前半边复制出后半边即可。9 G& f; w9 G  [, J( Q  F% U0 |

0 C+ ~0 i: e7 V奇数长度的回文数在复制出后半边前去掉末尾数即可。$ p7 |, Q: ]6 {1 d( U5 n

+ O; D9 Q6 f: l( G代码展示
  q" S. O1 X/ x) i: \: H
& X( _  z3 Y2 eclass Solution {
% w4 k6 u' c9 i2 k" J   public long[] kthPalindrome(int[] queries, int intLength) {# _& X3 T9 J7 W, W, x. X( _
       long[] res = new long[queries.length];
# g, M) X8 p: o5 h+ {       for (int i = 0; i < queries.length; i++) {
# q: R% L5 G! ?           res[i] = kthPalindrome(intLength, queries[i]);
6 L% J+ ?8 o- Z: b. j      }& L" _/ y" s  ~0 ~% g* ~
       return res;
" ^& U- R2 u6 \; n  }
' M- S, `, s' Z9 d1 p; n$ u% @/ b: Y5 B. ?
   // 返回长度为 intLength 的第 k 小的回文数! ?; ?' v  Z& |5 ^
   private long kthPalindrome(int intLength, int k) {# {. n8 p" f2 f" J6 l
       // 处理偶数
. k. ~( V2 o  c+ @2 x, `       if (intLength % 2 == 0) {4 j7 t. E" r2 p3 F4 L8 l
           long half = pow10(intLength / 2 - 1) + k - 1;0 L0 L4 |7 [0 U5 ?! g8 h
           if (length(half) * 2 > intLength) {
4 m  p$ I& V, S3 Z: ]               return -1;, t) W  c' ?$ H4 L3 F* @
          }' ^8 a' S4 j- ~
           long res = half;, R8 l' e' V2 i9 I6 f
           while (half > 0) {7 x0 |. O5 R/ F3 P9 l. [7 G8 S1 s
               res = res * 10 + (half % 10);
6 g2 f% ^3 s$ V7 C               half /= 10;: l- J4 Q) ?4 ]
          }
" g4 _& g  P5 S* D           return res;
$ M" d7 }7 @, w" @* Y5 s- A6 b% D      }! {1 k6 `; R+ f# z% o

6 h% N' e$ x( ~3 D; }+ t! R" B- \% _       if (intLength == 1) {
3 \- s' ?, x; b6 u5 W3 m0 ^! @6 o           return k > 9 ? -1 : k;
* q* x/ }& p  \7 _- z, i1 X7 M% C      }
$ |5 @. t/ j5 J3 n
8 Y- v" ^; K) A4 N2 l       // 处理奇数
4 Y& Y7 _" i- z; K1 b       long half = pow10(intLength / 2) + k - 1;, V4 Q! f+ l, p
       if (length(half) * 2 - 1 > intLength) {, J8 A( v. A, i3 w: w
           return -1;5 U. `- Q' N( ~; o" X; F% J
      }
4 {6 q( F. [* X3 h       long res = half;4 K) d. F1 y. ~4 A% i: P8 y0 [4 x
       half /= 10; // 去掉末尾数
6 }( c/ l6 r/ {# G( f1 ?8 T9 N$ A       while (half > 0) {
, Q& t' [) N, Y' H4 @" A- A$ D           res = res * 10 + (half % 10);$ L- e+ h9 ^+ [5 V- \6 q3 g
           half /= 10;
8 U- O9 M1 E4 W      }
% V4 L) _+ I# x6 g0 s6 l* g, l       return res;
/ P/ \, C* A. M6 ]  }+ `$ a1 U: w9 C8 a

! L# ^0 x% p; l0 R7 r; g1 r6 d   private int length(long n) {
! D% f: ~- k+ c: s2 s  d; k6 t3 ]       int res = 0;1 t3 A; s; J9 z
       while (n > 0) {# }/ V3 [# z1 T4 C2 e
           n /= 10;$ ]! V9 w2 v3 f7 l8 [0 }* G/ u
           res++;5 L1 U7 ?* N3 r; {+ m$ T
      }! h, q8 z) j: ^2 m- p% [  x' W
       return res;, L$ [* j6 z% L) u
  }' H- I1 K5 ^& z# u4 z( e" @4 d

: p" j- p: O- w, H2 k) M2 _$ i   private long pow10(int n) {
: C" q( x# q% I5 c5 @       long res = 1;
; o! F7 j2 J* i6 [       for (int i = 0; i < n; i++) {6 Y8 o6 n; I; U% D& T: ~
           res *= 10;5 D8 z. t2 h( }7 b: g
      }
8 t/ `- N9 J' Q# I& l  E( y6 Z6 l       return res;6 }0 R$ @! y3 s8 F7 [) u
  }7 N5 @; P/ L7 w
}
, D1 S; N$ h7 d. R
3 R7 n8 g3 X6 F, f
. v) Q. B6 W9 S& A【 NO.4 从栈中取出 K 个硬币的最大面值和】! q! k* p5 e5 ?. Y  B. h2 o

0 c2 a9 k9 }" y1 w# u解题思路
6 d$ f! h( o$ Y" D0 z/ I典型的动态规划问题。
/ |) p7 P/ [" u( p/ {# s+ ]' C! q6 I, _/ Q6 |# P6 z( w  M
定义状态:dp[i][j] 表示前 i 个栈取 j 次得到的最大和。
: D* n2 N& f. c5 P' q; N, I/ \' v: D7 I: q& h- a
状态转移:在第 i 个栈取几个,即 dp[i][j] = max{dp[i-1][j-t] + sum(i, t)},其中 sum(i, t) 表示在第 i 个栈取 t 个硬币得到的和。
. r! @) N3 f7 _+ A/ d+ {8 W0 r, m% n, d
代码展示
! J0 e$ D2 T9 O8 u4 \4 e* _; E
/ H0 l  |! y! X2 z7 F/ x. {class Solution {" ^0 Q6 `/ u7 r/ X6 w9 ]+ E2 b2 o
   public int maxValueOfCoins(List<List<Integer>> piles, int k) {6 h% \' x8 [: z9 b" o; [7 e
       int[][] dp = new int[1001][2001];, h' [: N' J! [, @( T% R
       for (int j = 1; j <= k; j++) {
/ A( H! n2 B; B& M- y' ?           for (int i = 1; i <= piles.size(); i++) {3 f5 X: I3 L/ {' ?6 ?, t  z% F
               var p = piles.get(i - 1);
; |# A. V+ t1 W* V  y               int sum = 0;4 @" I; O2 `' a+ V
               for (int t = 0; t <= j && t <= p.size(); t++) { // 枚举在 i 取 t 个
3 z) j7 V8 E% ^! ]                   dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - t] + sum);
3 z( Z3 @1 `* S0 B                   if (t < p.size()) {8 l) R5 B5 Q. P7 S/ a/ ~
                       sum += p.get(t);( Y4 A/ \8 G) ]4 M! W5 ]5 |
                  }
% w3 f# p0 h4 j0 ]/ y5 D$ V9 m! k4 Q2 ^, U6 ~
              }
  `; X# u7 o, [. ~: R. o          }
7 l- \4 R8 n- I      }
7 q; M) u! X5 c       return dp[piles.size()][k];1 e5 e  g" _# r7 }& @+ b
  }  f! h( I! C, S) ?" z$ `& ?
}# v! Q3 w- C3 Q
您需要登录后才可以回帖 登录 | 注册账号

本版积分规则

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