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

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++) {
   
4.             if (equal(mat, target)) {
   ) v. S% `; v- }2 ]; O& l, U! f, D& x! _
5.                 return true;
   
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;
   
10.     }
    4 ^# T# i0 Q7 h# x" T
11. 
    
12.     private int[][] rotate(int[][] mat) {
    
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--) {
    7 Z6 R( E& @+ r! d! u) I9 m7 \
16.                 r[i][j] = mat[x][y];
    
17.             }
    
18.         }
    
19.         return r;
    
20.     }
    8 h- C9 x: q) A% E1 f* y" t
21. 
    
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++) {
    
25.                 if (mat[i][j] != target[i][j]) {
    
26.                     return false;
    ! f, P& {* r9 H* b. ^: l! `# b
27.                 }
    
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 {
   
2.     public int reductionOperations(int[] nums) {
   0 x( B5 H( u, P5 ^* _
3.         TreeMap<Integer, Integer> count = new TreeMap<>();
   
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;
   
8.         while (count.size() > 1) {
   3 W9 \7 a" ?( W/ e5 [1 @5 G: N; p
9.             var largest = count.pollLastEntry();
   
10.             var nextLargest = count.lastEntry();
    
11.             result += largest.getValue();
    $ ?# z2 y& Y6 y" j' Y
12.             count.put(nextLargest.getKey(), nextLargest.getValue() + largest.getValue());
    
13.         }
    
14.         return result;
    
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 {
   
2.     public int minFlips(String s) {
   
3.         char[] str = s.toCharArray();
   
4.         // count[0] 表示偶数下标上 0 和 1 的数量
   
5.         // count[1] 表示奇数下标上 0 和 1 的数量
   
6.         int[][] count = new int[2][2];
   
7.         for (int i = 0; i < str.length; i++) {
   
8.             count[i % 2][str[i] - '0']++;
   
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']--;
    
13.             int tmp = count[1][0];
    
14.             count[1][0] = count[0][0];
    
15.             count[0][0] = tmp;
    $ g* U8 M: O' r& g7 i4 \) {4 S) j
16.             tmp = count[1][1];
    
17.             count[1][1] = count[0][1];
    1 ?3 G7 i! ?% s1 P7 ^
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.         }
    
22.         return result;
      i+ q2 E# v+ X* V# f$ ?1 F
23.     }
    
24. }

复制代码

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

解题思路

二分查找。

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

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

代码展示

1. class Solution {
   
2.     public int minWastedSpace(int[] packages, int[][] boxes) {
   4 ?6 \1 Z2 G% r: H) E+ {
3.         Arrays.sort(packages);
   
4.         long[] preSum = new long[packages.length];
   
5.         preSum[0] = packages[0];
   
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;
   
10.         for (int[] box : boxes) {
    . d; b8 t; n  I
11.             Arrays.sort(box);
    
12.             long t = waste(packages, preSum, box);
    6 A& a( H; }4 k
13.             if (t != -1 && (result == -1 || t < result)) {
    
14.                 result = t;
    ! S. Y( \, z5 w0 |0 n
15.             }
    1 n, ~3 n  V# N# }# B
16.         }
    
17.         return (int) (result % 1000000007L);
    
18.     }
    / d# [  S& M# V5 G- Q
19. 
    
20.     private long waste(int[] packages, long[] preSum, int[] boxes) {
    3 ?: h. ^0 H! }6 ?" E
21.         int start = 0;
    
22.         long result = 0;
    
23.         for (int box : boxes) {
    ! |% s( v. P, K8 m
24.             if (box < packages[start]) {
    
25.                 continue;
    
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) {
    
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) {
    
35.                 return result;
    
36.             }
    ' h7 r+ O$ |6 B, ~" q! b* Q
37.         }
    
38.         return -1;
    
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) {
    
42.         int l = 0, r = arr.length - 1;
    $ m5 {6 q+ U7 l" c
43.         while (l + 1 < r) {
    
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 {
    
48.                 r = mid;
      {4 ]( r$ t* o0 U
49.             }
    
50.         }
    
51.         return arr[r] <= target ? r : l;
    
52.     }
    
53. }

复制代码

- d( y# z' ?0 {2 e3 F) v! d