上岸算法 I LeetCode Weekly Contest 244解题报告

No.1判断矩阵经轮转后是否一致

解题思路

模拟矩阵的旋转即可。

代码展示

1. class Solution {
   ( _4 n0 @* M3 ]0 f0 K* B$ e
2.     public boolean findRotation(int[][] mat, int[][] target) {
   
3.         for (int i = 0; i < 4; i++) {
   
4.             if (equal(mat, target)) {
     A. y* i8 c2 F$ N& s
5.                 return true;
   
6.             }
   
7.             mat = rotate(mat);
   7 x; t! \" t4 Q
8.         }
   : S/ U0 L$ B0 l% p6 @, A
9.         return false;
   
10.     }
    7 z/ M6 {2 g3 _
11. 
    $ }7 }  H) D# Z, u. c
12.     private int[][] rotate(int[][] mat) {
    ; M4 V' g0 g) ?3 p
13.         int[][] r = new int[mat.length][mat[0].length];
    
14.         for (int i = 0, y = 0; i < mat.length; i++, y++) {
    
15.             for (int j = 0, x = mat.length - 1; j < mat[0].length; j++, x--) {
    
16.                 r[i][j] = mat[x][y];
    5 }' D7 U  D* Z6 J
17.             }
    
18.         }
    
19.         return r;
    / `, g+ H$ n: V: e3 \
20.     }
    
21. 
    3 z% J4 H) r8 [
22.     boolean equal(int[][] mat, int[][] target) {
    - k( t0 F6 o' |  g5 ~7 N* g
23.         for (int i = 0; i < mat.length; i++) {
    6 z) S3 |9 m& z7 J; b: F) o2 m
24.             for (int j = 0; j < mat[0].length; j++) {
    
25.                 if (mat[i][j] != target[i][j]) {
    
26.                     return false;
    " ~6 h) G6 Z1 n9 Y. f" r
27.                 }
    : q# \  y8 }/ c$ h9 E
28.             }
    3 ~) E1 e: U3 h0 T% R5 _+ ?, E
29.         }
    
30.         return true;
    ) j* P& `6 M8 r# e7 z
31.     }
    
32. }

复制代码

上岸算法公开课，毫无保留地将业界面试核心知识免费传授给大家，并配有课前课后习题以及标准答案集以方便大家学习。

长达近30小时的核心课程帮助大家掌握所有面试必备知识，在一个月内有效突破算法面试认知，从而有自信面对FAANG的挑战。

  联系上岸小年糕，领取课件及视频

No.2 使数组元素相等的减少操作次数

解题思路

简单暴力地，从大到小依次处理每个元素即可。使用 TreeMap 的代码非常简洁，或者可以使用链表，速度更快。

代码展示

1. class Solution {
   
2.     public int reductionOperations(int[] nums) {
   
3.         TreeMap<Integer, Integer> count = new TreeMap<>();
   2 t$ z1 ~& ^2 \
4.         for (var num : nums) {
   $ g6 {6 a& X4 J* c; a+ H
5.             count.put(num, count.getOrDefault(num, 0) + 1);
   
6.         }
   ! i; q) c3 Q0 z& L5 U2 P
7.         int result = 0;
   ; ^% x" O  O" J
8.         while (count.size() > 1) {
   0 T. x3 n* ]8 Q6 `6 v# |7 _
9.             var largest = count.pollLastEntry();
   
10.             var nextLargest = count.lastEntry();
    7 r6 T; e3 O. ^# X; j
11.             result += largest.getValue();
    " z( p) L3 u0 v7 K
12.             count.put(nextLargest.getKey(), nextLargest.getValue() + largest.getValue());
    
13.         }
    / m' |: o1 \5 o3 _9 n" t
14.         return result;
    4 ]4 D3 x5 }7 O" Y% _: ?9 O
15.     }
    
16. }

复制代码

No.3 使二进制字符串字符交替的最少反转次数

解题思路

枚举类型 1 操作执行的次数即可。

执行完类型 1 的操作之后，需要执行的类型 2 的操作次数是固定的。

我们只需要知道奇数下标上 0 和 1 的数量、偶数下标上 0 和 1 的数量就可以计算出类型 2 的操作次数。

每执行一次类型 1 的操作，奇数下标上 0 和 1 的数量、偶数下标上 0 和 1 的数量的变化都可以 O(1) 地计算出来。

代码展示

1. class Solution {
   ! c( q$ N0 m. Q  \# [
2.     public int minFlips(String s) {
   
3.         char[] str = s.toCharArray();
   % q5 y8 J0 e( m5 a7 P; a  O
4.         // count[0] 表示偶数下标上 0 和 1 的数量
   : z' c/ C! K( G; z% c
5.         // count[1] 表示奇数下标上 0 和 1 的数量
   / l2 d6 A; c  w, D4 g) V7 q6 W1 A# e
6.         int[][] count = new int[2][2];
   
7.         for (int i = 0; i < str.length; i++) {
   
8.             count[i % 2][str[i] - '0']++;
   " D% z$ M2 `2 P9 M
9.         }
   
10.         int result = Math.min(count[1][1] + count[0][0], count[1][0] + count[0][1]);
    
11.         for (int i = 0; i < str.length - 1; i++) {
    5 s, Q3 C1 S4 }% [: w$ P# B# Y
12.             count[0][str[i] - '0']--;
    ) a7 x9 I/ i# j" U* Q
13.             int tmp = count[1][0];
    * G  t: _# }' r6 J' ^
14.             count[1][0] = count[0][0];
    
15.             count[0][0] = tmp;
    % U- k- x$ F& L7 ]/ N* O% K
