本帖最后由 上岸算法 于 2022-5-5 00:11 编辑 - f, q# j" p7 j/ q7 Y) G8 d1 K3 N- y
' g3 _1 P; T- I+ B# n
【 NO.1 移除指定数字得到的最大结果】
`' O/ w- p* h* u! C% t解题思路$ m3 I4 x# d% ?( l/ J
2 h n& q# ]: ^" b; D+ |6 y( b, f0 w可以使用 BigInteger 来比较大小。6 Z( k6 I' Y) P. d4 G. |1 v
3 i/ @1 D: r W# _# P$ [9 t代码展示
9 [4 [* g6 \5 N) N" P. K& n1 U" J h! c3 h4 _( S! G
4 _; t" ?8 B3 N' d* S! ^) `3 K, G% ~: F' \
【 NO.2 必须拿起的最小连续卡牌数】
/ ~9 V4 w6 l) W5 B, w& O
2 m. Y8 u, ]2 X2 i解题思路: S# D3 d/ I) w7 G0 p
* o* V+ b x3 `. f题意即求相距最近的两个等值元素的距离，遍历一次，记录每个值上一次出现的位置即可。
; x# U! A4 w* q/ p6 m2 G8 D' a
" h! m; }0 ]* O. Z2 Z G* }2 G代码展示7 M$ I' e; x0 J- S" i
! w; z! o( q: x7 a; s& y
! |+ d5 n# b2 O( ?3 \1 g- e5 S6 J7 G# d+ p& ]8 |0 Z$ ]* j
【 NO.3 含最多 K 个可整除元素的子数组】/ Q8 q! N1 g3 ?" {" ?: f$ ~, ~
. g( n, f0 H8 |
解题思路, t- v9 G* G) @5 V V/ T+ ~8 l2 }' b8 l
$ k q4 E b6 i7 a; Y' X! @& [
定义一个 SubSeq 类，实现如下几个方法即可用 HashSet 统计数量。2 L0 X/ T, A" D: h6 V3 |4 D2 A
0 ]- Q3 ^) v& E7 rhashCode 计算哈希值5 i) }- l9 a' T3 O% t, I# G
check 检查是否满足最多有 k 个能被 p 整除的元素! a3 z" j6 b% B6 F, Z; W, z: F& M% t
equals 检查是否相等& n1 O. s' V0 c
& ^9 s7 W6 H8 `$ B9 y+ M7 d
代码展示# M! }$ V* k' i7 P3 F8 @# \
9 o3 s$ ?# i0 N( }
( f% e. F5 u' z6 ?
; Y- Q* x+ |! u【 NO.4 字符串的总引力】% L3 L7 S. f6 D% a
' [$ P ~( t4 v& h* t+ C1 n
解题思路& p4 y& Z& ^& p- e
V: ?8 J* i) F, i1 K+ Q" G7 p定义 f 表示以第 i 个字符结尾的子串的引力总和，再定义 pos 表示字符 i 上一次出现的位置。
: n' S; P3 O' Y
$ t) d7 W: {1 L则有 f = f[i - 1] + (i - 1 - pos[charAt[i - 1]])
8 J8 D0 D5 B% _* h, J: ^5 C/ ~% \# Y
因为以 i 结尾的子串中，pos[charAt[i - 1]] + 1 到 i 之间的子串都会多出一个字符 charAt[i - 1]，而其他的子串的总引力与以 i - 1 结尾的子串的总引力相等。: J. C4 o1 a+ M5 ]$ N/ y4 \
# y9 H+ }4 F: L3 \: C- B% S* B
代码展示
% L# s, p* J2 b. q: e; \ |0 G$ d4 x
9 J- `4 a, U' x- G4 H5 {! Q |
