Leetcode Weekly Contest Round 244

T1 5776. 判断矩阵经轮转后是否一致

题目

给你两个大小为 n x n 的二进制矩阵 mat 和 target 。现 以 90 度顺时针轮转 矩阵 mat 中的元素 若干次 ，如果能够使 mat 与 target 一致，返回 true ；否则，返回 false 。

示例 1：

输入：$mat = [[0,1],[1,0]], target = [[1,0],[0,1]]$
输出：true
解释：顺时针轮转 90 度一次可以使 mat 和 target 一致。

示例 2：

输入：$mat = [[0,1],[1,1]], target = [[1,0],[0,1]]$
输出：false
解释：无法通过轮转矩阵中的元素使 equal 与 target 一致。

示例 3：

输入：$mat = [[0,0,0],[0,1,0],[1,1,1]], target = [[1,1,1],[0,1,0],[0,0,0]]$
输出：true
解释：顺时针轮转 90 度两次可以使 mat 和 target 一致。
 
提示：
n == mat.length == target.length
n == $mat[i].length$ == $target[i].length$
1 <= n <= 10
$mat[i][j]$ 和 $target[i][j]$ 不是 0 就是 1

题解

上来直接贴代码

class Solution {
    public boolean findRotation(int[][] mat, int[][] target) {
        for(int i = 0; i < 4; i++){
            mat = change(mat);
            if(equals(mat, target)) return true;
        }
        return false;
    }
    public int[][] change(int[][] matrix){
		int[][] temp=new int[matrix[0].length][matrix.length];
		int dst = matrix.length - 1;
		for(int i = 0; i < matrix.length; i++, dst--){
			for(int j = 0; j < matrix[0].length; j++){
				temp[j][dst] = matrix[i][j];
			}
		}
		return temp;
	}
    public boolean equals(int[][] arr1, int[][] arr2){
        int rows = arr1.length;
        int cols = arr1[0].length;
        for(int i = 0; i < rows; i++){
            for(int j = 0; j < cols; j++){
                if(arr1[i][j] != arr2[i][j]) return false;
            }
        }
        return true;
    }
}

翻转matrix，每次翻转完比较即可

T2 5777. 使数组元素相等的减少操作次数

题目

给你一个整数数组 nums ，你的目标是令 nums 中的所有元素相等。完成一次减少操作需要遵照下面的几个步骤：

找出 nums 中的 最大 值。记这个值为 largest 并取其下标 i （下标从 0 开始计数）。如果有多个元素都是最大值，则取最小的 i 。
找出 nums 中的 下一个最大 值，这个值 严格小于 largest ，记为 nextLargest 。
将 $nums[i]$ 减少到 nextLargest 。
返回使 nums 中的所有元素相等的操作次数。

示例 1：
输入：$nums = [5,1,3]$
输出：3
解释：需要 3 次操作使 nums 中的所有元素相等：

• largest = 5 下标为 0 。nextLargest = 3 。将 $nums[0]$ 减少到 3 。$nums = [3,1,3]$
• largest = 3 下标为 0 。nextLargest = 1 。将 $nums[0]$ 减少到 1 。$nums = [1,1,3]$
• largest = 3 下标为 2 。nextLargest = 1 。将 $nums[2]$ 减少到 1 。$nums = [1,1,1]$

示例 2：
输入：$nums = [1,1,1]$
输出：0
解释：nums 中的所有元素已经是相等的。

示例 3：
输入：$nums = [1,1,2,2,3]$
输出：4
解释：需要 4 次操作使 nums 中的所有元素相等：

• largest = 3 下标为 4 。nextLargest = 2 。将 $nums[4]$ 减少到 2 。$nums = [1,1,2,2,2]$
• largest = 2 下标为 2 。nextLargest = 1 。将 $nums[2]$ 减少到 1 。$nums = [1,1,1,2,2]$
• largest = 2 下标为 3 。nextLargest = 1 。将 $nums[3]$ 减少到 1 。$nums = [1,1,1,1,2]$
• largest = 2 下标为 4 。nextLargest = 1 。将 $nums[4]$ 减少到 1 。$nums = [1,1,1,1,1]$
   
  提示：
  1 <= nums.length <= 5 * 10^4
  1 <= $nums[i]$ <= 5 * 10^4

题解

看在数据量为$5*10^4$的情况下，请勿使用下方类似的直接模拟，除非你想喜提一发TLE