16.             tmp = count[1][1];
    
17.             count[1][1] = count[0][1];
    
18.             count[0][1] = tmp;
    : j8 f' J# A0 T0 P* g
19.             count[(str.length - 1) % 2][str[i] - '0']++;
    / ~1 R, |2 e' c2 N  `' }+ {# ?
20.             result = Math.min(result, Math.min(count[1][1] + count[0][0], count[1][0] + count[0][1]));
    
21.         }
    
22.         return result;
    
23.     }
    
24. }

复制代码

No.4 装包裹的最小浪费空间

解题思路

二分查找。

对所有的包裹和供应商的盒子都排序，然后依次枚举每个供应商即可。

计算一个供应商的盒子的浪费空间时，从小到大使用每种盒子，每种盒子尽可能多装包裹即可，使用前缀和数组和二分查找可以快速计算结果。

代码展示

1. class Solution {
   2 V0 E" s' b* v8 M" [5 x0 s/ }
2.     public int minWastedSpace(int[] packages, int[][] boxes) {
   
3.         Arrays.sort(packages);
   1 z. e8 s! L4 U) Y4 d  z3 G
4.         long[] preSum = new long[packages.length];
   5 p! ?# V& ?0 V  d2 {* p( z
5.         preSum[0] = packages[0];
   8 D! C' f* w4 ?' d9 R& R
6.         for (int i = 1; i < preSum.length; i++) {
   
7.             preSum[i] = preSum[i - 1] + packages[i];
   3 X+ @; f# e% v' c" ~" n
8.         }
   
9.         long result = -1;
   8 V4 u$ u" q9 n4 h' b; f
10.         for (int[] box : boxes) {
    7 s% t6 ]  |; k' B, l
11.             Arrays.sort(box);
    2 U) J1 o1 b, {1 V+ I0 e+ B
12.             long t = waste(packages, preSum, box);
    - L% x! k: m  Y7 o" X
13.             if (t != -1 && (result == -1 || t < result)) {
    
14.                 result = t;
    
15.             }
    
16.         }
    
17.         return (int) (result % 1000000007L);
    
18.     }
    : h( t* K" H1 o8 a6 [
19. 
    1 G7 p- M& C. ]2 @3 T/ J
20.     private long waste(int[] packages, long[] preSum, int[] boxes) {
    
21.         int start = 0;
    
22.         long result = 0;
    $ o* Z& \/ L9 e1 b" U  }- ]) G
23.         for (int box : boxes) {
    
24.             if (box < packages[start]) {
    2 _3 S& a8 U$ t" |
25.                 continue;
    # B8 U5 Y" j) v4 v/ |
26.             }
    / ?( @" Y$ l% }! p2 f
27.             int index = binarySearch(packages, box);
    
28.             // [start, index] 之间的包裹使用 box 装
    3 x( B; P& y9 k3 S9 v! ]
29.             result += (long) box * (index - start + 1) - preSum[index];
    
30.             if (start != 0) {
    
31.                 result += preSum[start - 1];
    ; Y: f+ x- j5 \0 Z3 d8 X' O
32.             }
    
33.             start = index + 1;
    
34.             if (start >= packages.length) {
    9 f/ H& K1 K! _" Y  n0 [; _% W
35.                 return result;
    9 h1 b8 X' ]  N' K. i' @
36.             }
    * S) e$ n2 K  _4 R2 b( _- [' N3 v" l
37.         }
    : H& Q' L2 n) P0 K$ q/ V! S
38.         return -1;
    ! \% V3 L' K, n# Y
39.     }
    8 S. E' ^0 @2 u
40. 
    
41.     private int binarySearch(int[] arr, int target) {
    
42.         int l = 0, r = arr.length - 1;
    1 X: \, N2 R2 g7 s' Y" B
43.         while (l + 1 < r) {
    ; {4 [4 J" g3 g5 o: \. u7 Q2 S, K
44.             int mid = (l + r) / 2;
    & y8 h/ W; K5 }, Q
45.             if (arr[mid] <= target) {
    " y5 w; [, n* c2 {$ @5 g
46.                 l = mid;
    9 m( ^9 E6 R2 J* M
47.             } else {
    
48.                 r = mid;
    
49.             }
    
50.         }
    ) k6 U- w9 D+ Z! F1 m" g$ Z; ?
51.         return arr[r] <= target ? r : l;
    2 A9 j/ |0 x# J$ q
52.     }
    
53. }

复制代码

$ M# t: X+ a* u& }& F1 T/ S