LeetCode第166场周赛

Posted on | Post modified: | In
Words count in article: 1.9k

本文是leetcode contest 106的题解，包括：

1
2
3
4
1281.整数的各位积和之差（简单）
1282.用户分组 （中等）
1283.使结果不超过阈值的最小除数 （中等）
1284.转化为全零矩阵的最少反转次数（困难）

第一次打比赛，AC前三题，全国248 / 1675，全球1289 / 5585。

1281. 整数的各位积和之差

题目描述

给你一个整数 n，请你帮忙计算并返回该整数「各位数字之积」与「各位数字之和」的差。

示例 1：

1
2
3
4
5
6
输入：n = 234
输出：15 
解释：
各位数之积 = 2 * 3 * 4 = 24 
各位数之和 = 2 + 3 + 4 = 9 
结果 = 24 - 9 = 15

示例 2：

1
2
3
4
5
6
输入：n = 4421
输出：21
解释： 
各位数之积 = 4 * 4 * 2 * 1 = 32 
各位数之和 = 4 + 4 + 2 + 1 = 11 
结果 = 32 - 11 = 21

提示：

1
1 <= n <= 10^5

解题思路

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public int subtractProductAndSum(int n) {
        int mut = 1, sum = 0;
        while (n > 0){
            int temp = n % 10;
            mut *= temp;
            sum += temp;
            n /= 10;
        }
        return mut - sum;
    }
}

1282. 用户分组

题目描述

有 n 位用户参加活动，他们的 ID 从 0 到 n - 1，每位用户都 恰好 属于某一用户组。给你一个长度为 n 的数组 groupSizes，其中包含每位用户所处的用户组的大小，请你返回用户分组情况（存在的用户组以及每个组中用户的 ID）。

你可以任何顺序返回解决方案，ID 的顺序也不受限制。此外，题目给出的数据保证至少存在一种解决方案。

示例 1：

1
2
3
4
输入：groupSizes = [3,3,3,3,3,1,3]
输出：[[5],[0,1,2],[3,4,6]]
解释： 
其他可能的解决方案有 [[2,1,6],[5],[0,4,3]] 和 [[5],[0,6,2],[4,3,1]]。

示例 2：

1
2
输入：groupSizes = [2,1,3,3,3,2]
输出：[[1],[0,5],[2,3,4]]

提示：

1
2
3
groupSizes.length == n
1 <= n <= 500
1 <= groupSizes[i] <= n

解题思路

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

class Solution {
    public List<List<Integer>> groupThePeople(int[] groupSizes) {
        // 将原数据转化为map，key为分组长度，value为索引
        Map<Integer, List<Integer>> map = new HashMap<>();
        for (int i = 0; i < groupSizes.length; i++){
            if (!map.containsKey(groupSizes[i])){
                List<Integer> temp = new ArrayList<>();
                temp.add(i);
                map.put(groupSizes[i], temp);
            }else{
                map.get(groupSizes[i]).add(i);
            }
        }

        List<List<Integer>> res = new ArrayList<>();
        // 将map中数据按照长度拆分存入res
        for (Map.Entry<Integer, List<Integer>> entry:map.entrySet()){
            if (entry.getKey() == entry.getValue().size()){
                res.add(entry.getValue());
            }else{
                for (int i = 0; i < entry.getValue().size(); i += entry.getKey()){
                    List<Integer> temp = entry.getValue().subList(i, i+entry.getKey());
                    res.add(temp);
                }
            }
        }
        return res;
    }
}

1283. 使结果不超过阈值的最小除数

题目描述

给你一个整数数组 nums 和一个正整数 threshold ，你需要选择一个正整数作为除数，然后将数组里每个数都除以它，并对除法结果求和。

请你找出能够使上述结果小于等于阈值 threshold 的除数中 最小 的那个。

每个数除以除数后都向上取整，比方说 7/3 = 3 ， 10/2 = 5 。

题目保证一定有解。

示例 1：

1
2
3
4
输入：nums = [1,2,5,9], threshold = 6
输出：5
解释：如果除数为 1 ，我们可以得到和为 17 （1+2+5+9）。
如果除数为 4 ，我们可以得到和为 7 (1+1+2+3) 。如果除数为 5 ，和为 5 (1+1+1+2)。

示例 2：

1
2
输入：nums = [2,3,5,7,11], threshold = 11
输出：3

示例 3：

1
2
输入：nums = [19], threshold = 5
输出：4

提示：

1
2
3
1 <= nums.length <= 5 * 10^4
1 <= nums[i] <= 10^6
nums.length <= threshold <= 10^6

