項目 widget-area-1 尚未註冊或是沒有一個 view.php 檔案.
項目 widget-area-1 尚未註冊或是沒有一個 view.php 檔案.
項目 search-input 尚未註冊或是沒有一個 view.php 檔案.

【Leetcode】python – [2261] K Divisible Elements Subarrays 個人解法筆記 | 291th LeetCode Weekly Contest (內含 substring 常見作法)

題目出處

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 SolutionC++ SolutionNote
⭐BFS 相關題型 ⭐
104Maximum Depth of Binary TreeBFS (分層)Python
94Binary Tree Inorder TraversalBFS (分層)TreePython 內含 處理 Tree 樹問題的重點
102Binary Tree Level Order TraversalBFS (分層)TreePython
103