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

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

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

UWCSSA提醒您:

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

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

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

登录后可回复主题

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

x
【 NO.1 值相等的最小索引】
- v! u+ v$ z: ?6 ?: y4 H解题思路- R5 d# F$ V* ?9 N% s" }
签到题。
7 O  L4 q7 J7 G9 d
/ R& I4 f+ ~% \0 N' y2 d+ U' d代码展示9 D, O1 {) g$ }; X

2 M5 q, z  U2 h  }: p% g1 \7 j7 aclass Solution {
3 B) H$ s0 s# a   public int smallestEqual(int[] nums) {
; p' z6 H3 Z5 q, E) a3 m+ P7 @       for (int i = 0; i < nums.length; i++) {& X- \- B8 u7 W( D0 h
           if (i % 10 == nums[i]) {
; Y! d3 z) G( e3 C, Y( W               return i;
* q, m9 ^+ F6 u/ c$ O6 X          }* y$ h* c: E1 M% k7 R
      }
8 d- I: {- i# d9 h% u7 p. B8 {       return -1;4 |+ P: @- ]( j6 {7 {7 Q0 T4 W
  }# ~' m; o5 H8 s" ]
}. B& Q+ b3 N' ]: b! Y4 m: ~3 h9 |

- p: i6 u* M% Q* ?6 x5 d5 r【 NO.2 找出临界点之间的最小和最大距离】! P5 U! {& J8 l* \, }- _
解题思路
( o3 z& `# k5 k+ w0 {+ V遍历链表即可。, }5 V) z6 K% S1 W. y

) y/ o9 Z/ `; l( g, K, I& M代码展示
$ I8 ]- H3 ^% u: I- e* E8 ^8 b) e2 x: V: r! r' N
class Solution {
* w3 p9 J! G3 R" `   public int[] nodesBetweenCriticalPoints(ListNode head) {
! ]* b- `2 K; |( R" a       if (head.next == null) {
, S% v4 h& F% M           return new int[]{-1, -1};  e& p: K5 g; d, e" K
      }
6 G; t& ^3 @. N5 o0 I0 q! [3 K       List<Integer> pos = new ArrayList<>();
# C! _$ l! S: E/ g       int last = head.val;/ c4 Z1 d0 p8 A9 n; X7 _
       int p = 1;2 u) M# o9 _5 x3 G+ T+ `* ~" S( x
       for (ListNode i = head.next; i.next != null; i = i.next) {
, U5 ~3 u" f" d; X7 P) d           if (last < i.val && i.next.val < i.val) {' h0 S1 r9 n- E. r, P
               pos.add(p);+ B* y* S0 x' ^4 \" r8 r, s
          } else if (i.val < last && i.val < i.next.val) {* |  v4 D3 B, k; N
               pos.add(p);
1 n) x' S( `; \$ {4 B          }
3 I3 k% Q' h# T5 S0 i           last = i.val;6 ], N' ]- W5 j5 y. Z2 }# j
           p++;
4 q0 n! [! W0 b) Q, v) [$ N3 q      }
  `! a8 s2 B% v9 C( H       if (pos.size() < 2) {/ q8 w% t0 d* S# b& P% _
           return new int[]{-1, -1};0 z- z; u  b; ?) g+ P# a! h. u
      }9 b$ \) L) J  v) u2 R3 j2 e
       int[] res = new int[]{pos.get(1) - pos.get(0), pos.get(pos.size() - 1) - pos.get(0)};& |- M1 Y* [) V
       for (int i = 2; i < pos.size(); i++) {
- B; d; n. o. i9 `( w. G. t9 w' ?           int dis = pos.get(i) - pos.get(i - 1);
" _  t7 N+ c: N% X, Y9 t           res[0] = Math.min(res[0], dis);  B* O, C: {# F4 }0 n8 Y) M( F
      }" O% w, g* j& N* F. ^  x  K0 C5 U
       return res;4 y5 _3 c3 g. O# i, z* [
  }
! R) _! o3 n: P* x2 p) k3 w}4 D+ k+ H" Y7 J5 n+ l

