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

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

上岸算法 回复:0 | 查看:1920 | 发表于 2021-10-31 22:58:16 |阅读模式 |复制链接

UWCSSA提醒您:

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

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

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

登录后可回复主题

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

x
【 NO.1 值相等的最小索引】- E- ~1 g+ F* K+ H8 E1 s) L
解题思路
2 e1 G+ ?1 |2 Q  M  @签到题。
- c5 t/ ?. |5 @5 E" a. e
  p1 X' ]9 P7 `1 D% D; l, ?代码展示
7 M9 f; W/ v% {4 v) j2 T. G
! m" K4 j9 q1 [% g$ h- C6 ?class Solution {
+ F. u, y# C% E( b6 D: i   public int smallestEqual(int[] nums) {' e; R; q6 S6 ^6 K
       for (int i = 0; i < nums.length; i++) {
% q- I! c( H! }: G' }4 N8 P# D% b           if (i % 10 == nums[i]) {% x( W/ A" J  K8 F  A9 u! R1 c
               return i;
% W6 @; o# W' _0 o8 C          }
+ {( ?( m/ T5 _, u: K7 D! I" `      }9 L% I% ^) R6 D+ @1 i) T
       return -1;& M" Z* x9 e) q. w$ h! z( _  s) M
  }' L7 j' d1 t# ]
}
7 Q- ^' _* z0 ]; |2 W( w- S  O+ @' y* o- v0 @  P: Q+ i
【 NO.2 找出临界点之间的最小和最大距离】3 |' _4 C  m+ v: j+ e
解题思路. f0 R/ H  |- g' V; F" ?+ q  t1 g
遍历链表即可。
0 a/ `+ p: G) Q  f- r  [9 d; {' J
  ]' o, W  W  j$ W! I0 n代码展示0 ]% F/ E" U! [. E- n
: ]+ i  R1 c1 j' U+ H4 ]  ~8 R& q
class Solution {
( w# L. H$ T/ t# o, ~. p   public int[] nodesBetweenCriticalPoints(ListNode head) {1 V5 g! d' l4 b( w/ Q5 j9 w, k
       if (head.next == null) {
: `6 z4 S/ j0 b           return new int[]{-1, -1};
5 F! m! J0 P  d' o1 K* X) `- x" j      }
4 b* q5 F" w% U: Q" m2 H       List<Integer> pos = new ArrayList<>();5 w( z) d8 B0 z" v/ n. ?
       int last = head.val;
6 f( i8 e2 W2 @4 ~, T/ ]       int p = 1;% C; P9 B$ F* |2 t$ N! |
       for (ListNode i = head.next; i.next != null; i = i.next) {
# f" t; h0 I- r7 m" A           if (last < i.val && i.next.val < i.val) {! x0 W& s4 P' c7 L3 o
               pos.add(p);
* e+ @1 z, k+ n- y& Z          } else if (i.val < last && i.val < i.next.val) {
1 j$ y/ N2 b9 D! g* O               pos.add(p);
! G8 [. V6 s9 t4 d5 T2 v+ t; ^/ h          }
, P( U" n! f( v* E           last = i.val;- {. N, }7 P4 B
           p++;
- s' J5 I0 {' f4 `0 r4 K. ?" V" `      }
" P. P+ K$ `: n. _1 x& r+ _       if (pos.size() < 2) {0 N  |2 P2 ~$ a
           return new int[]{-1, -1};
% ^# J) u$ P& v- }* Q2 g$ p; q3 A5 o5 N$ |$ g      }
1 M3 _2 X# |8 L' p       int[] res = new int[]{pos.get(1) - pos.get(0), pos.get(pos.size() - 1) - pos.get(0)};/ U2 |! S3 i+ U' v, J* m
       for (int i = 2; i < pos.size(); i++) {
$ c  e1 I: {) E1 k           int dis = pos.get(i) - pos.get(i - 1);
1 M- i6 f, u; Q3 a           res[0] = Math.min(res[0], dis);
% H! H6 J% M/ {' }7 }  X6 U      }8 A5 a  k9 O+ X
       return res;
5 O! B; V  x4 G% E7 r  }1 y* r* v: Q! y* \7 B
}! X; l4 P% ~! Q9 n

4 y3 O$ @' b2 e( N! \: o. Q【 NO.3 转化数字的最小运算数】
, S- a+ B3 O! i* a9 U# A解题思路
, y' r: {, Q- ]+ f/ R5 n, @" j相当于 BFS 求最短路,为了提高运算速度,使用一个长度为 2001 的数组储存 [-1000, 1000] 范围内的数字,从 start 达到它们的最小步数。
6 B; i9 d: W; s# N; m9 f1 |# p9 l) k7 i  H. x  S& E
因为题目规定,绝对值超过 1000 的数字不能继续运算,所以无需储存到达这些数字的最小步数。. q: v) \* X0 ~3 T/ k

' P, I' a. t) w4 j- f( }. V代码展示: s' i! D  J+ P/ v
$ a  F1 K; P" l! I+ ~
class Solution {0 f8 \# A7 X0 ]3 d
   public int minimumOperations(int[] nums, int start, int goal) {
# N0 [6 [1 Q: R  [+ Q       int[] min = new int[2001];+ h" j1 i2 f# i2 X0 u' y
       Arrays.fill(min, 0x7fffffff);
0 g# j- w* H1 E' \1 {3 b! I       min[start + 1000] = 0;
8 {0 u7 J9 `; ?+ ~/ z/ f& [4 C4 s       LinkedList<Integer> queue = new LinkedList<>();/ O! i% l3 G; a+ a) g5 r: z
       queue.add(start);+ J6 r! u  h1 J& w  W" K
       while (!queue.isEmpty()) {, U% V$ y, V* A$ y3 p
           int cur = queue.poll();
/ i- F+ i- z6 p2 ], I           int dis = min[cur + 1000] + 1;# P! r3 P& }: @! P1 W5 C
           for (int i : nums) {
( E. X5 J" `9 F/ y" x4 C               int nxt = cur + i;
) T$ M: U6 [- ^+ h               if (nxt == goal) {1 ?& g9 F' p8 B. Y3 o* a, s2 K2 J
                   return dis;  j/ }7 m3 p& J& r: f( n; O+ L
              } else if (Math.abs(nxt) <= 1000 && min[nxt + 1000] > dis) {7 H' Z! a$ j' J" T' u
                   min[nxt + 1000] = dis;- q$ v" Z* \; v+ F& f
                   queue.add(nxt);
6 X  K1 u0 o7 ?5 P- b, n; ~9 d              }5 f/ R" \8 g1 |$ @9 Z3 s6 v9 ~
          }1 [0 n( ~* @. {
           for (int i : nums) {
- u* \  e6 @4 j               int nxt = cur - i;6 ~+ M: n0 B0 H( Q: }
               if (nxt == goal) {
7 c! y$ n& L: \$ u# Z  x' o                   return dis;$ N3 r' V6 P3 o* _; I
              } else if (Math.abs(nxt) <= 1000 && min[nxt + 1000] > dis) {
4 x- v8 c8 p( a# ^                   min[nxt + 1000] = dis;
% s" X0 L. c( r# b; e% g& B                   queue.add(nxt);/ W4 D0 F* F, G. Q
              }8 d/ n$ N$ w' r7 D8 Q
          }
* F" o  \; R9 G  l4 V           for (int i : nums) {
% k, m7 P# V1 E4 A               int nxt = cur ^ i;* A- w' m# r% P7 r
               if (nxt == goal) {' ?. _; N& @- d3 H- d
                   return dis;: s, e) K, x6 o5 I) ]" ?
              } else if (Math.abs(nxt) <= 1000 && min[nxt + 1000] > dis) {
" w  \( [! X6 d: h) |) [- j                   min[nxt + 1000] = dis;! L2 \0 z) w$ J" ]2 b
                   queue.add(nxt);
) U$ r# F7 f' l: [              }
, a6 X5 J% p; _% U" h3 P; r          }. I" F$ {8 u+ B! y7 P, q
      }+ Y5 o$ m# k; @+ y, S$ _6 p9 X+ |* t
       return -1;
' L9 P0 L- y, ]  }1 q; n* F8 r, E  b, V1 A
}0 l5 i1 _/ V% H; f9 F$ w1 l) n2 s
3 l8 |7 ?" x1 x1 U1 T' M
【 NO.4 同源字符串检测】
1 }0 }! T  Z9 P( [" x4 b. z解题思路
- A% k; y5 f3 ?. E) q6 n7 ?动态规划,细节见注释。# W; j6 E: t6 \& G% w1 p8 M

+ z9 L, i5 q6 B3 H代码展示
8 Z; Q# e5 C7 w: U0 r$ }0 X5 F8 e3 _% [3 p6 E4 }
class Solution {: f1 \" p+ ]! G1 E( O  Q) R1 l
   public boolean possiblyEquals(String s1, String s2) {& B5 X, V9 \! D4 o8 j8 ?
       // f[i][j] 表示 s1 的前 i 个字符和 s2 的前 j 个字符匹配时可能的长度差+ C7 C! Z3 h" D
       Set<Integer>[][] f = new Set[41][41];; F4 M/ W9 }/ `3 x$ P* {+ |
       for (int i = 0; i <= 40; i++) {3 J4 N% r: I, k, Q8 L
           for (int j = 0; j <= 40; j++) {
  O. B8 [4 T/ g* b* G" R               f[i][j] = new HashSet<>();
; `; p  F. j( V. l          }0 ^1 w) @/ F; q! j9 [
      }: w5 b4 k& y2 U: k7 u; A
       int n = s1.length();7 W$ U% X, R# K
       int m = s2.length();: V/ G2 D+ m7 F) m
       f[0][0].add(0); // 初始化 f[0][0] = {0}
