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

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

上岸算法 回复:0 | 查看:1823 | 发表于 2021-10-10 21:06:08 |阅读模式 |复制链接

UWCSSA提醒您:

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

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

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

登录后可回复主题

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

x
【 NO.1 至少在两个数组中出现的值】4 t% j( a/ @* C$ X

. v9 |! |, g/ I. N6 {解题思路
) B( f! p8 o5 \+ \( g签到题。
5 T( Z: g, M( I9 U3 e8 T) x+ G7 T$ q! s! d
代码展示
: r- H4 Q. \9 x) ?) I7 Z9 l) S1 \
5 e: j7 n, a9 ]4 z, m0 K$ @1 fclass Solution {
# G; \/ y  t( m; i* I, C7 n0 v) C   public List<Integer> twoOutOfThree(int[] nums1, int[] nums2, int[] nums3) {
  \3 j: ?% c- s1 [: x  h       int[] count1 = new int[200];
$ z: d) ?  f, [- Y9 I       int[] count2 = new int[200];
& C* `* P" ?. d& r' x       int[] count3 = new int[200];- ?' \& [4 \: \4 z5 B: a/ L
       for (int n : nums1) {* `* R# T  I% p- f" `
           count1[n] = 1;
/ `; m% f0 g+ j% [      }. s4 _- t* t3 R% W  u
       for (int n : nums2) {9 P' s) B3 _" f/ X& p$ }* c2 G
           count2[n] = 1;' J5 `4 H$ y; J" f
      }6 G6 E! U. T" ?
       for (int n : nums3) {
0 y7 d# w. {$ P) H           count3[n] = 1;
) d( t. Y& u3 M: b: a      }
! W) F8 @9 S) k$ Q/ j( T       List<Integer> result = new ArrayList<>();5 }, O; H% P# s
       for (int i = 0; i < 200; i++) {0 O3 ]% w! F3 s5 z* g$ N
           if (count1[i] + count2[i] + count3[i] >= 2) {
5 b  M6 l% s) u. e* L               result.add(i);( K/ P4 D6 ]) j: g7 c4 u
          }9 F% I1 Y" {( t5 Q0 D" h; f: Z
      }0 f: t3 U+ i( I- q7 R
       return result;
: E0 o, }, f0 M" E" Z3 m& H; t7 H  }
8 w" k  U1 v7 @3 @4 t0 a# i& o}
( s  t, Y; w3 l! t9 p$ E6 ^1 ?
【 NO.2 获取单值网格的最小操作数】' j: c5 p: A  Z6 u* U) j
1 d, a. q% |6 t; T! U" ~
解题思路8 j, D* u  [) }9 A5 l! g
网格可以转换成一维数组,然后排序。4 b' b+ E. u8 t( W3 ~7 Z3 s
' |' A8 x  E. k+ x0 b
不返回 -1 的条件就是:任意两个元素的差都是 x 的整倍数,我们只需要检查相邻元素即可。3 M, }) y! `( T, \
, m; O  W  N, i! {
然后枚举最终的唯一值,可以利用前缀、后缀和快速计算出把所有数字变成该值的操作次数。7 V  n8 ^! k  O' V7 H6 G
  H2 @+ d' _* a! k! o
代码展示7 ~9 l* r+ I* }2 d, }6 t  ^# A# X4 _
, c  ~# \* l  J" H- g( U, A3 z
class Solution {6 u: @- E0 g, l2 d! l
   public int minOperations(int[][] grid, int x) {  O( o( e2 b0 _. v# Q
       int[] arr = new int[grid.length * grid[0].length];  c. [! E: U8 A% q, x3 B- W* f) Q9 f
       for (int i = 0; i < grid.length; i++) {
: y7 r& o" P% \           for (int j = 0; j < grid[0].length; j++) {9 }5 l6 S; R6 Y; [" \2 _0 @
               arr[i * grid[0].length + j] = grid[i][j];
0 L4 O" _2 `( J" r4 Y9 t+ q4 N: Q          }
/ @5 m0 g% s( K5 [      }. Y2 n" h% h7 u4 `1 l! A9 U; I
       Arrays.sort(arr);" {. z4 F$ u' g9 U2 i# f8 v
       for (int i = 1; i < arr.length; i++) {* c% c5 W7 r! Q4 J, y* C
           if ((arr[i] - arr[i - 1]) % x != 0) {
3 B/ C  |( T" g* X- K  k6 |& @7 r               return -1;" l3 c6 I4 J" X4 I; Q8 Q9 u3 `
          }3 x& @, K. W( q# m
      }3 h' s+ ~: ?3 ?8 }# x' i( E
       int suffixSum = Arrays.stream(arr).sum();# w. I9 E. L7 j% z/ R% V$ ?
       int prefixSum = 0;$ @4 R+ t% z, ?8 ~7 m; J
       int result = suffixSum / x;
# [$ i; Q% R3 b* d* m* p! F* S. c- V       for (int i = 0; i < arr.length; i++) {3 H0 B. _  y9 Q
           suffixSum -= arr[i];8 Z2 D2 F% T/ P  z6 z+ i
           result = Math.min(result, calc(prefixSum, suffixSum, i, arr.length - i - 1, arr[i], x));
# j( F9 H  Q- n8 \- X7 C/ d           prefixSum += arr[i];& U: ^  j/ d+ h' `- ]* Z
      }
) k0 a! _! {8 x4 q7 k# d       return result;0 z: L1 z8 o% N% l
  }
1 g9 o) [" X- C  G1 T5 b
$ b6 {4 D) u: _: A; c   private int calc(int prefixSum, int suffixSum, int prefixNum, int suffixNum, int target, int step) {) x4 c3 C/ b/ \9 @
       return (prefixNum * target - prefixSum) / step + (suffixSum - suffixNum * target) / step;# p! u5 H4 F$ E* y4 Y; E6 V
  }* d' c5 p; L. a
}
0 U5 y% ?/ N- n0 e6 H' J
) k* R, T- J8 L/ ?, t, U+ b【 NO.3 股票价格波动】
/ A0 o( o2 @  }9 ?9 _& V2 f3 V; f- ?4 ^4 r" L
解题思路
8 ?. S& |: y  X使用两个 TreeMap 即可,一个储存时间戳到价格的映射,一个储存价格出现了多少次。
) L& A$ c$ u, @
, Z' o3 u# d- y7 T代码展示
  x9 o' U1 f6 f" j: ?) U  S$ ]7 y; Y  r/ h4 X  O
