登录后可回复主题
您需要 登录 才可以下载或查看,没有帐号?注册账号
x
本帖最后由 上岸算法 于 2021-5-25 23:25 编辑 : |! ~( ~8 r1 |# ?
; ]9 y4 x( a& p1 o2 k; U$ `
No.1 哪种连续子字符串更长 解题思路 签到题。 代码展示 - class Solution { 2 u+ d% ~9 C* y& F: H/ g
- public boolean checkZeroOnes(String s) { 6 g& Z: A; \+ i% y4 |' U- y
- return check(s, '1') > check(s, '0');
" k; C3 h. c1 ` - }
' R6 S5 j/ Z& C' [$ s/ ` - & G& t) T- B" Y7 @: T
- private int check(String s, char c) { 4 y- s, s8 n; E, G
- int result = 0, count = 0; n% w; B% e/ J
- for (int i = 0; i < s.length(); i++) { 7 |$ U `; L; c3 g: B; n( f
- if (s.charAt(i) == c) { 5 w3 y9 c1 y7 T9 W1 @% J
- count++; : d7 Y% r' ^- |/ H6 V
- result = Math.max(result, count);
& h8 X+ J- Y2 [" v - } else {
3 I' X5 |# h" G; ` - count = 0;
/ U& j' U; P7 B" s% q8 `3 V* L - }
: [. v" ^' g" C4 h" i! C - } ' H9 ^9 S. ]4 W# P; j: ~% G# q
- return result; ' o$ @) Y0 i* M9 C, T8 S7 [
- } + D& \$ I' `% x- [
- }
复制代码
5 W p3 {, y2 U秋招将近,华大学长/斯坦福学姐联合组织了一场面向北美2021秋招的算法带刷公益活动。 带刷内容源于Leetcode 原题/近期大厂算法面试真题。 模拟面试+面试技巧分享,备战秋招! 只要你熟练掌握一门计算机语言,比如:java/ python 等,即可免费参与本次刷题活动。 活动时间:2021/6/1-2021/6/25 No.2 准时到达的列车最小时速 解题思路 二分答案。 对于给定车速计算通勤总耗时的时候,建议仅在最后一次运算使用浮点运算,其他均使用整型向上取整的除法。 代码展示 - class Solution { 6 `5 Y8 d* `' ]8 t2 \5 _% W
- public int minSpeedOnTime(int[] dist, double hour) { 8 {' ?# t) h6 ?! m9 |
- if (!check(dist, hour, (int) (1e7 + 1))) {
1 m8 ?% r3 f M - return -1;
; E- e1 |1 @ K! ~9 g- Z - }
8 c5 v3 W! L: w0 B+ v6 y - int left = 1, right = (int) 1e7;
: a) g+ v- @ ]' r8 u - while (left + 1 < right) {
M8 W; ]: ]! A, P$ G/ h5 A - int mid = (left + right) / 2; . z0 [# m8 [1 b& g* d3 S
- if (check(dist, hour, mid)) {
+ T/ V- D! T1 A+ N& O' B - right = mid; 6 A6 ]* V% F2 ^0 R
- } else {
, l, D" J/ S1 ~) T1 J g) i - left = mid; 4 T, g' h" @& ~- X7 U$ w: N: B
- } & ?+ x# G- P7 t) ^' g+ a1 \
- }
8 {1 T3 _" n2 f+ r - return check(dist, hour, left) ? left : right;
3 V+ Z* l) @; |3 a9 s) c - } / v& o* X8 k/ v8 c; `, f( e8 S; ?
- 8 l7 V4 p% c4 t' o! q' R0 a d+ x
- private boolean check(int[] dist, double hour, int speed) {
" a1 L1 U4 l0 s; b& Z6 ~# w - int cost = 0;
# u( C) D7 G$ X1 r - for (int i = 0; i < dist.length - 1; i++) {
! L" K2 f* B/ B m- k - cost += (dist[i] + speed - 1) / speed;
, w/ |; ~+ _" @* R0 _; ` - } ( ?) f3 h m% h' f" m
- return hour >= (double) cost + (1.0 * dist[dist.length - 1] / speed);
! v' J, G% \2 j; Z( P! e7 H - } 0 B2 J) K- z: k- P: e+ j1 K
- }
复制代码 & b: s/ C0 t1 x9 L" {/ ?) K
No.3 跳跃游戏 VII 解题思路 类似于滑动窗口,使用队列维护可以跳跃到当前点的点集合。 代码展示 - class Solution { 3 Z* \1 Q, z( h6 U3 m$ N2 M }
- public boolean canReach(String s, int minJump, int maxJump) {
2 O3 d: c+ {& @& {; A, Y# ^* Q - int n = s.length(); ) E& x5 X. A& C& p
- char[] str = s.toCharArray(); * \, ?& V! \: e" F S/ s" E
- if (str[n - 1] == '1') {
- g% N. u* w( J* n6 |5 K - return false;
* V/ Q4 L2 ?$ e4 p* F9 D3 i - } 0 G2 z0 U0 V/ G N# a
- LinkedList<Integer> queue = new LinkedList<>(); 8 x. O' ?) I. Z, p- j* g/ X" _1 E
- queue.add(0); % Z# |, H" v/ A' S; `) Z2 E
- for (int i = 1; i < str.length; i++) {
$ _! x$ P* _, W( {* A2 R3 } - while (!queue.isEmpty() && queue.getFirst() + maxJump < i) { + [, `" u& {( G* w5 r
- queue.pollFirst(); ! w. B) w5 |4 @7 o7 A( e/ A, S" P6 }
- }
5 q. @$ D. w. j" K9 `' O/ a1 M* F - if (!queue.isEmpty() && str[i] == '0' && queue.getFirst() + minJump <= i) { . ^9 ^% l6 W% V
- if (i == str.length - 1) {
& g4 e3 F& J# @1 _ - return true; * h8 k8 v+ {& A0 @' e
- } ( E' c9 n- W; U- f
- queue.add(i); # r, o7 `0 C4 |$ G+ L
- }
/ V$ `6 l# [ U {/ C4 K - }
7 e% Y. d# w$ n1 k1 _, b% ~7 m9 f - return false; # r4 Z! d. c! o- l8 b) f
- }
' B" k2 T8 i1 U i8 E - }
复制代码No.4 石子游戏 VIII 解题思路 看似每次要重新放回去一个总和石子很复杂,但其实恰相反:放回去的石子必然被对手拿到,因此抵消了自己拿到的和。 代码展示 - class Solution { 7 u, x7 t) w9 ~& J! h4 c8 R: m
- public int stoneGameVIII(int[] stones) {
# F _" d8 h- |4 z6 ]& @3 e - int n = stones.length; # m0 z0 f. X1 t& L$ P' u- e
- long[] sum = new long[n];
% K( Q0 k' G$ B* x% e3 S$ N - sum[0] = stones[0];
& g7 M! ?6 o. F - for (int i = 1; i < n; i++) {
+ V! o c5 g* b- ]( a7 F - sum[i] = sum[i - 1] + stones[i];
6 u' ~! m" `6 ` - }
. R! u+ c/ {# v. \3 f( J - long[] dp = new long[n];
. _; G; J/ v' S( K3 _% D4 t - dp[n - 1] = sum[n - 1]; " K+ W# a; p; e3 ~3 M o3 s! u! e
- long max = dp[n - 1]; 2 P+ Q1 U- F: g9 y, X
- for (int i = n - 2; i > 0; i--) { " L- @! p5 R$ V
- dp[i] = sum[i] - max;
! g9 j* S" F. l) h8 y/ Z7 m5 q - max = Math.max(max, dp[i]);
9 N# S6 n0 X* t4 i* o5 g - } ( y& _9 f" d1 h% C
- return (int) max; 4 x0 Y7 y; K6 `; A5 S2 w) }3 V
- } # [" X9 m+ T( `$ I& X, G
- }) |6 ~6 t# l: c, ~
复制代码 5 @& d2 j& `2 N1 l/ A0 I
|