" n2 m0 \+ f& j8 l4 [8 W6 c* U       for (int i = 0; i <= n; i++) {
+ W: j$ h" G; y1 H7 V: \           for (int j = 0; j <= m; j++) {/ v' w. u( s7 i9 y
               for (Integer diff : f[i][j]) {8 n) R4 V# ~# {# ~# r+ |! T
                   // 当 s1[i] 为字母,且目前 s2 比 s1 长的时候,该字母可以直接被 s2 中的数字消化掉
- P% P! R, V: S3 ?) M8 b8 W) t! t                   if (i < n && !Character.isDigit(s1.charAt(i)) && diff < 0) {
) H; p# h" [9 T' S! p2 G: P5 Q                       f[i + 1][j].add(diff + 1);
) |2 w8 i) t3 O3 V                  }; j5 ~/ D0 W. h! F, x* T* L5 Y6 V8 n
                   // 当 s2[j] 为字母,且目前 s1 比 s2 长的时候,该字母可以直接被 s1 中的数字消化掉4 H  S6 N# i7 }' ^, ]% `
                   if (j < m && !Character.isDigit(s2.charAt(j)) && diff > 0) {
0 s' Z/ S! N2 N                       f[i][j + 1].add(diff - 1);8 S9 T* j, f  W' ~$ ~
                  }
