推 wu10200512: 一早就在卷 05/23 10:16
推 digua: 大師 05/23 10:20
→ DJYOSHITAKA: 別捲了 05/23 10:23
推 orangeNoob: 別捲了 05/23 14:24
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