On the shoulders of giants.

weekly-contest-166

整数的各位积和之差

给你一个整数 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^5
题解

直接模拟计算。

时间复杂度:\(O(\log_{10} n)\)

class Solution {
public:
    int subtractProductAndSum(int n) {
        long long sum1 = 1, sum2 = 0;
        
        while(n) {
            sum1 *= n % 10;
            sum2 += n % 10;
            n /= 10;
        }
        
        return sum1 - sum2;
    }
};

用户分组

有 n 位用户参加活动,他们的 ID 从 0n - 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
题解

对相同个数的组,合并在一起,因为数据保证有解,所以直接暴力合并。

时间复杂度:\(O(n\log n)\)

class Solution {
public:
    vector<vector<int>> groupThePeople(vector<int>& groupSizes) {
        int n = groupSizes.size();
        vector<pair<int, int>> pos;
        vector<vector<int>> result;
        
        for(int i = 0; i < n; i++) {
            pos.push_back(make_pair(groupSizes[i], i));
        }
        
        sort(pos.begin(), pos.end());
        
        for(int i = 0; i < n; i++) {
            int m = pos[i].first;
            vector<int> ans;
            for(int j = 0; j < m; j++) {
                ans.push_back(pos[i + j].second);
            }
            result.push_back(ans);
            i += m - 1;
        }
        
        return result;
    }
};

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

给你一个整数数组 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^4
  • 1 <= nums[i] <= 10^6
  • nums.length <= threshold <= 10^6
题解

二分法:很明显,当除数增大时,求和结果单调不增,所以二分除数,求不大于 threshold 的最大值。

时间复杂度:\(O(n \log m)\)

class Solution {
public:
    int smallestDivisor(vector<int>& nums, int threshold) {
        
        int lef = 1, rig = 1E9, mid;
        
        while(lef < rig) {
            mid = lef + rig >> 1;
            
            long long sum = 0;
            for(auto x : nums) {
                sum += ceil((double)x / mid);
            }
            if(sum <= threshold) rig = mid;
            else lef = mid + 1;
        }
        
        return rig;
    }
};

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

给你一个 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 。
题解

这里给出能适合更大数据范围的题解。

枚举第一行哪些单元格要翻转,然后从第二行开始,根据上一行同一列的单元格的值,判断该单元格是否翻转,最后检查最后一行的单元格是否存在不为 0 的情况,不存在则更新答案。

时间复杂度:\(O(2^m*n*m)\)

class Solution {
public:
    int n, m, tmp[5][5], result = 1E9;
    
    int cal(int x, int y, int num) {
        int sum = num + tmp[x][y];
        if(0 <= x - 1) sum += tmp[x - 1][y];
        if(0 <= y - 1) sum += tmp[x][y - 1];
        if(y + 1 < m) sum += tmp[x][y + 1];
        return sum;
    }
    
    int minFlips(vector<vector<int>>& mat) {
        n = mat.size(), m = mat[0].size();
        
        for(int s = 0; s < (1 << m); s++) {
            int total = 0;
            memset(tmp, 0, sizeof(tmp));
            for(int i = 0; i < m; i++) {
                if((s >> i) & 1) {
                    tmp[0][i] = 1;
                    total++;
                }
            }
            for(int i = 1; i < n; i++) {
                for(int j = 0; j < m; j++) {
                    if(cal(i - 1, j, mat[i - 1][j]) & 1) {
                        tmp[i][j] = 1;
                        total++;
                    }
                }
            }
            bool flag = true;
            for(int i = 0; i < m && flag; i++) {
                if(cal(n - 1, i, mat[n - 1][i]) & 1) {
                    flag = false;
                }
            }
            if(flag) result = min(result, total);
        }
        
        if(result == 1E9) result = -1;
        
        return result;
    }
};
Share

You may also like...

发表评论

电子邮件地址不会被公开。 必填项已用*标注