找回密码
 注册账号
img_loading
智能检测中
置顶:如何加入2024届新生微信群

[吹水聊天] 上岸算法 I LeetCode Weekly Contest 242解题报告

上岸算法 回复:0 | 查看:2700 | 发表于 2021-5-25 23:22:10 |阅读模式 |复制链接

UWCSSA提醒您:

警惕网络诈骗与盗号,不要在他人发送的网站中输入密码,换汇或付款时请小心诈骗。

为了避免个人信息泄漏,建议在帖子中使用不常用的邮箱,或使用私信发送联系方式(点击对方的头像,然后“发送消息”)。

帖子通过审核只代表内容不违规,CSSA 不会验证内容的真实性。请谨防诈骗。

登录后可回复主题

您需要 登录 才可以下载或查看,没有帐号?注册账号

x
本帖最后由 上岸算法 于 2021-5-25 23:25 编辑 : |! ~( ~8 r1 |# ?
; ]9 y4 x( a& p1 o2 k; U$ `
No.1 哪种连续子字符串更长
解题思路
签到题。
代码展示
  1. class Solution { 2 u+ d% ~9 C* y& F: H/ g
  2.    public boolean checkZeroOnes(String s) { 6 g& Z: A; \+ i% y4 |' U- y
  3.        return check(s, '1') > check(s, '0');
    " k; C3 h. c1 `
  4.    }
    ' R6 S5 j/ Z& C' [$ s/ `
  5. & G& t) T- B" Y7 @: T
  6.    private int check(String s, char c) { 4 y- s, s8 n; E, G
  7.        int result = 0, count = 0;   n% w; B% e/ J
  8.        for (int i = 0; i < s.length(); i++) { 7 |$ U  `; L; c3 g: B; n( f
  9.            if (s.charAt(i) == c) { 5 w3 y9 c1 y7 T9 W1 @% J
  10.                count++; : d7 Y% r' ^- |/ H6 V
  11.                result = Math.max(result, count);
    & h8 X+ J- Y2 [" v
  12.            } else {
    3 I' X5 |# h" G; `
  13.                count = 0;
    / U& j' U; P7 B" s% q8 `3 V* L
  14.            }
    : [. v" ^' g" C4 h" i! C
  15.        } ' H9 ^9 S. ]4 W# P; j: ~% G# q
  16.        return result; ' o$ @) Y0 i* M9 C, T8 S7 [
  17.    } + D& \$ I' `% x- [
  18. }
复制代码

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

本版积分规则

登录 发布 快速回复 返回顶部 返回列表