上岸算法 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)) {
   
5.                 return true;
   5 R+ r) Y3 ]7 M3 ^0 Z" q
6.             }
   . D" l7 A1 \* \
7.             mat = rotate(mat);
   
8.         }
   
9.         return false;
   , q# b: g- Y& `. b5 P7 F9 ~* Z5 R' r
10.     }
    9 [7 L$ U" ^* d# }
11. 
    : \! @+ O% R+ e5 b3 e2 h
12.     private int[][] rotate(int[][] mat) {
    
13.         int[][] r = new int[mat.length][mat[0].length];
    1 W0 e. R8 G) i4 E( r
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];
    ; o3 Q0 C! A' T4 F$ J& j% ^$ D2 w- s
17.             }
    & ]) C0 E0 R3 p; [/ ^
18.         }
    
19.         return r;
    
20.     }
    , O, u# E; C9 ^2 f
21. 
    . L* W6 Y1 U# U* j( v, m# `
22.     boolean equal(int[][] mat, int[][] target) {
    1 d2 Q0 ]' G9 w" n! D
23.         for (int i = 0; i < mat.length; i++) {
    ) `. b# R' n' N7 w- g' B
24.             for (int j = 0; j < mat[0].length; j++) {
    
25.                 if (mat[i][j] != target[i][j]) {
    
26.                     return false;
    , P+ q; `' s  d; Q/ q
27.                 }
    ( a$ `7 X: n- V7 I! s
28.             }
    
29.         }
    
30.         return true;
    . \% x& i3 y7 z* J' _0 B7 B
31.     }
    
32. }

复制代码

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

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

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

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

解题思路

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

代码展示

1. class Solution {
   * b1 P7 ~; D( [: z
2.     public int reductionOperations(int[] nums) {
   / }* k- m- J8 J4 v0 x
3.         TreeMap<Integer, Integer> count = new TreeMap<>();
   
4.         for (var num : nums) {
   * o6 f/ Z) g9 c: u& _) x
5.             count.put(num, count.getOrDefault(num, 0) + 1);
   
6.         }
     R; \. X; q4 @
7.         int result = 0;
   : b6 l" U4 ]" r* \& L: D
8.         while (count.size() > 1) {
   , B: t8 k6 v9 F, N/ d# k
9.             var largest = count.pollLastEntry();
   
10.             var nextLargest = count.lastEntry();
    
11.             result += largest.getValue();
    7 j3 c" N* U' H5 F
12.             count.put(nextLargest.getKey(), nextLargest.getValue() + largest.getValue());
    
13.         }
    
14.         return result;
    
15.     }
    
16. }

复制代码

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

解题思路

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

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

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

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

代码展示

1. class Solution {
   : B9 ^1 C; [: P7 Q8 [( k0 B0 r. P
2.     public int minFlips(String s) {
   6 B# @2 |- c% U& h5 f' U* w8 [( z
3.         char[] str = s.toCharArray();
   
4.         // count[0] 表示偶数下标上 0 和 1 的数量
   * f% _/ g: g. R2 R5 h$ Q+ {3 b% L
5.         // count[1] 表示奇数下标上 0 和 1 的数量
   
6.         int[][] count = new int[2][2];
   
7.         for (int i = 0; i < str.length; i++) {
   , l8 o0 C8 {; ]; A  z; j: {
8.             count[i % 2][str[i] - '0']++;
   0 q9 K& Q' [4 U! P$ V( h, q
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']--;
    / s; k9 s1 L1 c' e
13.             int tmp = count[1][0];
    . ~# [3 {9 P  g9 u5 c5 U
14.             count[1][0] = count[0][0];
    
15.             count[0][0] = tmp;
    
16.             tmp = count[1][1];
    * _3 B9 v, N# i  r+ @, a
17.             count[1][1] = count[0][1];
    7 ~3 m9 Q4 ?" u) e# U' v6 S& s
18.             count[0][1] = tmp;
    
19.             count[(str.length - 1) % 2][str[i] - '0']++;
    + @' C, j6 t) L% x* n. e
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 {
   
2.     public int minWastedSpace(int[] packages, int[][] boxes) {
   . i6 W/ t5 E2 N0 ]  f- d
3.         Arrays.sort(packages);
   ; T1 y- O1 }- S3 P% S
4.         long[] preSum = new long[packages.length];
   
5.         preSum[0] = packages[0];
   6 f2 Q+ o" l- p, U, r# G3 d
6.         for (int i = 1; i < preSum.length; i++) {
   5 j0 x: O( B' z. J
7.             preSum[i] = preSum[i - 1] + packages[i];
   : N2 W* m% L2 }( M" O3 u
8.         }
   * W0 q" ~/ ?% v" `) P9 ^
9.         long result = -1;
   
10.         for (int[] box : boxes) {
    ( \) ~& q% l0 Z7 O/ E, e' H% w
11.             Arrays.sort(box);
    
12.             long t = waste(packages, preSum, box);
    
13.             if (t != -1 && (result == -1 || t < result)) {
    3 `8 \' `& N# C4 U6 r8 b
14.                 result = t;
    
15.             }
    
16.         }
    
17.         return (int) (result % 1000000007L);
    
18.     }
    ( D# V0 G8 i- U6 k) |! b
19. 
    
20.     private long waste(int[] packages, long[] preSum, int[] boxes) {
    
21.         int start = 0;
    
22.         long result = 0;
    3 D* f7 o6 C: J9 a" c8 C6 k2 I
23.         for (int box : boxes) {
    
24.             if (box < packages[start]) {
    ( x& Q. q! U. F0 ]. f
25.                 continue;
    * U5 f- z0 u/ }9 f0 l) F% ?: `
26.             }
    4 o' @# X0 a/ y  e# q- X
27.             int index = binarySearch(packages, box);
    
28.             // [start, index] 之间的包裹使用 box 装
    
29.             result += (long) box * (index - start + 1) - preSum[index];
    
30.             if (start != 0) {
    8 `5 t. Z* m* R
31.                 result += preSum[start - 1];
    
32.             }
    6 V) z' }) L) k' q
33.             start = index + 1;
    
34.             if (start >= packages.length) {
    
35.                 return result;
    & c& ^, X( a+ \8 J
36.             }
    
37.         }
    0 [1 F8 s* @9 w* _, v5 A  l, f
38.         return -1;
    
39.     }
    / |2 @' v3 A* P7 Q# @& I6 ^1 R
40. 
    5 t% ]/ L3 s+ `
41.     private int binarySearch(int[] arr, int target) {
    $ e% K! H- {+ f, f' Z' k9 T
42.         int l = 0, r = arr.length - 1;
    
43.         while (l + 1 < r) {
    
44.             int mid = (l + r) / 2;
    
45.             if (arr[mid] <= target) {
    $ T7 M+ _3 K$ p- Z9 ~
46.                 l = mid;
    0 H7 S- ^( L( Q7 f' {0 {
47.             } else {
    ; d# D4 g2 W6 H$ S+ Z& m; S
48.                 r = mid;
    
49.             }
    . Y: w3 v9 \+ h- Z  _& |
50.         }
    
51.         return arr[r] <= target ? r : l;
    ! Z/ x$ q4 Q4 Q2 Q
52.     }
    8 ^- [1 R5 J$ l) G% l% R
53. }

复制代码

$ n# y2 D1 `+ s4 N