力扣第244场周赛

题一判断矩阵经轮转后是否一致

描述

给你两个大小为 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

思路

模拟。

顺时针旋转90度。

next[i][j]=mat[j][n-i-1];

代码

public class N1 {
    public boolean findRotation(int[][] mat, int[][] target) {
        int i=4;
        while (i-->0){
            mat=help(mat);
            if(check(mat,target))return true;
        }
        return false;
    }

    private boolean check(int[][] mat, int[][] target) {
       final int n=mat.length;
       for (int i=0;i<n;i++){
           for (int j=0;j<n;j++){
               if(mat[i][j]!=target[i][j])return false;
           }
       }
       return true;
    }

    private int[][] help(int[][] mat) {
        final int n= mat.length;
        int[][] res=new int[mat.length][mat.length];
        for (int i=0;i<n;i++){
            for (int j=0;j<n;j++){
                res[i][j]=mat[j][n-i-1];
            }
        }
        return res;
    }

}

题二使数组元素相等的减少操作次数

描述

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

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

返回使 nums 中的所有元素相等的操作次数。

示例 1：

输入：nums = [5,1,3]
输出：3
解释：需要 3 次操作使 nums 中的所有元素相等：
1. largest = 5 下标为 0 。nextLargest = 3 。将 nums[0] 减少到 3 。nums = [3,1,3] 。
2. largest = 3 下标为 0 。nextLargest = 1 。将 nums[0] 减少到 1 。nums = [1,1,3] 。
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 中的所有元素相等：
1. largest = 3 下标为 4 。nextLargest = 2 。将 nums[4] 减少到 2 。nums = [1,1,2,2,2] 。
2. largest = 2 下标为 2 。nextLargest = 1 。将 nums[2] 减少到 1 。nums = [1,1,1,2,2] 。 
3. largest = 2 下标为 3 。nextLargest = 1 。将 nums[3] 减少到 1 。nums = [1,1,1,1,2] 。 
4. 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

思路

排序，每次迭代找出第一大的和第二大的值，把第一大的值变成第二大的值。

假设第一大的个数为m,第二大的个数为n,变化需要的次数为m，变化后第二大的值为m+n。

当所有元素相等时结束迭代。

代码

public class N2 {
    public int reductionOperations(int[] nums) {
        Map<Integer,Integer> map=new HashMap<>();
        PriorityQueue<Integer> pq=new PriorityQueue<>((o1, o2) -> Integer.compare(o2,o1));
        for (int i:nums){
            map.put(i,map.getOrDefault(i,0)+1);
        }
        pq.addAll(map.keySet());
        int res=0;
        while (map.size()!=1){
            final int max = pq.poll();
            final int min = pq.poll();
            int m=map.get(max);
            int n=map.get(min);
            res+=m;
            pq.add(min);
            map.remove(max);
            map.put(min,m+n);
        }
        return res;
    }
}

题三使二进制字符串字符交替的最少反转次数

描述

给你一个二进制字符串 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' 。

思路

9O0fYc

代码

9O0fYc

题四装包裹的最小浪费空间

描述

给你 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 。由于答案可能会很大，请返回它对 109 + 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 <= 105
1 <= m <= 105
1 <= packages[i] <= 105
1 <= boxes[j].length <= 105
1 <= boxes[j][k] <= 105
sum(boxes[j].length) <= 105
boxes[j] 中的元素 互不相同 。

思路

二分超时

9O0fYc

代码

9O0fYc

超时代码

public class N4 {
    //TODO: TimeOut
    private final static int MOD= (int) (Math.pow(10,9)+7);
    public int minWastedSpace(int[] packages, int[][] boxes) {
        Map<Integer,Integer> pack=new HashMap<>(packages.length*2+5);
        int pMax=0;
        for (int p:packages){
            pack.put(p,pack.getOrDefault(p,0)+1);
            pMax=Math.max(pMax,p);
        }
        long res=Long.MAX_VALUE;
        List<Map.Entry<Integer, Integer>> list=new ArrayList<>(pack.entrySet());
        list.sort(Comparator.comparingInt(Map.Entry::getKey));
        for (int[] box:boxes){
            int bMax=0;
            for (int j : box) {
                bMax = Math.max(bMax, j);
            }
            if(bMax>=pMax){
                Arrays.sort(box);
                res=Math.min(res,slove(box,list,res));
            }
        }
        return res==Long.MAX_VALUE?-1: (int) (res % MOD);
    }

    private long slove(final int[] box,List<Map.Entry<Integer, Integer>> list , long max) {
        long res=0;
        int l=0;
        for (Map.Entry<Integer,Integer> e:list){
            int idx=find(e.getKey(),box,l);
            res+= (long) (box[idx] - e.getKey()) *e.getValue();
            if(res>=max)return res;
            l=idx;
        }
        return res;
    }

    private int find(int key, int[] box,int l) {
        int left=l;
        int right=box.length-1;
        int res=box.length-1;
        while (left<=right){
            int mid=left+(right-left)/2;
            if(box[mid]==key)return mid;
            else if(box[mid]>key){
                res=mid;
                right=mid-1;
            }
            else left=mid+1;
        }
        return res;
    }
}

力扣第244场周赛

题一 判断矩阵经轮转后是否一致

描述

思路

代码

题二 使数组元素相等的减少操作次数

描述

思路

代码

题三 使二进制字符串字符交替的最少反转次数

描述

思路

代码

题四 装包裹的最小浪费空间

描述

思路

代码

题一判断矩阵经轮转后是否一致

题二使数组元素相等的减少操作次数

题三使二进制字符串字符交替的最少反转次数

题四装包裹的最小浪费空间