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

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

image.png

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

第一题,防止溢出,乘积与和都用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
展开全部 22 讨论