Re: [閒聊] 每日leetcode已回收
※ 引述《Rushia (早瀬ユウカの体操服 )》之銘言：
: https://leetcode.com/problems/the-number-of-beautiful-subsets/description
: 2597. The Number of Beautiful Subsets
: 給你一個陣列表示一個集合和一個數字k，求出美麗子集數量，美麗子集是一個非空子集合
: ，所有子集元素彼此相差絕對值不會等於k。
:
: 思路：
: 1.回溯法，每次把元素加到當前子集前先檢查是否包含+k或-k，沒有才加。
中間的部分是用別人的方法
我本來的code一直卡在其中一個Test Case
這輩子就這樣了
Code:
impl Solution {
pub fn beautiful_subsets(mut nums: Vec<i32>, k: i32) -> i32 {
nums.sort_unstable();
let n = nums.len();
fn solve(nums: &Vec<i32>, k: i32, i: usize, subset: u32) -> i32 {
if i == nums.len() {
return 1;
}
let mut ans = 0;
let mut skip = false;
for j in 0..i {
if (subset & (1 << j)) != 0 {
if (nums[i] - nums[j]).abs() as i32 == k {
skip = true;
break;
}
}
}
if !skip {
ans += solve(nums, k, i + 1, subset | (1 << i));
}
ans += solve(nums, k, i + 1, subset);
ans
}
solve(&nums, k, 0, 0) - 1
}
}
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 60.248.143.163 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1716449881.A.4AA.html
→
05/23 15:38,
1年前
, 1F
05/23 15:38, 1F
→
05/23 15:40,
1年前
, 2F
05/23 15:40, 2F
→
05/23 15:40,
1年前
, 3F
05/23 15:40, 3F
→
05/23 15:41,
1年前
, 4F
05/23 15:41, 4F
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 267 之 1550 篇)：