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

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

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

UWCSSA提醒您:

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

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

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

登录后可回复主题

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

x
【 NO.1 值相等的最小索引】
6 f, G% S& |/ w( D/ i# \解题思路' {  e$ I. A5 ^' X
签到题。
1 Z" F( x/ o" R+ K0 ?8 Y# {3 p# [( a0 Y! Q& p7 H1 h( z
代码展示
0 }$ s, A+ G& h/ ]9 r: f
- `2 E/ X9 J8 u6 ^class Solution {
$ \( v- m9 J" M' V) ?   public int smallestEqual(int[] nums) {! G3 A4 b; g) E) f* ]- |! r
       for (int i = 0; i < nums.length; i++) {  `% \) A, [3 ?3 t* l) ^" n
           if (i % 10 == nums[i]) {
& B- \6 w  X- S$ }5 R" e               return i;
# U' W4 [) D4 I; X+ ?/ E2 W          }+ X5 V/ s% R/ a3 Y- N4 c* _6 Y
      }& E1 a) P8 C. k! j# Y
       return -1;; L2 O+ f# |% ^/ O; `
  }, Z7 n6 t: t. `
}
$ \' g5 K/ K' N! I0 r6 a0 M" q' f2 d* J$ U& s! Z( M
【 NO.2 找出临界点之间的最小和最大距离】5 t% Z; z1 b" A" K, V1 S0 E1 _9 a
解题思路! U! I( e) `: u" b0 m# b3 A
遍历链表即可。6 K5 g6 {$ i! ^( m. K2 p
  p6 b  z0 q  e
代码展示
% A2 Z, ?4 s! q0 ]
5 T  W( V0 g1 n' `4 @' Vclass Solution {
% U3 N  b& |% ?   public int[] nodesBetweenCriticalPoints(ListNode head) {* S8 p9 W1 G' X. ~# V( P
       if (head.next == null) {, p# _/ a1 K6 P! p$ M7 F
           return new int[]{-1, -1};1 Q/ n' }6 i: Q. z* I; M
      }
% Y0 B+ e9 [) i; c3 p       List<Integer> pos = new ArrayList<>();
$ L. m2 r: m% d! m2 {$ Z       int last = head.val;
% f1 [) v5 _8 w5 u* q& M6 O       int p = 1;+ i' b; t9 I$ ?& H5 A
       for (ListNode i = head.next; i.next != null; i = i.next) {
( R& {  z0 o% e1 w           if (last < i.val && i.next.val < i.val) {; J4 L$ l9 d2 g) I& m. J6 J- ]
               pos.add(p);5 @- Y# P: l6 u
          } else if (i.val < last && i.val < i.next.val) {5 m2 B! u( l8 A1 x) c
               pos.add(p);
. m* O, w9 f. u! N1 X( [' h          }& B0 p/ t! {6 Q$ A
           last = i.val;
, m- L6 M2 _1 ~% m: L           p++;
- |) m" K6 Q9 g: h, R      }
( I. @3 W5 f2 R5 b) ~       if (pos.size() < 2) {
0 ?* j/ N( ^! Q$ Q; W( t           return new int[]{-1, -1};
5 `. D6 z4 _- y5 p      }. J7 c6 V3 b( _1 k, o$ u5 b
       int[] res = new int[]{pos.get(1) - pos.get(0), pos.get(pos.size() - 1) - pos.get(0)};
5 E  {' _2 q( K* J8 q6 H2 C       for (int i = 2; i < pos.size(); i++) {
$ C5 ]( `5 K* w           int dis = pos.get(i) - pos.get(i - 1);
9 E6 c- J: X2 F1 X           res[0] = Math.min(res[0], dis);# q* G6 ~/ Z) |& X
      }) i5 g# ], l2 D: |
       return res;
% o) @! n6 z5 s9 y& k  }
6 H$ E$ h9 ^* ^0 }, S* s1 d}
8 b3 h: x8 d4 |* G" c' s( J% b# x+ z4 U1 L. ]( N
【 NO.3 转化数字的最小运算数】$ U6 T7 q; l  s. o$ E$ t6 t" s% W
解题思路
* D1 a9 H7 ~5 T4 v, s相当于 BFS 求最短路,为了提高运算速度,使用一个长度为 2001 的数组储存 [-1000, 1000] 范围内的数字,从 start 达到它们的最小步数。/ M% i0 A! F! h7 |$ H) Q

5 p" H# P& x2 v9 F0 p$ f因为题目规定,绝对值超过 1000 的数字不能继续运算,所以无需储存到达这些数字的最小步数。# K: Z5 M- E5 Z2 w* i
/ P$ ~( L* ~  h9 B6 b4 O1 t3 o
代码展示8 u3 z) M4 A3 n- |
3 D5 D1 h% `1 O* m8 E- m+ U
class Solution {
9 t8 ^4 }3 W' }, G   public int minimumOperations(int[] nums, int start, int goal) {
; b2 s4 r6 h3 ~       int[] min = new int[2001];' ?6 ~$ W8 X' u. j) E+ e
       Arrays.fill(min, 0x7fffffff);' m! v* G1 r3 q* H$ x
       min[start + 1000] = 0;
. `2 Q4 @2 N  ~; F       LinkedList<Integer> queue = new LinkedList<>();
5 a; |+ k8 c0 C8 \; z5 _       queue.add(start);/ a7 |  p, T# O/ f) w! v
       while (!queue.isEmpty()) {; }1 R+ {' \  G' s
           int cur = queue.poll();
6 k9 N1 z: q2 U& A& y  o& F4 q           int dis = min[cur + 1000] + 1;" ^% u9 \! p  g9 {
           for (int i : nums) {7 \8 R" b! J+ x6 ~9 }9 @& ], @
               int nxt = cur + i;/ i* _: Z& M7 [2 k1 h% g# J
               if (nxt == goal) {/ C; `+ c% ]5 k
                   return dis;8 c4 s$ H* ]# V! Q- l
              } else if (Math.abs(nxt) <= 1000 && min[nxt + 1000] > dis) {* P2 W& u5 L/ O6 d
                   min[nxt + 1000] = dis;/ I0 _9 F7 t8 O
                   queue.add(nxt);
" p) v/ N5 d0 ^  u              }
  R+ ~+ Z. S; k& {' @3 F          }
- R* \1 ?! ]/ y           for (int i : nums) {  [2 K4 f  h$ Y7 u( k5 w
               int nxt = cur - i;! v& s4 P, f" Y
               if (nxt == goal) {$ ^4 i9 J4 i- v: g
                   return dis;
: W0 J2 Z) u! [' X              } else if (Math.abs(nxt) <= 1000 && min[nxt + 1000] > dis) {
& C2 x: H, H8 X7 D( A                   min[nxt + 1000] = dis;; y4 A* `1 U1 ]; G9 \! l
                   queue.add(nxt);4 z9 h7 j4 M& U( U$ j2 b
              }# m: S9 h" R$ I0 G3 X
          }5 V* x% W4 W' A5 p# T
           for (int i : nums) {0 J9 q( D% P. P& k( o
               int nxt = cur ^ i;7 W4 g. X1 @* j7 t
               if (nxt == goal) {
( T7 w6 ?# ^1 C) n                   return dis;- W5 S1 {0 ~; S! [% _
              } else if (Math.abs(nxt) <= 1000 && min[nxt + 1000] > dis) {: B8 W$ g/ V' q
                   min[nxt + 1000] = dis;
. f( D: H1 I* r/ g% O7 J) ~8 i& l                   queue.add(nxt);0 i3 u9 d, J. M( D( Z
              }# W* e- k9 M* H2 M9 ~
          }# T3 B+ Z8 v* m
      }
( V  M( F9 \, S       return -1;6 A9 ?8 u; e" l6 d1 W
  }7 T( q- J4 d2 E
}
9 E% e/ ~( e( d
; S- d7 k; r9 n: |【 NO.4 同源字符串检测】
( D7 R, B4 ~9 @2 @3 Q; K- \; _5 Q解题思路. ?, r9 h! h' y
动态规划,细节见注释。
' _* S! m% t* `& b4 s3 j6 n8 p: y: s' m9 V- S% t: H8 A
代码展示
) M5 [( j/ f9 B6 h$ v: @
9 w2 F) N; E1 Q* Q* a2 ^/ uclass Solution {
7 M# t* t: h" `2 @   public boolean possiblyEquals(String s1, String s2) {" R. U) q+ d9 Z0 N( ^
       // f[i][j] 表示 s1 的前 i 个字符和 s2 的前 j 个字符匹配时可能的长度差0 A3 {+ {( f) k+ |
       Set<Integer>[][] f = new Set[41][41];
/ t: C. D6 g5 s8 M! s  e# b       for (int i = 0; i <= 40; i++) {4 _; U" ~. W- A' M+ D& @( M
           for (int j = 0; j <= 40; j++) {
) d& M" n* d1 h; z. h5 c               f[i][j] = new HashSet<>();
! ~+ b8 }) R+ |7 Q* Y          }
6 X( w* {9 e4 T2 B6 {1 ]3 N, K      }
6 m7 f9 c! r7 I, I- ?; K& K7 p' N3 q       int n = s1.length();! k+ p! `9 B* Z" j% e4 d
       int m = s2.length();
7 N- A0 G; u4 I  ]       f[0][0].add(0); // 初始化 f[0][0] = {0}
4 b" r/ @2 y6 w# P       for (int i = 0; i <= n; i++) {0 l. V6 D) ]2 G% f; R5 e
           for (int j = 0; j <= m; j++) {
: t# G, V! B+ E               for (Integer diff : f[i][j]) {
  J& Z( ?- N7 M) V( `) p                   // 当 s1[i] 为字母,且目前 s2 比 s1 长的时候,该字母可以直接被 s2 中的数字消化掉
7 B. N) I! _4 \) K" ?3 x                   if (i < n && !Character.isDigit(s1.charAt(i)) && diff < 0) {
. g8 s, h; b7 C6 O) ]# ?! G* E7 x/ W$ j                       f[i + 1][j].add(diff + 1);
) \0 ?  y7 }% m: l: Q, b6 E                  }4 P+ N/ n4 o: I
                   // 当 s2[j] 为字母,且目前 s1 比 s2 长的时候,该字母可以直接被 s1 中的数字消化掉# P1 y/ d4 {: O+ @! b: |8 c) p0 Z
                   if (j < m && !Character.isDigit(s2.charAt(j)) && diff > 0) {
2 f7 Z9 k. K# Y% e/ w! x                       f[i][j + 1].add(diff - 1);# o6 x0 J; A0 I  W" l* m
                  }( s9 _2 x  c2 f1 r8 @% h6 W
                   // 当 s1[i] == s2[j] 且都为字母时,必须完全匹配(即要求 diff == 0)( S5 H5 t# h" ~9 a& ?
                   if (i < n && j < m && s1.charAt(i) == s2.charAt(j) && !Character.isDigit(s1.charAt(i)) && diff == 0) {
; c2 r* F+ i9 W: Q9 x- C! ]. ]                       f[i + 1][j + 1].add(0);
5 }0 F8 T% C4 \" e8 q8 V                  }* P$ e! Z( o8 b8 r! o' g
                   // 枚举 s1[i:] 的数字,加入到集合中
3 I% p1 E9 l; H' c! O9 `" {$ |                   for (int o = i, p = 0; o < n && Character.isDigit(s1.charAt(o)); o++) {6 }; h( G. o  H5 S- [
                       p = p * 10 + (s1.charAt(o) - '0');5 ?2 ^) U! W+ o$ b7 j
                       f[o + 1][j].add(diff + p);# L! ?2 w- r% w! j5 q! z; |
                  }& X$ v# L, h6 @% M
                   // 枚举 s2[j:] 的数字,加入到集合中
6 z) I4 w8 T* G8 y: B+ V3 M                   for (int o = j, p = 0; o < m && Character.isDigit(s2.charAt(o)); o++) {$ D( k) }) Y; e* n3 Z
                       p = p * 10 + (s2.charAt(o) - '0');
2 C6 }8 s. k. r2 T! e                       f[i][o + 1].add(diff - p);
# X$ M/ g- @# o) C6 H' t, a                  }
1 x; \9 U  O2 Z* v4 x              }
: E7 P- P) M6 n( ?' R& W  L0 L, t& c2 G          }
. w3 @: P1 o$ m8 G% [0 B4 t      }9 p7 l* b2 r  _; ?2 C
       return f[n][m].contains(0);
( I2 @3 R* y5 V  ~$ Z. f  }
( D/ @/ c4 k* O  v" O  b: o}
& b. g9 q2 a8 m$ A5 v  A; x1 T
您需要登录后才可以回帖 登录 | 注册账号

本版积分规则

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