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 : -------------------------------------- 思路差不多 不過我速度慢很多 應該是檢查k那邊有差 Python Code: class Solution: def beautifulSubsets(self, nums: List[int], k: int) -> int: def backtrack(state,start): nonlocal res for i in range(start,len(nums)): if check(state,nums[i]): state.append(nums[i]) backtrack(state,i+1) state.pop() if state: res += 1 def check(state,num): for n in state: if num - n == k or num - n == -k: return False return True res = 0 backtrack([],0) return res --
※ 批踢踢實業坊(ptt.cc), 來自: 140.119.235.6 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1716433461.A.2B7.html