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

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

image.png

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

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

今天摇色子决定用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

初学者,才把第一题做完,今天首战---事实上,我找入口都找了好一会,what a memorable day.

7

我感觉我好菜啊,只能秒完第一题,其他的。。。

5

今天的题目总体不难,用时41分55秒做完全部4题,已经排名第53名了,竞争太激烈。

4

第四题线性方程组高斯消元法

class Solution {
public:
    void solve(vector<vector<int>>& board,vector<int>&pivot){
        int l=board.size();
        for(int j=0;j<l;j++){
            for(int i=0;i<l;i++){
                if(board[i][j]){
                    if(pivot[j]==-1){
                        if(find(pivot.begin(),pivot.end(),i)==pivot.end()){
                            pivot[j]=i;
                            i=-1;}
                        continue;
                    }else{
                        if(i!=pivot[j]){
                            for(int k=0;k<l+1;k++){
                                board[i][k]=(board[i][k]+board[pivot[j]][k])%2;
                            }
                        }
                    }
                }
            }
        }
    }
    int minFlips(vector<vector<int>>& mat) {
        int m=mat.size();
        int n=mat[0].size();
        vector<vector<int>>board(m*n,vector<int>(m*n+1,0));
        for(int k=0;k<m*n;k++){
            board[k][m*n]=mat[k/n][k%n];
            board[k][k]=1;
            if(k%n!=0)board[k][k-1]=1;
            if(k-n>=0)board[k][k-n]=1;
            if(k%n!=n-1)board[k][k+1]=1;
            if(k+n<m*n)board[k][k+n]=1;
        }
        vector<int>pivot(board.size(),-1);
        solve(board,pivot);
        if(find(pivot.begin(),pivot.end(),-1)!=pivot.end())return -1;
        int ans=0;
        for(int k=0;k<m*n;k++){
            ans+=board[k][m*n];
        }
        return ans;
    }
};
2
  • 整数的各位积和之差
    暴力计算每一位,然后计算和和积做差就行了。时间复杂度 O(n)O(n)nn 为数字位数。

  • 用户分组
    先把数字相同的分到一个组,然后例如一个组里面全是3,那么就每三个作为一个新组就可以了。时间复杂度 O(n)O(n)

  • 使结果不超过阈值的最小除数
    显然除数越小,最后的结果和越大,这是满足单调关系的。于是我们可以二分我们的除数,每次判断中间结果和阈值的大小关系就可以了。时间复杂度 O(nlogn)O(nlogn)

  • 转化为全零矩阵的最少反转次数

需要先证明几个推论:

  1. 不会以同一个位置为中心翻转超过1次:如果某个位置翻转 n 次,结果和翻转 n % 2 次其实等价,因为翻过去再翻过来等于没变化。
  2. 对于两个要翻转的位置,翻转顺序对结果没有影响:因为翻转本质上是对5个位置取异或操作,所以最后的改变只和该位置被操作的次数有关,而与操作顺序无关。

那么有了这两个结论以后,我们就可以枚举每个格子是否翻转,由于只有 9 个格子,所以可能的状态只有 29=5122^9=512 种。每一种我们暴力判断一下就可以了。

如果题目只要求一组可行解而不是次数最少的解的话,题目是存在多项式解的:

假设我们有 n 行 m 列,我们记每行每列是否翻转为 xijx_{ij}, 那么 xij0,1x_{ij}∈{0,1}。对于每个格子,假设他本身的值是 aija_{ij},能影响到他的点有 (i,j),(i,j1),(i1,j),(i,j+1),(i,j1)(i,j),(i,j-1),(i-1,j),(i,j+1),(i,j-1) 五个,最后我们希望他的值是 0, 那么:

(xij1+xij+1+xij+xi+1j+xi1j+aij)%2=0(x_{ij-1} + x_{ij+1} + x_{ij} + x_{i+1j} + x_{i-1j} + a_{ij} ) \% 2 = 0

对于每个格子我们都有这样的一个方程,最后就变成了一个n元1次模线性方程组,可以直接在多项式时间内用高斯消元求解各个变量。

2

第一题,防止溢出,乘积与和都用long,遍历一遍,然后返回结果。

class Solution {
    public int subtractProductAndSum(int n) {
        long pro = 1;
        long sum = 0;
        while(n != 0){
            pro *= n % 10;
            sum += n % 10;
            n /= 10;
        }
        return (int)(pro - sum);
    }
}

第二题,至少存在解决方案,则用TreeMap + TreeSet建立分组大小和用户ID之间的一对多映射,
对于每种size的分组,这种分组需要的数量就是用户ID数量 / 分组size,对于每个分组容器,遍历TreeSet,把用户ID加进去。

class Solution {
    public List<List<Integer>> groupThePeople(int[] groupSizes) {
        List<List<Integer>> res = new ArrayList<>();
        TreeMap<Integer, TreeSet<Integer>> map = new TreeMap<>();
        if(groupSizes.length == 0){
            return res;
        }
        for(int i = 0; i < groupSizes.length; i ++){
            int cnt = groupSizes[i];
            if(!map.containsKey(cnt)){
                map.put(cnt,new TreeSet<>());
            }
            map.get(cnt).add(i);
        }
        for(int cnt : map.keySet()){
            int num = map.get(cnt).size() / cnt;
            int i = 0;
            List<Integer> list = null;
            for(int index : map.get(cnt)){
                if(i % cnt == 0){
                    list = new ArrayList<>();
                }
                list.add(index);
                if(list.size() == cnt){
                    res.add(list);
                }
                i ++;
            }
        }
        return res;
    }
}