1 B+ ~5 H- a! g                   // 当 s1[i] == s2[j] 且都为字母时,必须完全匹配(即要求 diff == 0). m1 i( d: O# g9 u- s4 v
                   if (i < n && j < m && s1.charAt(i) == s2.charAt(j) && !Character.isDigit(s1.charAt(i)) && diff == 0) {0 L) V# k& H% ?# w# _# R5 r( I
                       f[i + 1][j + 1].add(0);
4 \3 k7 I7 k2 m: A" y" ?                  }( |, v; X3 M. N5 W" j7 O
                   // 枚举 s1[i:] 的数字,加入到集合中: l, `/ {% q: ^/ W+ t
                   for (int o = i, p = 0; o < n && Character.isDigit(s1.charAt(o)); o++) {5 r: E. p' G% u3 }* C# P$ h
                       p = p * 10 + (s1.charAt(o) - '0');
* J) z; l: n7 E$ Q9 e% Z                       f[o + 1][j].add(diff + p);
6 |8 [& _" H! ]                  }
4 o3 |" v# k: }/ p                   // 枚举 s2[j:] 的数字,加入到集合中
( s7 ], s5 j" ?+ z7 G                   for (int o = j, p = 0; o < m && Character.isDigit(s2.charAt(o)); o++) {3 n$ O4 |7 N/ i' b( m& _5 v
                       p = p * 10 + (s2.charAt(o) - '0');) p8 [7 z" s; ~9 v) S* n+ r
                       f[i][o + 1].add(diff - p);2 h" B7 V6 p2 t+ [* |8 _- L
                  }
# q. X! Y6 M. V$ R& Q* V2 `/ v' D              }
0 a) k8 E2 I) @, @          }
5 l% l: \8 b& o7 Y% v' n+ i      }8 t6 I" a7 q) P! `% [9 Y# l
       return f[n][m].contains(0);: y9 z: y) C# [# n8 Z, V6 W
  }
0 f. |0 A3 k1 {! X! x# t}
; I/ q) d# p1 d# g% g4 F9 G3 V2 M9 \0 x
您需要登录后才可以回帖 登录 | 注册账号

本版积分规则

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