登录后可回复主题
您需要 登录 才可以下载或查看,没有帐号?注册账号
x
【 NO.1 执行操作后的变量值】
' [; `3 e. Z& c解题思路
2 K6 m' |+ [9 g1 x3 h% e- p* T签到题。: B" R* K( x% A% u( L
1 U2 E0 W( o- Q* b
代码展示; W8 e7 o% J; L; N3 K
* m: H' h3 t/ F& \7 dclass Solution {& \* o. z6 q! d4 [6 Q* e
public int finalValueAfterOperations(String[] operations) {
2 c, e% e b' l+ l int v = 0;
5 K! Z% M) k4 U! n* c1 ~ for (String op : operations) {% o% F4 G* v) n* q) v
if (op.contains("++")) {( F4 V7 R6 z2 h3 I v! H
v++;: W0 N$ l; J% ?' h+ N
} else {4 P- Q' C2 y+ ~
v--;' Y2 F' H6 k @" `; J
} Y: l+ r+ s7 q
}2 N: k& p' c7 H# Y( f
return v;/ r, {7 W- V" Q! E& u; m" x
}
" U5 G; F1 z% e1 X4 _}. Y3 }. i( z' H; R) `- c2 R. U
" m! {& ^9 F0 X) o【 NO.2 数组美丽值求和】3 c" P; O4 T7 H% q2 J' ^' ]
P A0 v$ |" W' N4 J2 N6 w解题思路
. H4 P0 y1 x! F, \由前缀最大值和后缀最小值即可得到中间元素的美丽值,所以预处理出前缀最大值和后缀最小值数组即可。3 ]( O# k7 f4 R) }( i5 p% B6 f
8 ]2 A+ L- i4 H代码展示
P0 |% [& o, b" ^# @$ B! X. w3 R' w; k2 y5 y- s* I1 A. ^
class Solution {
( u5 Y6 R T5 e1 u2 s) L0 a- i, H5 e1 \ public int sumOfBeauties(int[] nums) {
! u! k+ `+ f9 R int[] preMax = new int[nums.length];6 E% t% |" R5 L/ a
preMax[0] = nums[0];! ]7 X3 X5 w3 n
for (int i = 1; i < nums.length; i++) {$ t5 w, A/ h& x- t o2 B
preMax[i] = Math.max(preMax[i - 1], nums[i]);( I% l/ d7 o7 n
}8 \8 x( |0 ?9 S9 \
int[] sufMin = new int[nums.length];
0 T0 G" @; o) @2 G& n2 O) `( g- ^; X sufMin[nums.length - 1] = nums[nums.length - 1];- _+ w" N, t* @6 Z/ o1 H
for (int i = nums.length - 2; i >= 0; i--) {
( X- o7 l1 v7 T0 M5 B* [; } sufMin[i] = Math.min(sufMin[i + 1], nums[i]);$ @$ ~" s( J8 X
}7 ^, _+ x* I6 |. Z* y
int res = 0;2 Y5 n6 F0 o$ }% e3 T% V
for (int i = 1; i < nums.length - 1; ++i) {1 Z0 J( q4 E& \* @7 f
if (preMax[i - 1] < nums[i] && nums[i] < sufMin[i + 1]) {9 G: `# h4 n6 d1 `& U% F2 C) ~* d. Q
res += 2;3 _ K5 b) z! Z- t* _4 h) X
} else if (nums[i - 1] < nums[i] && nums[i] < nums[i + 1]) {
" I# `8 P$ z" {/ Q- x& o4 M% K res += 1;! g* M% ~) r) N' t8 N& T$ P
}' o% j# V& K* @0 r4 d
}* ^/ D9 T" m& W
return res;% i4 |. q9 g) |7 u4 {& f, A
}% R2 O9 @" ^2 S2 M4 @
}# |2 h/ p+ s' ~7 @$ J3 V. ~
0 S# l- }/ B$ U' D5 A% H【 NO.3 检测正方形】
3 y) K3 P( Y* R1 V6 } d; ?5 B7 }3 W% S! `
解题思路
9 _. Q# u6 c7 @3 H0 J使用 Map 储存所有的顶点,然后在 count 查询时枚举对角线。& ?8 {- E8 z" d$ @' U/ M
. R: x0 V$ I* r; c# l/ U代码展示* m( E/ \' K V$ N- H4 V7 z9 O
d# }. Q8 A0 [( ~7 H, l+ _! ]class DetectSquares {! ^& B$ Y# B! y& Z' u7 I& J; R
5 Y1 r+ W. I9 p* c5 V+ r/ H( B Map<Integer, Integer> count;
0 P+ n5 S9 A! B7 Y7 S# @2 {; w2 m$ i) G) a8 e, {. x- S! l
public DetectSquares() {) x2 Q) q! ~5 S3 S0 u
count = new HashMap<>();$ R+ ]2 w+ W4 i& d; Q6 }
}3 k8 d2 s0 x/ P3 t% X
! M$ G3 ~3 @) M2 U+ v* T: C4 C public void add(int[] point) {4 ` \5 R; P: B. L: `( b- a
int c = comp(point[0], point[1]);2 q9 y8 p& W; K9 X [: v
count.put(c, count.getOrDefault(c, 0) + 1);
7 {2 ?% `9 `$ c7 p; A }
" t/ ~+ g" c0 b0 F, b S& b) t. u2 O
/ L4 I1 b0 G& E( N# V8 h; K public int count(int[] point) {
/ i* ^: W5 M1 r F* | int res = 0;
& B* a4 l. h: p" ~: y/ M, y for (var kv : count.entrySet()) {; B, S; L( A* l" Y% |7 k
int x = X(kv.getKey());
: A" D( o p. R5 S int y = Y(kv.getKey());. [0 r/ o+ I2 F9 N* ~: u, ?
if (Math.abs(x - point[0]) == Math.abs(y - point[1]) && x != point[0]) {' t( ~/ n, u% d6 ~
res += kv.getValue() *
/ C4 m$ s1 Q/ {/ v3 Y* I h9 N count.getOrDefault(comp(x, point[1]), 0) */ P7 m0 {9 D- R# R; N+ v
count.getOrDefault(comp(point[0], y), 0);
! b& H( O0 D6 k" f! ]. i- J0 L' { }; n0 q. I Y5 t
}
: Y+ C9 v! x/ g! U" u" g6 D# W9 t return res;
) @7 k! G3 [+ F1 X2 o! x, ^ }
; ]& a) S6 g7 o+ ^6 P8 Z7 S% i9 \# H# S
9 P6 F! ~: C/ r# s private int comp(int x, int y) {
- P+ Q4 @$ n, n1 z+ V0 l* Z return x * 10000 + y;) @, l: G) |. R$ c/ X W
}" T1 C4 b: h# _
7 a' |- ~" w4 M3 q
private int X(int c) {) C5 S0 `' J. _2 i
return c / 10000;
8 \$ P2 y4 o& g& {2 @6 F/ G }
( p- k% m) f7 H. | |" z$ v/ x+ M& z
2 n& y) C2 w/ N private int Y(int c) {
) Q6 M; ^! I* A9 i- j/ k return c % 10000;3 L) e" Q' \) q$ Q9 D
}2 r/ N3 @7 g! {9 {: k1 T8 o
}
$ b" q* O# a% J$ w
/ a1 X X6 |9 e& }) T' k0 \【 NO.4 重复 K 次的最长子序列】
+ n% U' Y v& c D) q8 [: p! o% }- M; n+ n9 [0 s7 V" C
解题思路
8 t4 i0 X$ B) }5 a' B. r注意 2 <= n < k * 8,而如果一个子序列想要重复出现 k 次,那么这个子序列中的每个字符都至少要出现 k 次,所以说答案的长度一定小于等于 7。
' f) [5 |- F1 F# T( A2 Z) i) p/ W0 s3 W/ g
我们首先找出来所有出现次数不小于 k 次的字符,然后枚举这些字符的排列组合,依次判断每一个排列组合是否出现了 k 次。
3 E3 |: Z- [( H% |2 f9 Z7 r" N9 M W
9 N4 g9 c. c( H! V$ P* `代码展示
. i; P; ], {- J
C: A0 w" w% y# m7 @class Solution {; n0 ^9 O5 s, N3 G
public String longestSubsequenceRepeatedK(String s, int k) {) G/ A$ a8 [0 s4 P6 m4 F6 J) Z
Map<Character, Integer> count = new HashMap<>();
8 e; @9 t4 h- B2 @# B for (char c : s.toCharArray()) {0 c7 t) [) s: i: i- i1 x9 t
count.put(c, count.getOrDefault(c, 0) + 1);
$ w5 {# B1 B) R0 c' b1 _ }0 I4 `- X8 S, R2 ?
StringBuilder s2 = new StringBuilder();: x: _+ F, g: Z: y! Z" b0 j
for (char c : s.toCharArray()) {: ~. \7 U6 i7 G
if (count.get(c) >= k) {
1 I) s& [5 r3 B- q4 _) i- R s2.append(c);5 u( P8 j8 V6 }1 S4 E) f
}# C- }3 X8 T/ `% t+ K4 r
}
5 C4 |& B s x# B5 u% C4 T count.clear();! Q4 Z- j* v+ V
for (char c : s2.toString().toCharArray()) {
& _$ e. m0 c" |% Q count.put(c, count.getOrDefault(c, 0) + 1);
* [4 T4 R- e. } S }
5 N/ `8 C/ w2 Q3 B" V; W return solve(new StringBuilder(), count, s2.toString().toCharArray(), k);
1 n) `& j t7 M3 a8 j% C+ u, j }2 N b+ R$ h! \
: O3 V( C4 P2 ] private String solve(StringBuilder cur, Map<Character, Integer> count, char[] s, int k) {
/ v; D* d- r1 ?5 H String res = "";
; S- g0 D5 @/ Y1 i var keys = new HashSet<Character>(count.keySet());
+ u. U9 N8 a& r' B6 n for (var c : keys) {5 Z8 u6 ~1 o0 i d
cur.append(c);
! z" T% D( L7 ~" B5 t( e- E2 \% q if (comp(cur.toString(), res)) {9 `$ ^, d" `/ c( N1 J
int cnt = 0, idx = 0;
% v5 w/ t; X$ l8 J: Y) P# p for (char cc : s) {8 d* O2 O: p; L; `7 \
if (cc == cur.charAt(idx) && ++idx == cur.length()) {* ]6 R9 U3 `2 a2 ]: Z; [ e) x" Y
idx = 0;
4 `$ U7 Q! c$ T if (++cnt == k) {/ n5 \. a$ U/ N4 T
res = cur.toString();+ F- K. R, ], N. U7 v6 E
break;. d# }$ _ y7 t( I& f t
}, [& p* x# x8 E
}
* X% p/ @, B: A- F9 j9 J s }
; e; w5 u4 q( o6 `$ `1 _+ m }" `$ ?. f& r/ p. p! x
int bak = count.get(c);
8 z& u9 p: d3 M/ b& {0 o if (bak - k < k) {
4 M/ C% N3 I$ w. t3 P7 ]! A" s count.remove(c);
5 [+ \1 o* D5 S0 Y# s; ? } else {4 i5 } c% d8 t1 U( t) f. @# G' X D
count.put(c, bak - k);- e S( B! c, B& ^$ q, Y
}
4 J3 X t- a8 h6 B5 A* I c String r = solve(cur, count, s, k);$ \3 p6 V' \2 J: t- q2 ?: J: b Y. m
if (comp(r, res)) {- u2 k, X0 R" T3 l: b+ R+ J
res = r;
v0 s" h9 a7 J) K" [ L6 f }1 U, C3 N7 h& s" T+ D: b( @6 b' ?+ X
cur.deleteCharAt(cur.length() - 1);
( y8 e' H5 b- R* d4 T count.put(c, bak);
+ B% m+ t( e0 ~$ O+ `) _2 p }6 `3 K" i) a( ~+ ?/ r3 P% ~
return res;
/ A; b3 l' d; n$ D' E7 V! q }3 R, e$ d( x1 V2 O" D2 S" b
2 q4 v5 A& ~% s- | c# o+ J
private boolean comp(String a, String b) {
& L7 l3 f, h/ b- I( c return a.length() > b.length() || (a.length() == b.length() && a.compareTo(b) > 0);. B! K' M% I( A% W1 P$ l6 P
}: F4 A4 s0 |9 A8 q8 Z: S2 o8 I" e: b
} |