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

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

上岸算法 回复:0 | 查看:2168 | 发表于 2021-6-8 05:32:43 |阅读模式 |复制链接

UWCSSA提醒您:

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

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

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

No.1判断矩阵经轮转后是否一致
解题思路
模拟矩阵的旋转即可。
代码展示
  1. class Solution {
    : M6 q, X' d$ u. B+ S2 _
  2.     public boolean findRotation(int[][] mat, int[][] target) {
    9 i' r0 z' P& {) C0 E) M9 n
  3.         for (int i = 0; i < 4; i++) {) V4 W+ X" p* r9 l+ y
  4.             if (equal(mat, target)) {
    ) v. S% `; v- }2 ]; O& l, U! f, D& x! _
  5.                 return true;& R3 R" Y; p- |6 j
  6.             }
    + J% _* x: w7 I) j% c
  7.             mat = rotate(mat);
    ; f/ @5 H5 }& @! G
  8.         }
    ! F! N7 `5 B8 ~. s' N! A6 b, p" R
  9.         return false;4 g4 ]6 `2 ]! `
  10.     }
    4 ^# T# i0 Q7 h# x" T
  11. " ]  z0 `2 Z& J
  12.     private int[][] rotate(int[][] mat) {4 X. t: a" }% F5 m9 {6 b
  13.         int[][] r = new int[mat.length][mat[0].length];! c" z- r8 p9 ^  C
  14.         for (int i = 0, y = 0; i < mat.length; i++, y++) {% B3 \4 c" G0 K( W
  15.             for (int j = 0, x = mat.length - 1; j < mat[0].length; j++, x--) {
    7 Z6 R( E& @+ r! d! u) I9 m7 \
  16.                 r[i][j] = mat[x][y];& r2 {/ V! N. N3 Y& `/ e5 v( L) D
  17.             }" w) m7 }  O- S8 m
  18.         }* x% `7 P" l; L5 n) K$ v
  19.         return r;4 ~, ?: G" w) }. D3 m8 @
  20.     }
    8 h- C9 x: q) A% E1 f* y" t
  21. - _. L1 u" O$ l0 j4 G8 M' w4 H# ~5 j& _
  22.     boolean equal(int[][] mat, int[][] target) {
    ! a) q9 t$ f: N# }- r
  23.         for (int i = 0; i < mat.length; i++) {
    1 h& u7 A; ?2 n0 z. Q7 K
  24.             for (int j = 0; j < mat[0].length; j++) {, w9 p! J& ~0 Z0 J  L4 W; A
  25.                 if (mat[i][j] != target[i][j]) {2 H$ t7 S" L7 L# b; |; \$ \$ d5 T
  26.                     return false;
    ! f, P& {* r9 H* b. ^: l! `# b
  27.                 }: D# K4 S& g  f* `9 ?) s; ~
  28.             }
    # x; g+ c; B( m+ W. p1 A
  29.         }
    ! A' s8 w, j2 w9 p8 o
  30.         return true;
    " e" d7 w2 S7 c( h& U2 o0 ^4 X' O
  31.     }
    1 R5 y* `) T* s  X7 r4 J
  32. }
复制代码
上岸算法公开课,毫无保留地将业界面试核心知识免费传授给大家,并配有课前课后习题以及标准答案集以方便大家学习。
长达近30小时的核心课程帮助大家掌握所有面试必备知识,在一个月内有效突破算法面试认知,从而有自信面对FAANG的挑战。
  联系上岸小年糕,领取课件及视频
No.2 使数组元素相等的减少操作次数
解题思路
简单暴力地,从大到小依次处理每个元素即可。使用 TreeMap 的代码非常简洁,或者可以使用链表,速度更快。
代码展示
  1. class Solution {  @' O3 K. D9 l( V! n
  2.     public int reductionOperations(int[] nums) {
    0 x( B5 H( u, P5 ^* _
  3.         TreeMap<Integer, Integer> count = new TreeMap<>();" ^5 L$ V8 i; D- \6 e
  4.         for (var num : nums) {
    7 B- w- y3 G# ]" b! |, Y
  5.             count.put(num, count.getOrDefault(num, 0) + 1);
    % e  a/ C2 b& v8 k
  6.         }
    ) v8 a9 a  }5 s% a
  7.         int result = 0;/ }; `1 F6 c; D9 B$ b4 D
  8.         while (count.size() > 1) {
    3 W9 \7 a" ?( W/ e5 [1 @5 G: N; p
  9.             var largest = count.pollLastEntry();# W7 H. @( P5 z( b7 D7 Q9 [
  10.             var nextLargest = count.lastEntry();( m4 ~- p* A- Y9 I$ N* K) @8 M- b, V0 J
  11.             result += largest.getValue();
    $ ?# z2 y& Y6 y" j' Y
  12.             count.put(nextLargest.getKey(), nextLargest.getValue() + largest.getValue());- p  z! J; B+ a1 u- c# J; t2 e; G8 E
  13.         }5 X: d6 \, y0 T
  14.         return result;5 l0 R2 f6 Y& B9 L0 L$ f$ i" N
  15.     }
    1 |) y& j. V& B: o6 ?* }
  16. }
