上岸算法 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 m3 t& i% v3 i. v1 c
4.             if (equal(mat, target)) {
   3 C) F) l; ]& e/ s8 P- W
5.                 return true;
   3 c3 O& B( Q. m# h: Z) A
6.             }
     Q, s2 x3 U. y0 k6 z$ Z
7.             mat = rotate(mat);
   ! \) V; B& c4 P/ R9 o7 _) D8 ?) B+ l
8.         }
     |" V6 {  a! f) S( {. }% ^2 [  b
9.         return false;
   ( b# i# |6 x& S$ |
10.     }
    
11. 
    
12.     private int[][] rotate(int[][] mat) {
    7 f0 G# p- P* V  E5 z; |6 u
13.         int[][] r = new int[mat.length][mat[0].length];
    
14.         for (int i = 0, y = 0; i < mat.length; i++, y++) {
    # w0 [: C# v! v! H4 b7 I, b4 u
15.             for (int j = 0, x = mat.length - 1; j < mat[0].length; j++, x--) {
    ; \% E1 R# k" Z
16.                 r[i][j] = mat[x][y];
    
17.             }
    ( h; o! y, Z* f/ j, U7 R  a) Q+ F, q
18.         }
    0 J) H1 x* s+ Q; b  M1 V; r
19.         return r;
    
20.     }
    ( \: A) S; `( M8 U1 I
21. 
    
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++) {
    
25.                 if (mat[i][j] != target[i][j]) {
    
26.                     return false;
    
27.                 }
      U! P( V  k) N" K
28.             }
    
29.         }
    ( k$ v* G: X0 B3 L+ M, ]2 ?8 k8 }
30.         return true;
    ) e4 x  ~2 |2 k* P( z
31.     }
    
32. }

复制代码

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

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

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

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

解题思路

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

代码展示

1. class Solution {
   
2.     public int reductionOperations(int[] nums) {
   
3.         TreeMap<Integer, Integer> count = new TreeMap<>();
   
4.         for (var num : nums) {
     F3 z; n# v% z
5.             count.put(num, count.getOrDefault(num, 0) + 1);
   
6.         }
   
7.         int result = 0;
   4 e3 i& r# ^6 ?/ y* N, o5 p
8.         while (count.size() > 1) {
   
9.             var largest = count.pollLastEntry();
   
10.             var nextLargest = count.lastEntry();
    % W2 q1 h% R: V7 J5 Z% Z+ Y8 D7 i# y( R) g
11.             result += largest.getValue();
    ) p0 m( ], a8 h4 [! O3 y
12.             count.put(nextLargest.getKey(), nextLargest.getValue() + largest.getValue());
    & g* \3 _/ t" h" K! [  q* z
13.         }
    
14.         return result;
    " c- h, V3 ~4 H+ A2 m' \
15.     }
    
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();
   * c7 ~( K! S3 U0 w7 j: ^. J
4.         // count[0] 表示偶数下标上 0 和 1 的数量
   
5.         // count[1] 表示奇数下标上 0 和 1 的数量
   % ~% B3 I* K" h4 G! D; o: J
6.         int[][] count = new int[2][2];
   
7.         for (int i = 0; i < str.length; i++) {
   0 U* T1 B1 {8 X# O3 ~
8.             count[i % 2][str[i] - '0']++;
   
9.         }
   # q7 {2 a! c! D+ ?( e. c
10.         int result = Math.min(count[1][1] + count[0][0], count[1][0] + count[0][1]);
    ' U9 o( ^) g/ d* i0 c
11.         for (int i = 0; i < str.length - 1; i++) {
    # w9 z" N9 H- C2 f( c7 Q
12.             count[0][str[i] - '0']--;
    
13.             int tmp = count[1][0];
    : ^4 h7 h. O& V0 X0 n9 I
14.             count[1][0] = count[0][0];
    
15.             count[0][0] = tmp;
    
16.             tmp = count[1][1];
    ! j, K/ ^, j6 @
17.             count[1][1] = count[0][1];
    
18.             count[0][1] = tmp;
    
19.             count[(str.length - 1) % 2][str[i] - '0']++;
    4 Q4 H8 g' i6 M) T$ @# s! d
20.             result = Math.min(result, Math.min(count[1][1] + count[0][0], count[1][0] + count[0][1]));
    - H' Y" _/ [* H7 \: j; N9 A
21.         }
    # g" l, k! W1 _9 x1 P/ D& x
22.         return result;
    # n  v5 I1 E! I$ @& W
23.     }
    
24. }

复制代码

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

解题思路

二分查找。

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

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

代码展示

1. class Solution {
   8 W% J! H2 l  w0 Z
2.     public int minWastedSpace(int[] packages, int[][] boxes) {
   
3.         Arrays.sort(packages);
   
4.         long[] preSum = new long[packages.length];
   ) p7 K) o, U2 V+ G% Q
5.         preSum[0] = packages[0];
   
6.         for (int i = 1; i < preSum.length; i++) {
   0 Z. d  r: a/ `# g