解题思路

除数越大，除法结果和越小。

使用二分，除数范围为1~ max(nums)。因为提示中nums有界，为了少一轮遍历求数组最大值，可直接将上界取为10^6+1。

  1. 如果这个除法结果和大于阀值， 说明除数mid取的太小了，我们在[mid+1, right]中继续查找
  2. 如果这个除法结果和小于等于阀值，说明除数mid或者取得太大，或者满足要求，我们在[left,mid]中继续查找。

注意在2的情形下，mid可能是我们所要求的解，不应被剔除在搜索区间之外。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int smallestDivisor(int[] nums, int threshold) {
        
        int left = 1, right = 1000000+1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            int sum = 0;
            for (int num : nums) {
            	//向上取整
                sum += num / mid + ((num % mid == 0) ? 0 : 1);
            }
            if (sum > threshold) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return right;
    }
}

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

题目描述

给你一个 m x n 的二进制矩阵 mat。

每一步，你可以选择一个单元格并将它反转（反转表示 0 变 1 ，1 变 0 ）。如果存在和它相邻的单元格，那么这些相邻的单元格也会被反转。（注：相邻的两个单元格共享同一条边。）

请你返回将矩阵 mat 转化为全零矩阵的最少反转次数，如果无法转化为全零矩阵，请返回 -1 。

二进制矩阵的每一个格子要么是 0 要么是 1 。

全零矩阵是所有格子都为 0 的矩阵。

示例 1：
mark

1
2
3
输入：mat = [[0,0],[0,1]]
输出：3
解释：一个可能的解是反转 (1, 0)，然后 (0, 1) ，最后是 (1, 1) 。

示例 2：

1
2
3
输入：mat = [[0]]
输出：0
解释：给出的矩阵是全零矩阵，所以你不需要改变它。

示例 3：

1
2
输入：mat = [[1,1,1],[1,0,1],[0,0,0]]
输出：6

示例 4：

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

提示：

1
2
3
4
5
m == mat.length
n == mat[0].length
1 <= m <= 3
1 <= n <= 3
mat[i][j] 是 0 或 1 。

解题思路

使用位向量（即整数）保存矩阵的状态，使用BFS对每一个可能的状态，对其中的每一位进行翻转。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
import java.util.ArrayDeque;
import java.util.HashSet;
import java.util.Queue;
import java.util.Set;

class Solution {

    int n, m;

    public int minFlips(int[][] mat) {
        n = mat.length;
        m = mat[0].length;
        //初始化状态
        int bitVec = createBitVec(mat);

        if (bitVec == 0) {
            return 0;
        }

        Queue<Integer> queue = new ArrayDeque<>(); // 队列
        queue.offer(bitVec);
        Set<Integer> visited = new HashSet<>(); // 保存访问过的数

        int res = 0;

        // 常规BFS
        while (!queue.isEmpty()) {
            int queueLen = queue.size();
            for (int k = 0; k < queueLen; k++) {
                int curVec = queue.poll(); // 取出队顶元素
                if (curVec == 0) { //如果为0,返回
                    return res;
                }
                //如果当前元素不为0,对其中每一位进行翻转
                for (int i = 0; i < n; i++) {
                    for (int j = 0; j < m; j++) {
                        bitVec = getFlip(i, j, curVec); // 获取翻转后的数值
                        if (!visited.contains(bitVec)) { //如果没访问过，加入队列和访问过的数的集合
                            queue.offer(bitVec);
                            visited.add(bitVec);
                        }
                    }
                }
            }
            res++;
        }
        return -1;
    }

    public int createBitVec(int[][] mat) {
        /*初始状态：获得矩阵的值
        [[1,1,1],
        [1,0,1],
        [0,0,0]]
        转化为二进制 111101000->十进制 488
         */
        int bitVec = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                bitVec <<= 1;
                bitVec |= mat[i][j];
            }
        }
        return bitVec;
    }


    public int getFlip(int i, int j, int bitVec) {
        int pos = i * m + j; //根据i,j位置得到对应位
        bitVec ^= (1 << pos); //翻转

        int[][] dirs = new int[][]{{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
        //翻转四个方向的
        for (int[] dir : dirs) {
            int x = i + dir[0], y = j + dir[1];
            if (x >= 0 && x < n && y >= 0 && y < m) {
                pos = x * m + y;
                bitVec ^= (1 << pos);
            }
        }
        return bitVec;
    }
}
Donate comment here
------------The End------------
0%