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

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

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

UWCSSA提醒您:

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

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

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

登录后可回复主题

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

x
【 NO.1 找出两数组的不同】& B% H0 U, u; q! B; G1 Z0 t

' W5 Y7 j: E8 o& ]& @解题思路5 v* T3 }9 F; F& k) |/ `* ]
可以使用 sort + binary search 求差集。. ~" \( r( t$ t
* Q- N7 D: r& g  V
代码展示
. w3 u- |6 F4 C8 d9 F
0 |" N- y' w1 w# y3 Fclass Solution {, L- r; c+ [* d2 c
   public List<List<Integer>> findDifference(int[] nums1, int[] nums2) {
! J3 D6 H5 j, X5 |+ r       Arrays.sort(nums1);
8 I8 n3 M6 p0 Y( F: f       Arrays.sort(nums2);, {/ @0 w8 }4 P' n7 ?
       List<Integer> res0 = Arrays.stream(nums1).
8 L. v' w. n5 E6 E. J$ O/ j               filter(i -> Arrays.binarySearch(nums2, i) < 0).( x8 e. y% w, d) z1 ^  O
               distinct().boxed().collect(Collectors.toList());( |/ B0 s4 i& O, X! c7 Y+ @6 n/ X
       List<Integer> res1 = Arrays.stream(nums2).6 A! z1 K" X' |: l2 K  o& n1 Z% Q$ [
               filter(i -> Arrays.binarySearch(nums1, i) < 0).
+ w2 z8 J" ~+ T) n% K. B6 d               distinct().boxed().collect(Collectors.toList());4 H& v8 X- [8 B% r8 ~- K
       return List.of(res0, res1);! f- c% O! w3 s& v! T
  }1 T+ j5 J, t4 n" Y  K
}
% A* T- ~2 A! w; N; g  F. U3 Z$ M* \& d+ @0 k% _
8 t/ H. J6 h' v! c& r+ G- w3 w
【 NO.2 美化数组的最少删除数】+ x0 z2 U# B1 @+ q; }; h* y
& {1 C9 @5 C+ Z) L" f* I0 N% o
解题思路& B2 A) Q5 S. h: ?! l
从左到右遍历即可。) @9 L5 \0 U' L3 A3 q* Q! A

/ K8 J& B; P$ d1 G! `) _' e/ }代码展示- p' y4 t, W5 k) B# u& J
( V4 ^# b' L0 b5 V
class Solution {
# }9 A  P8 |- z- e   public int minDeletion(int[] nums) {
6 B: T3 W. u7 \' v  n7 O$ v       int res = 0;/ I8 \, L( B" k. R  T* O, j# A! `
       for (int i = 0; i < nums.length; ) { // i 应当和 i + 1 不同+ @8 I. c; Q3 v+ T5 @- G' d3 Q1 V
           if (i == nums.length - 1) {     // i 是最后一个,应当删除0 ?) I% b/ c2 P  w
               res++;( n0 r$ g. r# o% m7 f) Z
               break;$ O9 p$ ?7 L4 ?' }
          }# A4 R  E3 G% \  ^* e( l# s
           if (nums[i] == nums[i + 1]) {   // i 和 i + 1 相同,应当删除,相当于 i++
3 q) A. Z" g6 Z1 t. h8 o. G/ U% O               i++;3 P; s( T; g- @: M( R
               res++;
6 d; U+ o2 p4 f2 C7 K3 |& b/ x          } else {                        // i 和 i + 1 不同,可以保留,i += 2 以判断下一组
) N1 X' B: P' U+ ^* b               i += 2;6 B' n  x# @: l7 L
          }
