Algorithm
lc368_最大整除子集
思路:
感觉像素数集合，就是把所有数字取模到同一个素数集合中，最后返回最大的。有1加1。
但是素数集有点大，而且不太合题意，被cursor直接提醒了用dp记录了…cursor应该集成了题库。
这里是每次都 prev 更新路径，也可以直接先找到对应的长度和数字，然后一次遍历 prev 路径。
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
|
impl Solution {
pub fn largest_divisible_subset(nums: Vec<i32>) -> Vec<i32> {
let mut nums = nums;
nums.sort_unstable();
let n = nums.len();
// dp[i] 表示以 nums[i] 结尾的最大整除子集的大小
let mut dp = vec![1; n];
// prev[i] 记录前一个元素的索引，用于重建子集
let mut prev = vec![-1; n];
let mut max_size = 0;
let mut max_index = 0;
for i in 0..n {
for j in 0..i {
// 如果 nums[i] 能被 nums[j] 整除，则可以将 nums[i] 加入到以 nums[j] 结尾的子集中
if nums[i] % nums[j] == 0 && dp[j] + 1 > dp[i] {
dp[i] = dp[j] + 1;
prev[i] = j as i32;
}
}
// 更新最大子集的大小和结束索引
if dp[i] > max_size {
max_size = dp[i];
max_index = i;
}
}
// 重建最大整除子集
let mut result = Vec::new();
let mut i = max_index as i32;
while i >= 0 {
result.push(nums[i as usize]);
i = prev[i as usize];
}
// 由于我们是从后往前构建的，需要反转结果
result.reverse();
result
}
}
|
Review
拥抱你的创造力！【TED演讲】
Embrace Your Love, Talk to someone, Do something you want to do.
不要被习惯和世俗束缚，做想做的事，就能释放原本就有的创造力。
经过思考的人生，才是感到治愈,感动和不后悔的人生。
Tip
PPP Vs PvP
Share
Jupiter介绍分享