讨论/题目交流/🏆 第 166 场力扣周赛/
🏆 第 166 场力扣周赛

欢迎小伙伴们在这里交流分享你的参赛心得以及体验。【前往竞赛

image.png

3 分 - 整数的各位积和之差
4 分 - 用户分组
5 分 - 使结果不超过阈值的最小除数
6 分 - 转化为全零矩阵的最少反转次数

展开讨论
力扣 (LeetCode)发起于 2019-12-08
最近编辑于 2019-12-08

今天摇色子决定用java写

第一题:

此题无需题解

class Solution {
    public int subtractProductAndSum(int n) {
        int p = 1;
        int s = 0;
        while (n != 0) {
            int t = n % 10;
            p *= t;
            s += t;
            n /= 10;
        }
        return p - s;
    }
}

第二题:

这题是原题啊。。。前几天刚看到有一个类似的题,不过那个题是判断可行性,这个题是输出可行解

相同group肯定相同的groupSizes,不同group肯定不同的groupSizes,我们可以按照groupSizes聚合,然后随机取出来groupSizes个组成列表抛出去即可

class Solution {
    public List<List<Integer>> groupThePeople(int[] groupSizes) {
        List<List<Integer>> result = new ArrayList<>();

        List<Integer>[] group = new List[groupSizes.length + 1];
        for (int i = 0;i < group.length;i++) {
            group[i] = new ArrayList();
        }

        for (int i = 0;i < groupSizes.length;i++) {
            group[groupSizes[i]].add(i);
        }

        for (int i = 1;i < group.length;i++) {
            int index = 0;
            for (;index < group[i].size();index += i) {
                result.add(group[i].subList(index, Math.min(index + i, group[i].size())));
            }
        }
        return result;
    }
}

第三题:

这类题周赛出过很多次了。。。就二分

f(k)=i=1nnums[i]/kf(k)=\sum_{i=1}^{n}nums[i]/k

很明显f(n)f(n)是一个单调非严格递减函数

注意题目的整除是向上取整

class Solution {

    private boolean judge(int[] nums, int threshold, int k) {
        int sum = 0;
        for (int i = 0;i < nums.length;i++) {
            int t = nums[i] / k;
            if (nums[i] % k != 0) {
                t++;
            }
            sum += t;
            if (sum > threshold) {
                return false;
            }
        }
        return true;
    }

    public int smallestDivisor(int[] nums, int threshold) {
        int left = 0, right = Integer.MAX_VALUE / 2;

        while (right - left > 1) {
            int temp = (left + right) / 2;

            if (judge(nums, threshold, temp)) {
                right = temp;
            } else {
                left = temp;
            }
        }
        return right;
    }
}

第四题:

一定要理解题目,每个格子最多只会被选择一次,为啥呢?因为选择两次相当于没选啊。再看一下数据范围,才3*3,枚举遍所有的情况不过是292^9种情况,暴力啊

这种用位运算来枚举的写法前几周的周赛题出得很多,大家可以联合起来学习

class Solution {
    // bit的每一位代表每个格子是否被选择,n*m的矩阵压成一个bit,这里的n在题目中表示n*m
    private int count(int bit, int n) {
        int ret = 0;
        for (int i = 0;i < n;i++) {
            if ((bit & (1 << i)) != 0) {
                ret++;
            }
        }
        return ret;
    }
    // 方向数组,注意最后的0,0,因为自身也有可能被选择
    private final int[][] d = {{0,1},{1,0},{0,-1},{-1,0},{0,0}};
    // 判断选择串bit是否能满足题目要求
    boolean judge(int[][] mat, int bit) {
        for (int i = 0;i < mat.length;i++) {
            for (int j = 0;j < mat[0].length;j++) {
                int sum = mat[i][j];
                for (int k = 0;k < d.length;k++) {
                    int dx = i + d[k][0];
                    int dy = j + d[k][1];
                    
                    if (dx >= 0 && dx < mat.length && dy >= 0 && dy < mat[0].length) {
                        int t = dx * mat[0].length + dy;
                        if ((bit & (1 << t)) != 0) {
                            sum++;
                        }
                    }
                }
                // 如果sum是奇数,说明经过bit转换后,mat[i][j]变成了1
                if (sum % 2 != 0) {
                    return false;
                }
            }
        }
        return true;
    }
    public int minFlips(int[][] mat) {
        int n = mat.length * mat[0].length;
        int ret = 100;
        for (int i = 0;i < (1 << n);i++) {
            if (judge(mat, i)) {
                ret = Math.min(ret, count(i, n));
            }
        }
        if (ret == 100) {
            return -1;
        }
        return ret;
    }
}
8
展开全部 22 讨论