No.1判断矩阵经轮转后是否一致 解题思路 模拟矩阵的旋转即可。 代码展示 - class Solution {; G5 v' O! s$ l0 X( B0 k. y( h$ G4 J
- public boolean findRotation(int[][] mat, int[][] target) {% Q+ w0 N3 t1 y9 L% O( G
- for (int i = 0; i < 4; i++) {( a+ M2 N( X+ S- [' d4 x3 r
- if (equal(mat, target)) {
# a7 T s3 i6 K( H( p' k - return true;9 d3 a2 }, A4 ~+ S1 }: X% a. P3 G* v
- }
0 s( W9 }: b7 J2 @ - mat = rotate(mat);
: n" n& M. }( I- R0 R1 v) G+ Q - }. ] d2 O! Y. z: R/ W" x S
- return false;
/ q8 H6 u6 F% B* @. m - }6 j; C+ k0 |* P. K% |! I3 ~
- / |: y. W- O* Q1 }9 V3 A/ y
- private int[][] rotate(int[][] mat) {8 a' P! \- Q$ F( M
- int[][] r = new int[mat.length][mat[0].length];) A* d, v; I- D. j% k
- for (int i = 0, y = 0; i < mat.length; i++, y++) {, A3 y% q$ i, u _5 Y
- for (int j = 0, x = mat.length - 1; j < mat[0].length; j++, x--) {
: `+ J- L* D D& R* Y - r[i][j] = mat[x][y];
) H5 z/ B/ f" f! d1 f) C' e9 @ - }" V9 k% D' J- B. p; s7 E% t+ @
- }3 ^8 ^6 ?! j2 H0 o
- return r;4 W2 \+ w- B% F$ p/ x( _9 Q0 m
- }
4 W; _4 @- p' | b' S4 C - 7 @% z8 b8 E) M; R
- boolean equal(int[][] mat, int[][] target) {
! B, i3 ?5 e- m1 W# I - for (int i = 0; i < mat.length; i++) {
5 C1 q2 m$ m8 k K, k1 t - for (int j = 0; j < mat[0].length; j++) {+ F" S0 _6 {5 _ S2 I
- if (mat[i][j] != target[i][j]) {/ A2 P4 R8 Q3 K& F; q
- return false;
* g: x! m0 K( d' \+ i - }
' { q: ?$ {0 N1 C- T( ] - }
( }* n! A; v! E' ~; a - }
3 P/ g, W* a0 I5 S* A) @. N0 q$ p, } - return true;, r$ C5 X; p" Q: x
- }
m/ C$ F8 J7 _: ]+ a* o& [ - }
复制代码上岸算法公开课,毫无保留地将业界面试核心知识免费传授给大家,并配有课前课后习题以及标准答案集以方便大家学习。 长达近30小时的核心课程帮助大家掌握所有面试必备知识,在一个月内有效突破算法面试认知,从而有自信面对FAANG的挑战。 联系上岸小年糕,领取课件及视频 No.2 使数组元素相等的减少操作次数 解题思路 简单暴力地,从大到小依次处理每个元素即可。使用 TreeMap 的代码非常简洁,或者可以使用链表,速度更快。 代码展示 - class Solution {
) p6 r$ l6 q6 v6 ?! g - public int reductionOperations(int[] nums) {# Q4 J8 a B3 \: F6 L1 j/ L: Q
- TreeMap<Integer, Integer> count = new TreeMap<>();. X1 a; \$ }! U% g
- for (var num : nums) {& G: N% P* ~' L% ]& z
- count.put(num, count.getOrDefault(num, 0) + 1);
/ A4 \" a0 e: H2 V0 d - } f7 o5 o! D8 A& w& ^) c
- int result = 0;/ h, r+ ?) f' V0 G% y1 w) \
- while (count.size() > 1) {) K0 [/ ]' p j9 |6 l
- var largest = count.pollLastEntry();2 L9 P8 H; [% Q. t2 ]5 @
- var nextLargest = count.lastEntry();; g" j/ O# Q3 d# z) p) @
- result += largest.getValue();/ v8 p# Y1 i# K$ R! i. c
- count.put(nextLargest.getKey(), nextLargest.getValue() + largest.getValue());
' i; p3 I5 }: A: T* R - }
, K. h. z: ^- d) h. C! d - return result;" a9 L4 a' [5 @8 n
- }
8 X6 h5 r6 z; k ]" i) } - }
复制代码No.3 使二进制字符串字符交替的最少反转次数 解题思路 枚举类型 1 操作执行的次数即可。 执行完类型 1 的操作之后,需要执行的类型 2 的操作次数是固定的。 我们只需要知道奇数下标上 0 和 1 的数量、偶数下标上 0 和 1 的数量就可以计算出类型 2 的操作次数。 每执行一次类型 1 的操作,奇数下标上 0 和 1 的数量、偶数下标上 0 和 1 的数量的变化都可以 O(1) 地计算出来。 代码展示 - class Solution {
/ ^( r9 p" t2 }/ k2 N( \+ X6 L - public int minFlips(String s) {( ]6 q6 K0 s4 Z# m
- char[] str = s.toCharArray();5 |1 p5 x& }* l9 _& ~3 |5 g0 n' V
- // count[0] 表示偶数下标上 0 和 1 的数量3 n. k6 ^2 A8 p1 `
- // count[1] 表示奇数下标上 0 和 1 的数量
- v, s* T0 \0 t. a0 Q/ R - int[][] count = new int[2][2]; Z2 @( g# `" U0 q; H* I; j; g
- for (int i = 0; i < str.length; i++) {
- K x8 {2 O$ j0 h - count[i % 2][str[i] - '0']++;1 x9 a- J1 \, W2 M+ H! N/ t- f; L0 D
- }
# V; o" u0 W) W5 Z# `0 J2 c( g* S4 | H - int result = Math.min(count[1][1] + count[0][0], count[1][0] + count[0][1]);7 S) O. S' l- v8 Q" e
- for (int i = 0; i < str.length - 1; i++) {& h( ?% S. U \( K
- count[0][str[i] - '0']--;
# a4 z/ p7 [4 a: H/ r' H: ? - int tmp = count[1][0];0 M% ^/ H1 N2 ?& L. j8 {
- count[1][0] = count[0][0];# n. M, E: K7 }, l0 d# T' |* p) w
- count[0][0] = tmp;
" \- M* `4 S: _8 X" F& K. r - tmp = count[1][1];) ^! z" s# k) P6 i
- count[1][1] = count[0][1];% A! J$ N' }* t4 v
- count[0][1] = tmp;- N5 d+ G8 v( S( ]5 w* H+ j
- count[(str.length - 1) % 2][str[i] - '0']++;# X2 E* ^$ l6 t! q" p$ B
- result = Math.min(result, Math.min(count[1][1] + count[0][0], count[1][0] + count[0][1]));; Y* ?5 }1 V: C
- }
6 h2 y+ w1 L- D6 } - return result;
5 ?5 y$ x$ c4 I8 ? s( s% V - }
6 K! r7 j! f }) e" F! U; n' g$ ] - }
复制代码No.4 装包裹的最小浪费空间 解题思路 二分查找。 对所有的包裹和供应商的盒子都排序,然后依次枚举每个供应商即可。 计算一个供应商的盒子的浪费空间时,从小到大使用每种盒子,每种盒子尽可能多装包裹即可,使用前缀和数组和二分查找可以快速计算结果。 代码展示 - class Solution {1 f2 K+ \, K B; ^, q" r+ z
- public int minWastedSpace(int[] packages, int[][] boxes) {" f; M" M) ~* c; J+ |2 a
- Arrays.sort(packages);
, j: e/ [6 p6 G! E( }! G7 g- [) D - long[] preSum = new long[packages.length];) x' u6 G1 a5 c# K# y9 f
- preSum[0] = packages[0];* Z3 P, ]* R; d* X+ D
- for (int i = 1; i < preSum.length; i++) {
8 K! x) x: ~, l - preSum[i] = preSum[i - 1] + packages[i];' k+ d* _6 |. U n. P
- }# g- x# Y7 D P$ m3 r
- long result = -1;2 u5 Z3 a/ t7 F: S" [/ u9 G$ H
- for (int[] box : boxes) {% l1 ]* r' _1 h& E
- Arrays.sort(box);
4 M9 p, d2 E" k8 z - long t = waste(packages, preSum, box);' ~8 y5 E/ f' I4 ^& P' A
- if (t != -1 && (result == -1 || t < result)) {
# T f+ i- ~: B1 x% J' e - result = t;
9 B' x/ o, A: z* J - }
( x% e+ Q+ A2 o) ]" N% ~ - }! |$ E* b0 F% t% [
- return (int) (result % 1000000007L);, S+ c+ [- ~/ ~4 A# Z( v% O
- }
' _( a t3 h- w5 |1 q9 `+ s - / z1 P) Z) x& J
- private long waste(int[] packages, long[] preSum, int[] boxes) {1 M# {: U( @4 U0 c5 W3 j }
- int start = 0;; [8 o0 D; K9 E9 g* g4 e) G
- long result = 0;3 I7 N) j V. q. J! f U! u
- for (int box : boxes) {
1 K" J" g, J% D9 f* X/ n7 Q, C( j - if (box < packages[start]) {
5 m' B" r/ U- j: i7 l+ a - continue;
+ m# i" V/ @9 z* L7 ^ - }4 P7 D' T# u H. q8 N; m5 _
- int index = binarySearch(packages, box);
; h/ N8 N: ~. j( \1 j. [8 O - // [start, index] 之间的包裹使用 box 装9 T; x" y9 M0 N6 r
- result += (long) box * (index - start + 1) - preSum[index];$ }# L2 V) h4 }1 u5 A+ }% y, q- r
- if (start != 0) {( J' H/ H4 h" }) {
- result += preSum[start - 1];
2 {; `4 e$ C' S - }
) z9 G8 Z6 M- ?+ Z - start = index + 1;
. R' T( c- R% p2 c9 c4 |8 T8 Y - if (start >= packages.length) {
( C Q4 M+ |1 z+ O' l - return result;$ h3 C/ [/ F: y. T
- }% Z# N+ b1 Y: h7 l5 Y' g4 |
- }8 f b% P }( Q" g5 D2 T' X" w
- return -1;; ^5 U! \9 t3 Y& ]/ X% `
- }( X0 ], g! S8 }) \- v
/ Y% O5 R, v1 l! k0 N- private int binarySearch(int[] arr, int target) {+ ]5 P& K8 I! t% q" m7 [
- int l = 0, r = arr.length - 1;
! P! n( K( S+ O9 F: d7 [& E - while (l + 1 < r) {. e& L q1 S5 V0 b2 \; y
- int mid = (l + r) / 2;$ o- J( q, L; Y" J& h$ Q
- if (arr[mid] <= target) {
y2 F6 v# M4 c' E3 b - l = mid;$ x8 y0 a) y9 T+ q+ @5 |
- } else {: J' \- q1 H5 t% }8 `
- r = mid;# r. ?, V* S4 t ]. o
- } i1 Q. D! o2 Z% s$ k
- }
) _( u& Z7 o0 k - return arr[r] <= target ? r : l;
6 S5 N k J& s. @# C% } - }2 ^/ z- G2 B" s4 K" ]5 k
- }
复制代码 6 R3 \! {8 Q+ g0 R7 h& B
3 U, I) ?- K/ E# w
|