題目出處

難度

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

[Python3] DFS