2019-12-09

力扣第166场周赛

第四题太可惜了，题目读错了以为反转要改变一行一列，其实只要改变相邻的元素（还是菜），第一次离ac这么近，记录一下。

1. 整数的各位积和之差 3分

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

示例 1:

输入：n = 234，输出：15

解释：

各位数之积 = 2 * 3 * 4 = 24，各位数之和 = 2 + 3 + 4 = 9，结果 = 24 - 9 = 15

示例 2:

输入：n = 4421，输出：21

解释：

各位数之积 = 4 * 4 * 2 * 1 = 32，各位数之和 = 4 + 4 + 2 + 1 = 11，结果 = 32 - 11 = 21

提示:

1 <= n <= 10⁵

求整数n的各位数字之积与之和的差，所以我们需要求出整数n每位上的数字。提示说1 <= n <= 10⁵所以n最多6位（为100000），使用一个大小为6的数组存储n的每位数字，这样需要处理当n不满6位时数组剩余空间存储的0对结果的影响。

其实数组剩余空间存储的0只会对乘积有影响，所以在求各位数字之积时，遇到0后判断数组剩余位是否有非0数字，若有则乘积为0（说明整数n中有0），否则当前值即为乘积（说明整数n中没有0）。

class Solution {
    public int subtractProductAndSum(int n) {
        int[] nums = new int[6];
        for (int i = 0; i < 6; i++) {
            nums[i] = n % 10;
            n /= 10;
        }

        int sum = 0;
        int product = 1;
        for (int i = 0; i < 6; i++) {
            sum += nums[i];
            if (nums[i] != 0) {
                product *= nums[i];
            } else {
                for (int j = i + 1; j < 6; j++) {
                    if (nums[j] != 0) {
                        product = 0;
                    }
                }
            }
        }

        return product - sum;
    }
}

2. 用户分组 4分

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

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

示例 1:

输入：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：

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

提示：

groupSizes.length == n

1 <= n <= 500

1 <= groupSizes[i] <= n

groupSize数组中元素的意思是：每个位置的索引为一个用户，值为这个用户所在组的大小，题目要求我们返回用户分组情况，即分为多少个组，每个组中的用户都有谁。

我们的可以任何顺序返回解决方案，ID的顺序也不受限制，所以只需遍历groupSize数组，将大小为1的组中的用户放入大小为1的组，将大小为2的组中的用户放入大小为2的组，以此类推。

class Solution {
    public List<List<Integer>> groupThePeople(int[] groupSizes) {
        List<List<Integer>> ans = new ArrayList<>();
        int[] group = new int[500];
        for (int i = 0; i < groupSizes.length; i++) {
            group[i] = groupSizes[i];
        }
        
        for (int i = 1; i <= 500; i++) { // 组的大小
            List<Integer> sub = new ArrayList<>();
            // 在group中寻找大小为i的组中的用户，将其放入大小为i的组中
            for (int j = 0; j < 500; j++) {
                if (sub.size() == i) {
                    ans.add(sub);
                    sub = new ArrayList<>();
                }
                if (group[j] == i) {
                    sub.add(j);
                }
            }
        }
        
        return ans;
    }
}

3. 使结果不超过阈值的最小除数 5分

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

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

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

题目保证一定有解。

示例 1：

输入：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：

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

示例 3：

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

提示：

1 <= nums.length <= 5 * 10⁴

1 <= nums[i] <= 10⁶

nums.length <= threshold <= 10⁶

尝试从1到nums数组中的最大值之间的数作为除数，使用二分搜索（从1一直往后试会超时了），当结果大于阈值时扩大除数，当结果小于等于阈值时缩小除数。

class Solution {
    public int smallestDivisor(int[] nums, int threshold) {
        int ans = 0;
        int biggest = 0;
        for (int i = 0; i < nums.length; i++) {
            biggest = biggest > nums[i] ? biggest : nums[i];
        }
        int lo = 1, hi = biggest + 1;
        while (lo < hi) {
            int divide = lo + ((hi - lo) >> 1);
            int curSum = 0;
            for (int i = 0; i < nums.length; i++) {
                int remain = nums[i] % divide;
                curSum += nums[i] / divide;
                if (remain != 0) {
                    curSum++;
                }
            }
            if (curSum > threshold) {
                lo = divide + 1;
            } else {
                hi = divide;
            }
            ans = lo;
        }
        
        return ans;
    }
}

4. 转化为全零矩阵的最少反转次数 6分

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

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

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

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

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

示例 1：

输入：mat = [[0,0],[0,1]]，输出：3

解释：

一个可能的解是反转 (1, 0)，然后 (0, 1) ，最后是 (1, 1) 。

示例 2：

输入：mat = [[0]]，输出：0

解释：

给出的矩阵是全零矩阵，所以你不需要改变它。

示例 3：

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

示例 4：

输入：mat = [[1,0,0],[1,0,0]]，输出：-1

解释：该矩阵无法转变成全零矩阵

提示：

m == mat.length

n == mat[0].length

1 <= m <= 3

1 <= n <= 3

mat[i][j] 是 0 或 1

由提示可得mat最大3 * 3，每个单元格最多返回一次，反转两次相当于没有反转，dfs直接尝试所有可能。

class Solution {
    boolean[][] visited = new boolean[3][3];

    public int minFlips(int[][] mat) {
        int rows = mat.length;
        int cols = mat[0].length;
        if (check(mat)) {
            return 0;
        }
        int count = 0;

        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (!visited[i][j]) {
                    int temp = count;
                    visited[i][j] = true;
                    change(mat, i, j);
                    count++;
                    count += minFlips(mat);
                    if (check(mat)) {
                        return count;
                    }
                    visited[i][j] = false;
                    change(mat, i, j);
                    count = temp;
                }
            }
        }

        return -1;
    }

    private void change(int[][] mat, int row, int col) {
        int rows = mat.length;
        int cols = mat[0].length;
        mat[row][col] = 1 - mat[row][col];
        if (row + 1 < rows) {
            mat[row + 1][col] = 1 - mat[row + 1][col];
        }
        if (row - 1 >= 0) {
            mat[row - 1][col] = 1 - mat[row - 1][col];
        }
        if (col + 1 < cols) {
            mat[row][col + 1] = 1 - mat[row][col + 1];
        }
        if (col - 1 >= 0) {
            mat[row][col - 1] = 1 - mat[row][col - 1];
        }
    }

    private boolean check(int[][] mat) {
        for (int i = 0; i < mat.length; i++) {
            for (int j = 0; j < mat[0].length; j++) {
                if (mat[i][j] == 1) {
                    return false;
                }
            }
        }

        return true;
    }
}