class Solution {
    public int reductionOperations(int[] nums) {
        TreeSet<Integer> set = new TreeSet<>();
        PriorityQueue<Integer> pq = new PriorityQueue<>((o1, o2) -> nums[o1] != nums[o2] ? nums[o2] - nums[o1]: o1 - o2);
        int len = nums.length;
        for(int i = 0; i < len; i++){
            set.add(nums[i]);
            pq.offer(i);
        }
        int cnt = 0;
        while(!pq.isEmpty()){
            int cur = pq.poll();
            int val = nums[cur];
            Integer tmp = set.lower(val);
            if(tmp == null) return cnt;
            nums[cur] = tmp;
            pq.offer(cur);
            cnt++;
        }
        return cnt;
    }
}

静下心来仔细思考，我们想到数组的操作实际上是有规律可循的，每一轮的若干操作都会将最高梯度削平并入第二高梯度，而这轮的操作数量记为最高梯度的元素个数。
随后第二高梯度成为最高梯度，数量加入了之前的梯度，继续此类操作，直到只剩最后一个梯度（即所有元素都被削成数组最小值），该梯度的高度为数组最小值
代码如下：

class Solution {
    public int reductionOperations(int[] nums) {
        TreeMap<Integer, Integer> map = new TreeMap<>((o1, o2) -> o2 - o1);
        //将map内部key由大到小排序
        int len = nums.length;
        for(int i = 0; i < len; i++){
            map.put(nums[i], map.getOrDefault(nums[i], 0) + 1);
        }
        int res = 0;
        int cnt = 0;
        for(int x: map.keySet()){//由大到小遍历key
            cnt += map.get(x); //cnt表示当前梯度的元素总数量（由之前的不断累加而来）
            res += cnt;
        }
        res -= cnt;//一不小心扣掉的最后一个梯度要还回来
        return res;
    }
}

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

题目

给你一个二进制字符串 s 。你可以按任意顺序执行以下两种操作任意次：

类型 1 ：删除 字符串 s 的第一个字符并将它 添加 到字符串结尾。
类型 2 ：选择 字符串 s 中任意一个字符并将该字符 反转 ，也就是如果值为 ‘0’ ，则反转得到 ‘1’ ，反之亦然。
请你返回使 s 变成 交替 字符串的前提下， 类型 2 的 最少 操作次数 。

我们称一个字符串是 交替 的，需要满足任意相邻字符都不同。
比方说，字符串 “010” 和 “1010” 都是交替的，但是字符串 “0100” 不是。

示例 1：
输入：s = “111000”
输出：2
解释：执行第一种操作两次，得到 s = “100011” 。
然后对第三个和第六个字符执行第二种操作，得到 s = “101010” 。

示例 2：
输入：s = “010”
输出：0
解释：字符串已经是交替的。

示例 3：
输入：s = “1110”
输出：1
解释：对第二个字符执行第二种操作，得到 s = “1010” 。

提示：
1 <= s.length <= 10^5
$s[i]$ 要么是 ‘0’ ，要么是 ‘1’

题解

看到这道题我们首先可以想到将s进行拼串，使用 String str = s + s 来表示第一轮操作后的位移后的各种情况，随后移位和"101010…"或者"01010101…"数组进行匹配，但是我们也注意到一个问题
位移共有s.length()种情况，而每次全串匹配又需要s.length()次操作，时间复杂度为$O(n^2)$，在$10^5$的数量级下会喜提一发TLE

代码如下：

class Solution {
    public int minFlips(String s) {
        String str = s + s;
        int res = Integer.MAX_VALUE;
        StringBuilder sb1 = new StringBuilder();
        StringBuilder sb2 = new StringBuilder();
        for(int i = 0; i < s.length(); i++){
            sb1.append(i % 2 == 0 ? '0': '1');
            sb2.append(i % 2 == 1 ? '0': '1');
        }
        for(int i = 0; i < s.length(); i++){
            int cnt1 = 0, cnt2 = 0;
            for(int j = 0; j < s.length(); j++){
                if(str.charAt(i + j) != sb1.charAt(j)) cnt1++;
                if(str.charAt(i + j) != sb2.charAt(j)) cnt2++;
            }
            res = Math.min(cnt1, res);
            res = Math.min(cnt2, res);
        }
        return res;
    }
}

经过仔细思考，我们发现事情好想并没有那么简单，但是好像出现了转机

首先明确：将移位后的字符串和"010101…“或"101010…” Pattern匹配，我们可以等价为将移位前的"01010…"或"101010…"Pattern和原串进行匹配

• 对于偶数长度的字符串，我们发现不论是否移位，其匹配规则某种程度上仍然满足原先条件。

