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

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

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

UWCSSA提醒您:

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

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

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

No.1判断矩阵经轮转后是否一致
解题思路
模拟矩阵的旋转即可。
代码展示
  1. class Solution {; G5 v' O! s$ l0 X( B0 k. y( h$ G4 J
  2.     public boolean findRotation(int[][] mat, int[][] target) {% Q+ w0 N3 t1 y9 L% O( G
  3.         for (int i = 0; i < 4; i++) {( a+ M2 N( X+ S- [' d4 x3 r
  4.             if (equal(mat, target)) {
    # a7 T  s3 i6 K( H( p' k
  5.                 return true;9 d3 a2 }, A4 ~+ S1 }: X% a. P3 G* v
  6.             }
    0 s( W9 }: b7 J2 @
  7.             mat = rotate(mat);
    : n" n& M. }( I- R0 R1 v) G+ Q
  8.         }. ]  d2 O! Y. z: R/ W" x  S
  9.         return false;
    / q8 H6 u6 F% B* @. m
  10.     }6 j; C+ k0 |* P. K% |! I3 ~
  11. / |: y. W- O* Q1 }9 V3 A/ y
  12.     private int[][] rotate(int[][] mat) {8 a' P! \- Q$ F( M
  13.         int[][] r = new int[mat.length][mat[0].length];) A* d, v; I- D. j% k
  14.         for (int i = 0, y = 0; i < mat.length; i++, y++) {, A3 y% q$ i, u  _5 Y
  15.             for (int j = 0, x = mat.length - 1; j < mat[0].length; j++, x--) {
    : `+ J- L* D  D& R* Y
  16.                 r[i][j] = mat[x][y];
    ) H5 z/ B/ f" f! d1 f) C' e9 @
  17.             }" V9 k% D' J- B. p; s7 E% t+ @
  18.         }3 ^8 ^6 ?! j2 H0 o
  19.         return r;4 W2 \+ w- B% F$ p/ x( _9 Q0 m
  20.     }
    4 W; _4 @- p' |  b' S4 C
  21. 7 @% z8 b8 E) M; R
  22.     boolean equal(int[][] mat, int[][] target) {
    ! B, i3 ?5 e- m1 W# I
  23.         for (int i = 0; i < mat.length; i++) {
    5 C1 q2 m$ m8 k  K, k1 t
  24.             for (int j = 0; j < mat[0].length; j++) {+ F" S0 _6 {5 _  S2 I
  25.                 if (mat[i][j] != target[i][j]) {/ A2 P4 R8 Q3 K& F; q
  26.                     return false;
    * g: x! m0 K( d' \+ i
  27.                 }
    ' {  q: ?$ {0 N1 C- T( ]
  28.             }
    ( }* n! A; v! E' ~; a
  29.         }
    3 P/ g, W* a0 I5 S* A) @. N0 q$ p, }
  30.         return true;, r$ C5 X; p" Q: x
  31.     }
      m/ C$ F8 J7 _: ]+ a* o& [
  32. }
复制代码
上岸算法公开课,毫无保留地将业界面试核心知识免费传授给大家,并配有课前课后习题以及标准答案集以方便大家学习。
长达近30小时的核心课程帮助大家掌握所有面试必备知识,在一个月内有效突破算法面试认知,从而有自信面对FAANG的挑战。
  联系上岸小年糕,领取课件及视频
No.2 使数组元素相等的减少操作次数
解题思路
简单暴力地,从大到小依次处理每个元素即可。使用 TreeMap 的代码非常简洁,或者可以使用链表,速度更快。
代码展示
  1. class Solution {
    ) p6 r$ l6 q6 v6 ?! g
  2.     public int reductionOperations(int[] nums) {# Q4 J8 a  B3 \: F6 L1 j/ L: Q
  3.         TreeMap<Integer, Integer> count = new TreeMap<>();. X1 a; \$ }! U% g
  4.         for (var num : nums) {& G: N% P* ~' L% ]& z
  5.             count.put(num, count.getOrDefault(num, 0) + 1);
    / A4 \" a0 e: H2 V0 d
  6.         }  f7 o5 o! D8 A& w& ^) c
  7.         int result = 0;/ h, r+ ?) f' V0 G% y1 w) \
  8.         while (count.size() > 1) {) K0 [/ ]' p  j9 |6 l
  9.             var largest = count.pollLastEntry();2 L9 P8 H; [% Q. t2 ]5 @
  10.             var nextLargest = count.lastEntry();; g" j/ O# Q3 d# z) p) @
  11.             result += largest.getValue();/ v8 p# Y1 i# K$ R! i. c
  12.             count.put(nextLargest.getKey(), nextLargest.getValue() + largest.getValue());
    ' i; p3 I5 }: A: T* R
  13.         }
    , K. h. z: ^- d) h. C! d
  14.         return result;" a9 L4 a' [5 @8 n
  15.     }
    8 X6 h5 r6 z; k  ]" i) }
  16. }
复制代码
No.3 使二进制字符串字符交替的最少反转次数
解题思路
枚举类型 1 操作执行的次数即可。
执行完类型 1 的操作之后,需要执行的类型 2 的操作次数是固定的。
我们只需要知道奇数下标上 0 和 1 的数量、偶数下标上 0 和 1 的数量就可以计算出类型 2 的操作次数。
每执行一次类型 1 的操作,奇数下标上 0 和 1 的数量、偶数下标上 0 和 1 的数量的变化都可以 O(1) 地计算出来。
代码展示
  1. class Solution {
    / ^( r9 p" t2 }/ k2 N( \+ X6 L
  2.     public int minFlips(String s) {( ]6 q6 K0 s4 Z# m
  3.         char[] str = s.toCharArray();5 |1 p5 x& }* l9 _& ~3 |5 g0 n' V
  4.         // count[0] 表示偶数下标上 0 和 1 的数量3 n. k6 ^2 A8 p1 `
  5.         // count[1] 表示奇数下标上 0 和 1 的数量
    - v, s* T0 \0 t. a0 Q/ R
  6.         int[][] count = new int[2][2];  Z2 @( g# `" U0 q; H* I; j; g
  7.         for (int i = 0; i < str.length; i++) {
    - K  x8 {2 O$ j0 h
  8.             count[i % 2][str[i] - '0']++;1 x9 a- J1 \, W2 M+ H! N/ t- f; L0 D
  9.         }
    # V; o" u0 W) W5 Z# `0 J2 c( g* S4 |  H
  10.         int result = Math.min(count[1][1] + count[0][0], count[1][0] + count[0][1]);7 S) O. S' l- v8 Q" e
  11.         for (int i = 0; i < str.length - 1; i++) {& h( ?% S. U  \( K
  12.             count[0][str[i] - '0']--;
    # a4 z/ p7 [4 a: H/ r' H: ?
  13.             int tmp = count[1][0];0 M% ^/ H1 N2 ?& L. j8 {
  14.             count[1][0] = count[0][0];# n. M, E: K7 }, l0 d# T' |* p) w
  15.             count[0][0] = tmp;
    " \- M* `4 S: _8 X" F& K. r
  16.             tmp = count[1][1];) ^! z" s# k) P6 i
  17.             count[1][1] = count[0][1];% A! J$ N' }* t4 v
  18.             count[0][1] = tmp;- N5 d+ G8 v( S( ]5 w* H+ j
  19.             count[(str.length - 1) % 2][str[i] - '0']++;# X2 E* ^$ l6 t! q" p$ B
  20.             result = Math.min(result, Math.min(count[1][1] + count[0][0], count[1][0] + count[0][1]));; Y* ?5 }1 V: C
  21.         }
    6 h2 y+ w1 L- D6 }
  22.         return result;
    5 ?5 y$ x$ c4 I8 ?  s( s% V
  23.     }
    6 K! r7 j! f  }) e" F! U; n' g$ ]
  24. }
复制代码
No.4 装包裹的最小浪费空间
解题思路
二分查找。
对所有的包裹和供应商的盒子都排序,然后依次枚举每个供应商即可。
计算一个供应商的盒子的浪费空间时,从小到大使用每种盒子,每种盒子尽可能多装包裹即可,使用前缀和数组和二分查找可以快速计算结果。
代码展示
  1. class Solution {1 f2 K+ \, K  B; ^, q" r+ z
  2.     public int minWastedSpace(int[] packages, int[][] boxes) {" f; M" M) ~* c; J+ |2 a
  3.         Arrays.sort(packages);
    , j: e/ [6 p6 G! E( }! G7 g- [) D
  4.         long[] preSum = new long[packages.length];) x' u6 G1 a5 c# K# y9 f
  5.         preSum[0] = packages[0];* Z3 P, ]* R; d* X+ D
  6.         for (int i = 1; i < preSum.length; i++) {
    8 K! x) x: ~, l
  7.             preSum[i] = preSum[i - 1] + packages[i];' k+ d* _6 |. U  n. P
  8.         }# g- x# Y7 D  P$ m3 r
  9.         long result = -1;2 u5 Z3 a/ t7 F: S" [/ u9 G$ H
  10.         for (int[] box : boxes) {% l1 ]* r' _1 h& E
  11.             Arrays.sort(box);
    4 M9 p, d2 E" k8 z
  12.             long t = waste(packages, preSum, box);' ~8 y5 E/ f' I4 ^& P' A
  13.             if (t != -1 && (result == -1 || t < result)) {
    # T  f+ i- ~: B1 x% J' e
  14.                 result = t;
    9 B' x/ o, A: z* J
  15.             }
    ( x% e+ Q+ A2 o) ]" N% ~
  16.         }! |$ E* b0 F% t% [
  17.         return (int) (result % 1000000007L);, S+ c+ [- ~/ ~4 A# Z( v% O
  18.     }
    ' _( a  t3 h- w5 |1 q9 `+ s
  19. / z1 P) Z) x& J
  20.     private long waste(int[] packages, long[] preSum, int[] boxes) {1 M# {: U( @4 U0 c5 W3 j  }
  21.         int start = 0;; [8 o0 D; K9 E9 g* g4 e) G
  22.         long result = 0;3 I7 N) j  V. q. J! f  U! u
  23.         for (int box : boxes) {
    1 K" J" g, J% D9 f* X/ n7 Q, C( j
  24.             if (box < packages[start]) {
    5 m' B" r/ U- j: i7 l+ a
  25.                 continue;
    + m# i" V/ @9 z* L7 ^
  26.             }4 P7 D' T# u  H. q8 N; m5 _
  27.             int index = binarySearch(packages, box);
    ; h/ N8 N: ~. j( \1 j. [8 O
  28.             // [start, index] 之间的包裹使用 box 装9 T; x" y9 M0 N6 r
  29.             result += (long) box * (index - start + 1) - preSum[index];$ }# L2 V) h4 }1 u5 A+ }% y, q- r
  30.             if (start != 0) {( J' H/ H4 h" }) {
  31.                 result += preSum[start - 1];
    2 {; `4 e$ C' S
  32.             }
    ) z9 G8 Z6 M- ?+ Z
  33.             start = index + 1;
    . R' T( c- R% p2 c9 c4 |8 T8 Y
  34.             if (start >= packages.length) {
    ( C  Q4 M+ |1 z+ O' l
  35.                 return result;$ h3 C/ [/ F: y. T
  36.             }% Z# N+ b1 Y: h7 l5 Y' g4 |
  37.         }8 f  b% P  }( Q" g5 D2 T' X" w
  38.         return -1;; ^5 U! \9 t3 Y& ]/ X% `
  39.     }( X0 ], g! S8 }) \- v

  40. / Y% O5 R, v1 l! k0 N
  41.     private int binarySearch(int[] arr, int target) {+ ]5 P& K8 I! t% q" m7 [
  42.         int l = 0, r = arr.length - 1;
    ! P! n( K( S+ O9 F: d7 [& E
  43.         while (l + 1 < r) {. e& L  q1 S5 V0 b2 \; y
  44.             int mid = (l + r) / 2;$ o- J( q, L; Y" J& h$ Q
  45.             if (arr[mid] <= target) {
      y2 F6 v# M4 c' E3 b
  46.                 l = mid;$ x8 y0 a) y9 T+ q+ @5 |
  47.             } else {: J' \- q1 H5 t% }8 `
  48.                 r = mid;# r. ?, V* S4 t  ]. o
  49.             }  i1 Q. D! o2 Z% s$ k
  50.         }
    ) _( u& Z7 o0 k
  51.         return arr[r] <= target ? r : l;
    6 S5 N  k  J& s. @# C% }
  52.     }2 ^/ z- G2 B" s4 K" ]5 k
  53. }
复制代码
6 R3 \! {8 Q+ g0 R7 h& B
3 U, I) ?- K/ E# w

本帖子中包含更多资源

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

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

本版积分规则

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