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

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

解题思路

模拟矩阵的旋转即可。

代码展示

1. class Solution {
   ) D% \. a& {. s/ f) a6 S
2.     public boolean findRotation(int[][] mat, int[][] target) {
   
3.         for (int i = 0; i < 4; i++) {
   ( `( B( ?; N# x
4.             if (equal(mat, target)) {
   & S2 i6 o4 S$ G6 v# g
5.                 return true;
   . x5 ?; c' M7 M3 M6 X: D5 ~
6.             }
   
7.             mat = rotate(mat);
   ' b6 e# U& T* l
8.         }
   
9.         return false;
   
10.     }
    ; L7 s, \7 n! R
11. 
    
12.     private int[][] rotate(int[][] mat) {
    - @  I* M) ]" o* T, `4 J
13.         int[][] r = new int[mat.length][mat[0].length];
    5 Q# W4 d  S  |, X
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--) {
    1 d# s/ R, Q5 X$ Z2 Z! t: V
16.                 r[i][j] = mat[x][y];
    ; \% B( v& A3 \% l4 r8 K
17.             }
    
18.         }
    
19.         return r;
    5 N1 ]  F( l( t4 {1 C# v% B
20.     }
    
21. 
    + O% F8 G7 S! z
22.     boolean equal(int[][] mat, int[][] target) {
    
23.         for (int i = 0; i < mat.length; i++) {
    
24.             for (int j = 0; j < mat[0].length; j++) {
    : L. `5 _3 p& k# i, K& J- e  J7 K# O
25.                 if (mat[i][j] != target[i][j]) {
    
26.                     return false;
    
27.                 }
    
28.             }
    0 f0 Y' ^! A* R6 ?" H5 v
29.         }
    6 u8 o2 B- \- m4 j. C
30.         return true;
    
31.     }
    0 _0 u9 \: K5 \! J
32. }

复制代码

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

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

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

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

解题思路

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

代码展示

1. class Solution {
   ! w2 ^- s0 I, N" r
2.     public int reductionOperations(int[] nums) {
   1 i/ M% i& {$ G5 T: V0 `
3.         TreeMap<Integer, Integer> count = new TreeMap<>();
   3 M! D( G; M# i! k% `7 x. O$ W
4.         for (var num : nums) {
   / K8 A( F  C  l+ E2 j
5.             count.put(num, count.getOrDefault(num, 0) + 1);
   9 s+ S  l$ R: @6 f! f% K0 R8 m" e
6.         }
   : O# x( P1 o( V; `; i- Y" @6 X1 Z
7.         int result = 0;
   ' F7 v' i# i+ B
8.         while (count.size() > 1) {
   
9.             var largest = count.pollLastEntry();
   
10.             var nextLargest = count.lastEntry();
    
11.             result += largest.getValue();
    
12.             count.put(nextLargest.getKey(), nextLargest.getValue() + largest.getValue());
    
13.         }
    # q8 _& W. ]6 f0 Z2 G& R* N" Y9 k
14.         return result;
    ( y' y/ z1 B4 }% I: c3 c5 r3 t2 {2 Q
15.     }
    ) V) u8 D  \) `8 D
16. }

复制代码

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

解题思路

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

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

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

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

代码展示

1. class Solution {
   ; H( O5 j- {+ v8 A$ E$ `
2.     public int minFlips(String s) {
   5 ~& X6 b( y  ~2 p! Z4 f( \1 E- }
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++) {
   4 G7 @! L* d) L# A; P- _* z/ x# {( h
8.             count[i % 2][str[i] - '0']++;
   
9.         }
   9 Y9 I: S9 C% m4 X% U4 ]
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];
    % g+ Q1 p8 W* o; b% v
14.             count[1][0] = count[0][0];
    . X5 i; g; |# U
15.             count[0][0] = tmp;
    
16.             tmp = count[1][1];
    $ J6 [1 A: D5 R+ W4 s/ \  y) @
17.             count[1][1] = count[0][1];
    7 d: M& J) U+ ~- S, f- e
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;
    
23.     }
    
24. }

复制代码

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

解题思路

二分查找。

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

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

代码展示

1. class Solution {
   ' n" K9 t% F% n' _0 v* q+ k
2.     public int minWastedSpace(int[] packages, int[][] boxes) {
   . _+ N4 A/ l7 d
3.         Arrays.sort(packages);
   7 C& U! ?7 v1 K/ w$ p! z
4.         long[] preSum = new long[packages.length];
   
5.         preSum[0] = packages[0];
   4 {" m& [4 H1 `$ V9 P
6.         for (int i = 1; i < preSum.length; i++) {
   
7.             preSum[i] = preSum[i - 1] + packages[i];
   1 b# L1 |2 Y( K
8.         }
   2 r: L4 v9 d7 p( G# O* P+ p6 P
9.         long result = -1;
   
10.         for (int[] box : boxes) {
    
11.             Arrays.sort(box);
    
12.             long t = waste(packages, preSum, box);
    
13.             if (t != -1 && (result == -1 || t < result)) {
    
14.                 result = t;
    
15.             }
    
16.         }
    1 L6 r. U% w! Z% K  V1 D/ K
17.         return (int) (result % 1000000007L);
    ) J0 j) i3 r* }4 O2 k
18.     }
    4 C. g/ k/ i$ P
19. 
    
20.     private long waste(int[] packages, long[] preSum, int[] boxes) {
    
21.         int start = 0;
    7 r; n$ J6 }, `6 l: b& R) R
22.         long result = 0;
    / Z2 x: ?4 D$ J: F
23.         for (int box : boxes) {
    ' O$ n( D$ V5 O9 j+ ^- C
24.             if (box < packages[start]) {
    
25.                 continue;
    - u; x! [0 h9 X! P2 B% `1 r% f* X
26.             }
    
27.             int index = binarySearch(packages, box);
    * i9 D: m( C! }$ I1 m
28.             // [start, index] 之间的包裹使用 box 装
    & s5 {1 l( P. ]( R: w% [3 _) A
29.             result += (long) box * (index - start + 1) - preSum[index];
    ( [; @9 m9 c% m7 ~/ c4 V/ b% S$ J/ f
30.             if (start != 0) {
    * N! w# X. w# G* Z( R5 g, T
31.                 result += preSum[start - 1];
    
32.             }
      P4 G  z, K0 V" t) U, h/ x
33.             start = index + 1;
    
34.             if (start >= packages.length) {
    
35.                 return result;
    
36.             }
    
37.         }
    
38.         return -1;
    2 p/ @  R3 V+ k1 Y
39.     }
    2 r+ Y$ A/ ]5 c
40. 
    
41.     private int binarySearch(int[] arr, int target) {
    " W' ?" |7 G# q; f" o5 f: Y7 U& V8 O! C
42.         int l = 0, r = arr.length - 1;
    
43.         while (l + 1 < r) {
    
44.             int mid = (l + r) / 2;
    
45.             if (arr[mid] <= target) {
    8 D) @+ A' ~  ?+ d" y, T- H
46.                 l = mid;
    $ h% @1 v/ Z  E. c! b# }  I
47.             } else {
      I4 Z( r* ^! ?7 A# E
48.                 r = mid;
    
49.             }
    " J/ v6 N% q1 ?$ _
50.         }
    $ F- r/ ~0 I1 a# b0 F0 V
51.         return arr[r] <= target ? r : l;
    7 i6 h3 G# `: y# T
52.     }
    4 Z1 L/ H& F: o+ K* V
53. }

复制代码

# C$ {! M8 E1 I. J