• 例如101010->010101，010101->010101，不论第一种操作操作几次，原先的Pattern始终就是两种模式中的一种，我们只需要对原串进行"01010101…"或者"10101010…"匹配即可

• 而对于奇数长度串，情况就有了一些复杂

• 例如01 | 10101->10101 01，101 | 1010->1010 101我们发现原先的Pattern很明显的从某个位置被划开分成了两部分，左右各遵循不同的匹配模式

• 据此我们想到了需要拼串，需要分别求解两段区间各自匹配不同模式后不满足的数字的总数

• 据此我们想到了前缀和，将两种匹配模式和s串不匹配的数目以前缀和的方式存储起来，方便求解区间

好啦差不多了，可以直接上代码了：
对于奇数情况，我们维护cnt1 cnt2两个数组表示匹配不满足的前缀和，随后遍历区间分割线，将情况全部遍历，对于偶数直接给出最终结果即可

class Solution {
    public int minFlips(String s) {
        int len = s.length();
        StringBuilder sb1 = new StringBuilder();
        StringBuilder sb2 = new StringBuilder();
        for(int i = 0; i < len; i++){
            sb1.append(i % 2 == 0? '0': '1');
            sb2.append(i % 2 == 0? '1': '0');
        }
        int[] cnt1 = new int[len];
        int[] cnt2 = new int[len];
        for(int i = 0; i < len; i++){
            cnt1[i] = (i > 0 ? cnt1[i - 1] : 0) + (s.charAt(i) == sb1.charAt(i)? 0: 1);
            cnt2[i] = (i > 0 ? cnt2[i - 1] : 0) + (s.charAt(i) == sb2.charAt(i)? 0: 1);
        }
        int res = Math.min(cnt1[len - 1], cnt2[len - 1]);
        if(len % 2 == 1){
            for(int i = 0; i < len; i++){
                res = Math.min(cnt1[i] + cnt2[len - 1] - cnt2[i], res);
                res = Math.min(cnt2[i] + cnt1[len - 1] - cnt1[i], res);
            }
            return res;
        }
        else return Math.min(cnt1[len - 1], cnt2[len - 1]);
    }
}

T4 5779. 装包裹的最小浪费空间

题目

给你 n 个包裹，你需要把它们装在箱子里，每个箱子装一个包裹。总共有 m 个供应商提供 不同尺寸 的箱子（每个规格都有无数个箱子）。如果一个包裹的尺寸 小于等于 一个箱子的尺寸，那么这个包裹就可以放入这个箱子之中。

包裹的尺寸用一个整数数组 $packages$ 表示，其中 $packages[i]$ 是第 i 个包裹的尺寸。供应商用二维数组 $boxes$ 表示，其中 $boxes[j]$ 是第 j 个供应商提供的所有箱子尺寸的数组。

你想要选择 一个供应商 并只使用该供应商提供的箱子，使得 总浪费空间最小 。对于每个装了包裹的箱子，我们定义 浪费的 空间等于 箱子的尺寸 - 包裹的尺寸 。总浪费空间 为 所有 箱子中浪费空间的总和。

比方说，如果你想要用尺寸数组为 $[4,8]$ 的箱子装下尺寸为 $[2,3,5]$ 的包裹，你可以将尺寸为 2 和 3 的两个包裹装入两个尺寸为 4 的箱子中，同时把尺寸为 5 的包裹装入尺寸为 8 的箱子中。总浪费空间为 (4-2) + (4-3) + (8-5) = 6 。
请你选择 最优 箱子供应商，使得 总浪费空间最小 。如果 无法 将所有包裹放入箱子中，请你返回 -1 。由于答案可能会 很大 ，请返回它对 10^9 + 7 取余 的结果。

示例 1：
输入：$packages = [2,3,5], boxes = [[4,8],[2,8]]$
输出：6
解释：选择第一个供应商最优，用两个尺寸为 4 的箱子和一个尺寸为 8 的箱子。
总浪费空间为 (4-2) + (4-3) + (8-5) = 6 。

示例 2：
输入：$packages = [2,3,5], boxes = [[1,4],[2,3],[3,4]]$
输出：-1
解释：没有箱子能装下尺寸为 5 的包裹。

示例 3：
输入：$packages = [3,5,8,10,11,12], boxes = [[12],[11,9],[10,5,14]]$
输出：9
解释：选择第三个供应商最优，用两个尺寸为 5 的箱子，两个尺寸为 10 的箱子和两个尺寸为 14 的箱子。
总浪费空间为 (5-3) + (5-5) + (10-8) + (10-10) + (14-11) + (14-12) = 9 。
 