1 p9 N7 R6 f! `9 Z  p【 NO.3 转化数字的最小运算数】
- _# m: C2 q7 J+ m; ~解题思路
3 @: r* v: |5 ?0 ^3 C相当于 BFS 求最短路,为了提高运算速度,使用一个长度为 2001 的数组储存 [-1000, 1000] 范围内的数字,从 start 达到它们的最小步数。5 ?" M+ W; L) l" p

4 C% C" F# Q* O4 O因为题目规定,绝对值超过 1000 的数字不能继续运算,所以无需储存到达这些数字的最小步数。# Y% D1 p5 _) z" n: Y+ Z8 G

6 T: [1 G% H* u, U% G代码展示
: Z" u6 I5 S' b9 Q3 n* d1 Q0 r# }; G0 r% }3 i2 F6 |
class Solution {! t1 {2 h9 K$ Y8 W! D
   public int minimumOperations(int[] nums, int start, int goal) {; O; [- X8 {6 `1 Q2 G" f9 o/ G
       int[] min = new int[2001];' m( m# C/ j" S, ~
       Arrays.fill(min, 0x7fffffff);
) q. L  Y) k8 S3 `       min[start + 1000] = 0;% C9 B! {! O; Q. M
       LinkedList<Integer> queue = new LinkedList<>();
& n2 T+ O6 }, a6 L/ U$ m7 ?$ b5 c       queue.add(start);& h  q( |) P  M8 D
       while (!queue.isEmpty()) {, ]; p; U" T  i; X
           int cur = queue.poll();  X) v% {+ ~% c) E; G6 r: H
           int dis = min[cur + 1000] + 1;  N: f5 `- m  ]+ L" i. P& q+ D
           for (int i : nums) {5 |8 w! A# z  I' L
               int nxt = cur + i;
2 P1 L: Q2 c1 i, \0 ?1 b               if (nxt == goal) {
2 c' ]$ w& R( a: H% i! H                   return dis;2 @% a6 Y- b* H( {
              } else if (Math.abs(nxt) <= 1000 && min[nxt + 1000] > dis) {
) X* V' r. W% Y                   min[nxt + 1000] = dis;% F+ V; `  z/ J" l! Z
                   queue.add(nxt);
9 @  `( A: s4 @              }- p# D9 \3 L$ V! c# g& Z
          }
' j) ]% y  |: u  T8 n6 f           for (int i : nums) {
3 ?) |0 V0 w# q               int nxt = cur - i;
( U. q# U! M) m) _4 v7 X5 Q; S7 Z               if (nxt == goal) {# C, ^8 W2 B/ b$ f- [; f7 J' [
                   return dis;; i% G$ C& s  z2 r4 q9 D1 `
              } else if (Math.abs(nxt) <= 1000 && min[nxt + 1000] > dis) {8 B. J+ S3 \1 k: i+ m2 a& ^* N
                   min[nxt + 1000] = dis;9 f+ P' ~) ^3 `; ~* p3 G2 Z+ y$ `: v
                   queue.add(nxt);5 {' N0 M5 k1 z# f; f0 D3 R
              }
; O% D. M3 ^6 v9 d+ {' Q3 i+ G4 l9 N          }
8 w; n9 X1 ]+ ]0 e" o. j9 }           for (int i : nums) {
$ t# O" r2 c2 W  d& x' D  }* \               int nxt = cur ^ i;
, D8 |5 ~% z2 X. x: M% M) L5 x+ |               if (nxt == goal) {
; P; L! x1 n) i* v# E) Y                   return dis;' L! {( r+ {, x. w
              } else if (Math.abs(nxt) <= 1000 && min[nxt + 1000] > dis) {
( A/ |' a$ W, _' q) B1 r% P                   min[nxt + 1000] = dis;
4 @$ Z( o% ]$ \& f7 u2 ?% A                   queue.add(nxt);
3 ]5 V' M8 ?2 N3 c0 I6 I              }" z. V3 ^' q( M# V
          }* F' @6 W& K5 i% w4 K
      }