7.             preSum[i] = preSum[i - 1] + packages[i];
   
8.         }
   , V/ m% t# {* Z1 O0 L4 n5 ]
9.         long result = -1;
   
10.         for (int[] box : boxes) {
    
11.             Arrays.sort(box);
    2 G7 P& q3 F5 y0 u8 e/ T, S- G' @4 O
12.             long t = waste(packages, preSum, box);
    
13.             if (t != -1 && (result == -1 || t < result)) {
    2 R& {- E5 c. h% c0 @
14.                 result = t;
    
15.             }
    , W- u3 d( d, }& [
16.         }
    
17.         return (int) (result % 1000000007L);
    
18.     }
    - G: U0 ]/ v2 j* g7 j
19. 
    
20.     private long waste(int[] packages, long[] preSum, int[] boxes) {
    % S! P$ G6 T9 P& N; H3 O6 V! H1 w
21.         int start = 0;
    
22.         long result = 0;
    * u, ?1 F! y0 w6 w- d% o1 q
23.         for (int box : boxes) {
    
24.             if (box < packages[start]) {
    
25.                 continue;
    
26.             }
    
27.             int index = binarySearch(packages, box);
    
28.             // [start, index] 之间的包裹使用 box 装
    
29.             result += (long) box * (index - start + 1) - preSum[index];
    $ `8 S4 q  R( D1 a* U
30.             if (start != 0) {
    ' B. p+ b3 _  T3 p' R+ V/ I8 i
31.                 result += preSum[start - 1];
    + E1 ~7 d4 l8 I- M
32.             }
    
33.             start = index + 1;
    
34.             if (start >= packages.length) {
    9 E( U2 p' g& S, H
35.                 return result;
    
36.             }
    
37.         }
    
38.         return -1;
    4 [6 b2 B* t$ h* k
39.     }
    
40. 
    9 I3 C" J9 M) T
41.     private int binarySearch(int[] arr, int target) {
    1 I8 N2 |- ?9 E  z: e
42.         int l = 0, r = arr.length - 1;
    + Z+ T1 R! z( Z
43.         while (l + 1 < r) {
    
44.             int mid = (l + r) / 2;
    
45.             if (arr[mid] <= target) {
    8 N4 @. {( a' h; ?9 g
46.                 l = mid;
    
47.             } else {
    % d/ n8 r- G) O% l, x
48.                 r = mid;
    . q7 B# H5 R. P; Y( ^. H# X% ?& Q# P
49.             }
    
50.         }
    
51.         return arr[r] <= target ? r : l;
    + C& i0 S8 P; m& d
52.     }
    , g) R- l1 `5 i2 g1 }
53. }

复制代码

' k7 J3 R  L2 ^' N, h8 Z