ARST打卡第277周

lc698_划分为k个相等的子集 岱川博士_学习技巧以及知行合一理解_八成问题实践 Go语言垃圾回收指南#GOGC git log后加功能的commit可能出现在版本commit前

Algorithm

lc698_划分为k个相等的子集

思路:

先给所有的数字计数，然后再递归计算能不能凑成k组。

结果自己写得很多错误, 然后一直超时，用GPT试了一下，发现找到了我输入计数map错误，尴尬… 后面被 GPT4o 的 debug 惊艳:

https://leetcode.cn/problems/partition-to-k-equal-sum-subsets/description/?envType=daily-question&envId=2024-08-25 帮我分析这个代码为啥会超时:

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

class Solution { public: bool findSol(map<int, int>& cnt, int k, int target, int cur_term, int cur_val) { if (cur_term == k) { return true; } int rem = target - cur_val; for (auto itp = cnt.rbegin(); itp != cnt.rend(); itp--) { auto& it = *itp; // 解引用获取实际元素 if (it.first > rem || it.second == 0) continue; it.second --; cur_val += it.first; if (cur_val == target) { if (findSol(cnt, k, target, cur_term+1, 0)) return true; } else { if (findSol(cnt, k, target, cur_term, cur_val)) return true; } it.second ++; cur_val -= it.first; } return false; } bool canPartitionKSubsets(vector<int>& nums, int k) { // 这里有序map可能比无序map好点 map<int, int> cnt; int sum = 0; for (auto& num : nums) { sum += num; cnt[sum]++; } if (sum % k != 0) { return false; } int target = sum / k; return findSol(cnt, k, target, 0, 0); } };

这个代码超时的原因主要有以下几个方面：

1. 错误的累加逻辑：

在 canPartitionKSubsets 函数中，累加 nums 的时候，你直接累加了所有元素的和，并且错误地将其作为键添加到 map 中。这会导致 map 中存储的键值对根本不是 nums 中元素的频次，而是前缀和的频次，导致在查找时复杂度大大增加，并且会产生错误的结果。

2. 重复计算和回溯：

在 findSol 函数中，存在大量的重复计算和回溯，这些都极大地增加了计算时间：

• 重复尝试相同的数字组合：在当前组合不满足条件时，程序会回溯并重新尝试相同的数字组合，导致大量的重复计算。
• 剪枝不够：虽然你有检查 it.first > rem 和 it.second == 0 的剪枝条件，但是对于很多情况下，剪枝的力度还不够，仍然会导致多余的计算。

3. 使用 map 的时间复杂度问题：

map 是基于红黑树实现的，因此查找、插入和删除操作的时间复杂度为 O(log n)。在频繁进行查找和更新操作的情况下，map 的性能可能不如 unordered_map。虽然你使用 map 是为了保持元素有序，但这也增加了时间开销。

解决方案：

1. 修正 cnt 的构造：

   cnt 应该统计 nums 中每个数字的出现频次，而不是累加和。

   1 2 3 4 5 6

   map<int, int> cnt; int sum = 0; for (auto& num : nums) { sum += num; cnt[num]++; }

2. 改进剪枝：

   在递归时，应该尽可能避免重复的计算，可以通过增加额外的剪枝条件来减少冗余计算。例如，在每次尝试选择一个新的元素时，应该考虑到已经选择过的元素不要再重复选择。

3. 优化数据结构：

