题目： 1103.分糖果2

题面

排排坐，分糖果。

我们买了一些糖果 candies，打算把它们分给排好队的 n = num_people 个小朋友。

给第一个小朋友 1 颗糖果，第二个小朋友 2 颗，依此类推，直到给最后一个小朋友 n 颗糖果。

然后，我们再回到队伍的起点，给第一个小朋友 n + 1 颗糖果，第二个小朋友 n + 2 颗，依此类推，直到给最后一个小朋友 2 * n 颗糖果。

重复上述过程（每次都比上一次多给出一颗糖果，当到达队伍终点后再次从队伍起点开始），直到我们分完所有的糖果。注意，就算我们手中的剩下糖果数不够（不比前一次发出的糖果多），这些糖果也会全部发给当前的小朋友。

返回一个长度为 num_people、元素之和为 candies 的数组，以表示糖果的最终分发情况（即 ans[i] 表示第 i 个小朋友分到的糖果数）。

示例

示例 1：
输入：candies = 7, num_people = 4
输出：[1,2,3,1]
解释：
第一次，ans[0] += 1，数组变为 [1,0,0,0]。
第二次，ans[1] += 2，数组变为 [1,2,0,0]。
第三次，ans[2] += 3，数组变为 [1,2,3,0]。
第四次，ans[3] += 1（因为此时只剩下 1 颗糖果），最终数组变为 [1,2,3,1]。

Tips

1 <= candies <= 10^9
1 <= num_people <= 1000

Code

代码解释

这段 C++ 代码的目的是计算一个整数向量 nums 中，将所有非零元素变为 0 所需的最小操作次数。每次操作可以选择一个正整数 x，然后将 nums 中所有大于或等于 x 的元素减去 x。最终，这个问题可以转化为计算 nums 中不同非零整数的数量。

原始代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int minimumOperations(vector<int>& nums) {
        vector<bool> dic(101, 0);
        int len = nums.size();
        for(int i = 0; i < len; i++){
            dic[nums[i]] = 1;
        }
        int res = 0;
        for(int i = 1; i < 101; i++){
            if(dic[i] == 1){
                res++;
            }
        }
        return res;
    }
};

逐行解释

1
2
class Solution {
public:
  • 这是 C++ 类 Solution 的定义开始，这是编程竞赛和平台（如 LeetCode）上常用的代码结构，用来封装解决方案。
1
int minimumOperations(vector<int>& nums) {
  • 定义了一个公共成员函数 minimumOperations，它接收一个整数向量 nums 作为引用参数，并返回一个整数结果。函数的目的是计算将 nums 中所有非零元素变为 0 所需的最小操作次数。
1
vector<bool> dic(101, 0);
  • 定义了一个大小为 101 的布尔类型向量 dic，并初始化为 0。这个向量用于记录 nums 中出现的数字，假设 nums 中的数字范围是 0 到 100。
1
int len = nums.size();
  • 获取 nums 向量的大小，并将其存储在 len 变量中。
1
2
3
for(int i = 0; i < len; i++){
    dic[nums[i]] = 1;
}
  • 这个 for 循环遍历 nums 向量的每一个元素。对于每个 nums[i]，将 dic[nums[i]] 设置为 1，表示该数字在 nums 中出现过。
1
int res = 0;
  • 定义了一个整数变量 res，并将其初始化为 0。这个变量将用于计数 nums 中不同非零整数的数量。
1
2
3
4
5
for(int i = 1; i < 101; i++){
    if(dic[i] == 1){
        res++;
    }
}
  • 这个 for 循环遍历从 1 到 100 的所有整数。对于每一个 i，如果 dic[i] 的值为 1，说明该整数在 nums 中出现过，则将 res 递增 1。这个过程计算了 nums 中不同非零整数的数量。
1
2
3
        return res;
    }
};
  • 最后，函数返回 res 的值，即 nums 向量中不同非零整数的数量。这个数量代表将 nums 中所有非零元素变为 0 所需的最少操作次数。类定义在此结束。

代码总结

这段代码的核心逻辑是使用布尔向量 dic 来记录 nums 中出现的每个非零整数，然后通过遍历 dic 来计算不同非零整数的数量。
这些不同的非零整数即表示需要进行的最小操作次数。代码的时间复杂度为 O(n)，其中 n 是 nums 向量的长度；
空间复杂度为 O(1)，因为 dic 向量的大小是固定的。