登录后可回复主题
您需要 登录 才可以下载或查看,没有帐号?注册账号
x
【 NO.1 Count Integers With Even Digit Sum】: U) b0 Y2 \9 x
" W- J' {# m" o$ s; c5 Y- n$ N
解题思路& Z7 V" \/ t9 m/ E7 t7 _6 H
签到题,枚举计算即可。
) t2 H! a! f/ S7 R' X( \8 C* K2 y9 y* K5 O' a6 K
代码展示; |; Z X; b, Q. c+ [. [6 E7 u+ w
2 c2 a0 x+ E1 U& }* E, \0 x7 R
class Solution {
: ~- o# e% d4 J" e' ~! f. a public int countEven(int num) {4 t P. j' r5 @9 f
int res = 0;
8 r$ ]# ?! R& r" M2 p for (int i = 1; i <= num; i++) {1 f# J$ z1 s( R" Z' z. K& ]( F
if (digitsSum(i) % 2 == 0) {& B7 j- y' ?" I+ G4 W o
res++;
% A5 z9 _/ M8 E7 j9 m }" n, k; A1 \4 @: l+ P3 ^) Q
}
# i& H6 X& M6 Z: c return res;) W6 ?; F9 e' g
}
' \: Y4 L7 o! M9 }+ P( l7 p$ d$ \% _2 |5 ?: I) l0 v0 E1 S1 z7 I
private int digitsSum(int num) {9 w9 |5 c; Z8 w( S
int res = 0;
; S+ N* B0 v; o& D2 F. n8 r: m for (; num > 0; num /= 10) {
W4 a& s5 C% v4 M' F+ | res += num % 10;( e) y% k# F* x) B! [6 }
}; W* b# r$ _6 [! w, W6 k# _2 K
return res;
% m: J9 G1 r; U) C' b; H8 h1 Q }/ P3 ~+ V& [( D' M
}& M$ K3 w/ p3 X! b( Y
. c1 N0 V8 v% C. I, }5 b" ~! s. a A7 k3 x3 s. i
【 NO.2 Merge Nodes in Between Zeros】& x7 x* z* N& L1 [, v- s2 D3 X
+ D/ h* L( g. [7 x& e& v/ |
解题思路7 B- L! Y) R; w [+ @. Y
遍历链表即可。* Q3 X+ s4 u. B+ m
7 Z' m8 Q: t; V0 C; l3 w
代码展示3 C! ]; A0 U4 \ `: x7 Z- l
0 w& b" p, D9 Qclass Solution {: o' f( ~; R, E( Z2 f# ^1 r( X
public ListNode mergeNodes(ListNode head) {: {* `# v1 `9 Q7 e
ListNode res = new ListNode(0);. K" Z# o: a: s
ListNode tail = res;8 F1 [) G) ~0 {. r! e
int sum = 0;
2 X2 N% K& }/ w. ^( Y$ D0 l$ u; S" h for (ListNode cur = head.next; cur != null; cur = cur.next) {
4 I% I. Y5 o! l/ E- \4 q$ {" m. H sum += cur.val;* m8 z* n4 |' ~! I+ v7 b
if (cur.val == 0) {9 b# M6 A# k; @; i \. r" Q+ W
tail.next = new ListNode(sum);% @/ \3 N0 v1 c4 G
tail = tail.next;
2 U1 B+ p) r8 F. O sum = 0;) n8 p" [4 G5 M; }7 s% b6 D! d
}
3 V! Q" j0 [, z }
1 j j g3 @( t7 i- _& G return res.next;
- T8 e6 L* [. b6 _& v+ y( @, U9 q F }
+ A( u" E3 T+ [3 C}
( K/ x2 [* a0 u
/ s& B$ O) d: L' d
! o7 \6 q- r$ o, D) E【 NO.3 Merge Nodes in Between Zeros】
) d: R9 t& p" B8 n- v# z! }
1 F! z% l- u. {( b: d) w0 P8 B' t5 O解题思路
. N% L) q f7 y* |8 k注意题目描述:“不必用完所有的字符”。所以直接贪心即可,从最大字符开始,只要连续超过了 limit 就使用次大的字符分割一下。6 U+ M* V7 G1 r) K% k
! O! L4 @0 L- M4 d" [% e代码展示/ F9 j' r# X3 ^$ O' G9 n* p
& G. x9 `. I. V) q0 l9 b1 X6 U
class Solution {
* f5 L( W6 c J& C/ n public String repeatLimitedString(String s, int repeatLimit) {8 Z2 B, ?6 [1 l# g6 [
int[] cnt = new int[26];
7 {% T6 v* w* Q9 c for (char c : s.toCharArray()) {
5 w: \5 L0 K/ s* v/ [* ] cnt[c - 'a']++;
2 \! t) H8 Y$ q0 }: k: @ }* r B3 Q# E7 V" Q* x. s
6 ?$ r0 b) p$ A0 S StringBuilder sb = new StringBuilder();( Y" W) _* P5 w
int repeat = 0;
. G7 Y k# u J- z! \0 k7 V4 x" E) u char cur = 0;' {- k) O# P% S' |& o* A9 L @
for (int i = 0; i < s.length(); i++) {* O. d* ~: l# q1 B
char c;3 ^ X4 L, I& B) g8 i" N
if (repeat == repeatLimit) {
6 f9 H: P. l' ]; J repeat = 1; |( ~, Y0 O- D" o# R
c = poll(cnt, cur);
+ g6 j3 j v, W: H- X+ m! K# y cur = c;1 B3 A% v$ L8 c4 [& I0 q+ R2 b
} else {
5 v* D ~5 n, D+ T! ? c = poll(cnt, (char) 0);1 N5 e% ?" N6 W+ j: y8 {
if (c == cur) {
9 m+ M$ @( \/ N! Z) m E ] repeat++;. P& K* W4 w, i0 j6 w+ j4 D
} else {1 e4 P& L6 r e% t
repeat = 1;
& D. M4 t$ N: j: V3 a! \ cur = c;
8 \- ]: z' h+ `' \5 P }
" q, e3 C# t. G9 O$ { }* d7 N- c# _, t/ e9 b' y5 o* i9 Q) T
if (c == 0) {
5 w* o7 V7 U( g- K5 \. v! B break;
- R4 S5 x1 Z* K, \* Q8 d }
9 o; D/ d, A' W2 f6 m! F1 j sb.append(c);8 ` y U+ u) h6 l
}# [' M+ K: j6 W }- X
return sb.toString();
: \9 |) T6 [0 ~) r C }" M @2 t+ W/ W8 C
" R2 `5 G- F! ]2 P* I t! g& h private char poll(int[] cnt, char not) {2 W" c- l( Z# Q6 n j
for (int i = 25; i >= 0; i--) {: _6 ^! ?" I) M
if (cnt[i] > 0 && not != (char) (i + 'a')) {9 j3 _ \# r7 ?7 R: m% V: l2 Z
cnt[i]--;% u6 ?7 i8 G2 d \/ r/ m( I% i8 s
return (char) (i + 'a');4 F' O6 V7 u& U9 f5 K" M! R/ D
}7 @7 h/ T) F9 D# |
}3 [) m, i1 i5 k/ W7 v. Y# P! p& Y
return 0;9 ~3 ?, k& t* p2 B; q
}
: F4 G( P% h$ l8 Y) m& F0 L# i& w}7 ~% e" G3 v6 ]) A
5 K& }# z, l' E/ _8 {( |
1 t4 Q3 L1 U, c) l7 O: k【 NO.4 Count Array Pairs Divisible by K】) p/ m$ u# b6 U
& f. I$ h( }1 w1 u
解题思路: ^+ D2 h3 Y) v' J7 `
预处理转换成最大公因数,详见注释。: r" S$ J R8 r- z# S: J7 m
% f! T5 ^' L0 U! G. \5 H: D2 V w. O
代码展示% A5 Y* x* ] w
" @5 x& x- d6 \1 p
class Solution {1 h/ s U/ `" z! i% ^5 k
public long coutPairs(int[] nums, int k) {# \' J' \, Q3 o+ g4 f7 Q
// 将 nums 转换成与 k 的最大公约数3 |; ~+ t" g; n
// 因为每个 num 中,k 的因数以外的部分没有意义 (即使做乘法这一部分也无法帮助结果成为 k 的倍数)
1 A& H& P/ N7 O& v. n3 M for (int i = 0; i < nums.length; i++) {
+ p0 ]8 O8 r2 P9 ]2 j! t nums[i] = gcd(nums[i], k);
& w# ^% s3 |. C, e4 d }
. `" Y( Z# v& } long res = 0;2 C/ u0 q) t) j* I9 `
int[] cnt = new int[k + 1]; // cnt[i] 表示因数 i 的出现次数
& e! S0 v/ e+ U4 p, q7 @- @8 o- K! v for (int num : nums) {
4 u( R( ~$ K4 H* [! a) O( C& e( q9 d // 经过了最初的转换, 此时还需要因数 k / num 即可组成 k 的倍数7 j# K) E n) J; y1 d) i, {/ Y. k- A7 G
res += cnt[k / num];. v% ]4 `* g+ X: c+ T
% v% r0 F; V; Z7 K2 L$ O; j // 使用 num 维护 cnt, 即 num 的每个因数 i 都对应一次 cnt[i]++
7 r: v0 U5 ?3 t. Y- h for (int j = 1; j * j <= num; j++) {# o. j" l! O1 p. n6 z8 U
if (num % j == 0) {0 M+ ]/ l! C# q
cnt[j]++;& q+ e w/ V( ]
if (j * j != num) {' q7 ~! G$ q5 ^& J9 J
cnt[num / j]++;
9 o# I: \& @8 _7 w4 T } H0 p+ `+ H" R+ u
}: T8 s' y8 E$ Q& f6 u" h
}2 A/ [5 H% @* N
}
% ?- j9 X$ ]2 W( k& ~8 _* B return res;* H6 U1 S. H% W4 V
}( e0 x" P& ?( a
# B" j# n" S7 w/ u9 [ int gcd(int a, int b) {
- F1 R9 M; `* P2 d. h- E return a % b == 0 ? b : gcd(b, a % b);! K* W( S* ?" \& y9 f' M
}
$ o8 j0 p1 |' z- J6 a6 C4 g2 X& V} |