第三题,典型的二分解法,解的范围肯定在1 到 max(nums[i])(i >= 0,i < nums.length) 之间,
令两个指针first,last分别为左边界和右边界,结合题意和区间知识,右边界的值一定是符合的条件的,所以当first == last的时候,
就夹逼到结果了,直接返回first或last。至于每个mid怎么判断,直接暴力O(n)判断。


class Solution {
    private int[] nums;
    private int threshold;
    public int smallestDivisor(int[] nums, int threshold) {
        this.nums = nums;
        this.threshold = threshold;
        long last = 0x80000000;
        for(int i = 0; i < nums.length; i ++){
            if(nums[i] > last){
                last = nums[i];
            }
        }
        long first = 1;
        while(first < last){
            long mid = first + ((last - first) >> 1);
            if(isOk(mid)){
                last = mid;
            }else{
                first = mid + 1;
            }
        }
        return (int)first;
    }
    private boolean isOk(long key){
        long sum = 0;
        for(int i = 0; i < nums.length; i ++){
            sum += nums[i] / key;
            if(nums[i] % key != 0){
                sum ++;
            }
        }
        return sum <= threshold;
    }

    public static void main(String[] args) {
        int[] nums = {1,2,5,9};
        System.out.println(new Solution().smallestDivisor(nums,6));
    }
}

第四题,由于m和n都比较小,所以用最暴力的bfs就好。但是有些小细节还是值得学习的,可以把mat压缩为一个比特串,
进而可以保存为一个整数,这就为bfs的去重、队列容器的基本类型大大降低了编码复杂度。
思路就是对于每个mat,暴力地对每个单元反转,
对于每一次反转,把当前矩阵转换回整数,判断是否为0,以及是否已经进过队了。
当矩阵全为0地时候,返回该矩阵的dist;如果队列为空了而退出,则没有答案,返回-1

import java.util.LinkedList;
import java.util.Queue;

class Solution {
    int R;
    int C;
    public int minFlips(int[][] mat) {
        int key = getKey(mat);
        if (key == 0) return 0;
        this.R = mat.length;
        this.C = mat[0].length;
        boolean[] isVisited = new boolean[1 << (mat.length * mat[0].length)];
        int[] dist = new int[1 << (mat.length * mat[0].length)];
        Queue<Integer> queue = new LinkedList<>();
        isVisited[key] = true;
        queue.add(key);
        int[][] dirs = {{-1,0},{0,-1},{1,0},{0,1}};
        while(!queue.isEmpty()){
            int curKey = queue.poll();
            int[][] curMat = getMat(curKey);
            for(int i = 0; i < R; i ++){
                for(int j = 0; j < C; j ++){
                    //对该单元格反转
                    curMat[i][j] = 1 - curMat[i][j];
                    for(int k = 0; k < dirs.length; k ++){
                        int nextX = i + dirs[k][0];
                        int nextY = j + dirs[k][1];
                        if(inArea(nextX,nextY)){
                            curMat[nextX][nextY] = 1 - curMat[nextX][nextY];
                        }
                    }
                    int nextKey = getKey(curMat);
                    if(!isVisited[nextKey]){
                        isVisited[nextKey] = true;
                        dist[nextKey] = dist[curKey] + 1;
                        queue.add(nextKey);
                        if(nextKey == 0){
                            return dist[nextKey];
                        }
                    }
                    //对该单元格反转复原
                    curMat[i][j] = 1 - curMat[i][j];
                    for(int k = 0; k < dirs.length; k ++){
                        int newX = i + dirs[k][0];
                        int newY = j + dirs[k][1];
                        if(inArea(newX,newY)){
                            curMat[newX][newY] = 1 - curMat[newX][newY];
                        }
                    }
                }
            }
        }
        return -1;
    }
    //判断是否越界
    private boolean inArea(int x, int y){
        return x >= 0 && x < R && y >= 0 && y < C;
    }
    //把mat压缩为一个整数
    private int getKey(int[][] mat){
        int key = 0;
        for(int i = 0; i < mat.length; i ++){
            for(int j = 0; j < mat[i].length; j ++){
                key <<= 1;
                key += mat[i][j];
            }
        }
        return key;
    }
    //把整数解压为key
    private int[][] getMat(int key){
        int[][] mat = new int[R][C];
        for(int i = R - 1; i >= 0; i --){
            for(int j = C - 1; j >= 0; j --){
                mat[i][j] = key & 1;
                key >>= 1;
                if(key == 0) return mat;
            }
        }
        return mat;
    }
}
2

头一次这么轻松地做完前三题,然后脑子一热看着第四题题目直接试图写暴力枚举,写着写着看见 示例 4

输入:mat = [[1,0,0],[1,0,0]]
输出:-1
解释:该矩阵无法转变成全零矩阵

瞬间傻眼、石化,临表涕零,不知所云/(ㄒoㄒ)/~~

2

积分什么时候更新呐~

. 使结果不超过阈值的最小除数
给你一个整数数组 nums 和一个正整数 threshold ,你需要选择一个正整数作为除数,然后将数组里每个数都除以它,并对除法结果求和。
[91,41,78,86,8]
114
预期结果3
我就想知道为啥是3 不应该是91吗?????