登录后可回复主题
您需要 登录 才可以下载或查看,没有帐号?注册账号
x
【 NO.1 得到 0 的操作数】
2 J, N) w- R0 ^. L9 R+ _! x: U& ~3 J+ q2 e5 ]
解题思路
' |+ D% ]: J; s; I签到题,模拟操作即可。
) v5 U+ x4 B& ^0 I/ a' H1 @# I. _$ u$ r: z/ T" L
代码展示
' O4 R u+ ^; m1 H d, t
7 d2 R9 m* s8 z1 \class Solution {1 O i* V( P! `4 m6 `+ o
public int countOperations(int num1, int num2) {- v3 s" I( D) P6 a+ F
int res = 0;
+ G* p# R1 O6 q) G' p; v for (; num1 * num2 != 0; res++) {0 g* R0 U% v4 Q% ]. o* a
if (num1 > num2) {
, e7 R4 J i, a, f/ s% v4 _, X num1 -= num2;
! b Y4 B# B) q } else {
7 F- Q- j3 C1 M4 Q9 E num2 -= num1;
, R( {$ Z# W( d4 { }' b) L5 G, K, z7 s5 G
}* O: n9 J/ x9 Y/ G9 x" j% A
return res;# s8 L, p% g3 w5 O, v& C) \+ X
}! K) R; @ j) S$ s
}# e3 D: D9 U* H. S( C; u8 _. b
; i0 O( x" l; R, p& n0 a3 ]" ~1 V8 q: n/ m5 T& Q3 z
【 NO.2 使数组变成交替数组的最少操作数】
/ T9 M2 h$ N" G I: \7 @1 }, b6 _2 s( l6 Z/ |+ Z( O
解题思路 O5 H4 R+ t! E% h5 C0 @' \
统计每种数字在奇数、偶数下标上的数量,然后使用最多的和次多的作为最终数字即可。# K: b. e; r! [. a
3 R4 x; n/ w/ {( [4 K
代码展示- B9 |0 ~1 C! |& Z. {5 U' r
' \* t: B( K2 g/ Y7 G- G2 p
class Solution {0 r$ n& m( |% R% w: w
public int minimumOperations(int[] nums) {
& g! K- ^9 T, q1 a0 P* x6 d Map<Integer, Integer> cnt0 = new HashMap<>(); // 偶数下标计数
* v% Y) ^- @. h' [ Map<Integer, Integer> cnt1 = new HashMap<>(); // 奇数下标计数0 v( z6 b" ~) _+ P; b" c' Z
for (int i = 0; i < nums.length; i++) {
; t( O, X/ c; \( G! F2 E" S if (i % 2 == 0) {
( I2 \5 G1 y* I; p V8 x cnt0.put(nums[i], cnt0.getOrDefault(nums[i], 0) + 1);
6 U- K: u& }1 N( a0 s } else {
! v7 V" }, G0 A, Z cnt1.put(nums[i], cnt1.getOrDefault(nums[i], 0) + 1);
# v/ U5 \! V1 D0 ^) b: i y# g }1 `' Y4 `& v& d* R; ^
}5 p/ q4 ~' g+ q: D# O( W: k
int[] cnt0Max = getMax(cnt0);
6 e& [7 q" @4 s: p5 ? int[] cnt1Max = getMax(cnt1);# }& y% _9 Q+ r! Q1 g: L
if (cnt0Max[0] != cnt1Max[0]) { u* ?" f3 l1 R7 `4 S
return nums.length - cnt0.getOrDefault(cnt0Max[0], 0) - cnt1.getOrDefault(cnt1Max[0], 0);
$ h" C+ e: m5 {* H4 W5 B }
5 w6 K# t) r* i. A& a return nums.length - Math.max(6 _6 T; Z: z `
cnt0.getOrDefault(cnt0Max[0], 0) + cnt1.getOrDefault(cnt1Max[1], 0),
5 X" v( ]5 u7 K* c) }( Y cnt0.getOrDefault(cnt0Max[1], 0) + cnt1.getOrDefault(cnt1Max[0], 0)
. A+ {" S' P% t1 ]! C );* Z) m3 e! n. H3 u) A7 a& O
}
" l x0 p' I7 m5 `( L
8 h% b& w0 t# d* E/ O private int[] getMax(Map<Integer, Integer> cnt) {5 Y7 X5 b* S% m/ H3 A# V
int[] res = new int[2];
3 [% E4 X! e; H4 q for (var c : cnt.keySet()) {
. @' }7 ^4 y) B( @9 r if (cnt.getOrDefault(res[0], 0) <= cnt.get(c)) {
0 b6 B8 A& S0 t" Y7 a res[1] = res[0];
, ]4 { ^ K# V. y# C: D res[0] = c;
; I+ \5 X! c A- Q } else if (cnt.getOrDefault(res[1], 0) <= cnt.get(c)) {# X" K$ |$ [6 I2 Z @9 ?
res[1] = c;% t/ E7 u& X$ j' ^1 N
}
" k3 o/ S0 y* G. c- g# I0 _ E }) N* Y8 H* a5 E' v( f
return res;
" r% t8 Y3 |, [6 h) w7 R1 Q }
) t! v5 K0 q! l( D}$ Z% h& b) W) \9 v) a A* h/ ^
9 }! ]0 W' ~7 { E" _" L7 B' F; o$ W% l
【 NO.3 拿出最少数目的魔法豆】
- V: k; y9 N% I8 J4 l6 Z/ ]( m% i ?! I) V, N8 B5 U
解题思路* S" \ X5 D" y% o% i' B0 K+ ^
前缀和。排序后,枚举分界点,分界点之前的全部置零,分界点之后的全部置为与分界点处相同的数目,通过前缀和可以快速计算。
. n1 Z j+ d9 V8 Z8 h6 T6 O% }$ v5 _4 Q H; `/ X1 f( m2 D1 d$ X* E- a
代码展示. e' V+ f) N6 r7 a! z
( j6 z0 l' ~% A3 I
class Solution {
+ ]! Q f8 S+ m- h public long minimumRemoval(int[] beans) {/ G9 K0 e3 e, V$ F* s! |
Arrays.sort(beans);+ A2 A4 ?3 D. Y6 g8 s, g- _& k
var sum = new IntervalSum(beans); n# ~; G+ ^" l5 W/ M ^( [/ @
long res = sum.suffix(0) - (long) beans[0] * (long) beans.length;" f0 U3 y& H$ a K Q
for (int i = 0; i < beans.length - 1; i++) {
6 w- n1 P& T) j8 i // [0, i] -> 0; [i+1, length) -> beans[i + 1]
* k1 Y# x6 T% B! ^ res = Math.min(res, sum.prefix(i) + sum.suffix(i + 1) - (long) beans[i + 1] * (beans.length - i - 1));
3 S; W7 W5 x5 x" Y }
: `$ [7 J: X4 Z7 \ return res;" Q$ u- K6 H0 S
}& {( `. C, D' U7 V
}
% j, @) J0 G, s1 D% X e* D$ _% x7 V5 e
class IntervalSum {/ b3 R- O/ f& h3 W! ]
private final long[] pre;
' C" T, K4 ]* T1 v$ b+ ~
# T: N( w3 s$ m7 } public IntervalSum(int[] arr) {- F* s) u9 F. B3 ~1 o! L
pre = new long[arr.length];
- }. q5 z; O; w) D7 b- N pre[0] = arr[0];% \- a. ?! j$ F" E7 p
for (int i = 1; i < arr.length; i++) {
+ b! V) S" a7 ? e# X pre[i] = pre[i - 1] + arr[i];
2 ^# n* Z1 O& W% v: L# @ }$ u4 `# e& q' Y+ a- ]2 Y
}9 g& G' R d* m. i8 F3 k
1 _, R3 _+ Q( x. T
// interval [0, i]9 l& U, A) m$ s8 J
public long prefix(int i) {& T% K5 B7 q8 u7 S& i
return interval(0, i + 1);
% c1 J" g5 B' }' |* i }
9 W( w4 Z* A0 \8 J! \3 y# b, g: a- V9 R1 F
// == interval [i, length)
B7 y& W+ e M3 S0 k5 E public long suffix(int i) {
4 ^# R* v% G3 {' O7 p& i return interval(i, pre.length);0 J# g( }# W* X" X
}( {. [8 B" U* I4 F- d5 F( J7 K, E
; j7 E! @: q5 d4 U/ \8 v! C // [start, end)
6 V" m; ?: [) U# J8 \% b public long interval(int start, int end) {
9 |/ `+ V5 @+ j! z3 z: i. a( p end--;
+ M# a3 N- n1 d. O+ z3 _ return pre[end] - (start == 0 ? 0 : pre[start - 1]);4 Q6 ^# b3 _. V* w' u, @( ?& l
}2 M2 o+ v' ]/ C. q& X5 |
}4 j6 W7 j( B# u
' O( o( q( V) B5 {; L P% E
9 o8 ` p6 R5 O, H3 T1 H1 y【 NO.4 数组的最大与和】9 h4 m2 c( ~" M% r$ V1 V3 [6 u1 H
/ y S m- _* y
解题思路* j2 {" w0 X" b! U) b9 H+ k
记忆化搜索,令 f[i] 表示 slots 状态为 i 时,还能获取到多少加和3 J9 f. E' s: u0 d' ?3 d3 f: q
3 r5 u- p0 P P5 q; @* Y
状态转移:枚举当前数字放到哪个 slot 里面' `7 _7 y& o2 K5 e# ?2 I+ i
1 O. S |( k8 I$ o) e A0 O$ Q
答案:f[0]
: @0 W- @+ { O4 B* F1 r! }8 r8 y. P( |7 y
其中 i 是一个 18 位的二进制数,每两位表示一个 slot 里已经放入了多少个数字' L9 T$ \4 t. z9 h4 k7 h2 I4 j$ c
) \ X4 G+ K% Z
代码展示
. s% |& V# K# n/ r; y6 \* X2 E" X+ K
3 s# h# v, k( p8 A. @+ Y9 T" S' Iclass Solution { ]- \8 O4 y" I7 E8 ~
public int maximumANDSum(int[] nums, int numSlots) {- d4 V" I& A0 P' ]
8 j1 v6 q, ^. K Map<Integer, Integer> mem = new HashMap<>();. g! }. \. S% ~2 v7 S' A& d
return maximumANDSum(0, nums, numSlots, nums.length, mem);
* Q4 C& T8 Z: D5 y; o }6 J" ^8 Y/ C9 ~0 }% Q( U
8 N& v6 y$ H q# I% l; H* H
private int maximumANDSum(int stat, int[] nums, int numSlots, int numLeft, Map<Integer, Integer> mem) {. x1 Z8 P- X T! a
if (mem.containsKey(stat)) {
4 d; \8 u2 y) O& ~ C return mem.get(stat);
. b3 v: t% ]( [$ z3 s4 q o3 k }
( A3 n1 h6 {" `, ~! S if (numLeft == 0) {
8 \( s, R3 L5 t- s7 x# D4 |/ g return 0;- S# o: E( i2 ~( C( W7 e! C
}
. W2 a% e: X0 S0 V R9 R$ p5 c: W+ u
int curRes = 0;
! _9 H0 [1 m$ n. U) H/ n$ V( W+ @ for (int i = 1; i <= numSlots; i++) {
! F+ y1 i; Y- p$ l0 d int slot = getSlot(stat, i);
R0 P/ o. u$ i; `6 r; I# S if (slot == 2) {+ E7 E) Y6 g9 @' a) \
continue;% _, ?& H$ M" ~ M7 R
}; ~9 C; \' |9 @- L7 V+ B
int and = i & nums[numLeft - 1];
7 h& f& w& q) S4 l% V. n int stat2 = setSlot(stat, i, slot + 1);
! |+ R. l; ?+ y. ^0 e$ U! y curRes = Math.max(curRes, and + maximumANDSum(stat2, nums, numSlots, numLeft - 1, mem));
9 b5 h# r& `4 o& I( J% U/ p0 G }
3 h F+ d# w9 D( C s- R* @0 f( r, T. k
mem.put(stat, curRes);
% n: X3 Q4 g. b& ]7 r8 @& \* ~ return curRes;
- W) f6 H- e7 \( f }1 q s1 Z3 |+ E% Y4 _- P
- D: R6 T1 _$ Y; U0 W# K // i start from 1 x% D, D x/ G# X. g9 V; C
private int getSlot(int bits, int i) {7 |0 T5 v' ]8 `
int offset = (i - 1) * 2;
/ ]$ q5 K! F/ z8 v; l return (bits >> offset) & 0b11; S2 d4 n( f/ C# p- e, s/ Z& F
}9 s" h) p# q9 W
; W0 G4 G& _/ F) e$ s9 @2 O$ Y // num = 0 or 1 or 22 S, f2 J |& l1 M- I$ a
private int setSlot(int bits, int i, int num) {9 L) W$ a) S) g4 F, B
int offset = (i - 1) * 2;$ f, i; I) J0 O1 y' C
bits -= bits & (0b11 << offset);% I$ y8 _4 j w& `0 ^
bits += num << offset;1 o1 A4 e: u' F3 R3 [# s
return bits;
" H; \. c4 ]( V+ N, E/ w }7 P5 |4 e) C! H$ C8 k
} |