   可以考虑将 map 换成 unordered_map 或者直接使用 vector 来保存数字的频次，从而减少查找的时间复杂度。

改进后的代码示例：

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

class Solution { public: bool findSol(vector<int>& nums, vector<bool>& visited, int k, int target, int cur_term, int cur_val, int start) { if (cur_term == k) { return true; } if (cur_val == target) { return findSol(nums, visited, k, target, cur_term + 1, 0, 0); } for (int i = start; i < nums.size(); i++) { if (visited[i] || cur_val + nums[i] > target) continue; visited[i] = true; if (findSol(nums, visited, k, target, cur_term, cur_val + nums[i], i + 1)) return true; visited[i] = false; } return false; } bool canPartitionKSubsets(vector<int>& nums, int k) { int sum = accumulate(nums.begin(), nums.end(), 0); if (sum % k != 0) { return false; } sort(nums.rbegin(), nums.rend()); // 降序排序以便更快地剪枝 vector<bool> visited(nums.size(), false); int target = sum / k; return findSol(nums, visited, k, target, 0, 0, 0); } };

改进要点：

• visited 数组：用于标记哪些元素已经被使用，避免重复选择。
• 排序优化：先对 nums 降序排序，先选择较大的元素以提高剪枝效果。
• 减少重复计算：通过增加 start 参数，避免在同一层次的递归中重复选择相同的元素。

这个改进版本应该可以避免超时问题，同时保持正确性。

nums = [3,2,1,3,6,1,4,8,10,8,9,1,7,9,8,1] k = 9 还是超时了，分析一下复杂度

对于这个问题，时间复杂度的分析和你所使用的算法设计是至关重要的。我们来详细分析你使用的回溯算法的时间复杂度。

1. 问题规模与复杂度的关系

在回溯算法中，最坏情况下，复杂度取决于：

• n 是数组 nums 的长度。
• k 是需要分成的子集数。

在每一层递归中，你需要检查每一个未访问过的元素，并尝试将其加入当前子集中。因为你可能会尝试每一种可能的组合，最坏情况下的时间复杂度可以达到 O(k * 2^n)。

• 子集数 k：每次递归有 k 种可能（你可能把当前元素放到任何一个已有的子集中，或者开启一个新的子集）。
• 所有子集的组合：总共有 2^n 种可能的子集组合。

2. 复杂度的具体分析

即使在进行了剪枝优化后，复杂度仍然非常高。特别是在每个元素都可以尝试放入多个子集的情况下，这种组合数会导致指数级增长。

以下是详细的复杂度分析：

• 回溯的深度：对于数组中的每一个元素，都需要决定它属于哪个子集。这一过程的最坏时间复杂度为 O(2^n)。

• 每一步的操作：在每一层递归中，你需要遍历 k 个子集以决定当前元素是否可以放入某个子集中。这个步骤的复杂度是 O(k)。

• 总体复杂度：结合起来，最坏情况的复杂度为 O(k * 2^n)。

3. 在实际问题中的表现

对于你的输入：

• nums 的长度是 16。
• k 是 9。

即使 2^16 = 65536 看似不大，但乘以 k = 9，并考虑到递归中可能的重复计算和状态空间，导致超时的几率非常高。

4. 进一步优化的建议

为了减少复杂度，可以尝试以下方法：

1. 动态规划（DP） + 状态压缩：

   • 使用状态压缩来记录当前哪些元素已经被选择。
   • 使用动态规划来记忆化已经计算过的状态，从而减少重复计算。

2. 更有效的剪枝策略：

   • 优先将大的数放入子集中（已做）。
   • 如果在某一个递归状态下发现所有子集都已经尝试过且无法成功，立刻停止该路径的探索（这点你已经实现了一部分，但可以更深入优化）。

3. 预处理与早期退出：

   • 如果发现 nums 中有一个元素比目标和还大，可以直接返回 false。
   • 检查是否存在 nums 中的元素的和小于 k，如果是的话，直接返回 false。

4. 分组和排序：