提示：
n == packages.length
m == boxes.length
1 <= n <= 10^5
1 <= m <= 10^5
1 <= packages[i] <= 10^5
1 <= boxes[j].length <= 10^5
1 <= boxes[j][k] <= 10^5
sum(boxes[j].length) <= 10^5
boxes[j] 中的元素 互不相同 。

题解

直觉之下我们知道要求解浪费空间最小，关键在于在$boxes[k]$中取得比当前$package[i]$大的最小的值，那就是二分喽，思路没错，但是有很多小细节需要注意

首先根据题目答案可能很大需要对$10^9+7$取余，但是在算法计算过程中我们却不能这么做，提前取余会影响大小的比较，取余只有最后一步得出答案时才能做。
那么问题又来了int能不能存下我们当前的计算值呢？以$packages$数组为例，我们求和时，总量有可能达到$10^5*10^5=10^{10}$，是有可能发生溢出的，故我们先采用long保存答案

所以为了顺序和方便起见，我们将$packages$和$boxes$数组内部一一进行排序，如果$boxes[k]$最大的盒子都存不下$packages$最大的包裹，说明不可行，直接跳过。
否则我们进行下一步计算，现在又面临了一个新问题，我们是遍历$packages$数组，针对每一个$packages[i]$去寻找他的上界；还是遍历$boxes[k]$内部的元素，去查找他下面的$packages$呢？

如果我们遍历$packages$，会喜得一发TLE，代码如下：

class Solution {
    public int minWastedSpace(int[] packages, int[][] boxes) {
        int p_len = packages.length;
        int b_len = boxes.length;
        Arrays.sort(packages);
        long sum = 0L;
        long res = Long.MAX_VALUE;
        for(int x: packages) sum += x;
        for(int i = 0; i < b_len; i++){
            int len = boxes[i].length;
            Arrays.sort(boxes[i]);
            if(boxes[i][len - 1] < packages[p_len - 1]) continue;
            long total = 0L;
            for(int x: packages){ //遍历packages，二分搜索boxes[i]
                int lo = 0, hi = len - 1;
                int ans = -1;
                while(lo <= hi){
                    int mid = lo + (hi - lo) / 2;
                    if(boxes[i][mid] >= x){
                        ans = mid;
                        hi = mid - 1;
                    }
                    else lo = mid + 1;
                }
                //ans为大于boxes[i]中大于packages的最小下标
                total += boxes[i][ans];
            }
            res = Math.min(res, total - sum);
        }
        return res == Long.MAX_VALUE? -1: (int)(res % 1000000007);
    }
}

原因是什么呢？我们看到提示$boxes[j]$ 中的元素 互不相同，而$packages$中的元素却是有可能重复的，我们根据遍历$packages$时一次只能求出一个对应的$boxes$的下标值，而且还多有重复，而如果我们遍历$boxes$数组，可能可以一次性在有序的$packages$划分出一个专属的区间来，直接调用乘法总比一次一次加要来的省事还快

不多说了，上代码：

class Solution {
    public int minWastedSpace(int[] packages, int[][] boxes) {
        int p_len = packages.length;
        int b_len = boxes.length;
        Arrays.sort(packages);
        //System.out.println(Arrays.toString(packages));
        long sum = 0L;
        long res = Long.MAX_VALUE;
        for(int x: packages) sum += x;
        for(int i = 0; i < b_len; i++){
            int len = boxes[i].length;
            Arrays.sort(boxes[i]);
            if(boxes[i][len - 1] < packages[p_len - 1]) continue;
            long total = 0L;
            int tmp = 0;
            for(int x: boxes[i]){ //遍历boes[i]，二分查找packages
                int lo = tmp, hi = p_len - 1;
                int ans = -1;
                while(lo <= hi){
                    int mid = lo + (hi - lo) / 2;
                    if(packages[mid] <= x){
                        ans = mid;
                        lo = mid + 1;
                    }
                    else hi = mid - 1;
                }
                //ans为小于packages中小于boxes[i]的最大下标
                if(ans != -1) {
                    total += (long)(ans - tmp + 1) * (long)x; 
                    //boxes[i]当前的packages专属区间为[tmp, ans]
                    //此区间的元素都使用boxes[i]最佳
                    tmp = ans + 1;
                    //下一个区间一定和当前不重合，可以直接调节下一轮二分搜索的上界
                    //当然你不调整，那问题也不大，答案仍然正确
                }   
            }
            res = Math.min(res, total - sum);
        }
        return res == Long.MAX_VALUE? -1: (int)(res % 1000000007);
    }
}

菜鸡本菜TLE到吐血