登录后可回复主题
您需要 登录 才可以下载或查看,没有帐号?注册账号
x
【 NO.1 将字符串拆分为若干长度为 k 的组】' z! }3 t. l) A5 N
解题思路/ f/ n% H b# P
签到题。! n/ l% H; t- \: o/ }, c) u
0 X' G* o$ k! `$ h5 d: `' z
代码展示) d4 I' Q) W4 A' [' r
class Solution {$ k; U& e( v$ w( Y) R
public String[] divideString(String s, int k, char fill) {
& J. ]; M6 R E, o2 I; A3 ~0 j+ Q9 M. R String[] res = new String[(s.length() + k - 1) / k];; P5 c9 t7 I. u8 r+ A. m
for (int i = 0; i < res.length; i++) {7 S* u) o8 H& [2 C1 \
if (k * i + k <= s.length()) {
" F5 o' L# e$ J res[i] = s.substring(k * i, k * i + k);* Z, a+ V, l) c& t6 ]4 ~/ {
} else {& @0 w# Y: y" J" e8 Z2 a0 e+ e
res[i] = s.substring(k * i) + repeat(fill, k - (s.length() - k * i));
2 A' E5 T: ?0 {7 ?" A }
# R. j0 Y X; _! e* ?; ~* F# P% k }; r! }2 v1 _2 k/ t2 d- m
return res;
- v o$ i) `8 |8 `1 u$ {0 }. s }# I- Q( b% H5 x- f- Q
. i; q1 _4 K4 _7 ^7 q, W1 A$ a private String repeat(char fill, int i) {
8 ]) v s9 A! A StringBuilder sb = new StringBuilder();+ d# Z1 Q! H8 Q% m8 I
for (; i > 0; i--) {
4 k6 B. m( }: c sb.append(fill);! s, V7 L* x+ W
}
( a3 I" ^* J1 V- B6 ]' t return sb.toString();! ^) d E! N4 q& Q: C, M
}
$ }7 N: L9 E) [}0 e1 a( C3 V3 i0 l6 j W
$ c% i0 J5 f# k% C; ~1 e8 Q( ~
【 NO.2 得到目标值的最少行动次数】5 h& x- k, ]4 g
解题思路
8 @1 m' N% v$ O3 r/ k' c逆序贪心,优先用除法。
* Y" M1 n6 g' B7 K K3 A
9 u+ S3 X$ D: y0 B代码展示" [$ e. f6 |2 M6 ~: ?
class Solution {
) ?' E3 A8 Y% w# H public int minMoves(int target, int maxDoubles) {/ n# `, Q) x7 M$ U- f V
if (target == 1) {
/ Y3 l/ v( z: y/ m2 o7 a3 V1 [ return 0;
- Q K# r1 s0 E, I. ]" z6 v }# j/ X E5 c" C) W" d
if (maxDoubles == 0) {
z( C; u+ A# o! V$ H G3 k return target - 1;9 [& A1 b, G7 g- P- @
}
( d/ A2 b0 n& t, x+ l. G& K if (target % 2 == 1) {: V) N# g5 e) d/ Y, J3 b
return minMoves(target - 1, maxDoubles) + 1;
8 g0 _- u2 q' T }
+ _9 u/ l/ n( S& o0 d9 _2 Y return minMoves(target / 2, maxDoubles - 1) + 1;
; j* I* O( Y* Z }9 w/ E3 e/ n* w- z
}* z. ?. Z3 ?7 m$ O; l7 m
* b) e+ I7 t3 v: `【 NO.3 解决智力问题】
/ m6 {) L/ _2 o3 s解题思路3 T. |; g. N" ]5 W, y5 Z! G* T
动态规划,定义状态 f[i] 表示解决问题 i 时,前 i 个问题最多得到的分数9 {+ @9 [# k r
1 V& W; F2 l( D6 t ?
则有状态转移方程 f[i] = max(f[j]) + score[i], 其中 j 满足 forbid[j] + j < i% L$ [3 ^1 n* W
/ ]* M* [" @( |9 v7 L7 J& a1 E# A
使用 TreeMap 维护 forbid[j] + j 即可
' |, Y2 m& q I5 n; v L9 o/ b# ^+ m' W/ z6 `6 F: N3 Z; W% @
代码展示
- O; e. U, n1 T1 L3 ?class Solution {
6 @8 R$ U; x, p; ~* G- x# d public long mostPoints(int[][] questions) {/ b' e* I! F) m+ g8 k! G# r! K, S
long[] f = new long[questions.length];* X$ u, C/ O" p0 R2 i5 i( [6 i
f[0] = questions[0][0];
, ^. P, g& ?( t TreeMap<Integer, Long> cand = new TreeMap<>();
s4 k4 Y" j: F& L1 I& Z) | cand.put(questions[0][1], f[0]);
* o( z& a2 o% M j1 |, X. h9 j- U$ U long max = 0;/ e {4 S$ t7 C/ A6 Z/ E
for (int i = 1; i < f.length; i++) {
2 `5 x. X( u+ I0 i* ^ while (!cand.isEmpty() && cand.firstKey() < i) {
- d; n, q3 @7 O5 x8 S$ p var e = cand.pollFirstEntry();% }, X- f9 s/ L. x
max = Math.max(max, e.getValue());
X& _2 X2 f1 S8 i m }, L k8 ]& i9 o
f[i] = questions[i][0] + max;
4 S( `) f$ [8 H6 _0 l int key = questions[i][1] + i;
+ U, Q1 u& e( t, e cand.put(key, Math.max(cand.getOrDefault(key, 0L), f[i]));6 D' `' _$ X7 j1 C* Y. @
}
7 E4 j& I) Q- @% W1 Z return Arrays.stream(f).max().getAsLong();# d1 @% [: [: V( Y' g% O
}! X' E' W# {, z) C1 j- ] c
}
; O7 Y* _/ J' N2 t7 S8 _7 d+ ] O2 H w% i2 @- w
【 NO.4 同时运行 N 台电脑的最长时间】
# e% q3 o$ H0 o4 j1 p* f% y. g$ |* \解题思路
) g6 T. Y+ y& n+ S, ?; W; e二分答案,详见注释。0 s, U! n3 [" O6 S1 p8 C
' g T( f% F9 k& \6 ]& e- A
4 \3 G1 B2 z A3 o9 l
代码展示
% J5 L4 W; q+ S& I4 S0 ~; S* tclass Solution {
6 e( |0 q1 s1 H' F3 m# j public long maxRunTime(int n, int[] batteries) {
( K( @4 _5 K, r0 {- v long l = 1, r = Arrays.stream(batteries).mapToLong(i -> i).sum() / n;
5 e' |, Z0 J8 Q5 k7 k& n3 c& L E while (l + 1 < r) {
8 r* P, K" M6 A3 y9 G7 Z. h long mid = (l + r) / 2;. R/ s8 Z5 d h
if (check(n, batteries, mid)) { P: B$ B2 l% w# O3 M' T: ~
l = mid;
/ |* ?' [1 d: \6 Y } else {
8 e$ T' Q4 d* d+ \/ w r = mid;& l+ T' T* Q8 q! i5 g i
}* r1 \5 O8 @: z9 I# F
}7 I3 r& i% D' O! i' w# O2 s3 f
return check(n, batteries, r) ? r : l;
# C9 {* E l, t! I& [! ^/ ^ }6 Q2 m, r W& s6 r
g6 V- W+ W5 ]% P' a H // 判断电池能否供给 n 台电脑使用 time 分钟+ u4 _6 h2 H3 c' \, m( D
// 相当于每块电池最多使用 time 分钟( e& Q' Y* u( m) Y
// 如果一块电池容量小于 time 分钟,那么它需要和其他电池拼一起才能组成 time 分钟
& X2 A. d0 S$ U; i) T" t& h. n. v // 如果一块电池容量多于 time 分钟,那么可以认为它将被浪费,可以认为这个电池容量只有 time 分钟" |# I7 n3 S) d8 o, w* _
// 因为换电池是不消耗时间的,所以只需检查电池容量之和是否达到了 time * n 即可# `! l+ e4 s- G3 f' q" F
private boolean check(int n, int[] batteries, long time) {
2 x1 R I8 C5 P return Arrays.stream(batteries).mapToLong(i -> Math.min((long) i, time)).sum() >= n * time;
- k0 _, A! ~( m @" \7 k }0 t+ D, W/ I( Q( y
}
+ b6 @# t" T+ o! U, l/ c3 O; z; d |