力扣第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 <= 105
求整数n的各位数字之积与之和的差，所以我们需要求出整数n每位上的数字。提示说1 <= n <= 105所以n最多6位（为100000），使用一个大小为6的数组存储n的每位数字，这样需要处理当n不满6位时数组剩余空间存储的0对结果的影响。
其实数组剩余空间存储的0只会对乘积有影响，所以在求各位数字之积时，遇到0后判断数组剩余位是否有非0数字，若有则乘积为0（说明整数n中有0），否则当前值即为乘积（说明整数n中没有0）。
1class Solution {
2 public int subtractProductAndSum(int n) {
3 int[] nums = new int[6];
4 for (int i = 0; i < 6; i++) {
5 nums[i] = n % 10;
6 n /= 10;
7 }
8
9 int sum = 0;
10 int product = 1;
11 for (int i = 0; i < 6; i++) {
12 sum += nums[i];
13 if (nums[i] != 0) {
14 product *= nums[i];
15 } else {
16 for (int j = i + 1; j < 6; j++) {
17 if (nums[j] != 0) {
18 product = 0;
19 }
20 }
21 }
22 }
23
24 return product - sum;
25 }
26}
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的组，以此类推。
1class Solution {
2 public List<List<Integer>> groupThePeople(int[] groupSizes) {
3 List<List<Integer>> ans = new ArrayList<>();
4 int[] group = new int[500];
5 for (int i = 0; i < groupSizes.length; i++) {
6 group[i] = groupSizes[i];
7 }
8
9 for (int i = 1; i <= 500; i++) { // 组的大小
10 List<Integer> sub = new ArrayList<>();
11 // 在group中寻找大小为i的组中的用户，将其放入大小为i的组中
12 for (int j = 0; j < 500; j++) {
13 if (sub.size() == i) {
14 ans.add(sub);
15 sub = new ArrayList<>();
16 }
17 if (group[j] == i) {
18 sub.add(j);
19 }
20 }
21 }
22
23 return ans;
24 }
25}
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 * 104
1 <= nums[i] <= 106
nums.length <= threshold <= 106
尝试从1到nums数组中的最大值之间的数作为除数，使用二分搜索（从1一直往后试会超时了），当结果大于阈值时扩大除数，当结果小于等于阈值时缩小除数。
1class Solution {
2 public int smallestDivisor(int[] nums, int threshold) {
3 int ans = 0;
4 int biggest = 0;
5 for (int i = 0; i < nums.length; i++) {
6 biggest = biggest > nums[i] ? biggest : nums[i];
7 }
8 int lo = 1, hi = biggest + 1;
9 while (lo < hi) {
10 int divide = lo + ((hi - lo) >> 1);
11 int curSum = 0;
12 for (int i = 0; i < nums.length; i++) {
13 int remain = nums[i] % divide;
14 curSum += nums[i] / divide;
15 if (remain != 0) {
16 curSum++;
17 }
18 }
19 if (curSum > threshold) {
20 lo = divide + 1;
21 } else {
22 hi = divide;
23 }
24 ans = lo;
25 }
26
27 return ans;
28 }
29}
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直接尝试所有可能。
1class Solution {
2 boolean[][] visited = new boolean[3][3];
3
4 public int minFlips(int[][] mat) {
5 int rows = mat.length;
6 int cols = mat[0].length;
7 if (check(mat)) {
8 return 0;
9 }
10 int count = 0;
11
12 for (int i = 0; i < rows; i++) {
13 for (int j = 0; j < cols; j++) {
14 if (!visited[i][j]) {
15 int temp = count;
16 visited[i][j] = true;
17 change(mat, i, j);
18 count++;
19 count += minFlips(mat);
20 if (check(mat)) {
21 return count;
22 }
23 visited[i][j] = false;
24 change(mat, i, j);
25 count = temp;
26 }
27 }
28 }
29
30 return -1;
31 }
32
33 private void change(int[][] mat, int row, int col) {
34 int rows = mat.length;
35 int cols = mat[0].length;
36 mat[row][col] = 1 - mat[row][col];
37 if (row + 1 < rows) {
38 mat[row + 1][col] = 1 - mat[row + 1][col];
39 }
40 if (row - 1 >= 0) {
41 mat[row - 1][col] = 1 - mat[row - 1][col];
42 }
43 if (col + 1 < cols) {
44 mat[row][col + 1] = 1 - mat[row][col + 1];
45 }
46 if (col - 1 >= 0) {
47 mat[row][col - 1] = 1 - mat[row][col - 1];
48 }
49 }
50
51 private boolean check(int[][] mat) {
52 for (int i = 0; i < mat.length; i++) {
53 for (int j = 0; j < mat[0].length; j++) {
54 if (mat[i][j] == 1) {
55 return false;
56 }
57 }
58 }
59
60 return true;
61 }
62}