登录后可回复主题
您需要 登录 才可以下载或查看,没有帐号?注册账号
x
【 NO.1 统计字符串中的元音子字符串】- L0 [9 r( K; w6 j% v8 e I
解题思路
! ]2 S6 H. g' r. u签到题。
/ c, R9 x% B$ D! y! `
( U3 q, c9 E' |+ M" o5 m3 p代码展示
4 N& c8 K. l% e( k- _/ A; o/ @# w' ^9 ]) [/ O! a6 w- v7 H7 y
class Solution {0 i2 l8 N3 C6 K& L6 ~
public int countVowelSubstrings(String word) { d! \, A5 }" o, o( c- Q
int count = 0;- A& q& y. _2 ~7 ~# ?" R0 q' c( i
for (int i = 0; i < word.length(); i++) {
: @- a6 z8 q, J! e& l for (int j = i + 1; j <= word.length(); j++) {. U9 y# |5 Y7 l; w
count += containsAll(word.substring(i, j));, T/ A0 R* X' |$ w
}4 g S |* P- o9 }/ M' D
}
2 n' u: Q; z$ @9 p/ O return count;' I } I }$ \ b! `
}" U. o" D6 J8 E2 Y' s6 L9 f
6 r2 ^- X" d" O/ x private int containsAll(String s) {
' E% ~) B8 m3 k. p, k if (s.contains("a") && s.contains("e") && s.contains("i") && s.contains("o") && s.contains("u")) {, u# I$ ^+ K# o# E
for (var c : s.toCharArray()) {
" A% B* {# [3 t7 v% ^ if (!"aeiou".contains(String.valueOf(c))) {
* u3 U4 c e! { return 0;
, C) ^% U, z1 g2 i" |1 k }1 V- X" J; O; b1 o# l: ]& P6 c R
}" X; {. E5 c0 e% i) f
return 1;- ?! A0 r! W5 @2 p- S. ]
}) L# C2 N4 N3 |8 C |
return 0;6 I% S- o1 C7 n5 U$ `5 ~: ~
}- o: p* O' p2 G- e& Z
}: V7 M" `" s) n" Z0 R% N
8 A7 D6 Z# U+ z& z8 a. V/ w4 u# h) W3 }& E
【 NO.2 所有子字符串中的元音】
# l2 j J2 Q( z解题思路; d5 U" \; s$ z' N8 i
依次计算每个位置的元音字符会被多少个子串计数即可。5 n. H$ y7 V5 m# z
8 ~2 x& d8 Z0 _9 {
代码展示: y! i" P# ]9 R9 R1 l) V
! \) ?& l- Z* _+ B* I# x( a
class Solution {/ z; H* E1 {8 Q1 s
public long countVowels(String word) {; b- {- Y$ Z, X: H9 d+ [- u( J8 p
long result = 0;) L) x1 R* }- E2 B. o1 h
for (int i = 0; i < word.length(); i++) {
# Q7 D( c" V: ?! K1 P2 X7 M if (!"aeiou".contains(String.valueOf(word.charAt(i)))) {) [4 o) }* L& s5 ^! Q, |
continue;
( J/ l# J* w/ i" ~& Y: r2 O" \( ?9 L }, `/ s. o+ d. H! d M' X. W
long left = i;
* T& W9 T( w% G% q } long right = word.length() - i - 1;: w) O6 a* }* Z& ^
result += left * right + left + right + 1;! v2 \1 B4 r0 \- K
}
' W8 G) U% l+ o return result;2 ~! p( E' O2 |! e! z/ p" z7 ^
}
- D: f x) _6 R/ H4 G5 G}
8 ~+ C7 J" T0 r D( c5 t2 Z. b) I6 H4 b) X g
【 NO.3 分配给商店的最多商品的最小值】% X9 o* w5 k! w' B$ w3 i
解题思路0 \- Q, p; o5 s' j
二分答案,假定一个商店最多能分配 x 个商品,那么我们可以轻易计算出需要多少个商店,即可得到 n 个商店能否分配完这 m 种商品。( Y0 [4 `& V$ X. S
; ?) M3 m2 W; k2 M% E- k% j
代码展示# I4 O; g p ]4 C
$ @% J8 S+ F3 V# c& {
class Solution {+ J J1 U' B* _, S5 N
public int minimizedMaximum(int n, int[] quantities) {
+ |5 F" p0 F' E int left = 1;
8 l5 \3 H9 I9 H+ r- `. W int right = Arrays.stream(quantities).max().getAsInt();. K! D% T( w& L( y% b: v
while (left + 1 < right) {
- G7 k4 X: I/ F. } int mid = (left + right) / 2;
6 X5 `& e5 m; i if (check(n, quantities, mid)) {
: K) |6 s* l3 K right = mid;5 C/ _( ^9 L$ {* K
} else {* S4 t/ ?6 w: Q4 @2 ]
left = mid;/ `0 J4 z& T0 a2 @( D3 I
}
. d( L6 N1 ~( I* B# b }! W- @) y# H2 o' \' z c! x
return check(n, quantities, left) ? left : right;9 o5 X/ [2 G: J" r) |4 z {
}
* L6 n; C% j# G
2 K, i. y+ I% M( i' h: W private boolean check(int n, int[] quantities, int x) {
: z- h9 g% ^* `5 M: ] s2 W int cnt = 0;
" q1 s) O7 H W' G- g9 \; U% P for (int q : quantities) {
; O+ P j/ b6 x& R$ S cnt += (q + x - 1) / x;
* k k( c& b0 @1 Q$ @" v. X: ]9 s3 G# [ }* e' @9 ^7 e2 C$ o/ A3 y
return cnt <= n;" R$ g0 b& T6 Z. Q
}
# T. x' G' `- l8 T; z! H1 ~}" b& A4 _( Z, Y# Y* i( Q& ~) |
# G2 L4 x. _3 X6 h) t- O( i【 NO.4 最大化一张图中的路径价值】3 h6 ~0 Q* a/ o
解题思路
4 y+ Z0 Q* m4 C c3 f$ R( g4 |2 H% ]2 g看似复杂,但是观察数据范围,发现直接回溯即可。
1 C& ]* o! \8 Y% m. |1 A c& I( C2 y
代码展示
8 F% O4 X7 y ]4 W5 t
: x8 {3 J' F! g1 dclass Solution {( s& u& I. g" J/ z& H% T
int result;
1 C- P. r2 ` v; P9 x List<Integer> empty = new ArrayList<>();
- [) V! Q/ e. X+ q: n/ z/ D! g6 @/ h& i% O# x! b
public int maximalPathQuality(int[] values, int[][] edges, int maxTime) {
. ~: e( }, k8 E+ `9 Q: K6 l Map<Integer, List<Integer>> children = new HashMap<>();. y. j8 @4 [. v3 f$ ?
Map<Integer, Map<Integer, Integer>> times = new HashMap<>();3 P, Z& N+ M" Q% G
for (int[] e : edges) {
/ G( W/ \* F% E2 S5 Y R. ^/ d6 v if (!children.containsKey(e[0])) {) V. g* z$ u+ F1 b7 Z2 _( q. p Y; ]
children.put(e[0], new ArrayList<>());4 n$ _3 x6 j' e5 { X4 t: g9 ]
}
' m" `: p3 Q- [& O; { if (!children.containsKey(e[1])) {; R6 A+ {6 }4 e- I% ^% H
children.put(e[1], new ArrayList<>());
7 n8 }- y& O5 d- K$ p4 ? }
( p) q4 M, ^2 E# E if (!times.containsKey(e[0])) {9 e! J7 M; I' e8 K9 R
times.put(e[0], new HashMap<>());
4 x% O6 V7 o- N; w5 g, b. Q }
# Y3 D1 b. ]1 J: |+ j' K if (!times.containsKey(e[1])) {
3 S2 e' i5 V6 G: p+ o ` times.put(e[1], new HashMap<>());3 h2 z5 M1 ]( S1 ^ D
}
1 H! ^$ |. B& @6 Z children.get(e[0]).add(e[1]);
( E. I! }/ ~, v I1 e" g7 ` children.get(e[1]).add(e[0]);. o8 s. m1 L J0 n1 A
times.get(e[0]).put(e[1], e[2]);) l8 i' ~ a# f; f, \4 w! J. o
times.get(e[1]).put(e[0], e[2]);- I5 `! k1 z$ C% B
}
k$ A& C b( } }. Z1 ] int[] vis = new int[values.length];
# D ^- v- @ L* k result = 0;7 g* N( Y% {% b; T3 Y) |
dfs(0, 0, 0, maxTime, vis, values, children, times);0 u! b8 P/ J! T! p# [3 p Z
return result;
7 _$ |4 o% {5 \ ]. I }! b6 T, y1 f9 v/ c3 H
4 ^& Y6 [+ ?$ Y" V$ ?
private void dfs(int pos, int sum, int time, int maxTime, int[] vis, int[] values, Map<Integer, List<Integer>> children, Map<Integer, Map<Integer, Integer>> times) {$ r8 t# E9 M$ T4 w
if (vis[pos] == 0) {# z1 {" g+ K) u# b0 {) ~
sum += values[pos];( R/ s* s. H6 _6 G* a G: N0 ~* f9 p
}
! U2 `4 ~! y3 I" y vis[pos]++;
5 |- ]; W+ Z: s2 F if (pos == 0) {
- ^ U$ E( ]6 v- A+ M5 M$ ~ result = Math.max(result, sum);
j6 m3 y, k8 P$ z% K* Z& ] }1 t R2 C" f9 E' g3 B- A! x
for (int nxt : children.getOrDefault(pos, empty)) {' O# H. g2 d6 T5 {- t( e a
if (time + times.get(pos).get(nxt) <= maxTime) {; u7 ]" o* z2 y" g5 y! M; F
dfs(nxt, sum, time + times.get(pos).get(nxt), maxTime, vis, values, children, times);% k8 ^& X, `+ l( z* v1 p
}5 X) _- A8 W" l+ w: i. }
}
6 x) c/ p" R2 a* Y5 p, V; {5 } vis[pos]--;
" ]* B+ `6 D& \) w* h }
8 v# j* z. h+ A. y: Y* m}
! `$ o$ v; t6 N" @" ?8 g |