ARST打卡第299周

2025-01-26 772 words 2 minutes

Contents

Algorithm

lc40_组合总和 II

思路:

预处理: 先剔除掉比 target 大的数字。

然后用递归遍历选与不选来获取不重复的答案集合(set维护)。每次选完之后进入下一个状态时把选择取消掉。

 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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60


impl Solution {
    pub fn combination_sum2(mut candidates: Vec<i32>, target: i32) -> Vec<Vec<i32>> {
        let mut result = vec![];
        let mut current = vec![];
        
        // 排序以便于去重和剪枝
        candidates.sort_unstable();
        
        // 递归辅助函数
        Self::backtrack(
            &candidates,
            target,
            0,
            &mut current,
            &mut result
        );
        
        result
    }
    
    fn backtrack(
        candidates: &[i32],
        remain: i32,
        start: usize,
        current: &mut Vec<i32>,
        result: &mut Vec<Vec<i32>>
    ) {
        if remain == 0 {
            result.push(current.clone());
            return;
        }
        
        for i in start..candidates.len() {
            // 剪枝：如果当前数字大于剩余目标值，后面的更大数字也不需要尝试
            if candidates[i] > remain {
                break;
            }
            
            // 去重：跳过同一层级的重复数字 (不同层级可以选相同数字，同一层级没必要)
            if i > start && candidates[i] == candidates[i-1] {
                continue;
            }
            
            // 选择当前数字
            current.push(candidates[i]);
            
            // 递归到下一层
            Self::backtrack(
                candidates,
                remain - candidates[i],
                i + 1,  // 注意这里是i+1，因为每个数字只能用一次
                current,
                result
            );
            
            // 回溯，撤销选择
            current.pop();
        }
    }
}

题解也差不多，只是去重方式不是按照层级来的，而是按照计数来实现层级的模式。

也就是计数+递归回溯。

 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
41


impl Solution {
    pub fn combination_sum2(candidates: Vec<i32>, target: i32) -> Vec<Vec<i32>> {
        let mut freq: Vec<(i32, i32)> = Vec::new();
        let mut ans: Vec<Vec<i32>> = Vec::new();
        let mut sequence: Vec<i32> = Vec::new();

        let mut candidates = candidates;
        candidates.sort();
        for &num in &candidates {
            if freq.is_empty() || num != freq.last().unwrap().0 {
                freq.push((num, 1));
            } else {
                freq.last_mut().unwrap().1 += 1;
            }
        }

        fn dfs(pos: usize, rest: i32, freq: &Vec<(i32, i32)>, sequence: &mut Vec<i32>, ans: &mut Vec<Vec<i32>>) {
            if rest == 0 {
                ans.push(sequence.clone());
                return;
            }
            if pos == freq.len() || rest < freq[pos].0 {
                return;
            }

            dfs(pos + 1, rest, freq, sequence, ans);

            let most = (rest / freq[pos].0).min(freq[pos].1);
            for i in 1..=most {
                sequence.push(freq[pos].0);
                dfs(pos + 1, rest - i * freq[pos].0, freq, sequence, ans);
            }
            for _ in 1..=most {
                sequence.pop();
            }
        }

        dfs(0, target, &freq, &mut sequence, &mut ans);
        ans
    }
}

Review

关于移民问题的讨论【TED演讲】

该视频从以下三个问题讨论移民问题

移民能否当工具？能否通过移民让国家富强？
移民是不是异己？能不能同化？
是否寄生？

分析到主要是移民没有被平等得接纳。

个人认为这种还是屁股决定脑袋的事情。本地人和移民都在争取自己的权利。

美国是个移民国家，整体的移民政策还需要听取多方意见，尽量保障基本权利。

Tips

CZ的原则

Sonic项目介绍

https://x.com/wolfdan666666/thread/1882072880047157298

Contents

ARST打卡第299周

Algorithm

Review

Tips

Share