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

解题思路

模拟矩阵的旋转即可。

代码展示

**classSolution**{
    **publicbooleanfindRotation**(**int**[][] mat, **int**[][] target){
        **for** (**int** i = 0; i < 4; i++) {
            **if** (equal(mat, target)) {
                **returntrue**;
            }
            mat = rotate(mat);
        }
        **returnfalse**;
    }

    **privateint**[][] rotate(**int**[][] mat) {
        **int**[][] r = **newint**[mat.length][mat[0].length];
        **for** (**int** i = 0, y = 0; i < mat.length; i++, y++) {
            **for** (**int** j = 0, x = mat.length - 1; j < mat[0].length; j++, x--) {
                r[i][j] = mat[x][y];
            }
        }
        **return** r;
    }

    **booleanequal**(**int**[][] mat, **int**[][] target){
        **for** (**int** i = 0; i < mat.length; i++) {
            **for** (**int** j = 0; j < mat[0].length; j++) {
                **if** (mat[i][j] != target[i][j]) {
                    **returnfalse**;
                }
            }
        }
        **returntrue**;
    }
}

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

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

添加上岸小年糕，发送【公开课】即可领取

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

解题思路

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

代码展示

**classSolution**{
    public int reductionOperations(int[] nums) {
        TreeMap<Integer, Integer> count = **new** TreeMap<>();
        **for** (**var**num : nums) {
            count.put(num, count.getOrDefault(num, 0) + 1);
        }
        int result = 0;
        **while** (count.size() > 1) {
            **var** largest = count.pollLastEntry();
            **var** nextLargest = count.lastEntry();
            result += largest.getValue();
            count.put(nextLargest.getKey(), nextLargest.getValue() + largest.getValue());
        }
        **return** result;
    }
}

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

解题思路

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

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

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

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

代码展示

class Solution {
    public int minFlips(String s) {
        char[] str = s.toCharArray();
        // count[0] 表示偶数下标上 0 和 1 的数量
        // count[1] 表示奇数下标上 0 和 1 的数量
        int[][] count = new int[2][2];
        for (int i = 0; i < str.length; i++) {
            count[i % 2][str[i] - '0']++;
        }
        intresult = Math.min(count[1][1] + count[0][0], count[1][0] + count[0][1]);
        for (inti = 0;i < str.length-1; i++) {
            count[0][str[i] - '0']--;
            inttmp = count[1][0];
            count[1][0] = count[0][0];
            count[0][0] = tmp;
            tmp = count[1][1];
            count[1][1] = count[0][1];
            count[0][1] = tmp;
            count[(str.length-1) % 2][str[i] - '0']++;
            result = Math.min(result,Math.min(count[1][1] + count[0][0], count[1][0] + count[0][1]));
        }
        returnresult;
    }

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

解题思路

二分查找。

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

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

代码展示

**classSolution** {
    **publicintminWastedSpace**(**int**[] packages, **int**[][] boxes){
        Arrays.sort(packages);
        **long**[] preSum = **newlong**[packages.length];
        preSum[0] = packages[0];
        **for** (**int** i = 1; i < preSum.length; i++) {
            preSum[i] = preSum[i - 1] + packages[i];
        }
        **long** result = -1;
        **for** (**int**[] box : boxes) {
            Arrays.sort(box);
            **long** t = waste(packages, preSum, box);
            **if** (t != -1 && (result == -1 || t < result)) {
                result = t;
            }
        }
        **return** (**int**) (result % 1000000007L);
    }

    **privatelongwaste**(**int**[] packages, **long**[] preSum, **int**[] boxes){
        **int** start = 0;
        **long** result = 0;
        **for** (**int** box : boxes) {
            **if** (box < packages[start]) {
                **continue**;
            }
            **int** index = binarySearch(packages, box);
            _// [start, index] 之间的包裹使用 box 装_
            result += (**long**) box * (index - start + 1) - preSum[index];
            **if** (start != 0) {
                result += preSum[start - 1];
            }
            start = index + 1;
            **if** (start >= packages.length) {
                **return** result;
            }
        }
        **return**-1;
    }

    **privateintbinarySearch**(**int**[] arr, **int** target){
        **int** l = 0, r = arr.length - 1;
        **while** (l + 1 < r) {
            **int** mid = (l + r) / 2;
            **if** (arr[mid] <= target) {
                l = mid;
            } **else** {
                r = mid;
            }
        }
        **return** arr[r] <= target ? r : l;
    }
}