登录后可回复主题
您需要 登录 才可以下载或查看,没有帐号?注册账号
x
【 NO.1 检查句子中的数字是否递增】2 q7 }- N% _- `4 J! |
+ X5 M: l6 e; q2 V6 A: S解题思路
1 F' K: H9 j6 @签到题。9 H4 g$ } ]; O; Y7 E
1 \( Z1 j' J1 {6 R/ X. j
代码展示$ x( P, [7 E4 |2 ?3 G
1 d. G5 S5 d$ G6 _2 F D+ Vclass Solution {
: Q" T: U- q3 o public boolean areNumbersAscending(String s) {1 D. c7 [ e9 P
var strList = s.split(" ");# j+ ~7 O6 O. P2 B+ L+ k
int last = -1;4 ^- F( i) c5 Z. z& w8 W4 ^
for (var str : strList) {
( f1 }8 Z' Q) g& s0 I+ O try {
$ g2 ^: n" |1 b) g8 K/ Z int num = Integer.parseInt(str);
, M% I3 ?. \) d- C, [' x- G if (num <= last) {
: A9 Z& A4 Q/ ^4 P6 s8 U return false;) q7 A* C; |0 Q. A% U
}8 J: B* u- x$ e/ c
last = num;
* u9 P# R$ J+ [4 d, b } catch (NumberFormatException ignored) {( a) w' z8 ?% d7 e' K9 I
}+ W% v, \8 l7 ]0 T# d) P$ s
}
& ^2 p1 A) }4 v O9 n- N2 s* N return true;
; G3 {% G" [3 \% b# t. g% Y S }
7 u# m& _ i7 V4 T+ H; X; G( Y2 U}% E0 Y$ v9 _* S7 R& p. J
" P- |' }0 \3 F" ?- e4 p7 l
}" F$ Q! p6 e2 P/ D
【 NO.2 简易银行系统】
, |" v$ o' h) x: D$ Y6 t5 z! E/ z4 \$ ?6 N* t k# i4 j
解题思路
% B f: I( R0 K2 f1 Y约等于签到题。如果题目说明 “可能多个人同时操作” 还好一些,那就需要加锁了。4 L5 B, t: O2 l5 @+ b6 ^/ r: Q4 E6 [3 Z( j
$ L8 `6 Z! _" y# ^9 |. i
代码展示
`1 |2 B% d- @3 ^: [- p( r# l" y B$ B, t
class Bank {) x6 L4 Y4 o! J. `" z3 @3 i
long[] balance;
) ^3 w% A3 V) Z8 ^& P9 K# n public Bank(long[] balance) {
& ~" i' k- ?& Z this.balance = balance;
( b" l* V) _) ~- ? f }* Y: B5 Z$ J6 ?
# _) R$ Y2 D( X$ U; X+ C& V
public boolean transfer(int account1, int account2, long money) {
( V, J7 u. o& H+ X account1--;
0 R" M9 p, B3 |; g6 L account2--;9 j. }/ T, f* M$ [8 X- z
if (account1 >= balance.length || account2 >= balance.length || balance[account1] < money) {3 C$ L4 X' \, e+ a: a
return false;) O M0 _5 t, l9 Y
}/ }# p9 `7 o! d0 Y
balance[account1] -= money;
7 r7 B' ^1 G, z7 N9 d0 d; G balance[account2] += money;
' ?+ w" f7 k' Q# o return true;% r0 |$ Y: g9 e& Y; | _/ d* |+ m
}3 ]/ T7 B8 z8 Z. Q
* i1 ~( K+ Y; \% [% I, J* p
public boolean deposit(int account, long money) {
5 D7 p5 Z& j# w4 I6 F& T* | account--;; B; N6 i, U/ N3 \. z6 V5 H5 ~. I
if (account >= balance.length) {- T; o0 V$ F0 I+ H1 f
return false;; m- u8 g+ F$ J6 ^& D f8 Z1 F$ s: D
}
$ P- Z$ ~6 I I' J" F balance[account] += money;$ \' k( S) g/ a9 ~' M
return true;$ k! l, g/ N6 q+ X2 m3 W. O
}0 X9 d9 D4 \7 R( [7 E4 |
) X% V- s, Z# s7 R2 X0 V) h public boolean withdraw(int account, long money) {
9 a% {8 m0 b5 A% G account--;
" g- @" t# ~$ G' p if (account >= balance.length || balance[account] < money) {
+ b* Z* B9 B7 u X Y return false;& a% _! J+ ^4 {+ A9 M9 v
}
1 x' r# Z. f5 E' v B( Z0 |* Q6 n balance[account] -= money;
( s2 @8 ^; F- B2 [, O5 p return true;. J; e2 c( n! Y% X1 T/ R4 C( T, d: g
}$ n7 _. V$ l d
}, x d' d- z7 W3 r* } B7 [
% C) q' A/ _1 i# f' T+ M
# C" o/ Y6 a7 q【 NO.3 统计按位或能得到最大值的子集数目】/ x% I2 }/ ^. ~9 H S8 v
~- y& r E' n/ A9 b
解题思路
$ ?4 g+ Q5 m( o! f数据范围很小,枚举所有子集即可。 X' U+ F0 _3 P- p F
7 z- e' x' S+ u }4 l2 N
代码展示
8 k- J( }2 g* L3 Q* m5 h& n! H4 d# j2 {. h d
class Solution {/ }: V, V' \- E3 {0 } ~
public int countMaxOrSubsets(int[] nums) {
6 x* I2 d( ^6 Y& M7 F X int max = 0;9 x+ g' ^) ~( e/ t( H$ S" Q
for (int num : nums) {, e0 U% ?. U, j5 z0 n% R
max |= num;
* R( y# O1 ]) Y3 O- B# v8 O }+ D5 k( I2 {7 r1 @# o7 _
int res = 0;! }) K! A5 X5 K& K5 ?7 O) R5 M1 G
for (int i = 1; i < (1 << nums.length); i++) {, ~. m% @1 ]: u9 o% Q1 \
int or = 0;/ y5 `4 {9 Y: W( |7 G+ F0 m
for (int j = 0; j < nums.length; j++) {
4 t" a" \" w9 N& j/ x ~4 k; R- X if (((1 << j) & i) != 0) {$ _# `( N" c' m& ]. k+ }1 K+ _
or |= nums[j];
( I% R _" |" z6 j6 ] f# S }# Q7 S) n, @. c- e
}# x3 c. ~* r0 {6 }: O
res += or == max ? 1 : 0; _+ ~& }. h) Y6 g X+ _( z4 E0 @8 [. k
}
; @ q) o( w6 ~7 o6 T return res;
$ Z0 h1 t0 f( l8 x }
( j& q% ?2 I4 r1 D6 T1 B/ G. a}
8 B/ d; I8 X' v/ ^, `3 }
- }( c. K P5 e( M1 o
! g- k7 \1 s0 y- `: A' v. X【 NO.4 到达目的地的第二短时间】; X+ K7 s5 x1 k, w. k
+ w0 U2 I. P3 z: o' k
解题思路9 @# K" }' d T% i
2 `# \: ?' e+ G: } c- {4 z% \
Dijkstra 求次短路即可。需要额外处理的就是红绿灯的转换,下述代码中,将等红灯的时间算做到达这个点的时间,比如从 A 走到点 B 后需要在点 B 等红灯 x 分钟,那么就相当于 A 到 B 的路径长为 time + x 分钟。
6 ] D" e5 C5 z
9 Z+ d |8 ]9 z& s" A6 V代码展示
$ L! ^: U/ s. s* O" t @7 I+ C
) `2 N" _; D- A# o" u4 {class Solution {& H+ e8 U! n+ Y1 ~$ i/ L' Y
static class Node implements Comparable<Node> {# r: t8 x) I7 y
int min;
1 M" [' P: v# |# a r int idx;
* B4 X1 w. N& Z N4 g0 z$ H! {7 Z, X0 P
public Node(int min, int idx) {" \: M7 x7 |/ |
this.min = min;
w" u% R6 Y; i" ~ this.idx = idx;$ W; z# j/ C7 t$ r) Y5 Z* [# m
}: D5 H# N% _/ E. G2 \) K
, {5 \, K/ ]- G, a @Override! L3 i8 l1 J, h$ X0 n" [
public int compareTo(Node o) {. q6 s1 T8 r1 Y& B
return min - o.min;
0 m$ O% k* m, P }& `2 i9 X* B" y; a ~
}& E8 y v5 L- I; e/ g
0 r6 D3 ]8 v2 h2 ~( n% R# g2 _
public int secondMinimum(int n, int[][] edges, int time, int change) {
) j- o" |" f: r) a% ^ List<List<Integer>> graph = new ArrayList<>();
$ C6 Q! x1 ~+ U; ~. Z# J5 u: y4 f for (int i = 0; i < n; i++) {
: F. o0 _/ w3 f; P! j graph.add(new ArrayList<>());0 ?' ^6 `; T4 D, B" s1 N& w
}! }% l" S# h. j! t6 |4 N
for (var e : edges) {
3 O! ?, x9 P( |/ L/ }) f+ V graph.get(e[0] - 1).add(e[1] - 1);& x' e4 b/ V9 t7 h
graph.get(e[1] - 1).add(e[0] - 1); O, n: ~ f: z% Z9 w- c+ G
}% p, K% W) x6 e! u: t( s p
R# R6 ~6 P- E M) r int result = 0; // 最终答案
, `* a6 |1 ~2 {' [ int[][] min = new int[2][n]; // min[0] 最短路;min[1] 次短路 (min 数组包含等待时间)- m& d+ {1 g7 Y2 p, I
Arrays.fill(min[0], 0x3f3f3f3f);- U) ~8 x5 r- e. B! D5 e I( b6 h
Arrays.fill(min[1], 0x3f3f3f3f);* Q g" F, C$ v+ i
min[0][0] = 0;, @7 j) S6 G1 R0 `- }
PriorityQueue<Node> heap = new PriorityQueue<>();
! h- M* O; H) @6 V4 o heap.add(new Node(0, 0));
# D0 z/ n" t8 A while (!heap.isEmpty()) {
. f8 P- B5 i3 u Node node = heap.poll();0 S$ x! p5 I6 U1 I2 }9 b
if (min[1][node.idx] < node.min) {
2 v# p0 X/ o$ W! d M3 q continue;2 ^ N: m) {( ^( ~
}
+ F+ g# y! k6 \8 ^% v for (int nxt : graph.get(node.idx)) {5 Q5 d, c$ ?, L. a+ `
int nxtMin = node.min + time;: l9 h. |5 Q0 C' G6 ?" Q
nxtMin += waitRedLight(nxtMin, change);- F1 j0 T0 I; g/ p* c: ?
if (nxtMin < min[0][nxt]) {
2 a: h9 S& U! c: Z y int tmp = nxtMin;4 e8 r' Q5 B( |/ n
nxtMin = min[0][nxt];7 n1 E$ o! i4 Z3 k6 V! n4 `
min[0][nxt] = tmp;
0 ^) `+ n$ G3 |+ C8 c4 l) d* h8 [1 U heap.add(new Node(min[0][nxt], nxt));6 R; j* G# k/ H
}
1 k2 r) c, [/ U5 L' }% D2 w if (nxtMin < min[1][nxt] && min[0][nxt] < nxtMin) {
' W+ O7 C! z; L9 l g; r if (nxt == n - 1) {% ~% F) H6 \1 R8 k* v; Y
result = node.min + time;) n8 q/ U. l" }$ i
}
# H+ }4 j0 d+ a, _; | min[1][nxt] = nxtMin;; V0 m" f* j$ ?4 y' `/ r
heap.add(new Node(min[1][nxt], nxt));" ~! S) `0 V. v8 j; S$ S. y
}- W4 K5 D4 I H- r6 S
}
, w S' ]' H) @* G' d6 ]' p M } F9 J5 d9 z4 }9 ]* h3 g
return result;' m8 _% ~' i& h. A
}6 Z' {+ J- L# h9 g& T* ?% T' \
8 Q4 o$ I6 [) ~( W' W1 y# K2 P
private int waitRedLight(int now, int change) {
$ w4 O! W9 ]0 Y7 R if ((now / change) % 2 == 0) {& V: ]: b5 l* R5 E* r, F
return 0;
+ @/ P+ O2 O/ _. V: R }/ {: P7 d% [% x/ n( X2 {8 M
return change - (now % change);. }+ z) l4 J. K/ O/ b- C' P( k
}
6 ~9 d& F$ b+ G. }; T' G} |