登录后可回复主题
您需要 登录 才可以下载或查看,没有帐号?注册账号
x
【 NO.1 Count Integers With Even Digit Sum】" E0 V+ y; S8 t: E/ n
$ H+ \% Z, o4 r+ L6 U/ H7 c w解题思路7 P2 w% }4 D& ?3 n6 d3 [; X" T
签到题,枚举计算即可。
0 c7 ]% h- }- P0 d
% K" [3 [) x* u/ ^/ f' f/ E$ P代码展示
- x# X7 B0 } a- l1 G, t
0 v8 d3 k. R' @, {/ l0 } _# Qclass Solution {
4 R4 I3 s3 |. ^* e- l public int countEven(int num) {
; A5 _4 w' U; ?: ^ int res = 0;; E; s. t" o) z4 m
for (int i = 1; i <= num; i++) {
& F. {$ u' X4 K+ B# I if (digitsSum(i) % 2 == 0) {
3 @/ G3 k0 X) U5 o% U" {7 z: H# o res++;& v9 G2 b. V8 R6 k6 B! g+ S/ z: U
}3 N$ O+ F5 Z0 m# q
}
/ F5 O2 i" U, K) Q# f2 s5 P return res;1 u; \9 B/ q$ y$ Z7 y# b0 m
}
0 D( `" p0 }. r# @1 B0 @! r! x- k- _& `3 g
private int digitsSum(int num) {
! Z5 W0 Q' r4 w0 r int res = 0;" b$ A; ^ Y& l8 H, ?) \- c
for (; num > 0; num /= 10) {
6 J6 G( N/ `9 o3 D2 G res += num % 10;$ p; v+ y$ t" b! j
}, A7 }4 ~1 K: K4 I3 o+ d5 H" T
return res;
& A9 U9 ^" y5 T T& k7 e }1 T- g, ]3 `. M7 G
}1 P7 j4 _/ j5 |2 E1 F
% X1 U; f3 t+ m) c4 k$ y+ Y* m+ ~
' ?/ S3 O. D. ]. A6 {. l
【 NO.2 Merge Nodes in Between Zeros】
& i* r! \+ w. n$ O+ D9 B0 v8 w6 p: J) k W# D" n& h/ E8 Y
解题思路5 B/ X2 B0 A! I7 \# Q/ C7 \
遍历链表即可。4 i' z D/ Q$ f. E# U, o
0 X3 q A! C8 v: y! C/ x代码展示# ~) v9 C( V/ I% R6 ]( T3 m# `
. o2 H+ s, I$ k7 ?7 `
class Solution {! i7 K$ p, |; U* c C7 n9 m% v1 M
public ListNode mergeNodes(ListNode head) {9 V$ q% k1 T, T0 n2 [
ListNode res = new ListNode(0);
" k. q- i9 ]3 s4 K" J9 }5 }, m ListNode tail = res;
k1 g+ e8 D" A) Z' Z int sum = 0;; @2 i% v7 z8 d! n- V& x0 ]; `
for (ListNode cur = head.next; cur != null; cur = cur.next) {
8 N/ M. I1 |! _2 P8 U sum += cur.val;' d* u W/ H3 H' o6 s
if (cur.val == 0) {* M' d R) |- J% P' a2 T4 L& \
tail.next = new ListNode(sum);
. b! @+ |3 ]: m$ }2 l/ u tail = tail.next;
* F$ J) w' e* } ^# K# x sum = 0;, \- t( t$ n6 |- u! l7 \
} k3 |6 {/ e8 y- J( G: Z- @ m
}
4 y0 o/ \ R( j+ `9 C+ c, F1 w5 { return res.next;: u& ^$ _* {0 B ~1 G3 `
}
$ h" t5 a- l+ h0 }1 o, T# @}
2 z' k. T, r! e+ j( c: H
4 H! o; F5 L1 i! I0 s9 A/ X0 E. ?0 ]
s+ O' d' e' P2 T4 \- U【 NO.3 Merge Nodes in Between Zeros】
# n: Z$ X& }5 V2 S j* [! i
7 S$ S. y7 G7 U- l# c解题思路& s1 v( T: g9 m/ @
注意题目描述:“不必用完所有的字符”。所以直接贪心即可,从最大字符开始,只要连续超过了 limit 就使用次大的字符分割一下。$ C4 E. N, Q4 a4 O U
1 s! _) P4 J6 z: x1 ^) J, }代码展示, M* N2 j7 b5 U9 a3 c; a! c. _
" A- W! B4 T% j
class Solution {
9 v6 a ?6 m0 h9 H3 u public String repeatLimitedString(String s, int repeatLimit) {$ U( m: U3 O7 W( R: `
int[] cnt = new int[26];7 Y/ z- {8 ?; i6 I0 G- b, K
for (char c : s.toCharArray()) {0 x& N( U$ V/ t, \; s
cnt[c - 'a']++;
0 B, Y4 y! P# y7 }' M a( x, x }! ?& z9 R( C; \: G
n4 i$ L! M0 g5 i2 X StringBuilder sb = new StringBuilder();& l0 f/ I3 c. L' B
int repeat = 0;
0 Z0 {# m5 d2 I6 K/ U* u' K, s char cur = 0;2 k+ Y1 A9 H" @, q( v& w0 z+ J
for (int i = 0; i < s.length(); i++) {' Y$ w; P7 [4 @5 E
char c;9 C2 M( C& u5 C! O( L8 j1 F
if (repeat == repeatLimit) {
" D# q& [& n7 } repeat = 1;
# P: m" j. p) V6 j3 z3 T c = poll(cnt, cur);% `# N) S3 f {$ _- s% |; O+ ?7 j6 t
cur = c;
; C7 e2 K$ J5 J" G } else {
1 P% ^& a9 k0 L! K( K6 T+ N c = poll(cnt, (char) 0);
5 L, C. Y; x) T2 l, @# n if (c == cur) {, U- ^% s9 N9 y5 ]* Q1 M, n
repeat++;/ `- P9 x; @! O& f9 d3 L T" y
} else {/ J0 H) y, i% F" J& U- s8 {( @8 G5 S! m
repeat = 1;) z7 x* Q8 M; p5 v+ q$ i
cur = c;
6 l& D: d/ g" d- Y6 W7 q( r; e }+ U9 q9 p$ x8 ]' z
}
3 H# T) s% p8 I2 A7 X if (c == 0) {
0 I- b" K! g. Y. m- g2 m& z) B break;
4 H w. i! n; K$ q) i5 Q }
, M. s2 p8 \9 J; j ?0 k sb.append(c);
1 ]% b( ]5 o4 t }. ~( {' J; ^* A3 B$ y* O& _$ D& W
return sb.toString();& ?3 V# N* b) @+ c6 y
}
+ G4 G3 W$ d& @! r5 R: R! ?8 G8 [
" n1 H, J A8 `4 O+ o$ r% |" _ private char poll(int[] cnt, char not) {
6 Y$ P$ v! g ~ Y for (int i = 25; i >= 0; i--) {/ p4 p$ S: \$ ]; Z. Z, |6 Z; A/ [" v
if (cnt[i] > 0 && not != (char) (i + 'a')) {- C0 o4 E1 b3 r5 X# S
cnt[i]--;
* O6 @1 E* m# A+ o! }' z return (char) (i + 'a');' R7 g4 F. J( a S( z9 V
}4 k M7 Q; a2 d$ ?4 n
}% A: ?* a+ H% G
return 0;4 h; G+ M* H( J, ?) V
}
1 ^5 Z* \7 j# F, G}( ]* t/ q. m% z- j4 K6 C8 U, ?
" o5 K& Y. @* Q8 r
% f* n8 W. X" a3 ~1 [2 W8 F* o7 A5 r
【 NO.4 Count Array Pairs Divisible by K】
/ K( f0 K4 M% E) ]! T {% X" P. g& |0 P3 Z! [$ A0 q ~3 s
解题思路
+ l+ @" A: {* `' m8 H预处理转换成最大公因数,详见注释。' k2 {& t* f, V% X( k( p6 f
4 n; V/ \6 D6 I+ u! b
代码展示
5 _ C. w- r6 X/ w% D" j# f) l
$ p% A1 E8 J: |3 v% e1 S2 }class Solution {
?" F% c6 u$ O% _+ C" h! H) l! E public long coutPairs(int[] nums, int k) {$ I- V& S% s+ _, z: }' u' \* }
// 将 nums 转换成与 k 的最大公约数( p% q/ E# a- M; \
// 因为每个 num 中,k 的因数以外的部分没有意义 (即使做乘法这一部分也无法帮助结果成为 k 的倍数)1 V, K @ d! E' M8 ~6 C
for (int i = 0; i < nums.length; i++) {( C* v! F4 @: o0 S. H) {
nums[i] = gcd(nums[i], k);, N0 j6 P) c9 e3 }0 D( M: a! i
}
7 r: j. z# ^' m% \9 k long res = 0;
) f2 [4 d2 W7 ~ int[] cnt = new int[k + 1]; // cnt[i] 表示因数 i 的出现次数
* B& [8 i, d. A9 l for (int num : nums) {& e0 x4 |" m8 U3 f
// 经过了最初的转换, 此时还需要因数 k / num 即可组成 k 的倍数. F4 m; K( N0 Q8 e V
res += cnt[k / num];
" p8 w; Z1 @) b; e' u
; T, A, \4 U% L, w% q: V // 使用 num 维护 cnt, 即 num 的每个因数 i 都对应一次 cnt[i]++
9 z* R% k4 b I8 w0 x for (int j = 1; j * j <= num; j++) {
; [7 l* a, O3 o, c if (num % j == 0) {
3 j+ u, a& O7 x) @6 ] cnt[j]++;
) c: P% p) s2 K& C if (j * j != num) {* X! I) D; _$ J
cnt[num / j]++;
1 c0 W- b4 U8 M9 M9 R% e- n9 z5 ?; t }& _* X, |, N; C/ k( S5 d
}4 K X7 y9 J5 H& M
}+ e2 ^' N- D6 R* W% e3 `+ O0 P8 k
} w. @$ o# U3 G0 g
return res;, ~; w2 R2 h% G3 I
}) [' v+ {9 A: o# K" l
, T6 y! C! F6 L6 K& w/ ?
int gcd(int a, int b) {
$ ]/ O1 Y) u- _+ q* A5 T* b) k return a % b == 0 ? b : gcd(b, a % b);8 p% {8 r) l4 H8 u4 I
}' u: R. ]5 U& ^ E- e9 Y% P
} |