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

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

上岸算法 回复:0 | 查看:48 | 发表于 2021-11-14 17:02:13 |阅读模式 |复制链接

UWCSSA提醒您:

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

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

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

登录后可回复主题

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

x
【 NO.1 买票需要的时间】7 J. y$ C: }* e$ V: U  L

$ H2 @6 s: J6 l0 M) Z1 H解题思路+ G0 J4 F' U) l  @
签到题,使用一个 LinkedList 模拟即可。
8 ~$ g2 J6 `6 O3 K; b8 ?% c. L, z' ~, v/ u& d% V5 Y7 _
代码展示: M5 W5 J; M  U! L+ C

  @6 c* e% o) Rclass Solution {% ]2 e& E. o& a: }, p/ W/ w5 C' @! X
   public int timeRequiredToBuy(int[] tickets, int k) {
) q9 W, V- y5 r+ p( h       LinkedList<Integer> queue = new LinkedList<>();% B9 k4 d3 R# L0 a; k
       for (int i : tickets) {3 q9 X4 c8 [& n2 j  G
           queue.add(i);( f# ?1 M, {" A4 m  ~6 C
      }
8 R4 E  y! v% n9 \! B! f       int result = 0;" `% d' V5 @- N5 j0 F* V
       while (!queue.isEmpty()) {9 q! U3 S% q; C9 n
           result++;8 V/ f+ S5 V3 V- {
           int t = queue.pollFirst() - 1;( ]( [, f( j) [8 L1 w& j8 H
           if (t == 0 && k == 0) {+ ]+ [& F" i/ c  c: R
               break;
( M1 L1 q6 W6 H! h6 W+ g6 Z8 t          }
. j# N! i8 p" s" R% g           if (t > 0) {: x% Q* w. |% S5 k
               queue.addLast(t);
3 _7 _3 H  m! J          }  C/ N( t, z# P3 E. @& v$ P/ e  C1 I% }
           k = (k - 1 + queue.size()) % queue.size();( p4 b" T6 \% D6 W5 f- \
      }8 m+ u- {: H: a& Y8 @- L
       return result;
( b2 T( [6 Z; p& z2 e# J  }; I) ^8 N) ~. O. R( n
}
; G; R8 J* {5 @7 ^) C
. ]! \2 W, e4 Q% ]6 N% g& k4 o1 N【 NO.2 反转偶数长度组的节点】
+ U* ~! J% g; r  y- {
/ ~5 z6 I$ h- ~8 n' `5 |解题思路7 g% V/ \6 n3 L/ I+ J+ }
数组更有利于反转操作,可以先将链表转换成数组,操作完后再转换成链表。
, C/ m# a0 {3 o& u8 S+ U. Z* d7 l. g
$ |3 u, i( A1 H3 {代码展示
1 {$ o& F; t  g" S2 o  _$ L; u1 w, c% R& f% z0 I+ u. `( N0 O
class Solution {
$ i/ n( N: {( E# ]& i" Z8 I* W   public ListNode reverseEvenLengthGroups(ListNode head) {% p' W6 [( T+ ^- X: ]  r
       List<Integer> list = new ArrayList<>();1 S- n' J5 J  u! D
       for (ListNode i = head; i != null; i = i.next) {
$ o- w5 z" U, C$ r* ?! ]9 a5 |           list.add(i.val);$ W( E% k9 d  x- T9 L4 ]' ?  R
      }7 w- ?* ^7 F3 m" x( b
       for (int start = 1, len = 2; start < list.size(); ) {
: y+ h+ b; X% i7 z           int end = Math.min(list.size(), start + len);/ @2 X) ~* f5 J
           if ((end - start) % 2 == 0) {. H/ z' `9 A& L3 @, T
               // reverse [start, end)$ W8 h1 _% S9 T6 a
               for (int l = start, r = end - 1; l < r; ) {. v) T  \. ~3 g; O" B
                   int t = list.get(l);
! o% v: s4 X5 H2 W                   list.set(l, list.get(r));, [& p% \' v0 p2 D8 L
                   list.set(r, t);6 S; ?4 k; E1 g) Q8 G
                   l++;$ c3 T! ^4 ?5 O: C- {
                   r--;4 S3 y: E' K9 d7 U, K
              }  l( B9 {$ p% W) l- e
          }1 J; S5 ]) Y0 C
           start += len;
. R/ k& A3 V0 M  B, K           len++;# D  y4 P2 i( W
      }; E3 q- p$ U! [9 j; q! j2 D
       ListNode h = new ListNode(list.get(0));
: n0 [; d9 A, T" [1 e       ListNode cur = h;
6 S% S2 Y8 s; d, t       for (int i = 1; i < list.size(); i++) {  y3 T' {1 S4 q7 K
           cur.next = new ListNode(list.get(i));4 r5 X7 N2 o& E2 I0 a8 h4 N
           cur = cur.next;$ I" ^0 ~4 a$ a
      }
* p' M& l6 K) O- J       return h;
; ~7 j+ Q! Z6 r  }
+ _9 o& o1 e" s' Z4 b$ T) k0 H}" f, O+ k. p5 z" ~

( F4 W5 p  i2 M, a$ i+ D【 NO.3 解码斜向换位密码】
+ ?9 S6 J/ u5 \; f; ]2 ?% g: I, w- K$ o) |9 r" B1 [6 Z3 i
解题思路
" |' o! v4 A+ L2 e7 e还原出矩阵即可,最后注意将后缀空格删去。5 h: p& e3 ?. s, h1 U0 L

3 v3 E# ]% k" y) x& F代码展示
. A0 d4 M7 `' t. h, ?& r
/ `, K" g1 y5 q  m$ l1 Mclass Solution {2 C1 M0 E7 `# H& P' ]. C
   public String decodeCiphertext(String encodedText, int rows) {7 A3 t2 O8 F( I+ ~) q
       int cols = encodedText.length() / rows;' V! m% v/ a/ O$ a
       char[][] mtx = new char[rows][cols];4 o/ d3 ?- B; A
       for (int i = 0; i < encodedText.length(); i++) {2 l% A% y3 A2 w. R+ u8 B8 V
           int x = i / cols;
# l3 C% y$ |) b, [           int y = i % cols;9 i& _6 P6 C% w
           mtx[x][y] = encodedText.charAt(i);
* x! [: F0 Y( x. V7 d      }
9 u/ n& f* I5 z5 S+ I" f       StringBuilder sb = new StringBuilder();
. O6 }/ K1 G" ]" N& p+ ~       for (int startY = 0; startY < cols; startY++) {
4 ^0 G' a: [2 i           for (int x = 0, y = startY; x < rows && y < cols; x++, y++) {
) L! G* |+ K+ P9 x% b               sb.append(mtx[x][y]);
, Z/ F( c7 o3 w" @# B$ N- S          }! P: U7 ^, G( S- g! t
      }% {" Z+ I; i- T, V
       while (sb.length() > 0 && sb.charAt(sb.length() - 1) == ' ') {
! n# E. Y! F1 R, w8 P: ]           sb.deleteCharAt(sb.length() - 1);$ f% K  J& w* O2 e% n  R
      }
+ [' }) S! N; o6 B4 _       return sb.toString();
! c6 ^: r# b" i9 ~  }' N4 ^' N' x. i0 G9 b# V# K- i
}9 u* |+ [( f/ H& E9 Y+ w1 r4 ^
+ d6 G( L+ |3 C
3 N4 [. c' c& B, `9 w; ]1 H/ G
【 NO.4 处理含限制条件的好友请求】# i! `( A9 L, B3 O- _

, j' e% [& ?6 q7 p- w. C: ]解题思路; o6 {5 Q! \* B0 r. T+ [
并查集,详见代码注释。; y; J) f+ f) s7 O
, d8 r+ ~/ H' A" [$ |
代码展示  W" v' g# N  w. a1 g
4 k  l5 C8 p2 U" e% q7 B& t
class Solution {
5 {5 \0 p* U; x( ~. i   public boolean[] friendRequests(int n, int[][] restrictions, int[][] requests) {
! Q6 N: P8 a2 H1 \" p" M- H" v       boolean[] result = new boolean[requests.length];
( z9 T5 N* t5 C2 l       // R[i] 表示不能与 i 做朋友的人# d% L% Y0 r; f3 a. C
       List<Set<Integer>> R = new ArrayList<>();
4 N; @+ Y. ~# d- i! {8 c       for (int i = 0; i < n; i++) {
$ @5 k( a. H7 f' h6 q! v  x           R.add(new HashSet<>());
9 x3 q" G1 Q, D2 a+ `3 h" a8 r+ ]0 {* A      }2 u- z, b0 J7 i9 p/ s
       for (var r : restrictions) {
+ S- J- C3 F' W0 ~; n; H0 U/ I           R.get(r[0]).add(r[1]);8 s5 N: p3 N, X/ P/ U/ z+ u9 X
           R.get(r[1]).add(r[0]);2 r! T4 r; q, x$ B8 ?3 m5 H; K
      }% R7 P  ]/ W$ c1 V- _. O% q
       // uf 维护间接朋友关系
3 X" N: ]# O% s1 k1 n  \       UnionFind uf = new UnionFind(n);  e$ K% b% p% `$ h
       for (int i = 0; i < requests.length; i++) {/ p% S' L7 @* {- G6 E  w8 L9 o
           var r = requests[i];
+ s5 Y! T+ |# z' @5 s6 D           int f0 = uf.find(r[0]);6 C8 \$ s7 ~' K1 n4 T
           int f1 = uf.find(r[1]);
3 }3 X4 L. a$ U5 R8 k' {           if (f0 == f1) { // 说明 r[0] 和 r[1] 已经是直接或间接朋友了( u$ `: \, a& N/ v5 c8 N$ y; q! b  W
               result[i] = true;% p- R. _7 b5 D$ v
               continue;
9 H' j  G  I  f( j2 J! I& V) W6 u          }
  w$ X0 R0 ?' O           // 由于我们总是将限制关系合并到根,所以只需判断根节点即可6 y$ `6 {; U4 @5 {4 y, F1 E
           result[i] = !R.get(f0).contains(f1) && !R.get(f1).contains(f0);. L6 K6 v' L" V0 t$ p/ t
           if (result[i]) {2 w5 f' ~- G, O7 o5 ~5 F4 A
               uf.merge(f0, f1); // merge 后 f1 将成为 根
( g% r9 V4 C( j9 _1 _! y4 A$ ?               // 原本不能与 f0 做朋友的人也不能与 f1 做朋友了! \% L* }8 p1 i# \) G; _& O
               R.get(f1).addAll(R.get(f0));
' a- t) |) }5 W5 Y8 `               for (int j : R.get(f1)) {2 K% b& n# F; i; A- w  p8 u
                   R.get(j).add(f1);
0 B" L' v. z- Y  c  P8 w              }# Y. q& q; M% V2 i: D0 A
          }
, S, H1 x$ {; x- b1 T- u      }" f  a$ `4 V& [: j. G+ i# D
       return result;$ |. @: K/ d4 j4 Q* F
  }5 V2 t7 {6 V" e+ E, a: {) z
}6 t3 E1 h* j' o; [4 C  ]

. X' _5 E+ F9 ?class UnionFind {
. A$ u# @1 L0 i) s) j. Q- o   public UnionFind(int size) {4 G. r( u# T6 `8 V; x, u
       f = new int[size];" I: g1 h. \. s
       Arrays.fill(f, -1);% c# \0 U, E& x! S7 r: O
  }
/ U8 A$ n, V0 _$ c* L
  r. u2 u9 @6 u   public int find(int x) {2 x/ S7 p  ?- R2 M
       if (f[x] < 0)
! L0 j2 h+ y+ [+ g2 t) l           return x;3 @) F3 C& b: M1 S% h* V
       return f[x] = find(f[x]);+ b# q' r% o; [. f' V
  }
  Q/ N* W+ A8 b- x2 ^1 Q- G" X
9 @3 z% F$ w  x   public boolean merge(int a, int b) {1 w1 n' I! l/ s& ]9 P9 W
       int fa = find(a);
. Q0 [# W! A1 K       int fb = find(b);3 J9 O$ x2 X! S* B
       if (fa == fb)
5 o- B" A2 q7 v% y, [3 T) k" O           return false;" ]# t0 O; x' }6 s* `
       f[fa] = fb;- _/ _& }! J6 R) u4 T' j. o
       return true;0 _/ F, X! D  ^0 q! B3 |6 |! [
  }
) |  `2 k$ y6 {9 k" r$ q( G2 r4 e* U) C, C5 w3 S
   public Map<Integer, List<Integer>> sets() {
) A+ _$ h0 @* _9 w: P       Map<Integer, List<Integer>> res = new HashMap<>();# ^- s  Q+ l! j  v& u
       for (int i = 0; i < f.length; i++) {
# Y- \) `! l5 ^' n           int fi = find(i);
+ K% R5 K$ u, ^& L2 L           if (!res.containsKey(fi)) {
; f  l) b# f1 {' b5 o; E( _               res.put(fi, new ArrayList<>());4 L2 ]; L, Q/ ^, i) o- V5 F
          }
& J& \6 H0 G! Q" Q           res.get(fi).add(i);( p) g, p# b' W4 Y& B- _/ ?
      }
7 ?$ n9 s7 k1 s2 h2 F       return res;5 u* w3 C/ ~6 s
  }8 ~, b! L  k' I+ x- V

% W, [/ J- e; c) v7 E   private int[] f;: J4 T+ F( r. u, A
}7 g5 J+ r  q( H" a
您需要登录后才可以回帖 登录 | 注册账号

本版积分规则

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