找回密码
 注册账号
置顶:如何加入2024届新生微信群

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

上岸算法 回复:0 | 查看:51 | 发表于 2022-1-9 21:41:18 |阅读模式 |复制链接

UWCSSA提醒您:

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

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

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

登录后可回复主题

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

x
【 NO.1 检查是否每一行每一列都包含全部整数】8 f1 _5 ?  Y7 J, _6 ]0 ~- f8 b
8 r5 S! T2 N7 {/ s
解题思路
* K/ N% T. g, @) a, X& u+ {签到题,可以用排序做,也可以用 Set 做。9 S: F; G' n, Z0 |/ H- s
1 H( v" G$ ~( L" k7 ]$ q9 I' A
代码展示' ?# L- s0 r  ^4 Y, D- I3 w

/ m4 V9 i7 B$ f! m- Wclass Solution {
: F! S& v% h2 y; y2 ^/ u   public boolean checkValid(int[][] matrix) {
/ K7 W$ a" I9 w       for (int[] mat : matrix) {& ]+ T4 m/ O' ?: H/ N
           int[] m = Arrays.copyOf(mat, mat.length);
+ X+ A4 |, h8 n4 |0 U% m           Arrays.sort(m);
1 R6 i- j1 c' S9 l9 {           for (int i = 0; i < m.length; i++) {+ T  N4 a& g$ k+ N
               if (m[i] != i + 1) {
0 e8 ]& C: \$ Y3 \: N+ X4 f; d3 k                   return false;; H6 G' ^: q* O5 v
              }
9 P, A" ^- Z" @0 i* X          }8 ]/ P; h: y. j5 [
      }
