本帖最后由 上岸算法 于 2022-5-5 00:11 编辑
+ D; Z+ s9 b. w. w- o" O
2 L+ _3 F- u5 Z. ]【 NO.1 移除指定数字得到的最大结果】0 @1 b: ~- N8 H3 {" H) |) v, V7 r
解题思路
. p# N0 q% A% G$ e) q1 q$ ]
: o: B! r4 Y: C7 A$ [可以使用 BigInteger 来比较大小。. u) [. s$ M) h9 x4 m2 r' T
' m9 X% G) C: H3 ^, L6 I1 z
代码展示
I* Q8 a3 A; g0 h! P$ S9 m' `) M: M3 y& W
# B3 I9 T! r8 M
& b3 z2 G$ S$ _' K
【 NO.2 必须拿起的最小连续卡牌数】+ Q+ k3 p: E8 _ g1 y2 Y" F1 c( U1 Z
8 A- [( L" n2 k& r6 U- D
解题思路$ y' x: M2 v5 ?3 V1 g5 T% W
. N7 y o$ j+ T. a1 Q1 I% _* T" e
题意即求相距最近的两个等值元素的距离，遍历一次，记录每个值上一次出现的位置即可。
- T: M- K. O0 Q& P& N) v' m* F; A$ ~& d/ i: r' g4 c* y6 y' M7 G
代码展示
6 Z$ ]' i8 G6 g' r; T% S6 ], _$ [8 D3 O
- M# S' Z3 p( E# m: J' B& v( G+ _( ^$ r4 Q
【 NO.3 含最多 K 个可整除元素的子数组】
. {) r9 O$ P4 D# L% G2 p! `6 E R) i% j5 m! |; E# U6 b
解题思路
7 r% |+ p% f8 ]* y: S7 N5 E+ u" |" U) A7 O
定义一个 SubSeq 类，实现如下几个方法即可用 HashSet 统计数量。3 @! {" n2 c! A( [
! j# C; ^$ U! L! |) i) m# J, y M
hashCode 计算哈希值
" b! A K' a' B7 N. E1 Pcheck 检查是否满足最多有 k 个能被 p 整除的元素- o$ D0 i7 p9 H! x) T
equals 检查是否相等* I) ?& `& S9 E2 m, K2 }
5 `- y. v/ K9 C; j/ y/ ^+ m代码展示1 T+ y1 }& H+ u# g8 a$ a
# @& v9 G- m/ P& }3 c
; s+ d% _' A7 M3 t4 q5 Q. u3 l7 w8 W/ y
【 NO.4 字符串的总引力】
$ k/ [# ]8 `( M- H1 a3 ~9 q5 f! b/ E% I+ i' e n! D" V6 @* k, A! {
解题思路7 F, p* H# E1 d0 }0 s
. c, p& j0 M3 f& u6 r定义 f 表示以第 i 个字符结尾的子串的引力总和，再定义 pos 表示字符 i 上一次出现的位置。% f! V& b+ w5 Q. R) w- a
1 S7 m: _/ `0 r2 [则有 f = f[i - 1] + (i - 1 - pos[charAt[i - 1]])
( h0 m; [& p& E* ?" B( e5 Z; B2 |: d/ L1 F# y% T' @7 S1 Q P0 S# s
因为以 i 结尾的子串中，pos[charAt[i - 1]] + 1 到 i 之间的子串都会多出一个字符 charAt[i - 1]，而其他的子串的总引力与以 i - 1 结尾的子串的总引力相等。. v+ i0 p0 ~& n$ I
1 z) q, f) ?$ L/ l& p2 j& T0 V代码展示
: H6 K$ d/ X! ^7 ^- R8 }* S* j: N R+ l; ~) \ _
3 W/ ~; ]! ^4 @. f
|
