登录后可回复主题
您需要 登录 才可以下载或查看,没有帐号?注册账号
x
【 NO.1 Count Integers With Even Digit Sum】8 B4 g9 Y" w# u9 d' G8 @
* G0 Y/ f9 `* }5 c: @: m解题思路
! h* P3 G2 ^$ q$ H4 j, ^3 p7 g签到题,枚举计算即可。! v: o7 ^$ s7 h! c4 N
9 f) S8 x# q7 [0 H" y8 x5 ^, `0 e
代码展示
3 i, `6 J+ [0 g" M' p- z: s4 Q6 P9 V/ G0 C5 j" ~
class Solution {+ e# S4 f2 S+ e6 |5 U: V" C$ q+ Y
public int countEven(int num) {; Y. T: e4 K- g0 I5 J0 |
int res = 0;0 ]8 k2 C( ?' A2 @. N
for (int i = 1; i <= num; i++) {3 W1 L% T& L# b# t4 S
if (digitsSum(i) % 2 == 0) {
7 J8 g) H3 {5 S, N. I5 P res++;
: q( ?2 X9 ?8 z3 X }
) | e4 \/ U* N2 F }
9 p4 r6 b# \' [% _ return res;
* j h/ O0 x0 N }; |! y& X* `! |6 k. N
0 C! ~! M4 f1 @0 `; `0 F, P1 { private int digitsSum(int num) {; Q3 a) i! o6 V& v& h$ T
int res = 0;7 `3 c9 b P( x& s/ I
for (; num > 0; num /= 10) {
) G% R; ^+ |6 h" L7 s5 W res += num % 10;
" s: ~; o* D8 E: i3 v }
/ r ] d, P8 w% z' _6 s return res;! D- a# f1 C6 T6 }$ @4 m8 K
}8 ~. X5 j2 B2 K
}
& D# v( Z8 o1 O+ o+ J
' t4 Y* p' p& h, M: u' R$ H5 z w: J. M m; H+ ?3 {/ U% k
【 NO.2 Merge Nodes in Between Zeros】9 A1 r- d$ K O. l7 E
* h3 u/ D) U2 ]
解题思路6 C: C& j4 P4 M2 |
遍历链表即可。
# t( @/ N4 b& Q) K# R
8 k5 e- y" k* C: [3 |0 w3 W* \代码展示5 O' }* l% o9 b1 {* j
- i! _: K( v/ r$ c% jclass Solution {
- `/ X8 e2 v3 Y. b2 i public ListNode mergeNodes(ListNode head) {
2 p; @1 `; b' L2 v" w; ^ ListNode res = new ListNode(0);
, Y5 E. G$ W8 k$ G% _$ J3 Z ListNode tail = res;+ o) k0 }- X1 R+ x: r+ W
int sum = 0;9 `# [, n4 e* s: {. o4 l$ v/ ?# e
for (ListNode cur = head.next; cur != null; cur = cur.next) {
6 e1 u3 ?$ _' v$ j sum += cur.val;3 J! z U5 w" \% g! v
if (cur.val == 0) {
8 }: K/ A9 {4 T( @ {9 p tail.next = new ListNode(sum);
( j1 Y |# y: k% w tail = tail.next;
% J7 ?* V V3 Z& a* z3 b+ R sum = 0;/ x2 \) p7 T! q, y& H: p
}% ~/ Q( p* d8 y& P" h! U
}
) s% x/ i$ N- J8 K/ _ return res.next;8 S" N4 M5 w- [' C' A) M. @
}
+ d6 R5 ?" K) P3 ?2 e6 ^1 ?( \2 I9 T}; f+ t( i; I. |( m$ x9 R2 I3 y& @( A
4 a; H' e# r9 b# }( w
7 w/ D! [$ }4 Y% s0 G+ {* H) T9 R# G
【 NO.3 Merge Nodes in Between Zeros】0 P+ `( B6 z2 m9 _; I- A9 F& ?8 _
/ F) X& c4 o% D5 q. {' `3 z6 W1 ^
解题思路
" L) l# F+ G6 P注意题目描述:“不必用完所有的字符”。所以直接贪心即可,从最大字符开始,只要连续超过了 limit 就使用次大的字符分割一下。 f; _* B. Y# u
' _# y: J9 n: t" |. f! b代码展示8 H7 D6 t M" l S1 v
O8 Z3 B/ x( F- f/ `
class Solution {/ E' r7 G4 c5 a9 P% f
public String repeatLimitedString(String s, int repeatLimit) { H# K) l* q7 W8 ~. Y" l
int[] cnt = new int[26];
. q4 x( [- }+ J6 C8 g& ?" E for (char c : s.toCharArray()) {6 z" u: y; A; q1 i- l5 T# e
cnt[c - 'a']++;# d% {$ v" b% R) f1 ^0 d" C) B
}9 o$ R, c% v% A% E$ P
+ p7 K$ G' X& @ StringBuilder sb = new StringBuilder();3 ~' ]8 | d& K G% L: m
int repeat = 0;
- L6 y5 l6 [8 K, S5 o: y char cur = 0;
$ o+ d& E9 W. t$ J4 J for (int i = 0; i < s.length(); i++) {
, \1 T8 m( t: C char c;
" B1 C0 b3 E# ]( x# @2 ` if (repeat == repeatLimit) {
: P! j4 |! L& ` G repeat = 1;6 M$ C( j' M }4 T# @8 D* ~
c = poll(cnt, cur);' ?* c; o5 p1 L$ s
cur = c;6 ]6 N y; Y1 _/ f+ M- {7 m% W
} else {
' K, n# u1 F4 j: b0 q3 t3 F c = poll(cnt, (char) 0);) v4 s2 J) B4 j3 R' y2 s" o
if (c == cur) {
( u: o; Q: c% \% q6 }8 Y2 ?# I repeat++;) e# p5 S) i7 l% f5 d1 \
} else {
+ j# N% A$ i# v repeat = 1;( o& ]8 _& y8 h7 c% c- q- b
cur = c;9 [# s, j( L' B/ @2 Z! T" A1 G
}
+ E. G; _ G3 r0 ` }
: B) j4 k: K9 ^ if (c == 0) {
/ \) I0 @ u( n break;
$ [8 Z" m1 Y2 {5 T: M' R! r! d5 P; _+ Z8 A }
\% b6 j8 Q. z) {8 c sb.append(c);
. P* R- V) U6 G" e* O }
4 ]) [' [3 C4 g* G' z2 ]7 S0 g return sb.toString();5 a% ~1 X+ X! y+ V! v' a, [
}
1 K" N/ g$ X5 D% k+ {+ D
) t3 A4 Q$ H$ e2 s; @ private char poll(int[] cnt, char not) {
1 g* _" {+ _. y- ^0 R/ b+ _ for (int i = 25; i >= 0; i--) {
$ ?% z: W+ k3 f9 m) r1 p if (cnt[i] > 0 && not != (char) (i + 'a')) {
9 y( d& D; F- b! \# G cnt[i]--;8 s6 k) x* }+ V: q
return (char) (i + 'a');
" N( c- N; U+ i$ L5 {- Q }5 D' S0 B, O( U h9 }
}8 J. T2 C4 ?, C3 g/ p/ P
return 0;7 G4 M& w; O7 U. n
}
+ m- D3 C5 p: c: C7 I8 G) O}
d7 t, D& ]6 X9 X2 q1 m% S3 k! r& r% v. }! }% J/ O
2 g+ h4 t' b. L" a' D' h
【 NO.4 Count Array Pairs Divisible by K】5 s/ t# t6 D, }
& u7 \- K9 L6 u1 [7 d0 Z解题思路: C* b# Z2 E( d4 E
预处理转换成最大公因数,详见注释。% ^% _0 P; R/ A3 b: ~0 m" m
$ D: C8 d7 a+ z$ H, F' Y* R
代码展示
& I- y3 N4 @4 \% }8 m8 b% l" C9 a" {* G1 i6 _! @/ ^. {# I5 v+ N
class Solution {
6 `1 u1 T- R$ k; m' x public long coutPairs(int[] nums, int k) {
& K: S1 w/ }. w5 { // 将 nums 转换成与 k 的最大公约数
4 N7 P/ u3 X1 i9 z. s. G // 因为每个 num 中,k 的因数以外的部分没有意义 (即使做乘法这一部分也无法帮助结果成为 k 的倍数)* e6 Y. Q9 {! L2 b! [
for (int i = 0; i < nums.length; i++) {% N% B) r0 n4 {
nums[i] = gcd(nums[i], k);6 A/ g7 A% R, P6 }) ~5 e$ R) @1 |8 S
}9 X9 Q- A/ I, |9 \' b* x
long res = 0;4 A5 P9 c, |1 R4 b& y4 c( N
int[] cnt = new int[k + 1]; // cnt[i] 表示因数 i 的出现次数
; T5 u+ w& {( { y" B" ^0 N: v9 Q for (int num : nums) {
; A0 }" u$ J" S; g2 v5 j* l, I" j // 经过了最初的转换, 此时还需要因数 k / num 即可组成 k 的倍数* |( F, f% E+ ^6 E' K, \$ T6 Y n
res += cnt[k / num];7 R+ }6 A; A3 b$ f
8 _2 @, w$ c3 {! P3 m ~& e4 W0 K
// 使用 num 维护 cnt, 即 num 的每个因数 i 都对应一次 cnt[i]++& ~$ q5 \& d( h/ w {5 F5 `4 O+ _- b* r3 v
for (int j = 1; j * j <= num; j++) {
: _: ~2 ?1 R+ D0 G if (num % j == 0) {
8 l9 @2 Z& ]9 Z cnt[j]++; b L' `8 O- t6 y$ V# V5 o. a
if (j * j != num) {/ a% w/ H# g- m: Q: _4 k; @6 R
cnt[num / j]++;
/ v! q/ i x$ A. Q3 d }
4 c6 G- m+ p! `: s. e- Z- p }1 r7 |, i$ ^7 X. _( C
}
/ \" ^% ]! ?5 o! _: J# @' R0 O; p }
+ Y. k# F& S; v' X, i& ?1 e. C6 J' R return res;
2 s# f0 D; h6 N2 u3 X/ A0 C }# Z c9 R: E3 s
! x; J' ]( i+ s* I% p6 w5 d
int gcd(int a, int b) {
; W" h. h( |6 [ return a % b == 0 ? b : gcd(b, a % b);
5 R% K r) v) U3 L8 o, \! v+ z }
& T- n# J$ W0 y) ]7 s9 f} |