登录后可回复主题
您需要 登录 才可以下载或查看,没有帐号?注册账号
x
【 NO.1 至少在两个数组中出现的值】4 t% j( a/ @* C$ X
. v9 |! |, g/ I. N6 {解题思路
) B( f! p8 o5 \+ \( g签到题。
5 T( Z: g, M( I9 U3 e8 T) x+ G7 T$ q! s! d
代码展示
: r- H4 Q. \9 x) ?) I7 Z9 l) S1 \
5 e: j7 n, a9 ]4 z, m0 K$ @1 fclass Solution {
# G; \/ y t( m; i* I, C7 n0 v) C public List<Integer> twoOutOfThree(int[] nums1, int[] nums2, int[] nums3) {
\3 j: ?% c- s1 [: x h int[] count1 = new int[200];
$ z: d) ? f, [- Y9 I int[] count2 = new int[200];
& C* `* P" ?. d& r' x int[] count3 = new int[200];- ?' \& [4 \: \4 z5 B: a/ L
for (int n : nums1) {* `* R# T I% p- f" `
count1[n] = 1;
/ `; m% f0 g+ j% [ }. s4 _- t* t3 R% W u
for (int n : nums2) {9 P' s) B3 _" f/ X& p$ }* c2 G
count2[n] = 1;' J5 `4 H$ y; J" f
}6 G6 E! U. T" ?
for (int n : nums3) {
0 y7 d# w. {$ P) H count3[n] = 1;
) d( t. Y& u3 M: b: a }
! W) F8 @9 S) k$ Q/ j( T List<Integer> result = new ArrayList<>();5 }, O; H% P# s
for (int i = 0; i < 200; i++) {0 O3 ]% w! F3 s5 z* g$ N
if (count1[i] + count2[i] + count3[i] >= 2) {
5 b M6 l% s) u. e* L result.add(i);( K/ P4 D6 ]) j: g7 c4 u
}9 F% I1 Y" {( t5 Q0 D" h; f: Z
}0 f: t3 U+ i( I- q7 R
return result;
: E0 o, }, f0 M" E" Z3 m& H; t7 H }
8 w" k U1 v7 @3 @4 t0 a# i& o}
( s t, Y; w3 l! t9 p$ E6 ^1 ?
【 NO.2 获取单值网格的最小操作数】' j: c5 p: A Z6 u* U) j
1 d, a. q% |6 t; T! U" ~
解题思路8 j, D* u [) }9 A5 l! g
网格可以转换成一维数组,然后排序。4 b' b+ E. u8 t( W3 ~7 Z3 s
' |' A8 x E. k+ x0 b
不返回 -1 的条件就是:任意两个元素的差都是 x 的整倍数,我们只需要检查相邻元素即可。3 M, }) y! `( T, \
, m; O W N, i! {
然后枚举最终的唯一值,可以利用前缀、后缀和快速计算出把所有数字变成该值的操作次数。7 V n8 ^! k O' V7 H6 G
H2 @+ d' _* a! k! o
代码展示7 ~9 l* r+ I* }2 d, }6 t ^# A# X4 _
, c ~# \* l J" H- g( U, A3 z
class Solution {6 u: @- E0 g, l2 d! l
public int minOperations(int[][] grid, int x) { O( o( e2 b0 _. v# Q
int[] arr = new int[grid.length * grid[0].length]; c. [! E: U8 A% q, x3 B- W* f) Q9 f
for (int i = 0; i < grid.length; i++) {
: y7 r& o" P% \ for (int j = 0; j < grid[0].length; j++) {9 }5 l6 S; R6 Y; [" \2 _0 @
arr[i * grid[0].length + j] = grid[i][j];
0 L4 O" _2 `( J" r4 Y9 t+ q4 N: Q }
/ @5 m0 g% s( K5 [ }. Y2 n" h% h7 u4 `1 l! A9 U; I
Arrays.sort(arr);" {. z4 F$ u' g9 U2 i# f8 v
for (int i = 1; i < arr.length; i++) {* c% c5 W7 r! Q4 J, y* C
if ((arr[i] - arr[i - 1]) % x != 0) {
3 B/ C |( T" g* X- K k6 |& @7 r return -1;" l3 c6 I4 J" X4 I; Q8 Q9 u3 `
}3 x& @, K. W( q# m
}3 h' s+ ~: ?3 ?8 }# x' i( E
int suffixSum = Arrays.stream(arr).sum();# w. I9 E. L7 j% z/ R% V$ ?
int prefixSum = 0;$ @4 R+ t% z, ?8 ~7 m; J
int result = suffixSum / x;
# [$ i; Q% R3 b* d* m* p! F* S. c- V for (int i = 0; i < arr.length; i++) {3 H0 B. _ y9 Q
suffixSum -= arr[i];8 Z2 D2 F% T/ P z6 z+ i
result = Math.min(result, calc(prefixSum, suffixSum, i, arr.length - i - 1, arr[i], x));
# j( F9 H Q- n8 \- X7 C/ d prefixSum += arr[i];& U: ^ j/ d+ h' `- ]* Z
}
) k0 a! _! {8 x4 q7 k# d return result;0 z: L1 z8 o% N% l
}
1 g9 o) [" X- C G1 T5 b
$ b6 {4 D) u: _: A; c private int calc(int prefixSum, int suffixSum, int prefixNum, int suffixNum, int target, int step) {) x4 c3 C/ b/ \9 @
return (prefixNum * target - prefixSum) / step + (suffixSum - suffixNum * target) / step;# p! u5 H4 F$ E* y4 Y; E6 V
}* d' c5 p; L. a
}
0 U5 y% ?/ N- n0 e6 H' J
) k* R, T- J8 L/ ?, t, U+ b【 NO.3 股票价格波动】
/ A0 o( o2 @ }9 ?9 _& V2 f3 V; f- ?4 ^4 r" L
解题思路
8 ?. S& |: y X使用两个 TreeMap 即可,一个储存时间戳到价格的映射,一个储存价格出现了多少次。
) L& A$ c$ u, @
, Z' o3 u# d- y7 T代码展示
x9 o' U1 f6 f" j: ?) U S$ ]7 y; Y r/ h4 X O
class StockPrice {3 d( X+ |+ J" c! n- p8 y
: S. n$ i: b. u! K
TreeMap<Integer, Integer> timestampToPrice;
/ a: o, d2 ] G9 b! S TreeMap<Integer, Integer> priceCount;
. I6 ?: ^( V/ E" \7 ?0 c" ~% Y
% O* u s/ E: H& j/ f public StockPrice() {8 T+ ?5 y4 C% G
timestampToPrice = new TreeMap<>();+ b. e% D* R: [: c" l7 P5 w
priceCount = new TreeMap<>();9 r9 G! A4 l5 B/ s- t* l
}
3 B1 q; E. F$ A# \0 o# C% G. ^! Q" l5 ~- L6 n; h
public void update(int timestamp, int price) {
6 w |5 B! o2 M% r9 ^ if (timestampToPrice.containsKey(timestamp)) {0 R% Q8 z) b; z8 A+ z# F' \1 m
int oldPrice = timestampToPrice.get(timestamp);
: r6 W# {9 n0 U. }, l/ t7 }! ] int count = priceCount.get(oldPrice);/ s) J2 C7 b5 U/ N' K, |; R
if (count == 1) {
# z1 x( S' {. |: a: d+ f priceCount.remove(oldPrice);) A! E4 l% q0 n* Y+ S' {
} else {; u+ X$ p5 @! R
priceCount.put(oldPrice, count - 1);
5 K$ J5 _( z6 l" X; p& f# e) t }, _- y6 F4 k F" C: b3 j
}
$ [! ^6 U* |# j8 ^ timestampToPrice.put(timestamp, price);4 r/ V0 n% ? ~
priceCount.put(price, priceCount.getOrDefault(price, 0) + 1);$ i1 s) I2 k! | K
}
* I, ?& \4 _+ c% R- U5 s' ]5 T# R6 `0 O% W5 E: e
public int current() {
- I1 |+ c0 ?' R4 a return timestampToPrice.lastEntry().getValue();
4 s1 ~. o7 C3 i& d }
, W1 Y) j' T; Y
9 w; T, a7 f% N1 _$ f+ c public int maximum() {
' p5 F8 n! b4 `& J8 A return priceCount.lastKey();
/ o. R6 s- r: `( i$ M; W* p }5 c7 u( P& o% H( t7 M
- [) h0 s) ?" y4 B& m
public int minimum() {
; s+ l1 m9 f& M% t# E9 m) u. Z return priceCount.firstKey();
) p! C$ E4 a* d Y, q }, C* h6 [; t3 y0 c1 R
}
! [4 a: `' f9 d4 ]# w! Z5 Q1 x" E: B8 f+ R
【 NO.4 将数组分成两个数组并最小化数组和的差】0 J( Q3 G& l7 w2 {9 Z9 B
: M3 A! f2 q+ \& \& }解题思路
/ n; f# m7 p; k8 Z% l' m& d: h7 Z& f1 d( _' A; U
枚举 + 双指针,具体思路见代码注释。
% A- w, H3 X' u4 a/ f, f: b# V* | p/ i0 C6 D4 x O
代码展示* Q/ q' Y7 C& @4 O
2 u& _8 x8 q9 d- h( |* [
class Solution {
/ r, L, r3 J0 H, }* B public int minimumDifference(int[] nums) {
: z5 K' j' b1 E, W- q3 Y: K. ] S int half = nums.length / 2;1 R% F: s" g+ ]
int[] half1 = Arrays.copyOf(nums, half);- P8 t* ` e$ H3 F8 z# a+ a; l
int[] half2 = new int[nums.length - half];
0 w$ _. E$ g7 }+ ]5 y System.arraycopy(nums, half, half2, 0, half2.length);
& R& o7 }7 Z3 B# i // sums1[i] 表示从 half1 中选出 i 个数字得到的和的所有情况,并且从小到大排序) m9 V- \, F+ J) @
List<List<Integer>> sums1 = getSums(half1);
- Q0 D7 M& V/ a% D) B9 j. s List<List<Integer>> sums2 = getSums(half2);
0 x Q6 L; p% F2 P int sum = Arrays.stream(nums).sum();
/ I8 `3 V9 o9 t5 y2 q8 } int result = 0x3f3f3f3f;
2 f- Y( ~5 @+ W0 f( K P // 枚举从 half1 中选出 select 个,则需要从 half2 中选出 half - select 个+ P1 G% [1 W! y
for (int select = 0; select <= half; select++) {/ H1 S6 p; k+ @3 F$ D
List<Integer> half1Sums = sums1.get(select);) {! ~' P2 Q: d: ~2 z7 u, X4 I
List<Integer> half2Sums = sums2.get(half - select);0 a+ v0 [- Z& |* _, N
// 从 half1Sums 和 half2Sums 中各选出一个数字,使得它们的和最接近 sum / 2: ~) E( \8 w4 C0 w# H6 [0 g
int i = 0, j = half2Sums.size() - 1;
" G" r- w0 i7 Z* h9 S$ O P1 B* U result = Math.min(result, Math.abs(sum - (half1Sums.get(i) + half2Sums.get(j)) * 2));
# V4 R: e# }5 G0 Q for (; i < half1Sums.size(); i++) { a& a9 ?7 ^! \4 L
while (j > 0 && Math.abs(sum - (half1Sums.get(i) + half2Sums.get(j - 1)) * 2) <= Math.abs(sum - (half1Sums.get(i) + half2Sums.get(j)) * 2)) {2 J H. }2 z0 h( J
j--;( ^* l$ T2 I- {1 k8 k- Q) T m
}8 `( `; ^8 q& \; ?# J7 X
result = Math.min(result, Math.abs(sum - (half1Sums.get(i) + half2Sums.get(j)) * 2));
) _0 B+ d6 l3 b3 _( j1 S& h' A( m }& ^7 _- p$ Y ?2 N' A
}* g# u7 m5 l0 A
return result;5 f5 ]3 g. C5 N
}
: n! R) s/ |+ c3 N" Y
6 M* ^" {, [: h // getSums 求出 nums 的所有子集的和4 ~7 X7 ~- Z2 F1 q
// 返回 List<List<Integer>> sums
" L3 X, b! V! ?+ o. R' o // 其中 sums[i] 表示 nums 的所有大小为 i 的子集的和# l u; k- b1 p) O# o- o/ ?
// 去重并排序
2 i* h r% K, h: b9 @ private List<List<Integer>> getSums(int[] nums) {. h5 R9 Z6 @$ _# z0 f) J& ]
int n = nums.length;
8 M; A* r, E: H3 U, I3 n List<Set<Integer>> set = new ArrayList<>();4 ~- w9 T; K# r3 _: X; `% u
List<List<Integer>> sums = new ArrayList<>();. i& I7 I9 L4 v( \
for (int i = 0; i <= n; i++) {9 F" O3 u2 I) ~! i3 b* `3 N/ I
sums.add(new ArrayList<>());
! P3 I% Q2 i/ Z; }- ~ v# T* p1 U& s set.add(new HashSet<>());
. |2 f9 f y4 v( w# \ }* V2 Y/ J0 w R$ I: F/ F
for (int i = 0; i < (1 << n); i++) {* N$ e' x& v7 s
int sum = 0;- ?9 x# O n% w8 x5 g; B$ |. D
int num = 0;
c: j* Q; d( [& T% P: E. @ for (int j = 0; j < n; j++) {
3 j* B% \+ c! o$ q! b9 _3 I if ((i & (1 << j)) != 0) {+ p/ L0 v7 C8 S. E
sum += nums[j];4 _ y# q, ^4 ]% `& m: `2 N7 J
num++;
7 v- _' t/ R, n! n9 e6 ?6 T" G7 K5 ? }
6 h) d9 K$ \2 V# G. }% |3 h }
# o/ N9 Q# q& `/ m# j) ~6 s/ u" ` if (!set.get(num).contains(sum)) {
5 s& y2 S" G- d5 P set.get(num).add(sum);1 s/ Q; @) H2 z, ^ E
sums.get(num).add(sum);' t$ _: w3 v! y7 R }" z J
}. t8 b: |5 P+ a7 {. ^, L8 w
}9 Z9 e `- o+ v4 d+ b9 X
for (int i = 0; i < n; i++) {# h/ U6 c; l4 c
Collections.sort(sums.get(i));4 p$ X( T$ Z* E( ]- F( K8 j
}
. p2 E# }0 ~2 ?+ E/ m {0 H return sums;' H/ p! {/ u4 o6 s# E
}7 |- U2 Z# [+ h$ A3 {# A4 v
} |