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

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

解题思路

模拟矩阵的旋转即可。

代码展示

1. class Solution {
     b. c  g2 |' @$ E$ o4 Z0 P+ G. Z
2.     public boolean findRotation(int[][] mat, int[][] target) {
   3 {/ j- p# o% i
3.         for (int i = 0; i < 4; i++) {
   / F9 u& [' d0 S# j! P$ g" c# T
4.             if (equal(mat, target)) {
   
5.                 return true;
   
6.             }
   ( |) r5 I4 z" J8 E3 l
7.             mat = rotate(mat);
   ; W% V0 w% i( Q, T* p- R  r
8.         }
   
9.         return false;
   9 e9 D# f) ~4 U0 h/ _* T0 l
10.     }
    . n: V$ Z% l% K6 R% c+ b5 y
11. 
    
12.     private int[][] rotate(int[][] mat) {
    
13.         int[][] r = new int[mat.length][mat[0].length];
    4 K! _2 _* [2 R0 d
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];
    
17.             }
    
18.         }
    8 Q$ s3 c" a% g. Q# o# D* N* o
19.         return r;
    " p6 [0 b8 A4 Y1 s, W
20.     }
    9 b* w: Q% N4 O! S
21. 
    , v- U2 p) c! a5 X3 d; F0 y
22.     boolean equal(int[][] mat, int[][] target) {
      a) k$ A4 I3 e2 u+ z# U# H
23.         for (int i = 0; i < mat.length; i++) {
    % {- Z) p( p0 V8 T% z3 w9 r7 V
24.             for (int j = 0; j < mat[0].length; j++) {
    
25.                 if (mat[i][j] != target[i][j]) {
    + {. z2 S& A& j$ C; u0 n: V% i
26.                     return false;
    ) R8 W8 n% i. B
27.                 }
    + o9 W: N  o* A! \
28.             }
    
29.         }
    
30.         return true;
    * N( |, P4 {8 _
31.     }
    & a- n% g4 Y% m
32. }

复制代码

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

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

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

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

解题思路

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

代码展示

1. class Solution {
   1 Y0 E4 [3 y* V9 H1 |9 n" g4 ?
2.     public int reductionOperations(int[] nums) {
   : n; Z+ z. [* y
3.         TreeMap<Integer, Integer> count = new TreeMap<>();
   8 T+ {/ v4 {0 R; U) L
4.         for (var num : nums) {
   / E% h; ?* f$ Z3 F
5.             count.put(num, count.getOrDefault(num, 0) + 1);
     x- `" N: i4 r
6.         }
   
7.         int result = 0;
   . ]4 [  P) T2 M8 O' O, @' \
8.         while (count.size() > 1) {
   6 ]5 r# a6 d% n  M2 I* V3 d
9.             var largest = count.pollLastEntry();
   
10.             var nextLargest = count.lastEntry();
    ) V5 o  Z- w, F& H
11.             result += largest.getValue();
    0 @9 t; [) H$ g  |2 R" G& B7 q" T
12.             count.put(nextLargest.getKey(), nextLargest.getValue() + largest.getValue());
    $ `; E6 V& d* Q
13.         }
    
14.         return result;
    / r( F* [0 G! |- C% R' H
15.     }
    
16. }

复制代码

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

解题思路

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

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

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

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

代码展示

1. class Solution {
   0 ?4 F8 @8 r* w
2.     public int minFlips(String s) {
   . Z5 I1 ?6 ~* y  u' ~( z
3.         char[] str = s.toCharArray();
   + V1 t1 k) @6 i. I: Y6 u, k
4.         // count[0] 表示偶数下标上 0 和 1 的数量
   - A9 M; C* M6 Z8 T6 f. u% L
5.         // count[1] 表示奇数下标上 0 和 1 的数量
   
6.         int[][] count = new int[2][2];
   7 W3 T$ g: D/ ]& U
7.         for (int i = 0; i < str.length; i++) {
   3 T9 \1 z2 _% o; T: J
8.             count[i % 2][str[i] - '0']++;
   & f( F3 a; O6 E* \/ f, t
9.         }
   ( W$ w8 c9 N+ a8 n
10.         int result = Math.min(count[1][1] + count[0][0], count[1][0] + count[0][1]);
    * A+ O3 t' C- F4 S* J7 s2 Q6 H; n
11.         for (int i = 0; i < str.length - 1; i++) {
    
12.             count[0][str[i] - '0']--;
    . Z2 f2 `; ~8 M; T' Y
13.             int tmp = count[1][0];
    , f8 f8 _9 v; `5 \
14.             count[1][0] = count[0][0];
    
15.             count[0][0] = tmp;
    
16.             tmp = count[1][1];
    4 X  R' O# Q" J
17.             count[1][1] = count[0][1];
    
18.             count[0][1] = tmp;
    ( F. C3 ^+ k" ~
19.             count[(str.length - 1) % 2][str[i] - '0']++;
    6 S, c, d, m" r7 l
20.             result = Math.min(result, Math.min(count[1][1] + count[0][0], count[1][0] + count[0][1]));
    $ x" e( a. G7 j% f8 r1 r
21.         }
    
22.         return result;
    
23.     }
    5 v* t* o( c" _# i1 b. S
24. }

复制代码

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

解题思路

二分查找。

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

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

代码展示

1. class Solution {
     M; M5 l0 u! u$ F$ T9 G
2.     public int minWastedSpace(int[] packages, int[][] boxes) {
   
3.         Arrays.sort(packages);
   
4.         long[] preSum = new long[packages.length];
   * [+ ^1 `5 x+ }% m0 W
5.         preSum[0] = packages[0];
   6 |. f' H3 z  |8 d
6.         for (int i = 1; i < preSum.length; i++) {
   
7.             preSum[i] = preSum[i - 1] + packages[i];
   
8.         }
   
9.         long result = -1;
   
10.         for (int[] box : boxes) {
    6 _. S" ~7 M4 [- @9 u1 i  u
11.             Arrays.sort(box);
    ) J, b7 _$ u0 C
12.             long t = waste(packages, preSum, box);
    ) R; q) M& i8 p% F# _
13.             if (t != -1 && (result == -1 || t < result)) {
    
14.                 result = t;
    
15.             }
    
16.         }
    2 h5 y4 t" H! V# K- o5 O$ [- B
17.         return (int) (result % 1000000007L);
    # `, }+ _& ?& b8 P. t" S- S! g
18.     }
    ! `$ r& M5 t3 ~% M
19. 
    
20.     private long waste(int[] packages, long[] preSum, int[] boxes) {
    
21.         int start = 0;
      y! n: z/ o$ ]( p/ L# A
22.         long result = 0;
    % i6 A4 N: t' H% {& @
23.         for (int box : boxes) {
    
24.             if (box < packages[start]) {
    1 M$ p; y% E+ a( z7 W8 |
25.                 continue;
    
26.             }
    
27.             int index = binarySearch(packages, box);
    
28.             // [start, index] 之间的包裹使用 box 装
    
29.             result += (long) box * (index - start + 1) - preSum[index];
    
30.             if (start != 0) {
    ! S4 B# W* ~2 T6 X" R
31.                 result += preSum[start - 1];
    
32.             }
    
33.             start = index + 1;
    
34.             if (start >= packages.length) {
    
35.                 return result;
    
36.             }
    
37.         }
    ( d3 W. }  q9 `9 M, Q' E
38.         return -1;
    
39.     }
    
40. 
    - t: ]1 s7 o% ~8 f, u
41.     private int binarySearch(int[] arr, int target) {
    
42.         int l = 0, r = arr.length - 1;
    
43.         while (l + 1 < r) {
    
44.             int mid = (l + r) / 2;
    2 s" H6 I! U2 J
45.             if (arr[mid] <= target) {
    
46.                 l = mid;
    
47.             } else {
    6 p0 k9 L$ F' f3 a5 ]
48.                 r = mid;
    
49.             }
    ; X" T; w6 m/ D4 m/ X4 l
50.         }
    ( }/ C8 t  h0 e7 ]& ]7 e' B* z
51.         return arr[r] <= target ? r : l;
    ! l+ B8 Q* j+ w; n( c
52.     }
    & i2 U. U& E9 g& n; ~# h
53. }

复制代码