登录后可回复主题
您需要 登录 才可以下载或查看,没有帐号?注册账号
x
【 NO.1 至少在两个数组中出现的值】
& W, k& p- C. P- M
, n ` E# ]" @$ a/ ]7 h解题思路7 ]! q+ N6 l9 H2 G
签到题。
+ Z1 o; _$ z8 g8 L& o, Q$ C
6 q/ G: K- g) o* _4 {" `9 s代码展示( B9 L% p9 I7 z* O# ~3 G
- F+ B7 |2 J( I) [1 S# q
class Solution {- ` |# r% G9 N. c7 [# G
public List<Integer> twoOutOfThree(int[] nums1, int[] nums2, int[] nums3) {3 ^; o, `, V1 A; U- u# E/ v& W
int[] count1 = new int[200];
+ \5 r9 t# l* ^, ~- s/ K! l p int[] count2 = new int[200];+ k+ }; w6 v4 e Z# s& T
int[] count3 = new int[200];
( d g2 D7 \9 e for (int n : nums1) {# u3 T. e! ?$ }/ c
count1[n] = 1;" o8 R- w3 w" d5 a
}
) }" \, O" G1 p) ?" z for (int n : nums2) { }/ P7 x" G+ \ N; y1 G
count2[n] = 1;
7 c. t! v8 h' X5 }8 X }0 A: Q L/ z" t/ x K L, A
for (int n : nums3) {5 Q7 m) u% q7 f* _! W/ K1 h4 y
count3[n] = 1;
" X! f; t1 j! k }9 T0 H6 F9 r+ d8 [
List<Integer> result = new ArrayList<>();
( I5 p+ n7 }1 L/ I5 Y for (int i = 0; i < 200; i++) {
7 V8 C$ t2 r4 W+ d5 d if (count1[i] + count2[i] + count3[i] >= 2) {. \1 c* K+ C3 p% J; e. t
result.add(i);
% C1 M9 e2 c4 c }8 q! o: t) L" o m t% e- T
}5 ?$ A0 G$ e$ f4 V f
return result;
* D# i C$ P5 r' Q5 p }
7 [' J3 L+ U# j5 f) z}
( e0 l1 }# U. J, N1 R
/ O ?: h% t$ F1 A7 Q' H【 NO.2 获取单值网格的最小操作数】: w c2 `+ [" C# G
7 V6 h5 o l# z
解题思路& _& S$ x/ S% Z* J2 X, v+ y% T' v2 w
网格可以转换成一维数组,然后排序。
% @9 Z+ ~8 R. {' m) d* \3 r' I; J, K/ `; e
不返回 -1 的条件就是:任意两个元素的差都是 x 的整倍数,我们只需要检查相邻元素即可。4 ~7 z6 |2 L+ D) R8 S2 s9 F. ~
2 A% r; r9 S$ Z
然后枚举最终的唯一值,可以利用前缀、后缀和快速计算出把所有数字变成该值的操作次数。9 W$ g' x4 V$ W3 j
! s5 H5 v! y' J9 m# r1 }
代码展示
' Z& V9 Y; S3 v X5 a3 u0 o
) D' m% l. M% C" B0 q' N8 gclass Solution {) h+ c4 |- C2 H7 w( ~! n
public int minOperations(int[][] grid, int x) {
5 C4 a8 l! E9 p |1 `8 [ int[] arr = new int[grid.length * grid[0].length];# I3 w X- l6 V% E+ R7 Z2 J# ]# R) P
for (int i = 0; i < grid.length; i++) {* t4 O) ]$ u4 }% D" H1 k
for (int j = 0; j < grid[0].length; j++) {5 L# P$ P. Z4 X2 j
arr[i * grid[0].length + j] = grid[i][j];+ Q7 h. X# P+ w
}
* O2 s/ K" o2 j3 ^ }
6 o1 ]1 c7 g/ r1 F& B Arrays.sort(arr);
/ L8 m( ^3 N- S+ j4 w: Z& [9 B for (int i = 1; i < arr.length; i++) {
0 S, A8 J j5 ~, Z if ((arr[i] - arr[i - 1]) % x != 0) {! @7 E: W7 `* M' B- N) x" a/ K2 f7 u
return -1;, y8 L2 s6 W( F- M" y0 f
}
$ Z+ [) h* v# ]: T9 i" e$ Q }
+ L, b5 k% R1 n: J int suffixSum = Arrays.stream(arr).sum();6 V8 n3 N$ Q9 }. s" e% F
int prefixSum = 0;
# V K- m* B Z( L6 W Y int result = suffixSum / x;4 ^ c: p) A) B; R9 K# r) x
for (int i = 0; i < arr.length; i++) {
4 |4 E: p4 z, c* e' q suffixSum -= arr[i];
( H# p5 M8 b! s( D6 j result = Math.min(result, calc(prefixSum, suffixSum, i, arr.length - i - 1, arr[i], x));9 n7 C% N3 ~: B6 p. D
prefixSum += arr[i];
! F4 s+ p8 `2 e }
+ r4 y8 v2 Y1 S return result;
" B4 `; O& |9 N2 d; ~# x }: d7 X. G3 Y6 Y @
( {" Y9 }9 a' |+ K f& S: ?; t
private int calc(int prefixSum, int suffixSum, int prefixNum, int suffixNum, int target, int step) {
$ O0 P) s$ ]; r. b8 }6 F return (prefixNum * target - prefixSum) / step + (suffixSum - suffixNum * target) / step;
* M. |1 Q- \: Y F( Q8 @+ { }
5 J3 W; m, X8 x K1 w: Q0 [}
9 b# H' K8 s v) D& r3 f. G! z& M' \ L
【 NO.3 股票价格波动】
8 `$ \+ }3 M! c, c
0 {" A0 w4 I8 W/ O解题思路
; J* m( i! h, d8 a- ?使用两个 TreeMap 即可,一个储存时间戳到价格的映射,一个储存价格出现了多少次。; z: |: o* M% e; R+ \/ x2 z
( U7 r# C; v$ j& q( i% O2 B
代码展示9 J5 r# s) p: O5 [: b
, [7 H2 O3 s4 ^( V0 }
class StockPrice {) z( A$ k. |* G- j5 d' P0 l4 O
$ t2 e2 G" `* E) @" e
TreeMap<Integer, Integer> timestampToPrice;
c: N$ [5 i4 u; w" c( K' x3 X TreeMap<Integer, Integer> priceCount;
' R$ M0 s; Z% x! u( p
6 l. z& R/ ]/ K& T) T! m public StockPrice() {. I) N) H' J( \0 V& N! d; I; O
timestampToPrice = new TreeMap<>();( R; k# }) v! ~* o; r
priceCount = new TreeMap<>();
' L4 ?$ `3 h2 S( w1 x/ p$ C) N }2 q' u2 Y6 F, I
9 A3 k' B# a' c: N0 F+ U public void update(int timestamp, int price) {6 B+ C2 c/ A/ P1 h5 F
if (timestampToPrice.containsKey(timestamp)) {' k6 e* J' l8 u5 q6 u2 V+ `3 @1 _7 J% d7 e
int oldPrice = timestampToPrice.get(timestamp);
6 }2 [2 S! s, e$ L% M int count = priceCount.get(oldPrice);0 E* o7 A+ `; D0 F, A( v
if (count == 1) {, I# P5 A( `6 o" z
priceCount.remove(oldPrice);
. n$ B, R3 d0 u& H } else {# a6 Y) G# K3 _ D. Q: `- R0 p
priceCount.put(oldPrice, count - 1);
+ A& X* R1 e2 `* `' t3 A }/ P8 h: C8 i" d& b$ c- G
} l! V/ B5 P; Z H+ O1 f% Y
timestampToPrice.put(timestamp, price);' ~& n2 g6 C: T. L P
priceCount.put(price, priceCount.getOrDefault(price, 0) + 1);
* n3 d+ c2 n5 j7 b6 m6 G9 f8 R }3 \$ A8 O1 c. g' t- s% ]* G0 X
" Z& P0 E; t7 w0 T3 P public int current() {
7 B- T3 Y- D4 b2 x7 U* I return timestampToPrice.lastEntry().getValue();7 w1 i/ F" G. ^4 d. \+ |
}
+ \1 m$ o1 A, R
' {! O- t; G% G ~6 b+ W public int maximum() {$ U3 j8 i, H8 a) ^# y! {0 x
return priceCount.lastKey();! \6 d/ `/ [% N; K/ i
}
( ~" c' y2 W) v
/ Q- X; e7 t, w& x, Q$ E' Y0 p+ S public int minimum() {( p" ?2 m5 |2 h+ B, j8 M! O6 N. G
return priceCount.firstKey();
0 J! I% O7 a n% s }2 M% P$ @& S; `) _* N/ R* ^- o
}9 u' g( O$ U* J( S+ e
1 {+ m* f* z5 N0 w# S6 G O【 NO.4 将数组分成两个数组并最小化数组和的差】
5 z, B4 W6 D! `# E+ v1 X" T( G
: C1 `: H1 O* d8 F5 |& N解题思路
9 Y# }/ q3 N1 J2 ?
; r7 |9 y8 @: y9 ]枚举 + 双指针,具体思路见代码注释。
; @9 {# Y( S& B1 m$ V4 u6 n/ l1 H9 f2 e2 v4 V7 {
代码展示1 L2 T" o& E# o Z, S# G; H3 e
7 U3 F, r+ @& i- q4 Iclass Solution {
) v( j. H7 S' H8 y- j# e public int minimumDifference(int[] nums) {; x# @4 Z! p. `% H7 P
int half = nums.length / 2;: Q: Q4 F3 e% w ` }+ R5 P
int[] half1 = Arrays.copyOf(nums, half);4 r' [" U* M5 ?* J/ `' d1 O! N2 f
int[] half2 = new int[nums.length - half];* t( e; p; }- Z# ?. H* G1 s
System.arraycopy(nums, half, half2, 0, half2.length);* `! D" ~* ]9 _" r! j
// sums1[i] 表示从 half1 中选出 i 个数字得到的和的所有情况,并且从小到大排序
6 [$ [% f5 Q N4 _% O) k$ h List<List<Integer>> sums1 = getSums(half1);# @( Y7 S' k, |) O# b; I
List<List<Integer>> sums2 = getSums(half2);
& u# ?1 A. J9 g$ w int sum = Arrays.stream(nums).sum();0 `/ g' _* R' N- F+ x
int result = 0x3f3f3f3f;
! g* J! h5 N- R% z; e8 Y // 枚举从 half1 中选出 select 个,则需要从 half2 中选出 half - select 个
" ] t# F0 L% F' ]2 t for (int select = 0; select <= half; select++) {
& R8 o2 |- Y; i- i8 S X List<Integer> half1Sums = sums1.get(select);. V/ D8 l" V' J* D' C
List<Integer> half2Sums = sums2.get(half - select);
/ ^* D1 Y. W7 R V. w // 从 half1Sums 和 half2Sums 中各选出一个数字,使得它们的和最接近 sum / 2
4 Y( P) N- | I0 q- `- q: g' a int i = 0, j = half2Sums.size() - 1;
; l; `% m' U# p result = Math.min(result, Math.abs(sum - (half1Sums.get(i) + half2Sums.get(j)) * 2));
1 y6 z" M, i& ? I+ ?1 [ for (; i < half1Sums.size(); i++) {2 C% V' |( S$ F1 B. P y! ]
while (j > 0 && Math.abs(sum - (half1Sums.get(i) + half2Sums.get(j - 1)) * 2) <= Math.abs(sum - (half1Sums.get(i) + half2Sums.get(j)) * 2)) {
8 T1 f/ `4 F3 g* C j--;( c9 j$ R! W4 \8 a& x. Q
} b R ^) N+ ^; b
result = Math.min(result, Math.abs(sum - (half1Sums.get(i) + half2Sums.get(j)) * 2));
4 N! ~8 S# x( a s7 ~7 ^2 h }
# @/ _- w6 z5 M; q( x8 t0 W. n4 r }
/ [& }( S1 L# `7 c/ M return result;, m# R0 j+ o5 u
}. L! U6 `0 ]3 |. L/ U0 x- ]6 z. n' {
' J8 Z. e& L9 g
// getSums 求出 nums 的所有子集的和
7 ?" U. w$ z3 x$ |4 D# | // 返回 List<List<Integer>> sums
0 |2 v$ V5 Y1 J- m! [ // 其中 sums[i] 表示 nums 的所有大小为 i 的子集的和
( h; Z" I" Y: Z // 去重并排序7 N/ p) ~2 i8 E0 L1 R0 n' \3 Z4 X
private List<List<Integer>> getSums(int[] nums) {
1 n; o) u; e; k; j! k1 e& b3 n4 e# g int n = nums.length;. B2 T# k6 Z& f$ H; V5 @! r
List<Set<Integer>> set = new ArrayList<>();6 {7 z* E g1 x
List<List<Integer>> sums = new ArrayList<>();1 `' A+ K- P0 E8 f) Z; A% p% f
for (int i = 0; i <= n; i++) {1 c6 F( [5 i% @4 x0 D5 z
sums.add(new ArrayList<>());
\9 a- c6 u/ m9 }# _ set.add(new HashSet<>());8 a5 u) g- v3 d3 x% D
}4 Q( _4 D, l! |5 {% ~
for (int i = 0; i < (1 << n); i++) {
: e; r9 S, ^+ [/ H* ^/ s int sum = 0;$ }* k! x+ R6 {$ ]) q; [5 `
int num = 0;! K3 V& D- g. x
for (int j = 0; j < n; j++) {4 e2 O' T/ e8 X+ n- B% o2 Z! L
if ((i & (1 << j)) != 0) {0 j. x" m8 X2 O. H8 i/ G; r( \1 }
sum += nums[j];$ o; v1 e" q* Y( p& U0 ~
num++;
2 c8 g2 T Y# b. |% P% q0 j3 R! s$ c! p; u }' v& @6 s" A" X n& e$ S, `, w
}
7 ^% F; s' H4 G3 {1 H. p* w, L if (!set.get(num).contains(sum)) {% g% G; {$ _' O3 v4 H$ c: |
set.get(num).add(sum);
) i% b+ M2 }) z) C2 T, t" ?4 V1 n% O sums.get(num).add(sum);
0 X' k) u$ K$ m3 C0 `4 e }* A# U0 L" E* u6 }+ _ [) t+ R
}
: G* n4 ? O3 G3 r1 z; W, U for (int i = 0; i < n; i++) {- g* j! c, t# ]- W% Q
Collections.sort(sums.get(i));
y' c* t: N% L8 { A }
8 c8 q) {" b; U# u) M) X return sums;
: i v+ h7 y, Y) L9 d g& u0 v0 d }0 C# D2 K, ?+ o# G
} |