class StockPrice {3 d( X+ |+ J" c! n- p8 y
: S. n$ i: b. u! K
   TreeMap<Integer, Integer> timestampToPrice;
/ a: o, d2 ]  G9 b! S   TreeMap<Integer, Integer> priceCount;
. I6 ?: ^( V/ E" \7 ?0 c" ~% Y
% O* u  s/ E: H& j/ f   public StockPrice() {8 T+ ?5 y4 C% G
       timestampToPrice = new TreeMap<>();+ b. e% D* R: [: c" l7 P5 w
       priceCount = new TreeMap<>();9 r9 G! A4 l5 B/ s- t* l
  }
3 B1 q; E. F$ A# \0 o# C% G. ^! Q" l5 ~- L6 n; h
   public void update(int timestamp, int price) {
6 w  |5 B! o2 M% r9 ^       if (timestampToPrice.containsKey(timestamp)) {0 R% Q8 z) b; z8 A+ z# F' \1 m
           int oldPrice = timestampToPrice.get(timestamp);
: r6 W# {9 n0 U. }, l/ t7 }! ]           int count = priceCount.get(oldPrice);/ s) J2 C7 b5 U/ N' K, |; R
           if (count == 1) {
# z1 x( S' {. |: a: d+ f               priceCount.remove(oldPrice);) A! E4 l% q0 n* Y+ S' {
          } else {; u+ X$ p5 @! R
               priceCount.put(oldPrice, count - 1);
5 K$ J5 _( z6 l" X; p& f# e) t          }, _- y6 F4 k  F" C: b3 j
      }
$ [! ^6 U* |# j8 ^       timestampToPrice.put(timestamp, price);4 r/ V0 n% ?  ~
       priceCount.put(price, priceCount.getOrDefault(price, 0) + 1);$ i1 s) I2 k! |  K
  }
* I, ?& \4 _+ c% R- U5 s' ]5 T# R6 `0 O% W5 E: e
   public int current() {
- I1 |+ c0 ?' R4 a       return timestampToPrice.lastEntry().getValue();
4 s1 ~. o7 C3 i& d  }
, W1 Y) j' T; Y
9 w; T, a7 f% N1 _$ f+ c   public int maximum() {
' p5 F8 n! b4 `& J8 A       return priceCount.lastKey();
/ o. R6 s- r: `( i$ M; W* p  }5 c7 u( P& o% H( t7 M
- [) h0 s) ?" y4 B& m
   public int minimum() {
; s+ l1 m9 f& M% t# E9 m) u. Z       return priceCount.firstKey();
) p! C$ E4 a* d  Y, q  }, C* h6 [; t3 y0 c1 R
}
! [4 a: `' f9 d4 ]# w! Z5 Q1 x" E: B8 f+ R
【 NO.4 将数组分成两个数组并最小化数组和的差】0 J( Q3 G& l7 w2 {9 Z9 B

: M3 A! f2 q+ \& \& }解题思路
/ n; f# m7 p; k8 Z% l' m& d: h7 Z& f1 d( _' A; U
枚举 + 双指针,具体思路见代码注释。
% A- w, H3 X' u4 a/ f, f: b# V* |  p/ i0 C6 D4 x  O
代码展示* Q/ q' Y7 C& @4 O
2 u& _8 x8 q9 d- h( |* [
class Solution {
/ r, L, r3 J0 H, }* B   public int minimumDifference(int[] nums) {
: z5 K' j' b1 E, W- q3 Y: K. ]  S       int half = nums.length / 2;1 R% F: s" g+ ]
       int[] half1 = Arrays.copyOf(nums, half);- P8 t* `  e$ H3 F8 z# a+ a; l
       int[] half2 = new int[nums.length - half];
0 w$ _. E$ g7 }+ ]5 y       System.arraycopy(nums, half, half2, 0, half2.length);
& R& o7 }7 Z3 B# i       // sums1[i] 表示从 half1 中选出 i 个数字得到的和的所有情况,并且从小到大排序) m9 V- \, F+ J) @
       List<List<Integer>> sums1 = getSums(half1);
- Q0 D7 M& V/ a% D) B9 j. s       List<List<Integer>> sums2 = getSums(half2);
0 x  Q6 L; p% F2 P       int sum = Arrays.stream(nums).sum();
/ I8 `3 V9 o9 t5 y2 q8 }       int result = 0x3f3f3f3f;
2 f- Y( ~5 @+ W0 f( K  P       // 枚举从 half1 中选出 select 个,则需要从 half2 中选出 half - select 个+ P1 G% [1 W! y
       for (int select = 0; select <= half; select++) {/ H1 S6 p; k+ @3 F$ D
           List<Integer> half1Sums = sums1.get(select);) {! ~' P2 Q: d: ~2 z7 u, X4 I
           List<Integer> half2Sums = sums2.get(half - select);0 a+ v0 [- Z& |* _, N
           // 从 half1Sums 和 half2Sums 中各选出一个数字,使得它们的和最接近 sum / 2: ~) E( \8 w4 C0 w# H6 [0 g
           int i = 0, j = half2Sums.size() - 1;
" G" r- w0 i7 Z* h9 S$ O  P1 B* U           result = Math.min(result, Math.abs(sum - (half1Sums.get(i) + half2Sums.get(j)) * 2));
# V4 R: e# }5 G0 Q           for (; i < half1Sums.size(); i++) {  a& a9 ?7 ^! \4 L
               while (j > 0 && Math.abs(sum - (half1Sums.get(i) + half2Sums.get(j - 1)) * 2) <= Math.abs(sum - (half1Sums.get(i) + half2Sums.get(j)) * 2)) {2 J  H. }2 z0 h( J
                   j--;( ^* l$ T2 I- {1 k8 k- Q) T  m
              }8 `( `; ^8 q& \; ?# J7 X
               result = Math.min(result, Math.abs(sum - (half1Sums.get(i) + half2Sums.get(j)) * 2));
) _0 B+ d6 l3 b3 _( j1 S& h' A( m          }& ^7 _- p$ Y  ?2 N' A
      }* g# u7 m5 l0 A
       return result;5 f5 ]3 g. C5 N
  }
: n! R) s/ |+ c3 N" Y
6 M* ^" {, [: h   // getSums 求出 nums 的所有子集的和4 ~7 X7 ~- Z2 F1 q
   // 返回 List<List<Integer>> sums
" L3 X, b! V! ?+ o. R' o   // 其中 sums[i] 表示 nums 的所有大小为 i 的子集的和# l  u; k- b1 p) O# o- o/ ?
   // 去重并排序
2 i* h  r% K, h: b9 @   private List<List<Integer>> getSums(int[] nums) {. h5 R9 Z6 @$ _# z0 f) J& ]
       int n = nums.length;
8 M; A* r, E: H3 U, I3 n       List<Set<Integer>> set = new ArrayList<>();4 ~- w9 T; K# r3 _: X; `% u
       List<List<Integer>> sums = new ArrayList<>();. i& I7 I9 L4 v( \
       for (int i = 0; i <= n; i++) {9 F" O3 u2 I) ~! i3 b* `3 N/ I
           sums.add(new ArrayList<>());
! P3 I% Q2 i/ Z; }- ~  v# T* p1 U& s           set.add(new HashSet<>());
. |2 f9 f  y4 v( w# \      }* V2 Y/ J0 w  R$ I: F/ F
       for (int i = 0; i < (1 << n); i++) {* N$ e' x& v7 s
           int sum = 0;- ?9 x# O  n% w8 x5 g; B$ |. D
           int num = 0;
  c: j* Q; d( [& T% P: E. @           for (int j = 0; j < n; j++) {
3 j* B% \+ c! o$ q! b9 _3 I               if ((i & (1 << j)) != 0) {+ p/ L0 v7 C8 S. E
                   sum += nums[j];4 _  y# q, ^4 ]% `& m: `2 N7 J
                   num++;
7 v- _' t/ R, n! n9 e6 ?6 T" G7 K5 ?              }
6 h) d9 K$ \2 V# G. }% |3 h          }
# o/ N9 Q# q& `/ m# j) ~6 s/ u" `           if (!set.get(num).contains(sum)) {
5 s& y2 S" G- d5 P               set.get(num).add(sum);1 s/ Q; @) H2 z, ^  E
               sums.get(num).add(sum);' t$ _: w3 v! y7 R  }" z  J
          }. t8 b: |5 P+ a7 {. ^, L8 w
      }9 Z9 e  `- o+ v4 d+ b9 X
       for (int i = 0; i < n; i++) {# h/ U6 c; l4 c
           Collections.sort(sums.get(i));4 p$ X( T$ Z* E( ]- F( K8 j
      }
. p2 E# }0 ~2 ?+ E/ m  {0 H       return sums;' H/ p! {/ u4 o6 s# E
  }7 |- U2 Z# [+ h$ A3 {# A4 v
}
您需要登录后才可以回帖 登录 | 注册账号

本版积分规则

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