題目出處
2261. K Divisible Elements Subarrays
難度
medium
個人範例程式碼 – 同向 two pointers, 正三角
class Solution:
def countDistinct(self, nums: List[int], k: int, p: int) -> int:
self.ans = set()
# decide start (one side)
for i in range(len(nums)):
self.dfs(nums, i, i, k, p) # decide end
# print(self.ans)
return len(self.ans)
def dfs(self, nums, start, end, k, p):
# end of recursion
if end >= len(nums):
return
# define
if nums[end] % p == 0:
k -= 1
if k < 0:
return
self.is_valid_ans(nums, start, end, k, p)
# split
self.dfs(nums, start, end+1, k, p)
def is_valid_ans(self, nums, start, end, k, p):
if k < 0:
return
subset = tuple(nums[start:end+1]) # start~end
# print(subset, k)
if subset in self.ans:
return
else:
self.ans.add(subset)
最近在練習程式碼本身就可以自解釋的 Coding style,可以嘗試直接閱讀程式碼理解
算法說明
用 dfs 搭配同向的 two pointers 控制頭尾(dfs 控制尾巴移動),組出全部的結果。
input handling
x (題目沒有特別要求要處理)
Boundary conditions
控制 recursion 結束條件 if end >= len(nums)
個人範例程式碼 – 反向 two pointers, 反三角
class Solution:
def countDistinct(self, nums: List[int], k: int, p: int) -> int:
self.ans = set()
# decide start (one side)
for i in range(len(nums)-1, -1, -1):
self.dfs(nums, i, i, k, p) # decide end
# print(self.ans)
return len(self.ans)
def dfs(self, nums, start, end, k, p):
# end of recursion
if start < 0:
return
# define
if nums[start] % p == 0:
k -= 1
if k < 0:
return
self.is_valid_ans(nums, start, end, k, p)
# split
self.dfs(nums, start-1, end, k, p)
def is_valid_ans(self, nums, start, end, k, p):
if k < 0:
return
subset = tuple(nums[start:end+1]) # start~end
# print(subset, k)
if subset in self.ans:
return
else:
self.ans.add(subset)
最近在練習程式碼本身就可以自解釋的 Coding style,可以嘗試直接閱讀程式碼理解
算法說明
用 dfs 搭配反向的 two pointers 控制頭尾(dfs 控制頭移動),組出全部的結果。
input handling
x (題目沒有特別要求要處理)
Boundary conditions
控制 recursion 結束條件 if start < 0
Reference
⭐ Leetcode 解題紀錄 ⭐ | 題型 | 資料結構 | Python Solution | C++ Solution | Note | |
---|---|---|---|---|---|---|
⭐BFS 相關題型 ⭐ | ||||||
104 | Maximum Depth of Binary Tree | BFS (分層) | Python | |||
94 | Binary Tree Inorder Traversal | BFS (分層) | Tree | Python | 內含 處理 Tree 樹問題的重點 | |
102 | Binary Tree Level Order Traversal | BFS (分層) | Tree | Python | ||
103 |