Re: [閒聊] 每日leetcode已回收
https://leetcode.com/problems/the-number-of-beautiful-subsets/description
2597. The Number of Beautiful Subsets
給你一個陣列表示一個集合和一個數字k，求出美麗子集數量，美麗子集是一個非空子集合
，所有子集元素彼此相差絕對值不會等於k。
思路：
1.回溯法，每次把元素加到當前子集前先檢查是否包含+k或-k，沒有才加。
py code:
--------------------------------------
class Solution:
def beautifulSubsets(self, nums: List[int], k: int) -> int:
self.res = 0
n = len(nums)
mp = defaultdict(int)
def dfs(start: int):
if mp:
self.res += 1
for i in range(start, n):
if mp[nums[i] - k] <= 0 and mp[nums[i] + k] <= 0:
mp[nums[i]] += 1
dfs(i + 1)
mp[nums[i]] -= 1
dfs(0)
return self.res
--------------------------------------
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 122.100.73.13 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1716430098.A.237.html
※ 編輯: Rushia (122.100.73.13 臺灣), 05/23/2024 10:09:09
推
05/23 10:16,
1年前
, 1F
05/23 10:16, 1F
推
05/23 10:20,
1年前
, 2F
05/23 10:20, 2F
→
05/23 10:23,
1年前
, 3F
05/23 10:23, 3F
推
05/23 14:24,
1年前
, 4F
05/23 14:24, 4F
討論串 (同標題文章)
以下文章回應了本文 (最舊先)：
完整討論串 (本文為第 265 之 1550 篇)：