! H, m- m+ N# w3 |6 n+ o      }
& R0 L+ p* `; g       return res;, R$ ?; [8 Z- d+ G: J: z2 B
  }
- V$ G( _% S* Q" S6 f% r7 s) l}. S* Q' X: E" z

7 n# h) S( K9 t' U& U/ D2 U% I7 W" [
【 NO.3 找到指定长度的回文数】
% u& |- I. g3 v- _! {/ ~* |
" G( _+ S2 S$ y! M# O# S$ z解题思路( L: E6 l( y& @  I
举个例子:长度为 6 的第 k 大的回文数的前半边其实就是 100 + k - 1,由前半边复制出后半边即可。0 Z6 k9 ]/ n, N' F6 F; P  ~
, s4 d. b. c. E$ [" ~
奇数长度的回文数在复制出后半边前去掉末尾数即可。
2 r) F7 v6 k3 T: E2 m! Q  ?; x8 D
& x6 I/ Y! j5 b4 r4 i: C9 u代码展示; @" `8 e2 u" T+ m  N. ~9 T6 w; w

, H" s: S  M% dclass Solution {
% y+ n3 L5 x1 ^! N   public long[] kthPalindrome(int[] queries, int intLength) {
) z" r" Z: v5 m- h. M; `       long[] res = new long[queries.length];0 l, L8 n. A7 H( L, b' u" W
       for (int i = 0; i < queries.length; i++) {- q% Z6 v2 C5 ]) ]" k% F
           res[i] = kthPalindrome(intLength, queries[i]);* i( Q' ]; `+ s( M6 _: I7 m$ `1 _) R
      }
) k. b# B1 B1 m0 W1 P3 K9 p       return res;
. l/ w* J. k: \4 B7 Z  }
/ x7 s) H5 V. D+ e$ r" O
( ^, X# E, T7 i+ D! _% _6 `   // 返回长度为 intLength 的第 k 小的回文数: i. H7 c! P& E8 g8 Z1 D
   private long kthPalindrome(int intLength, int k) {
& Q5 y% m2 m- X5 x4 I1 r- U# G       // 处理偶数3 C& Z( _$ \8 p& }$ v" c, _$ B
       if (intLength % 2 == 0) {4 P& H5 ]" d& `" T- z- S, H
           long half = pow10(intLength / 2 - 1) + k - 1;
3 {* h5 e5 g3 ]8 @5 u           if (length(half) * 2 > intLength) {$ J5 H% h7 @( P3 m# l4 i8 {  M, q
               return -1;$ A' P: u0 a- [
          }
" C" c" B* q' k# R9 B- v# q9 r           long res = half;
9 H8 m8 k8 ~6 Y5 r# a' H, Q           while (half > 0) {# `; A+ ^, N& s/ v! L
               res = res * 10 + (half % 10);# f& Q. c- W; O/ T; B* B) a: w
               half /= 10;1 N, e' V/ c+ W, {$ V
          }
. f9 n- k0 M' _           return res;  b( i1 g6 [. f; \8 s# ~% W2 E) J# A0 ?
      }1 r2 K6 E6 i6 m% z1 B* j7 k, P
) h  g1 w& U  ]* D4 |. j
       if (intLength == 1) {
" `  M1 D! D& Z8 F1 Q; ^           return k > 9 ? -1 : k;
4 b: Y% J" h4 C/ R  w& ?      }
8 D2 y2 N4 `+ S0 g1 g6 |/ R4 S$ P/ U4 |( V
       // 处理奇数4 O! J2 {- [& ^5 k" n: ~4 L
       long half = pow10(intLength / 2) + k - 1;0 P& W+ C: ?# B1 |+ G6 Y
       if (length(half) * 2 - 1 > intLength) {
' b$ ~4 f+ |$ A( B' y0 |           return -1;
3 D& Q5 M7 y. e9 u      }
2 i1 Z2 \" i+ R4 U# o. H- g7 G       long res = half;$ z! S1 z5 L" w
       half /= 10; // 去掉末尾数
5 M: }3 B0 L2 B% V       while (half > 0) {# t9 E, g" X- d' P3 E: b9 N
           res = res * 10 + (half % 10);: @5 j( N$ |/ \' U' l
           half /= 10;
: Z4 J, \9 U! T# g2 K! u      }* k8 ^8 ?' O& O8 D2 r
       return res;
* W' e9 \/ Y7 w# D: Q1 U- q  }5 D) W2 k+ G6 b  N* _+ _

1 i4 G: X! Y# o2 V   private int length(long n) {
3 P$ |5 t4 d: @' g       int res = 0;
5 F/ e, |+ r, f& F, Q) x2 @       while (n > 0) {
: X$ F8 F6 o& n# n/ i% g           n /= 10;
% N. y) F4 M' S2 R+ Q           res++;. q, ?9 `. b! ]2 F1 g: A& J
      }1 M1 i; g, l' P+ A. C
       return res;- S5 `" Q- \; A
  }
% b8 u! I+ M# R& r) d. f6 j
' e5 Y# y7 e: [  ^5 C   private long pow10(int n) {
* [- C. l% R  K9 M) I/ T2 O6 [% g3 F+ R       long res = 1;
6 C' S5 f( D# ^       for (int i = 0; i < n; i++) {
  D+ w7 f* d9 w' [- o           res *= 10;) M+ o- v$ w/ s8 m- Q' M* E7 a) a* b
      }5 l% m0 E: c* _
       return res;( B( o% ?/ j( c+ W. L9 p8 H; U7 y
  }
- l) ~! p" i4 g1 p}
/ b5 \0 a# G% E- Z) j; u5 ~/ d' o4 o9 M) F
5 r/ l+ l6 V) q6 s7 |1 X
【 NO.4 从栈中取出 K 个硬币的最大面值和】
: O: c6 b- o2 r( i7 s3 ^
' n4 a  A. d/ n, k  e解题思路$ K  \' S$ g/ S( h0 k8 ^
典型的动态规划问题。
" ?* j7 g; X. X* B8 u% j: ~2 o* [5 f; t* Z9 E6 k9 p$ K/ t  R
定义状态:dp[i][j] 表示前 i 个栈取 j 次得到的最大和。
9 D8 {; ~9 r, ~
- l3 B5 m/ N9 d* l  _: C状态转移:在第 i 个栈取几个,即 dp[i][j] = max{dp[i-1][j-t] + sum(i, t)},其中 sum(i, t) 表示在第 i 个栈取 t 个硬币得到的和。7 {- p; R9 {) [& Q5 X* A& O  t
3 {# T! g" w4 p1 x; U! [$ J
代码展示
) x5 e/ [9 r) ]5 ~& S: @& J0 k. L- A7 a) t
class Solution {
  o$ A' B1 S$ ]% n2 I$ w$ j   public int maxValueOfCoins(List<List<Integer>> piles, int k) {
" R- H5 ?2 J0 m2 q  {       int[][] dp = new int[1001][2001];
9 b5 v6 G0 {/ O1 l; g' n  t       for (int j = 1; j <= k; j++) {
- `* G$ U4 s) N5 R) `           for (int i = 1; i <= piles.size(); i++) {& A7 g, @8 ~! v2 C5 X4 a
               var p = piles.get(i - 1);
8 E& n0 J; ?$ Q" O* L               int sum = 0;
+ V) O/ S" Y0 A! f6 o* p, c               for (int t = 0; t <= j && t <= p.size(); t++) { // 枚举在 i 取 t 个8 u1 ]& n( i* d
                   dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - t] + sum);+ j* k  @/ t+ b3 }" c5 b$ X- x& q
                   if (t < p.size()) {& w5 n7 ?, r( ^' y& I7 n
                       sum += p.get(t);8 P( ~* M6 K6 ~; K2 a* i: L& t
                  }
2 N% z9 c; h& Q" n* _7 N: v5 s6 W2 v9 V* q+ w* }6 |
              }- h. I4 @% A+ ~& e8 v6 O
          }
2 ^; a+ R$ y5 [1 d9 }/ _; L      }
9 s/ p5 g! N0 e$ i0 u- N+ A       return dp[piles.size()][k];
1 V! G* U  m: s4 H' s) i: ?  }
2 n% N- W9 e" s" e2 c1 n0 ^: s}) t: T) @/ @2 |) p7 w; _+ S1 S. u
您需要登录后才可以回帖 登录 | 注册账号

本版积分规则

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