5 f# a% [: X# {) i! K5 `$ C       return -1;8 e0 R* M$ Y! X- K0 k* ~4 y
  }& E9 q8 r: x; n8 \
}6 G/ c$ K/ F* ~& a: `2 @0 e' e

$ i% m* V; s5 p4 f【 NO.4 同源字符串检测】9 w! r; q% }% y
解题思路1 |+ c# J, _4 j: {1 j! k; V- K
动态规划,细节见注释。
& B0 u1 m) _# a# N/ c% c. i1 |. J5 g1 L7 [
代码展示
6 L# Q7 S# a( J  b
& A3 J3 }- V, l8 G' ~$ v% C3 nclass Solution {  C/ u+ h6 l% l
   public boolean possiblyEquals(String s1, String s2) {$ X, F: R; ]) f( ]- X
       // f[i][j] 表示 s1 的前 i 个字符和 s2 的前 j 个字符匹配时可能的长度差
5 P; ?  B2 f! n- n; A       Set<Integer>[][] f = new Set[41][41];' t, ]9 c2 c$ Y. N  B& H# r8 n" v
       for (int i = 0; i <= 40; i++) {
& V% R4 Q; [4 j) z, w6 `           for (int j = 0; j <= 40; j++) {
; B6 H4 \) {( \2 H4 Q, y# }               f[i][j] = new HashSet<>();& G! R; {& d: ]
          }6 z8 |& Z' b' \: t
      }4 g# H7 e7 \7 H! V% w# f
       int n = s1.length();
0 y9 B  M) Z3 p# x5 J       int m = s2.length();
0 `- v% W' T" d! k) t, M       f[0][0].add(0); // 初始化 f[0][0] = {0}) Y" ?9 A- J! i9 i" s& d3 j
       for (int i = 0; i <= n; i++) {) @7 ]! ?6 @2 B3 v* H! C, M
           for (int j = 0; j <= m; j++) {
' V; n. g' g$ o               for (Integer diff : f[i][j]) {
3 f8 ]9 G' r: a2 ]                   // 当 s1[i] 为字母,且目前 s2 比 s1 长的时候,该字母可以直接被 s2 中的数字消化掉, J6 Y) y; p( b/ B' F
                   if (i < n && !Character.isDigit(s1.charAt(i)) && diff < 0) {# o4 t' {/ f* l
                       f[i + 1][j].add(diff + 1);
7 O6 X8 T  _! S, Q                  }% s6 o5 {2 n) j& d
                   // 当 s2[j] 为字母,且目前 s1 比 s2 长的时候,该字母可以直接被 s1 中的数字消化掉
2 ~2 d/ x4 T* C5 E" c6 ~& r1 s                   if (j < m && !Character.isDigit(s2.charAt(j)) && diff > 0) {4 a- Z5 O' X# E' o: d& _0 a
                       f[i][j + 1].add(diff - 1);
0 T9 R5 v9 L4 Y4 Y7 {                  }
, G2 ?! K  D/ |                   // 当 s1[i] == s2[j] 且都为字母时,必须完全匹配(即要求 diff == 0); L5 y4 Z- ~  W+ l! P8 n% U7 e
                   if (i < n && j < m && s1.charAt(i) == s2.charAt(j) && !Character.isDigit(s1.charAt(i)) && diff == 0) {( l$ ~) N! X3 T7 u
                       f[i + 1][j + 1].add(0);2 s0 U* h" Z4 F$ `9 o! X" a
                  }7 }4 ^$ ~/ p4 `8 o8 X0 {! S2 I9 G
                   // 枚举 s1[i:] 的数字,加入到集合中) B9 W! \4 K  C2 _/ ]
                   for (int o = i, p = 0; o < n && Character.isDigit(s1.charAt(o)); o++) {
, T8 ?2 h3 j4 k/ F; c$ q                       p = p * 10 + (s1.charAt(o) - '0');
9 Y, Q9 |* a3 O9 J                       f[o + 1][j].add(diff + p);
5 `) A5 P3 z3 _$ F                  }- K1 j1 E$ @! E7 ^" ^
                   // 枚举 s2[j:] 的数字,加入到集合中* }/ W2 x/ K& C0 z' H; ~# k9 `( v
                   for (int o = j, p = 0; o < m && Character.isDigit(s2.charAt(o)); o++) {+ K, h' q* Q9 _7 h9 K
                       p = p * 10 + (s2.charAt(o) - '0');2 r3 L& L  n7 M( i
                       f[i][o + 1].add(diff - p);- c7 e3 M+ h& Z5 C; ]2 F& Q* h0 j
                  }
* v1 b/ m* s$ R# Y7 ^2 c              }! k. h4 s0 {5 u- Q- d6 q
          }' p4 k9 X  ~/ e2 J" E4 \9 x4 }
      }& N6 Z4 L1 ?" j6 z4 g1 Q
       return f[n][m].contains(0);
) B% P1 h% e7 ?( [  }1 G7 @) J  R! R, `  X3 d9 T0 @
}: X5 G8 W+ b4 d
您需要登录后才可以回帖 登录 | 注册账号

本版积分规则

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