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

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

解题思路

模拟矩阵的旋转即可。

代码展示

1. class Solution {
   
2.     public boolean findRotation(int[][] mat, int[][] target) {
   
3.         for (int i = 0; i < 4; i++) {
   
4.             if (equal(mat, target)) {
   & d/ h& L8 q9 C& i, K' a; S9 _5 b
5.                 return true;
   5 H( B# E) m0 N  }3 U
6.             }
   ( ?- s' M. j" G4 ?4 Q- w5 R# T2 B* X
7.             mat = rotate(mat);
   
8.         }
   
9.         return false;
   
10.     }
    ( w) Q; x) L  L# l8 d' n( A- H
11. 
    
12.     private int[][] rotate(int[][] mat) {
    ; m; T+ x& ?8 W5 r8 G/ T3 q
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--) {
    # ?0 t  y6 D2 m
16.                 r[i][j] = mat[x][y];
    1 c" o4 Q" u/ Z# E
17.             }
    
18.         }
    $ M' P" C9 C5 H% a/ v
19.         return r;
    ( \7 M5 t; ^' i/ c1 F8 q
20.     }
    
21. 
    + m1 J) ]( r7 G
22.     boolean equal(int[][] mat, int[][] target) {
    . x5 l) I4 D0 r  \
23.         for (int i = 0; i < mat.length; i++) {
    
24.             for (int j = 0; j < mat[0].length; j++) {
    : x5 h& k6 c8 s+ B; q  j0 _
25.                 if (mat[i][j] != target[i][j]) {
    
26.                     return false;
    
27.                 }
    # `: ]( p; ^- z5 [" n
28.             }
    
29.         }
    $ m5 Z; s/ v' f. {% a; d
30.         return true;
    
31.     }
    6 h% h& T6 r  U* g
32. }

复制代码

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

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

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

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

解题思路

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

代码展示

1. class Solution {
   / d) L. W. [+ N* ]% _# k' ]$ {
2.     public int reductionOperations(int[] nums) {
   
3.         TreeMap<Integer, Integer> count = new TreeMap<>();
   
4.         for (var num : nums) {
   0 n3 A- T- d5 U+ H( R
5.             count.put(num, count.getOrDefault(num, 0) + 1);
   1 a8 T7 f3 ]$ V+ J2 b5 L9 L* N( b  e
6.         }
     ^* c) s) A) ^' n: N" i' P
7.         int result = 0;
   7 R0 A& z! i2 C8 h
8.         while (count.size() > 1) {
   . A# t8 @6 H% ]1 a- m; B9 ^
9.             var largest = count.pollLastEntry();
   
10.             var nextLargest = count.lastEntry();
    
11.             result += largest.getValue();
    / F4 P" m% M( `3 P" C$ W
12.             count.put(nextLargest.getKey(), nextLargest.getValue() + largest.getValue());
    ' {3 d% @2 T1 I# X% f; i. E
13.         }
    
14.         return result;
    , I+ d4 C& g1 T: f! g
15.     }
    4 C, ^( t! F& S
16. }

复制代码

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

解题思路

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

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

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

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

代码展示

