No.1判断矩阵经轮转后是否一致 解题思路 模拟矩阵的旋转即可。 代码展示 - class Solution {
: M6 q, X' d$ u. B+ S2 _ - public boolean findRotation(int[][] mat, int[][] target) {
9 i' r0 z' P& {) C0 E) M9 n - for (int i = 0; i < 4; i++) {) V4 W+ X" p* r9 l+ y
- if (equal(mat, target)) {
) v. S% `; v- }2 ]; O& l, U! f, D& x! _ - return true;& R3 R" Y; p- |6 j
- }
+ J% _* x: w7 I) j% c - mat = rotate(mat);
; f/ @5 H5 }& @! G - }
! F! N7 `5 B8 ~. s' N! A6 b, p" R - return false;4 g4 ]6 `2 ]! `
- }
4 ^# T# i0 Q7 h# x" T - " ] z0 `2 Z& J
- private int[][] rotate(int[][] mat) {4 X. t: a" }% F5 m9 {6 b
- int[][] r = new int[mat.length][mat[0].length];! c" z- r8 p9 ^ C
- for (int i = 0, y = 0; i < mat.length; i++, y++) {% B3 \4 c" G0 K( W
- for (int j = 0, x = mat.length - 1; j < mat[0].length; j++, x--) {
7 Z6 R( E& @+ r! d! u) I9 m7 \ - r[i][j] = mat[x][y];& r2 {/ V! N. N3 Y& `/ e5 v( L) D
- }" w) m7 } O- S8 m
- }* x% `7 P" l; L5 n) K$ v
- return r;4 ~, ?: G" w) }. D3 m8 @
- }
8 h- C9 x: q) A% E1 f* y" t - - _. L1 u" O$ l0 j4 G8 M' w4 H# ~5 j& _
- boolean equal(int[][] mat, int[][] target) {
! a) q9 t$ f: N# }- r - for (int i = 0; i < mat.length; i++) {
1 h& u7 A; ?2 n0 z. Q7 K - for (int j = 0; j < mat[0].length; j++) {, w9 p! J& ~0 Z0 J L4 W; A
- if (mat[i][j] != target[i][j]) {2 H$ t7 S" L7 L# b; |; \$ \$ d5 T
- return false;
! f, P& {* r9 H* b. ^: l! `# b - }: D# K4 S& g f* `9 ?) s; ~
- }
# x; g+ c; B( m+ W. p1 A - }
! A' s8 w, j2 w9 p8 o - return true;
" e" d7 w2 S7 c( h& U2 o0 ^4 X' O - }
1 R5 y* `) T* s X7 r4 J - }
复制代码上岸算法公开课,毫无保留地将业界面试核心知识免费传授给大家,并配有课前课后习题以及标准答案集以方便大家学习。 长达近30小时的核心课程帮助大家掌握所有面试必备知识,在一个月内有效突破算法面试认知,从而有自信面对FAANG的挑战。 联系上岸小年糕,领取课件及视频 No.2 使数组元素相等的减少操作次数 解题思路 简单暴力地,从大到小依次处理每个元素即可。使用 TreeMap 的代码非常简洁,或者可以使用链表,速度更快。 代码展示 - class Solution { @' O3 K. D9 l( V! n
- public int reductionOperations(int[] nums) {
0 x( B5 H( u, P5 ^* _ - TreeMap<Integer, Integer> count = new TreeMap<>();" ^5 L$ V8 i; D- \6 e
- for (var num : nums) {
7 B- w- y3 G# ]" b! |, Y - count.put(num, count.getOrDefault(num, 0) + 1);
% e a/ C2 b& v8 k - }
) v8 a9 a }5 s% a - int result = 0;/ }; `1 F6 c; D9 B$ b4 D
- while (count.size() > 1) {
3 W9 \7 a" ?( W/ e5 [1 @5 G: N; p - var largest = count.pollLastEntry();# W7 H. @( P5 z( b7 D7 Q9 [
- var nextLargest = count.lastEntry();( m4 ~- p* A- Y9 I$ N* K) @8 M- b, V0 J
- result += largest.getValue();
$ ?# z2 y& Y6 y" j' Y - count.put(nextLargest.getKey(), nextLargest.getValue() + largest.getValue());- p z! J; B+ a1 u- c# J; t2 e; G8 E
- }5 X: d6 \, y0 T
- return result;5 l0 R2 f6 Y& B9 L0 L$ f$ i" N
- }
1 |) y& j. V& B: o6 ?* } - }
复制代码No.3 使二进制字符串字符交替的最少反转次数 解题思路 枚举类型 1 操作执行的次数即可。 执行完类型 1 的操作之后,需要执行的类型 2 的操作次数是固定的。 我们只需要知道奇数下标上 0 和 1 的数量、偶数下标上 0 和 1 的数量就可以计算出类型 2 的操作次数。 每执行一次类型 1 的操作,奇数下标上 0 和 1 的数量、偶数下标上 0 和 1 的数量的变化都可以 O(1) 地计算出来。 代码展示 - class Solution {' n& x+ D' D c2 G. t
- public int minFlips(String s) {# H |2 `9 f8 e* H# A
- char[] str = s.toCharArray();" T1 c! V5 ?& `! r; }9 }
- // count[0] 表示偶数下标上 0 和 1 的数量 C8 q1 z7 N: f, ~
- // count[1] 表示奇数下标上 0 和 1 的数量3 [, x& u2 d3 N: z* h
- int[][] count = new int[2][2];# _2 {" A9 s: `; w6 o# _
- for (int i = 0; i < str.length; i++) {+ T4 _& |7 `: J' k' ]2 O
- count[i % 2][str[i] - '0']++;. N9 ~% i; K& i% h" y
- }
' W3 d( h+ n) @" I. M( R9 j - 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 - for (int i = 0; i < str.length - 1; i++) {
' s2 m$ F4 w% }$ K2 Y - count[0][str[i] - '0']--;2 \; E; k6 s2 c% f h
- int tmp = count[1][0];$ A4 P i2 ^; e& }2 t" a
- count[1][0] = count[0][0];$ ^) U; y. D1 t0 u+ h/ c
- count[0][0] = tmp;
$ g* U8 M: O' r& g7 i4 \) {4 S) j - tmp = count[1][1];& x6 z3 K: W/ N# t J7 L* p
- count[1][1] = count[0][1];
1 ?3 G7 i! ?% s1 P7 ^ - count[0][1] = tmp;) Z. }/ e# q. R
- count[(str.length - 1) % 2][str[i] - '0']++;3 Y5 l0 q' a6 n) a% Y
- result = Math.min(result, Math.min(count[1][1] + count[0][0], count[1][0] + count[0][1]));8 w: b$ o2 V) C* b/ p- T$ a
- } H! v& m$ J9 g
- return result;
i+ q2 E# v+ X* V# f$ ?1 F - }3 ~+ n' r, m/ F; t" w! w/ G/ u+ B
- }
复制代码No.4 装包裹的最小浪费空间 解题思路 二分查找。 对所有的包裹和供应商的盒子都排序,然后依次枚举每个供应商即可。 计算一个供应商的盒子的浪费空间时,从小到大使用每种盒子,每种盒子尽可能多装包裹即可,使用前缀和数组和二分查找可以快速计算结果。 代码展示 - class Solution { N+ C6 O" X' u6 J. {0 o5 Z1 V: j
- public int minWastedSpace(int[] packages, int[][] boxes) {
4 ?6 \1 Z2 G% r: H) E+ { - Arrays.sort(packages);7 @' {& x7 b, E
- long[] preSum = new long[packages.length];+ H2 D1 M2 d0 ?; W4 c0 j
- preSum[0] = packages[0];0 L w& a; z/ r
- for (int i = 1; i < preSum.length; i++) {
( ?; R# f5 R# L, n2 ~ - preSum[i] = preSum[i - 1] + packages[i];
' L. ?( d" {5 ^2 r/ K - }
0 g' @" s5 |% r. ]) }8 E* p - long result = -1;8 e# G) O+ M) n1 B B8 s! E# e) L6 t
- for (int[] box : boxes) {
. d; b8 t; n I - Arrays.sort(box);( I7 d& v" `- R
- long t = waste(packages, preSum, box);
6 A& a( H; }4 k - if (t != -1 && (result == -1 || t < result)) {3 Y0 R/ @) Z* k' ?
- result = t;
! S. Y( \, z5 w0 |0 n - }
1 n, ~3 n V# N# }# B - }4 ]0 d& p, }8 V1 x0 A
- return (int) (result % 1000000007L);% G5 h0 g# R, o
- }
/ d# [ S& M# V5 G- Q - $ V3 s" T6 n' O3 V3 ^! y* A
- private long waste(int[] packages, long[] preSum, int[] boxes) {
3 ?: h. ^0 H! }6 ?" E - int start = 0;% K' E7 I7 V1 K1 b K7 E! ^. q
- long result = 0;6 ^" r/ _& a' c* A" ^+ J
- for (int box : boxes) {
! |% s( v. P, K8 m - if (box < packages[start]) { x* k2 @$ a" V) A1 l, @/ g# |' k
- continue;( {, B- ?9 X, \# i7 _
- }
( h4 p/ J" |" W' w0 @; x - int index = binarySearch(packages, box);
( X( L3 T" i2 y* n" M4 Y1 g - // [start, index] 之间的包裹使用 box 装
1 d0 S# t# A( \4 y/ }: u - result += (long) box * (index - start + 1) - preSum[index];
! K9 A) B1 C2 a7 r- f3 K5 j - if (start != 0) {* b% F& c$ D% C# b# q& |& X/ }, {
- result += preSum[start - 1];
7 G7 ~. x% H/ w - }
5 }* T9 ~$ Y' ^# a+ { - start = index + 1;
+ D! F+ y+ I2 j7 N' t - if (start >= packages.length) {) c5 U) }) [/ S, Z7 V# x
- return result;& ]2 |' x% e) x2 w8 E# v
- }
' h7 r+ O$ |6 B, ~" q! b* Q - }2 V2 j( s: H [: f$ a" o. W6 O6 l
- return -1;2 r2 P$ E% l6 s
- }
" U& [$ m$ v& K6 h9 d; j
6 x$ e. k# J4 S# G( \' Y4 n- private int binarySearch(int[] arr, int target) {9 r+ w! T1 u8 N5 m% G' y& w/ f5 }
- int l = 0, r = arr.length - 1;
$ m5 {6 q+ U7 l" c - while (l + 1 < r) {9 e( W3 g" c, h; Q
- int mid = (l + r) / 2;
/ j- W7 y% m: j" k# F5 O% w - if (arr[mid] <= target) {
8 N4 A2 @, w% n& I* X - l = mid;
* }& h" G6 M% ]2 _ - } else {+ J" S. K3 ?- z
- r = mid;
{4 ]( r$ t* o0 U - }6 S. G2 k: n. B" R( v$ K7 O6 a- w
- }, |2 L6 g" e' y3 r. g5 ]' n" }
- return arr[r] <= target ? r : l;. T8 H& v5 r( U) w' ]3 t
- }2 b; h6 }6 n, X& e" @0 }
- }
复制代码
- d( y# z' ?0 {2 e3 F) v! d% q' h* M4 D, t
|