$ {3 `: Q* }! m9 `, c       for (int i = 0; i < matrix.length; i++) {! [' K- ?+ E: ~: H
           int[] m = new int[matrix.length];
. ]& L) R& C$ ?3 ~/ e           for (int j = 0; j < matrix.length; j++) {* F5 C) G2 K- T7 J! e5 L
               m[j] = matrix[j][i];
5 T* d: T' F) x9 @5 ^  [          }5 k$ ^5 a, @0 {& ~. P* W0 A2 G% p
           Arrays.sort(m);
' D- N' P; z1 X! c           for (int j = 0; j < m.length; j++) {6 X2 p' J! Q% m$ H$ Z
               if (m[j] != j + 1) {  h6 L- f. V# j4 {9 E9 n
                   return false;1 b9 b, l4 h7 l. l- h# b3 n
              }& g% g( {, ]3 X) z3 t
          }
1 w6 n$ T7 q% Z! V3 T      }* ~6 E/ ?6 P+ O  m0 r
       return true;5 D3 L5 X( f" Q8 o/ C6 C
  }5 R- ^4 J7 ?& K+ T' a- D
}4 |; l  L' ^$ q' E- l! |; _7 X
9 [- J: y$ S7 j: y0 Z- Y, B

' T" v' J. N# R0 w% c9 z, k【 NO.2 最少交换次数来组合所有的 1 II】
+ I( d3 R, q# Q+ s4 n8 V  A) a3 a  l8 j
解题思路
; \/ E7 Q4 D9 J- {8 Z首先化环为链(将 nums 复制一次拼接到尾部)。( \( N/ W' `4 s; w# R

/ [) T. Q# w0 v" s  _0 m* I然后枚举最终结果的位置 —— 连续 tot 个 1 分布于 [i, i + tot) 下标时,需要转换的次数就是这段下标中 0 的数量。
: R2 N( y' m* V" m/ F) M5 i3 q: v5 R3 G
每一段下标中 0 的数量可以用前缀和求出来。
* N6 w% G! ]# {4 Z
* T% O# N& H$ s# d3 ^% O代码展示3 b0 [4 Q6 C' V, Z" J7 A
8 W3 c" j, F7 @
class Solution {0 |- w: G& E) L# F; w6 k0 H
   public int minSwaps(int[] nums) {8 \1 v9 I, I# v( }' ?+ B
       int[] link = new int[nums.length * 2];
! n* Z2 T1 E9 Z1 Z       for (int i = 0; i < nums.length; i++) {" B6 y' `5 [/ L! G9 b+ e6 w1 A3 @4 ^
           link[i] = link[i + nums.length] = nums[i];6 @0 Q; V$ \. H2 O8 p
      }
7 A' ?* h& f  g: ?1 q       int[] preSum = new int[link.length];7 P0 L' Q" j' G8 `# c0 W# |
       preSum[0] = link[0];
/ b+ m( g: Y5 O0 _       for (int i = 1; i < link.length; i++) {
; @' y: N; J3 F6 f7 G6 [% O           preSum[i] = preSum[i - 1] + link[i];+ i! @# q, {' J# L' L
      }7 h" A; ~2 |0 T8 M
       int tot = preSum[preSum.length - 1] / 2;6 f) i, U" y# m6 A9 A
       if (tot == nums.length) {
# J7 v( \, J3 K4 V5 M           return 0;6 I7 f& Z( c9 c$ k6 m! k* O8 |
      }
$ z& X" i: e" L       int max = 0;( i# ~5 K1 O; x' h$ j0 I
       for (int i = tot + 1; i < preSum.length; i++) {- L+ U- a  v3 W' `# B7 a6 Z
           max = Math.max(max, preSum[i] - preSum[i - tot]);8 S: }# c$ u* d  y8 V
      }
! O6 t- [& h+ D9 G       return tot - max;
) |/ F0 E  u1 E  }
; }- }  D7 A' q9 S% p- a}
" c- v! s. i" y3 s4 A0 P  ?0 V
- I' `# u( m/ X1 v3 ?& q
1 E$ G  b# D( D; d$ ^1 D2 C% P# B【 NO.3 统计追加字母可以获得的单词数】' [( y" A2 D7 y: o8 _) Y

& _4 b) Z1 e0 l/ E/ e解题思路
& N& J! g' v" ?. D注意审题,只能追加一个字母。9 F5 H( l& e( \$ y  B! M3 l

6 \/ r3 {+ |- J/ d6 ^, _因为题目不要求顺序,所以我们可以使用一个 26 位的二进制数来表示一个单词。
+ T/ ^! C: C! R. W# m6 `7 a0 p6 G
6 U& N; ~, F/ `! i: I: Y2 X/ M代码展示
" K3 L& X+ \& c6 c' c
! j7 V* J" w4 h. P- x3 Pclass Solution {
" m2 T& f, ~0 G2 d& ^- I: ]   public int wordCount(String[] startWords, String[] targetWords) {
) T. x# n. y1 s/ I+ a       Set<Integer> startSet = new HashSet<>();4 V$ l  }+ I6 F+ b2 s( A
       for (var s : startWords) {
7 Y9 Z" [: W* E9 U5 J           startSet.add(toBinary(s));
/ M" E, {1 L8 u4 w      }
5 |# E& w3 t% p' a8 b       int result = 0;
  O! a! n$ M2 f5 f4 W; ~1 t       for (var t : targetWords) {
* v& Y* X0 [: u1 {8 Z7 h! f! q           int target = toBinary(t);6 Q1 t' a9 g/ Y/ l9 D5 A% K4 I
           // 枚举追加的是哪个字母8 i, Q* l1 D9 ?! u- M9 O
           for (char c : t.toCharArray()) {
& M0 D5 ]5 E) J2 ^/ s               if (startSet.contains(target - (1 << (c - 'a')))) {! t% }0 L. e" l9 w  D# m
                   result++;
# Q( K; d( l1 R  c- Q* u                   break;
3 a* z0 C; c2 J9 @7 \/ Z              }1 m1 q! K" ^) L! R3 p
          }
6 S4 v/ B( Z6 K& s& x- w8 \      }
) \( O- ]. a4 K- _       return result;
& q7 p( g5 _. G1 k4 Y  }
$ Z! O0 l" c: s; r9 {/ U7 t( J# @7 a
7 Z8 O4 r% M# c" V. q1 J   private int toBinary(String s) {
! ^, \" z0 b  A: I       int res = 0;
/ J" C/ c" |! ^       for (char c : s.toCharArray()) {
. G9 I; K" v8 V           res += 1 << (c - 'a');
  J( L) w8 f$ C: c8 w0 Q7 _' ]      }
( a7 F+ h, ]! w9 ^! W2 _       return res;
' ^5 C: v* A, ?  _8 J$ @1 D  }
2 ]1 Q8 }! Z9 P& X- t" g}
$ E* l  S% D4 f* M
) z8 [  J8 Y9 A6 t9 g0 I" W: P
2 _) B6 h9 ]- X【 NO.4 全部开花的最早一天】# s* |: }5 y; w9 a
: t2 E) B4 j5 ~' n8 C3 W% k; q
解题思路1 G* E2 f, R8 H: f: [& S. a
贪心,先种开花时间长的即可。
. u( s* ?1 H2 l1 R( }; X5 H! j" X( m: h* g
代码展示9 I7 F; ^# M7 W

, T. F; x- B; Y7 b1 Tclass Solution {
( V  D4 ~: s0 ^7 C; S5 i   static class Flower implements Comparable<Flower> {- d' ?5 V. ~2 h9 X7 x0 o
       public Flower(int plant, int grow) {9 |* g" `1 W# r. \
           this.plant = plant;
( |! @4 |$ y! {6 `# s           this.grow = grow;
8 V' \; M8 ~2 P6 d6 e9 U8 c: {           this.tot = grow + plant;3 c+ [, y5 v8 p: ^9 O8 O
      }/ t1 y6 o- B9 s* ^4 ]

; F. p, _; A" M  q       int plant;
3 O1 c7 ]( L# w       int grow;' m6 ?$ o+ Y& V
       int tot;
$ ?3 ^9 k2 _9 f5 W0 a- ~4 d# `' m: j. Q" f. v2 U
       @Override
3 u& a6 i4 x( C5 [5 A5 ?       public int compareTo(Flower o) {
3 Y& z0 s" Z% d/ Z6 I( |& D) x, v. C           return o.grow - grow;( _/ w( ]9 Z8 {
      }
, ]& o7 b# o" _: y) a  }
+ X9 k: v" T( }% G3 p2 E
- W( q% ^& U; l   public int earliestFullBloom(int[] plantTime, int[] growTime) {* }/ {# }9 h% I4 D5 e# r$ P2 X
       Flower[] flowers = new Flower[plantTime.length];) t& q! u( G8 P) [
       for (int i = 0; i < plantTime.length; i++) {( ]0 P* Z7 [  V- V8 L& o0 O
           flowers[i] = new Flower(plantTime[i], growTime[i]);+ W6 P- D; s& s3 w" W7 [
      }+ ?% ?. v  ?& ^" [
       Arrays.sort(flowers);8 v1 R" g& `* d: u+ F
       int result = 0;
  f/ v- H! S) o  I7 y       int current = 0;
5 v' S/ n$ z3 B* p6 S       for (var f : flowers) {6 l; g) Z" U) d. `: D# h- W
           result = Math.max(result, f.tot + current);
$ L  N( T% u7 j( X1 V           current += f.plant;% w; C/ q: [4 z
      }
6 A/ `5 a6 [. A* T  i# m7 |: E       return result;; u& b( M" }# A( f2 I# p
  }
) i! A: q# {8 k6 v9 d}! V3 q$ N) ~- H. b/ R9 W+ D+ Y
您需要登录后才可以回帖 登录 | 注册账号

本版积分规则

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