1. class Solution {
   
2.     public int minFlips(String s) {
   ( {5 J' `3 w! w" v. g9 U
3.         char[] str = s.toCharArray();
   - O7 w2 p! f, S- D! n3 R; [
4.         // count[0] 表示偶数下标上 0 和 1 的数量
   
5.         // count[1] 表示奇数下标上 0 和 1 的数量
   0 h, m  v5 q  t( {4 h- W- G/ U/ A5 @
6.         int[][] count = new int[2][2];
   
7.         for (int i = 0; i < str.length; i++) {
   
8.             count[i % 2][str[i] - '0']++;
   ' _5 }8 o" ?0 ~( y
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++) {
    
12.             count[0][str[i] - '0']--;
    
13.             int tmp = count[1][0];
    * b- s7 C4 G4 u2 N2 {; a" u3 k
14.             count[1][0] = count[0][0];
    
15.             count[0][0] = tmp;
    
16.             tmp = count[1][1];
    
17.             count[1][1] = count[0][1];
    
18.             count[0][1] = tmp;
    
19.             count[(str.length - 1) % 2][str[i] - '0']++;
    
20.             result = Math.min(result, Math.min(count[1][1] + count[0][0], count[1][0] + count[0][1]));
    
21.         }
    ' }' |9 l" M: O+ x9 ?( t9 z
22.         return result;
    ) `# j- \7 V; s' N
23.     }
    
24. }

复制代码

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

解题思路

二分查找。

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

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

代码展示

1. class Solution {
   0 m8 R& R. G+ B
2.     public int minWastedSpace(int[] packages, int[][] boxes) {
   / O3 \2 ?6 j4 _8 s( V
3.         Arrays.sort(packages);
   # ~% i' s. p% N) D" e( w
4.         long[] preSum = new long[packages.length];
   
5.         preSum[0] = packages[0];
     ^( H. y0 X" G! ^8 |, s' S; Z
6.         for (int i = 1; i < preSum.length; i++) {
   
7.             preSum[i] = preSum[i - 1] + packages[i];
   
8.         }
   
9.         long result = -1;
   5 V) x  p+ s# p' H' ^% k: G: W
10.         for (int[] box : boxes) {
    
11.             Arrays.sort(box);
    
12.             long t = waste(packages, preSum, box);
    ! b6 z7 C5 [* |- f9 o' ^
13.             if (t != -1 && (result == -1 || t < result)) {
    
14.                 result = t;
    
15.             }
    
16.         }
    
17.         return (int) (result % 1000000007L);
    7 d. a. L& B3 z: r/ r9 u- }3 n
18.     }
    $ a' e5 z* s* j$ ?
19. 
    
20.     private long waste(int[] packages, long[] preSum, int[] boxes) {
    
21.         int start = 0;
    1 ?. E# O4 U- M% s- ~+ ^" X4 S
22.         long result = 0;
    - |0 e; e: ]6 z8 `
23.         for (int box : boxes) {
    
24.             if (box < packages[start]) {
    
25.                 continue;
    
26.             }
    9 W, U$ i$ i$ s' x
27.             int index = binarySearch(packages, box);
    " k/ e$ i8 w- k5 p( }/ K% }( l
28.             // [start, index] 之间的包裹使用 box 装
    
29.             result += (long) box * (index - start + 1) - preSum[index];
    
30.             if (start != 0) {
    4 y2 I  w7 J% k! H
31.                 result += preSum[start - 1];
    
32.             }
    # Q4 |* @7 k1 }3 e; C+ `2 K' Z
33.             start = index + 1;
    4 \* ?) Y) U' V
34.             if (start >= packages.length) {
    
35.                 return result;
    
36.             }
    4 {( E% e+ ]  a/ o2 e3 s3 L6 v
37.         }
    . }$ j4 m* o' I/ s! E% t) N2 r
38.         return -1;
    
39.     }
    
40. 
    
41.     private int binarySearch(int[] arr, int target) {
    
42.         int l = 0, r = arr.length - 1;
    ( |2 t+ X% r( A8 A5 I- O7 c
43.         while (l + 1 < r) {
    ( y+ @! V! {2 g
44.             int mid = (l + r) / 2;
    2 O9 J* [' U: `) z3 U
45.             if (arr[mid] <= target) {
    ! R% i# ^+ B6 h; {
46.                 l = mid;
    
47.             } else {
    
48.                 r = mid;
    " V+ q  g% G. {% `2 y8 j9 V
49.             }
    4 \, \- }( {5 W
50.         }
    
51.         return arr[r] <= target ? r : l;
    2 M/ s* h' r* F6 M* J+ o" w) k
52.     }
    
53. }

复制代码