登录后可回复主题
您需要 登录 才可以下载或查看,没有帐号?注册账号
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 |