复制代码
No.3 使二进制字符串字符交替的最少反转次数
解题思路
枚举类型 1 操作执行的次数即可。
执行完类型 1 的操作之后,需要执行的类型 2 的操作次数是固定的。
我们只需要知道奇数下标上 0 和 1 的数量、偶数下标上 0 和 1 的数量就可以计算出类型 2 的操作次数。
每执行一次类型 1 的操作,奇数下标上 0 和 1 的数量、偶数下标上 0 和 1 的数量的变化都可以 O(1) 地计算出来。
代码展示
  1. class Solution {' n& x+ D' D  c2 G. t
  2.     public int minFlips(String s) {# H  |2 `9 f8 e* H# A
  3.         char[] str = s.toCharArray();" T1 c! V5 ?& `! r; }9 }
  4.         // count[0] 表示偶数下标上 0 和 1 的数量  C8 q1 z7 N: f, ~
  5.         // count[1] 表示奇数下标上 0 和 1 的数量3 [, x& u2 d3 N: z* h
  6.         int[][] count = new int[2][2];# _2 {" A9 s: `; w6 o# _
  7.         for (int i = 0; i < str.length; i++) {+ T4 _& |7 `: J' k' ]2 O
  8.             count[i % 2][str[i] - '0']++;. N9 ~% i; K& i% h" y
  9.         }
    ' W3 d( h+ n) @" I. M( R9 j
  10.         int result = Math.min(count[1][1] + count[0][0], count[1][0] + count[0][1]);
    $ v, W- O7 |; a/ \0 ]: k- l2 l6 j
  11.         for (int i = 0; i < str.length - 1; i++) {
    ' s2 m$ F4 w% }$ K2 Y
  12.             count[0][str[i] - '0']--;2 \; E; k6 s2 c% f  h
  13.             int tmp = count[1][0];$ A4 P  i2 ^; e& }2 t" a
  14.             count[1][0] = count[0][0];$ ^) U; y. D1 t0 u+ h/ c
  15.             count[0][0] = tmp;
    $ g* U8 M: O' r& g7 i4 \) {4 S) j
  16.             tmp = count[1][1];& x6 z3 K: W/ N# t  J7 L* p
  17.             count[1][1] = count[0][1];
    1 ?3 G7 i! ?% s1 P7 ^
  18.             count[0][1] = tmp;) Z. }/ e# q. R
  19.             count[(str.length - 1) % 2][str[i] - '0']++;3 Y5 l0 q' a6 n) a% Y
  20.             result = Math.min(result, Math.min(count[1][1] + count[0][0], count[1][0] + count[0][1]));8 w: b$ o2 V) C* b/ p- T$ a
  21.         }  H! v& m$ J9 g
  22.         return result;
      i+ q2 E# v+ X* V# f$ ?1 F
  23.     }3 ~+ n' r, m/ F; t" w! w/ G/ u+ B
  24. }
复制代码
No.4 装包裹的最小浪费空间
解题思路
二分查找。
对所有的包裹和供应商的盒子都排序,然后依次枚举每个供应商即可。
计算一个供应商的盒子的浪费空间时,从小到大使用每种盒子,每种盒子尽可能多装包裹即可,使用前缀和数组和二分查找可以快速计算结果。
代码展示
  1. class Solution {  N+ C6 O" X' u6 J. {0 o5 Z1 V: j
  2.     public int minWastedSpace(int[] packages, int[][] boxes) {
    4 ?6 \1 Z2 G% r: H) E+ {
  3.         Arrays.sort(packages);7 @' {& x7 b, E
  4.         long[] preSum = new long[packages.length];+ H2 D1 M2 d0 ?; W4 c0 j
  5.         preSum[0] = packages[0];0 L  w& a; z/ r
  6.         for (int i = 1; i < preSum.length; i++) {
    ( ?; R# f5 R# L, n2 ~
  7.             preSum[i] = preSum[i - 1] + packages[i];
    ' L. ?( d" {5 ^2 r/ K
  8.         }
    0 g' @" s5 |% r. ]) }8 E* p
  9.         long result = -1;8 e# G) O+ M) n1 B  B8 s! E# e) L6 t
  10.         for (int[] box : boxes) {
    . d; b8 t; n  I
  11.             Arrays.sort(box);( I7 d& v" `- R
  12.             long t = waste(packages, preSum, box);
    6 A& a( H; }4 k
  13.             if (t != -1 && (result == -1 || t < result)) {3 Y0 R/ @) Z* k' ?
  14.                 result = t;
    ! S. Y( \, z5 w0 |0 n
  15.             }
    1 n, ~3 n  V# N# }# B
  16.         }4 ]0 d& p, }8 V1 x0 A
  17.         return (int) (result % 1000000007L);% G5 h0 g# R, o
  18.     }
    / d# [  S& M# V5 G- Q
  19. $ V3 s" T6 n' O3 V3 ^! y* A
  20.     private long waste(int[] packages, long[] preSum, int[] boxes) {
    3 ?: h. ^0 H! }6 ?" E
  21.         int start = 0;% K' E7 I7 V1 K1 b  K7 E! ^. q
  22.         long result = 0;6 ^" r/ _& a' c* A" ^+ J
  23.         for (int box : boxes) {
    ! |% s( v. P, K8 m
  24.             if (box < packages[start]) {  x* k2 @$ a" V) A1 l, @/ g# |' k
  25.                 continue;( {, B- ?9 X, \# i7 _
  26.             }
    ( h4 p/ J" |" W' w0 @; x
  27.             int index = binarySearch(packages, box);
    ( X( L3 T" i2 y* n" M4 Y1 g
  28.             // [start, index] 之间的包裹使用 box 装
    1 d0 S# t# A( \4 y/ }: u
  29.             result += (long) box * (index - start + 1) - preSum[index];
    ! K9 A) B1 C2 a7 r- f3 K5 j
  30.             if (start != 0) {* b% F& c$ D% C# b# q& |& X/ }, {
  31.                 result += preSum[start - 1];
    7 G7 ~. x% H/ w
  32.             }
    5 }* T9 ~$ Y' ^# a+ {
  33.             start = index + 1;
    + D! F+ y+ I2 j7 N' t
  34.             if (start >= packages.length) {) c5 U) }) [/ S, Z7 V# x
  35.                 return result;& ]2 |' x% e) x2 w8 E# v
  36.             }
    ' h7 r+ O$ |6 B, ~" q! b* Q
  37.         }2 V2 j( s: H  [: f$ a" o. W6 O6 l
  38.         return -1;2 r2 P$ E% l6 s
  39.     }
    " U& [$ m$ v& K6 h9 d; j

  40. 6 x$ e. k# J4 S# G( \' Y4 n
  41.     private int binarySearch(int[] arr, int target) {9 r+ w! T1 u8 N5 m% G' y& w/ f5 }
  42.         int l = 0, r = arr.length - 1;
    $ m5 {6 q+ U7 l" c
  43.         while (l + 1 < r) {9 e( W3 g" c, h; Q
  44.             int mid = (l + r) / 2;
    / j- W7 y% m: j" k# F5 O% w
  45.             if (arr[mid] <= target) {
    8 N4 A2 @, w% n& I* X
  46.                 l = mid;
    * }& h" G6 M% ]2 _
  47.             } else {+ J" S. K3 ?- z
  48.                 r = mid;
      {4 ]( r$ t* o0 U
  49.             }6 S. G2 k: n. B" R( v$ K7 O6 a- w
  50.         }, |2 L6 g" e' y3 r. g5 ]' n" }
  51.         return arr[r] <= target ? r : l;. T8 H& v5 r( U) w' ]3 t
  52.     }2 b; h6 }6 n, X& e" @0 }
  53. }
复制代码

- d( y# z' ?0 {2 e3 F) v! d% q' h* M4 D, t

本帖子中包含更多资源

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

x
您需要登录后才可以回帖 登录 | 注册账号

本版积分规则

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