【 NO.1 字母在字符串中的百分比】* ]3 v( k; u* F; b/ w
& b8 {6 K( Q1 K) v' V% t9 u% Z5 B0 U/ {
解题思路. T3 c+ f/ g, M' w8 P8 |2 Y! r
2 I$ V7 S U2 D签到题，循环统计即可。
: {5 J4 {; x1 Y$ @ y/ {. q
; F9 b( O9 V. E8 Y$ R0 v9 N, b代码展示
% |% R, X$ y8 S4 e
% |0 A+ ]4 D+ S" U
) E: o& K; H: J【 NO.2 装满石头的背包的最大数量】
' w1 e& L* G- V, Z& ?5 `. A& ~# t
$ G) o% z" j' o3 b- s# g0 v; _解题思路: ?! v9 G! x* ~2 j: }- D
0 P" T* u ?) U" k. _( w- K8 n贪心，先装容易装满的。
6 w! N5 c' a" F n8 \5 c" q/ m9 t1 ~2 o1 |$ R6 h& l
代码展示
) M- I6 `+ T1 K) b, y- j! [& K; E' b$ W3 U
& R( }: j1 `6 k4 k2 _5 Q$ H【 NO.3 表示一个折线图的最少线段数】3 F' ?# {) g: F* e2 v0 o5 Z: h" N
4 M* T7 r4 y, m% Q% i L" P
解题思路
0 F! l- h, C. v. R
% }1 h1 V- b+ Q. J8 x/ `横坐标之差除以纵坐标之差即斜率，相邻两对点之间如果斜率相同，那么就可以用一条折线表示。
6 r% @6 [- G# V1 ]8 P
- p7 r2 L2 }% H1 P7 U! q代码展示* ]- M5 X2 s/ n- Y/ g
& Q. X' Q' L+ ^% X( y
) u5 d- w5 [* J" y$ | |0 t. |) e
【 NO.4 巫师的总力量和】* l; Y: C+ o8 W/ H0 [4 D% f
. X5 F- f7 F4 ?! I) I3 A
解题思路# Y! e' {( A. t) z( z0 A8 H
/ X5 q" P0 N4 u, c
前缀和 + TreeSet. 依次求出每个巫师作为最弱巫师时贡献的乘积。
! L8 M( @+ @; k i* w
& Y1 {1 @/ Q l. ?3 ]7 l当一个巫师作为最弱巫师时，他能贡献的乘积就是左右两侧比他更弱的巫师之间的这段数组的所有包含他自己的子数组。6 N4 \8 J) K0 z+ u; E
- Q' k; p+ y( H1 C9 e0 Y* `- N
可以利用 TreeSet 快速找到一个巫师左右两侧距离他最近的比他弱的巫师；然后利用前缀和求出所有这些子数组的和。2 G6 v* z L3 j' I6 J5 r
- V) T# J/ [& x/ o6 @
代码展示' Y, w3 Q; a9 q) u' }6 ~
. c/ J5 Y$ s! X% K7 \2 H6 k/ x8 |6 m% h
|