   • 尝试提前将元素分组，然后排序，通过排序后的信息推断出更早退出的可能。

5. 复杂度调整后的代码实现（示例）

可以考虑一个优化的动态规划 + 状态压缩的方法来避免重复计算：

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

class Solution { public: bool canPartitionKSubsets(vector<int>& nums, int k) { int sum = accumulate(nums.begin(), nums.end(), 0); if (sum % k != 0) return false; int target = sum / k; sort(nums.rbegin(), nums.rend()); vector<int> subsets(k, 0); return backtrack(nums, subsets, target, 0); } bool backtrack(vector<int>& nums, vector<int>& subsets, int target, int index) { if (index == nums.size()) { for (int i = 0; i < subsets.size(); i++) { if (subsets[i] != target) return false; } return true; } for (int i = 0; i < subsets.size(); i++) { if (subsets[i] + nums[index] > target) continue; subsets[i] += nums[index]; if (backtrack(nums, subsets, target, index + 1)) return true; subsets[i] -= nums[index]; if (subsets[i] == 0) break; // 优化：如果当前子集为空，则跳出循环，避免冗余计算 } return false; } };

总结

即使经过优化，这类问题在最坏情况下仍然会有高时间复杂度。但通过剪枝、动态规划和状态压缩等方法，你可以显著减少实际运行时间，避免超时。

结合题解中的优化，其实还可以更快:

 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

class Solution {
public:
    bool canPartitionKSubsets(vector<int>& nums, int k) {
        int sum = accumulate(nums.begin(), nums.end(), 0);
        if (sum % k != 0) return false;
        int target = sum / k;
        sort(nums.rbegin(), nums.rend());
        if (nums.back() > target) {
            return false;
        }
        vector<int> subsets(k, 0);
        return backtrack(nums, subsets, target, 0);
    }
    
    bool backtrack(vector<int>& nums, vector<int>& subsets, int target, int index) {
        if (index == nums.size()) {
            for (int i = 0; i < subsets.size(); i++) {
                if (subsets[i] != target) return false;
            }
            return true;
        }
        for (int i = 0; i < subsets.size(); i++) {
            if (subsets[i] + nums[index] > target) continue;
            subsets[i] += nums[index];
            if (backtrack(nums, subsets, target, index + 1)) return true;
            subsets[i] -= nums[index];
            if (subsets[i] == 0) break;  // 优化：如果当前子集为空，则跳出循环，避免冗余计算
            // 这里可以理解成: 
            // k组轮流挑选，假设一轮index下来，有一组完全没挑选到合适的，直接 false.
        }
        return false;
    }
};

然后题解的状态压缩方法也值得学习.

不过试了一下，题解方法都没有递归方法速度快。

Review

岱川博士_学习技巧以及知行合一理解_八成问题实践

视频中提到学习要通过学习思考，并且更重要的是找到你八成能解决的现实问题去实践反馈。

行是知之始知是行之成，知行合一。

并且视频作者对"知"的理解更加深刻地认知为是一种"解决实际问题的能力".

Tips

Go语言垃圾回收指南#GOGC

Share

git log后加功能的commit可能出现在版本commit前

找 GPT 求证了一下:

master分钟第一天提交了A,第二天dev分支提交了B，第三天master提交了C, 并且打包发版。 第四天dev分支提交了D, 然后把dev分支合并到master分支，master分支的 git log信息是怎样的，是 A B C D ？ 还是 A C B D?

在这种情况下，git log 的顺序取决于合并的方式。如果你在第四天将 dev 分支合并到 master 分支时使用了默认的合并（即 git merge dev），通常会保留提交的时间顺序。

场景假设：

1. 第一天：master 分支提交了 A。
2. 第二天：dev 分支提交了 B。
3. 第三天：master 分支提交了 C 并发版。
4. 第四天：dev 分支提交了 D，然后将 dev 分支合并到 master 分支。

如果你执行普通的合并（non-fast-forward merge）：

• git merge dev

那么合并后的 master 分支的 git log 将显示如下（顺序从上到下表示 git log 的输出顺序）：

1. Merge commit（合并提交，记录合并了 dev 分支）
2. D（来自 dev 分支）
3. C（来自 master 分支）
4. B（来自 dev 分支）
5. A（来自 master 分支）

如果你执行重置再合并（rebase and merge）：

• git checkout master
• git rebase master dev
• git merge dev

在这种情况下，git log 的顺序可能是：

1. D
2. B
3. C
4. A

因此，git log 显示的顺序是与具体操作相关的。通常情况下，如果是普通合并，git log 会按提交时间顺序显示提交历史，时间越新的提交越靠前，最早的提交靠后。