登录后可回复主题
您需要 登录 才可以下载或查看,没有帐号?注册账号
x
【 NO.1 统计特殊四元组】0 C+ H, @, ~8 M4 v( p
解题思路2 P' N4 t9 ?: q' X
签到题,枚举即可。
" F" N9 _: g" \, N3 ^- [+ z7 c
' ]' N7 f: ^- z, X3 X. J, {! u代码展示6 K! K/ R, `/ e0 ^' h4 z
8 I: ^" @7 X7 P& Dclass Solution {
$ l7 ]1 ^& w1 k! q$ ~ public int countQuadruplets(int[] nums) {
* \4 l' w( a2 Q* j$ `( u. q3 o% z int n = nums.length;
$ A! ]5 n; v3 F( U) B% D! d! Q( P int res = 0;
1 |6 Z q0 |, C2 @$ a for (int a = 0; a < n; a++) {
9 j! I; m' X; c" g for (int b = a + 1; b < n; b++) {
9 D* [: O$ e6 r& l* I, R for (int c = b + 1; c < n; c++) {
& K! n( S6 l; N9 Z" H- V$ M for (int d = c + 1; d < n; d++) {
+ y, u( ?! \' u1 R) d: G% @ if (nums[a] + nums[b] + nums[c] == nums[d]) {
$ d( ?4 G) o+ n res++;
4 K! K! a5 ^+ | }
& r$ Q/ m7 l# d. K. s( x }
9 J* `5 g0 u* u' n }
5 |' Q, F g f# G* G2 U% R }
% j% {$ P' R- [& v/ U, J }
8 N# J8 M% E5 R' F return res;, I2 Q5 k. O" o; j0 ~& _0 o9 M5 X
}4 v$ P* P) @/ y+ K0 q$ O
}
5 ^1 Q" q) k! M! t1 I" N K- g1 b% d
: N9 G' T' V) e; o) \: z# I
m, Q9 y. Y3 c
# T! `% \, q" K* \6 ?' g3 I; N【 NO.2 游戏中弱角色的数量】2 x! Z; Y$ I& Q
解题思路
) W1 j) ?- H9 z% s5 z按照攻击力、防御力从小到大排序,然后逆序统计即可。要注意处理攻击力相同的情况。/ g" D: O0 [ y/ ]
+ Y5 X- L: N# C7 {: T
代码展示0 q+ j% \% J) D9 K- ~* j0 C( a
/ x/ ]. t/ p1 H$ N# Z( ], hclass Solution {5 |) [% B& E* ~4 j
public int numberOfWeakCharacters(int[][] properties) {5 r7 p* u6 |$ }& g" }. w
Arrays.sort(properties, (a, b) -> {" X6 H$ ^. @' V/ c& L
if (a[0] == b[0]) {1 e# u$ q4 _1 ?5 V' Q+ h
return a[1] - b[1];( M6 c9 e- s8 i% z1 c
}( h% d J" z; F; h( @6 L$ K! v
return a[0] - b[0];4 D/ t3 ^8 i6 |0 c( e' g
});
! M k) H+ D( a( p int res = 0;4 `7 ~+ U4 u' y
int lastAttack = properties[properties.length - 1][0];% r+ t$ q8 y7 I& y
int lastDefense = properties[properties.length - 1][1];" z2 b, u( M' x* X2 c3 C. {! `1 d
int maxDefense = 0; // maxDefense 表示大于 lastAttack 的角色中,最大的防御力
- C( b) G' U6 R, t for (int i = properties.length - 2; i >= 0; i--) {$ e6 m4 P$ A8 V \* B
if (properties[i][0] < lastAttack) {/ A# E* I0 d5 v1 K% E
maxDefense = Math.max(maxDefense, lastDefense);
) d" J6 H0 Y8 a1 N lastAttack = properties[i][0];1 g. I' w( n& t" r8 Z9 v
lastDefense = properties[i][1];8 [ U6 S- k' Y/ `; w2 B* [- r- A
}
- G, |6 r2 P8 X# [ if (properties[i][1] < maxDefense) {! ~ h a- w1 e$ c
res++;
) A! f/ u R6 q# ?: f }/ W- r- d8 [, l0 Q- \% S9 ^) e g6 h
}
$ r5 o- J+ q$ O* n1 S+ Y return res;! [% F! P+ @- T/ A9 w# \( Q
}3 e2 }/ T7 ?2 J2 {1 s1 T& H- O2 G
}
- q% e4 M* c! ~0 a, t$ w! M- F6 w/ Y# R/ d8 H; j
: V( h! j, Y& }. f1 a+ e: p! D' R
【 NO.3 访问完所有房间的第一天】
; W6 B2 o a4 I: |# o* J* P
- r& C4 T1 l7 u4 R/ O解题思路$ o+ w/ j: }1 C' s F
动态规划,dp[i] 表示访问完第 i 个房间的最小天数。, ?# c9 \! g$ e0 \8 _: y
5 E" Y0 M# a7 ?/ U$ V$ @+ k& K [
代码展示
9 }9 `9 n* f2 ?" {3 Y+ Z4 E9 v* v5 {; R) L2 y P" ^0 o
class Solution {' K! L) m/ R$ q
public int firstDayBeenInAllRooms(int[] nextVisit) {
% a" ]3 ]% i P9 ~2 G0 { int n = nextVisit.length;) a% ^5 i! b/ J0 g5 _5 H
long[] dp = new long[n];' x f* f$ ^5 T7 q
long P = (long) (1e9 + 7);
9 R }- J, k! |* p* J for (int i = 1; i < n; ++i) {
* r m$ l' w2 |3 i0 u' p dp[i] = (2 * dp[i - 1] - dp[nextVisit[i - 1]] + 2 + P) % P;! _: ]; u. o% L% [+ u8 P
}
9 l4 J6 C/ `- \4 h return (int) dp[n - 1];
! w! [3 V; F. {. ^ }
* ^, m/ e' x( A% N8 P}
4 t3 W& l$ x' G% F8 ~7 e- p0 v: ^* g3 m( x. z
【 NO.4 数组的最大公因数排序】
" H' U. v: `6 h9 T/ Z5 Q- l# m1 J/ G% E8 ?1 C3 p
解题思路
5 c- h; a/ `/ _3 |- y只要元素之间有公因数,那么他们就可以任意排序。所以我们将有相同公因数的元素排序,最后再看序列整体是否有序即可。 \" u+ p) I7 _' _: p6 f. M4 F
! H$ H# w) A/ v4 \- z- s/ u9 e! T) p: [; Q
代码展示, a# j5 |; l: W0 b: {
$ \( j' l# \3 F1 k7 V% s0 Uclass UnionFind {
$ \' g4 n+ a4 @/ W" i public UnionFind(int size) {
, f: f/ D: |3 z9 H' W2 R( H f = new int[size];; J. `; R/ g4 s1 i
Arrays.fill(f, -1);
# a' c3 w$ }( o& W( [; ?2 @# } }
" G: F: x+ i0 s" i
- ^( m) {* K7 w7 s) N/ g- O public int find(int x) {
* s* p% m9 g: @8 \, P2 A7 p |4 Z$ b if (f[x] < 0)
8 v) j6 e2 Q, ^2 j( S6 c return x;3 K6 }5 r; \6 {. }9 j! F& e+ Z
return f[x] = find(f[x]);- U* e# A ^6 U e' }$ \- U
}0 c8 R$ U1 O, w0 ]3 Y; w" z) Y
& r. j% C! @8 A
public boolean merge(int a, int b) {
$ X/ F! m( S" D5 V, y/ g; l int fa = find(a);
$ s0 b ^1 U: e/ M% x( z! s: R# c int fb = find(b);% f0 N6 f& j/ K" ]) \8 x
if (fa == fb)/ t# K* G- L6 X3 _
return false;9 y) K+ u" }: M3 h0 V5 i
f[fa] = fb;* h5 U4 G( K& N' h' r
return true;! S/ E3 g7 o8 a% P: E* b9 Z* L
}
: Y6 j! I# ?$ v5 S6 b, `. C: i" c( M; }! j
public Map<Integer, List<Integer>> sets() {
$ p x* D U$ ~+ E Map<Integer, List<Integer>> res = new HashMap<>();' J [( H6 s2 V' B9 n6 `0 T5 q
for (int i = 0; i < f.length; i++) {
7 T7 d, N0 j5 q! D! ?& B* j5 j int fi = find(i);+ m+ }, {2 f% t f; f, b4 W, L+ V
if (!res.containsKey(fi)) {
4 E2 k( Z" L% H- e& t6 Q2 c res.put(fi, new ArrayList<>());
1 D/ F* J; U9 Z3 I8 @' i0 e }6 P% z* K. W" O% P) `! l
res.get(fi).add(i);: m* z8 n" f+ e6 l3 y. b: F, ~
}
4 ]1 o7 S9 C$ c H0 h1 t0 ` return res;
l9 I' r$ ?, X! i2 ] }
$ a6 ~1 _" C# h! ?) R
; R4 G% {8 U! n0 q; R$ P" y$ W( d& Y private int[] f;1 u, Y5 L7 n" g! [6 f: U3 E
}
5 t ~0 W9 l0 I& A$ R% e: k+ z
; |: ]8 f. L1 k: g# q+ o+ C
. m0 [% j: F6 f6 Z% ?0 [1 Cclass Solution {
: M( {; e7 a: P# c* s public boolean gcdSort(int[] nums) {
: _6 U n$ z; E9 H Map<Integer, List<Integer>> set = new HashMap<>();7 X9 o+ I3 I% Y, Y
for (int i = 0; i < nums.length; i++) {
( q5 I U+ i4 U& n# k1 O6 I# R9 y& o for (int j = 1; j * j <= nums[i]; j++) {5 ?8 K4 R3 I/ g6 {4 s7 B. G% }! h
if (nums[i] % j == 0) {
# n/ t( A; g: `% Z if (!set.containsKey(j)) {5 x" w9 E* A$ Q9 P
set.put(j, new ArrayList<>());" Z! T9 M' M8 V8 d8 I; s
}6 p s3 g3 W7 E% {( H8 [
set.get(j).add(i);
f7 C/ p- E, z8 E- b$ q, P0 t if (j * j < nums[i]) {6 y% R/ k) D/ z/ h/ s
int k = nums[i] / j;0 t5 l+ N$ u* `1 T0 m: Y
if (!set.containsKey(k)) {
. t3 |% p6 v0 I2 M( E2 u' j O set.put(k, new ArrayList<>());
* I! x0 ~# m3 a* u8 k. D* l' k X }2 b+ `3 X% P; o( |- L# O3 x
set.get(k).add(i);
, b# a$ U' x8 d5 Y: C9 o6 A1 y }; k; D% M. O$ s4 W+ l2 c
}% R3 j% C) m5 g2 e1 d1 B! ?- o1 _
} ^8 z( H6 w8 P8 Q$ J y
}
- t$ c7 Z! @5 d) }4 K C9 g+ l9 }' e9 @! J9 e" v! z
UnionFind uf = new UnionFind(nums.length);. y) u& _% Y9 G) i }
for (var e : set.entrySet()) {
: a, `$ ?% `& N3 L# y; C if (e.getKey() < 2) {! N& x$ x: x( C6 Q4 l
continue;' r% C, o4 l! Z' U/ a$ t
}) \% k" n/ ?+ ~9 \& d1 w
var list = e.getValue();
: z/ b* h7 M) W/ _ for (int i = 1; i < list.size(); i++) {
( f# l6 H) X- @7 U uf.merge(list.get(i - 1), list.get(i));
/ _) n: a6 [, q- O' b7 W% I( n: q }
4 f* ?0 I5 ]) C1 ~ }
( G% h. A+ t8 N8 O" i% I var sets = uf.sets();
2 d0 K/ Q! z; f& ` int[] res = new int[nums.length];+ M: d/ K* m" W. j+ ?5 F
for (var e : sets.entrySet()) {3 D- R8 f5 R5 k: ~7 X/ L
var list = e.getValue();
: M: g; Y8 v' [1 \; r+ H1 j var sortedList = new ArrayList<>(list);: ?8 k. V0 `: f
sortedList.sort(Comparator.comparingInt(a -> nums[a]));& T! V6 d6 y& a$ ~
for (int i = 0; i < list.size(); i++) {( C0 F1 v. Z; [ O' t4 L0 v* m2 w
res[list.get(i)] = nums[sortedList.get(i)];
3 j4 H& \1 k4 J7 G# A }$ b( P1 V/ S7 h# G
}+ _+ `( Q' N4 b9 W( V. t
for (int i = 1; i < res.length; i++) {/ _) E3 ]8 g' i2 G7 U4 r3 M
if (res[i] < res[i - 1]) {& T0 z6 U) c- [6 J
return false;
& @8 {) _4 P L* o }! L/ v' Y& f0 A
}
9 m1 x7 t+ n+ Q- w, W6 N return true;0 {$ c4 {" I6 Q( B# x
}
, j) M( u; k! K/ V( T0 F0 F; e} |