Chrome Pointer

2024年6月28日 星期五

Trees / Sorting and Searching Pyhton - LeetCode

Binary Tree

  Maximum Depth of Binary Tree


class Solution: def maxDepth(self, root: Optional[TreeNode]) -> int: # Input: root = [3,9,20,null,null,15,7] # Output: 3 if root==None: return 0 left = self.maxDepth(root.left) right = self.maxDepth(root.right) return max(left,right)+1 


AttributeError: 'NoneType' object has no attribute 'left'
                         ^^^^^^^^^

💓這個錯誤是因為在樹的葉子節點上，你試圖訪問 NoneType 的屬性。當 root 是 None 時，它沒有屬性 left 和 right。為了解決這個問題，你需要在遞迴調用之前檢查 root 是否為 None。

在這段程式碼中，我們首先檢查 root 是否為 None，如果是，則直接返回 0，表示這棵樹的深度為 0。這樣可以避免在 root 為 None 時，試圖訪問其屬性而引發的錯誤。

💓因為 root 是 Optional[TreeNode]，這表示 root 可以是 TreeNode 類型或 None。在傳值的時候，可以直接傳遞 root.left 或 root.right，因為它們也是 Optional[TreeNode] 類型。

💓這種解法稱為「遞迴」（Recursive）。遞迴是一種在函數內部調用自身的技術，用於解決問題的某些部分可以表述為更小的相同問題。例如，計算二元樹的最大深度這個問題，可以分解為計算其左子樹和右子樹的最大深度，然後取兩者中的較大者加1。這樣的問題可以通過遞迴來有效地解決。

  Validate Binary Search Tree

class Solution:
    def isValidBST(self, root: Optional[TreeNode]) -> bool:

        def vai(node,low=float("-inf"),high=float("inf")):
            if node==None:
                return True
            
            left = vai(node.left,low,node.val)
            right = vai(node.right,node.val,high)
            
            if node.val>low and node.val<high:
                if left and right:
                    return True
                else:
                    return False
            
        return vai(root)

class Solution: def isValidBST(self, root: Optional[TreeNode]) -> bool: # Input: root = [2,1,3] # Output: true def validate(node, low=float('-inf'), high=float('inf')): if node==None: return True else: left = validate(node.left,low,node.val) right = validate(node.right,node.val,high) if node.val<=low or node.val>=high: return False if left and right: return True else: return False return validate(root)

在 Python 中，float('-inf') 和 float('inf') 分別表示負無窮大和正無窮大。這些值用於在初始調用時設定二元樹的節點值範圍，以確保所有節點值都在這些範圍內。

具體來說：

  • low=float('-inf')：表示節點值下限為負無窮大。初始時，根節點的值可以是任意的，因此沒有實際的下限約束。
  • high=float('inf')：表示節點值上限為正無窮大。初始時，根節點的值可以是任意的，因此沒有實際的上限約束。
AttributeError: 'Solution' object has no attribute 'validate'
           ^^^^^^^^^^^^^
    left = self.validate(root.left,low,root.val)

在你的程式碼中，validate 是一個內部函數，它僅在 isValidBST 方法的範圍內可見。當你在內部函數中使用 self.validate 時，它試圖訪問 Solution 類中的 validate 方法，但這個方法並不存在，因此會引發 AttributeError。

解決這個問題的方法是直接調用內部函數 validate，而不是通過 self。

我們直接在 validate 函數內部調用它自己，而不是通過 self。這樣可以避免 AttributeError 並正確執行檢查。

left = validate(root.left,low,root.val)

另外，我們將 root 參數改名為 node 以避免與外部變數重名，使得程式碼更加清晰。


  Symmetric Tree

我的寫法

class Solution: def isSymmetric(self, root: Optional[TreeNode]) -> bool: # Input: root = [1,2,2,3,4,4,3] # Output: true def ismirror(node,left:Optional[TreeNode],right:Optional[TreeNode]): if node==None: return True else: if left==None and right==None: return True elif left==None or right==None: return False if left.val==right.val: left_recursive = ismirror(left, left.left, right.right) right_recursive = ismirror(right, left.right, right.left) if left_recursive and right_recursive: return True else: return False return ismirror(root,root.left,root.right)

另一種寫法

class Solution:
    def isSymmetric(self, root: Optional[TreeNode]) -> bool:
        def isMirror(left: Optional[TreeNode], right: Optional[TreeNode]) -> bool:
            if not left and not right:
                return True
            if not left or not right:
                return False
            return (left.val == right.val and 
                    isMirror(left.left, right.right) and 
                    isMirror(left.right, right.left))
        
        if not root:
            return True
        return isMirror(root.left, root.right)

遞迴方法(recursion)通過比較樹的左子樹和右子樹來檢查樹是否對稱。我們定義一個輔助函數 isMirror，這個函數比較兩個節點及其子節點。


  Merge Sorted Array

錯誤寫法

class Solution: def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None: """ Do not return anything, modify nums1 in-place instead. """ # Input: nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3 # Output: [1,2,2,3,5,6] n1= nums1 n2= nums2 for i in range(m,len(nums1)): n1[i]=n2[i-m] nums1 = sorted(n1) print(nums1)

Q: 為何這樣會不行? 是因為in-place嗎?

是的，這段程式碼之所以不適用於這個問題，主要問題在於 nums1 = sorted(n1) 這行程式碼。

在 Python 中，變數 nums1 是一個指向 List[int] 的引用。當你寫 nums1 = sorted(n1) 時，這會將 nums1 指向一個新的排序後的列表，而不是修改原始的 nums1。這樣做並不符合題目要求的 in-place 修改 nums1。

題目要求我們直接修改 nums1，而不是返回一個新的排序後的列表。因此，我們必須在原地修改 nums1 的元素，而不是創建新的列表並賦值給 nums1。

正確的方法是使用雙指針法，從後往前合併 nums1 和 nums2，這樣可以保證在不需要額外空間的情況下進行合併。這種方法的時間複雜度為 O(m + n)，符合題目的要求。

正確寫法

class Solution: def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None: """ Do not return anything, modify nums1 in-place instead. """ # Input: nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3 # Output: [1,2,2,3,5,6] # 初始化三個指針 p1 = m - 1 # nums1 的最後一個有效元素的索引 p2 = n - 1 # nums2 的最後一個元素的索引 p = m + n - 1 # 合併後的最後一個位置的索引 # 從後往前合併 nums1 和 nums2 while p1 >= 0 and p2 >= 0: if nums1[p1] > nums2[p2]: nums1[p] = nums1[p1] p1 -= 1 else: nums1[p] = nums2[p2] p2 -= 1 p -= 1 # 如果 nums2 還有剩餘的元素，則直接放入 nums1 中 nums1[:p2 + 1] = nums2[:p2 + 1]


nums1[:p2 + 1] = nums2[:p2 + 1]

這行程式碼的目的是將 nums2 中的元素複製到 nums1 中。這裡用到了 Python 中的切片操作：

  • nums2[:p2 + 1] 表示從 nums2 中取出索引從 0 到 p2 的元素，這裡的 p2 是 nums2 的最後一個有效元素的索引。
  • nums1[:p2 + 1] 表示將 nums2[:p2 + 1] 複製到 nums1 中，從索引 0 到 p2 的位置。

這樣做的效果是將 nums2 中的元素從索引 0 到 p2 複製到 nums1 中對應的位置，這是合併操作中的一部分，確保所有的元素都能被放入合併後的 nums1 中。

如果你希望用 for 迴圈來達到相同的效果，可以這樣做：

# 假設 p2 是 nums2 的最後一個元素的索引
for i in range(p2 + 1):
    nums1[i] = nums2[i]

這段程式碼中的 for 迴圈遍歷 nums2 中索引從 0 到 p2 的範圍，並將每個元素逐一複製到 nums1 的相應位置。這樣也能達到將 nums2 中的元素複製到 nums1 的目的。

讓我們來詳細分析兩種方法的差異：

  1. 切片方式 (nums1[:p2 + 1] = nums2[:p2 + 1])：

    • 時間複雜度： 這個操作的時間複雜度是 O(p2 + 1)，因為它僅僅是將 nums2 中的一部分元素複製到 nums1 中。這個操作是非常高效的，因為它是在一個步驟中完成的。
    • 空間複雜度： 使用切片方式不需要額外的空間，因為它是在原地修改 nums1 的內容。

  2. for 迴圈方式 (for i in range(p2 + 1): nums1[i] = nums2[i])：

    • 時間複雜度： 這個操作的時間複雜度也是 O(p2 + 1)，因為它需要遍歷 nums2 中的元素，並逐個將其複製到 nums1 中。
    • 空間複雜度： 使用 for 迴圈方式同樣不需要額外的空間，因為它也是在原地修改 nums1 的內容。

從上述分析可以看出，兩種方式的時間複雜度是相同的，都是 O(p2 + 1)，但切片方式在實際操作中更加簡潔和直觀，也更容易理解。此外，切片操作可能會受到 Python 解釋器的優化，執行速度可能會比顯式的 for 迴圈方式稍快一些。

總結來說，雖然兩種方式的效果是一樣的，但從效率和代碼簡潔性來看，切片方式 nums1[:p2 + 1] = nums2[:p2 + 1] 通常會更好。

Input

[0]
0
[1]
1

讓我們來檢查一下你提到的情況：

  • nums1 = [0]
  • m = 0
  • nums2 = [1]
  • n = 1

根據你的描述，你可能期望的情況是將 nums2 中的元素 [1] 複製到 nums1 中。然而，如果直接使用 nums1[:p2 + 1] = nums2[:p2 + 1] 的方式，其中 p2 是 nums2 的最後一個元素的索引，它是 0。這會將 nums2[:0 + 1] 即 [1] 的元素複製到 nums1 中。

  First Bad Version

錯誤寫法: 超時

class Solution: def firstBadVersion(self, n: int) -> int: for i in range(1,n+1): consider=isBadVersion(i) # print(consider) if consider==True: return i

Submission Result: Time Limit Exceeded More Details 

Last executed input:2126753390 1702766719





讓我們來解釋一下對數的概念，特別是以2為底的對數，即log₂ n。

  1. 對數的基本概念： 對數是一個數學概念，用來描述某個數字需要以某個底數為幾次方才能得到該數字。以2為底的對數（log₂ n）就是找到某個數字 n，使得2的幾次方等於 n。例如：

    • log₂ 1 = 0，因為2⁰ = 1。
    • log₂ 2 = 1，因為2¹ = 2。
    • log₂ 4 = 2，因為2² = 4。
    • log₂ 8 = 3，因為2³ = 8。
    • 以此類推。

  2. 對數的特性：

    • 對數的值隨著 n 的增加而增加，但增長速率是緩慢的。舉例來說，當 n 從 1 增加到 2 時，log₂ n 從 0 增加到 1；當 n 從 2 增加到 4 時，log₂ n 從 1 增加到 2，以此類推。
    • 以2為底的對數在計算機科學中非常常見，因為許多算法的時間複雜度可以用 log₂ n 表示，例如二分搜尋、堆積排序等。

  3. 在算法中的應用：

    • 當我們說某個算法的時間複雜度為 O(log n) 時，意味著這個算法的執行時間隨著輸入規模 n 的增加而增加，但增長速率是對數級別的，這通常意味著效率比線性增長更高。
    • 例如，在二分搜尋算法中，每一步都能將搜索範圍減半，這樣的效率使得它在大量數據中快速地找到目標。

  4. 簡單的例子： 假設我們有一個數字為 8 的問題，那麼以2為底数的对数为3

當我們說某個算法的時間複雜度是 O(log n) 時，這意味著該算法的執行時間隨著輸入規模 n 的增加而增加，但是增長速率是對數級別的。這裡的「對數級別」指的是以某個底數（通常是2）為基數的對數函數，例如 log₂ n。

為什麼這樣的算法效率比線性增長更高呢？主要有兩個關鍵點：

  1. 增長速率較慢：

    • 對數函數的增長速率比線性函數慢。舉例來說，當 n 從 1 增加到 2 時，對數函數 log n 只增加了一個單位；當 n 從 100 增加到 200 時，log n 也只增加了一個單位。這與線性函數 n 的增長相比顯得非常緩慢。

  2. 對大規模問題的效能提升顯著：

    • 當處理大量數據時，對數時間複雜度的算法能夠在每次操作中快速地將問題規模減半或接近減半，例如二分搜尋。這種特性使得對數級別的算法在處理大型數據集時能夠顯著地減少所需的操作次數，從而提高效率。

總結來說，對數級別的時間複雜度通常意味著算法在處理大規模數據時能夠更有效率地完成任務，因為它們的增長速率遠低於線性增長，從而在時間和資源上節省成本。


一般情況下，當我們說「log n」時，通常指的是以2為底的對數函數，即log₂ n。

在數學和計算機科學的文獻中，如果沒有特別指明底數，通常預設為2。這是由於計算機系統中二進制的性質所決定的，許多算法和數據結構的分析都使用以2為底的對數。

如果有其他底數的情況，通常會明確標示，例如：

  • log₁₀ n：以10為底的對數。

解題思路

由於需要盡量減少 API 的調用次數，可以使用二分搜尋法來解決這個問題。二分搜尋法可以有效地將查找範圍減半，從而達到減少調用次數的目的。

二分搜尋法步驟

  1. 初始化左右邊界，left 設為 1，right 設為 n。
  2. 當 left 小於 right 時進行迴圈：
    • 計算中間點 mid。
    • 如果 isBadVersion(mid) 為 true，則壞版本在 mid 或之前，將 right 設為 mid。
    • 否則，壞版本在 mid 之後，將 left 設為 mid + 1。
  3. 當 left 等於 right 時，返回 left 或 right，此時即為第一個壞版本。

以下是 Python 程式碼實現：

def firstBadVersion(n):
    left, right = 1, n
    while left < right:
        mid = left + (right - left) // 2
        if isBadVersion(mid):
            right = mid
        else:
            left = mid + 1
    return left

這樣的實現能夠有效地找到第一個壞版本，並且盡量減少調用 isBadVersion API 的次數。

詳細步驟解釋

初始化

首先，我們需要設定左右兩個邊界：

  • left 設為 1，表示版本的起始位置。
  • right 設為 n，表示版本的結束位置。

這是因為我們要在版本 1 到版本 n 之間進行搜尋。


left, right = 1, n

進行二分搜尋

接著，我們使用 while left < right 的迴圈進行二分搜尋。當 left 小於 right 時，迴圈會一直執行，直到找到第一個壞版本。


while left < right:

計算中間點

在每次迴圈中，我們計算中間點 mid。這裡使用 mid = left + (right - left) // 2 來避免直接 (left + right) // 2 可能出現的整數溢出問題。


mid = left + (right - left) // 2

檢查中間點是否為壞版本

使用 isBadVersion(mid) 函數檢查中間點是否為壞版本：

  • 如果 isBadVersion(mid) 返回 true，說明 mid 這個版本以及它後面的版本都是壞的。所以我們將 right 設為 mid，繼續在 left 和 mid 之間尋找第一個壞版本。

if isBadVersion(mid):
    right = mid
  • 如果 isBadVersion(mid) 返回 false，說明 mid 這個版本是好的，第一個壞版本一定在 mid 的後面。所以我們將 left 設為 mid + 1，繼續在 mid + 1 和 right 之間尋找。

else:
    left = mid + 1

結束條件

當 left 等於 right 時，迴圈結束，這時候 left 或 right 都指向第一個壞版本。我們返回 left 即可。

return left

為什麼這樣做有效？

這個方法有效是因為二分搜尋法可以每次將搜索範圍減半，從而大幅減少需要檢查的版本數量。這樣能夠在 O(log n) 的時間複雜度內找到第一個壞版本，確保解法在處理大規模輸入時也能高效運行。

希望這樣的解釋能幫助你更好地理解這個問題的解法。

https://blog.huli.tw/2016/09/23/binary-search-introduction/


為何二分搜尋要 mid = left + (right - left) // 2 而不是mid = (right + left) // 2 ?

在二分搜尋中，mid = left + (right - left) // 2 與 mid = (right + left) // 2 的差異主要在於防止整數溢位（Integer Overflow）。

當 right 和 left 的值都非常大時，right + left 的值可能會超過整數的表示範圍，導致溢位錯誤。但如果使用 left + (right - left) // 2，這個公式會先計算 right - left，這個值通常會比 right 或 left 小很多，然後再加上 left，這樣就避免了溢位的風險。

具體來說，假設有以下的情況：

  • left = 2147483640
  • right = 2147483647

如果使用 mid = (right + left) // 2，會計算 2147483647 + 2147483640 = 4294967287，這個值超過了 32 位整數的範圍，會導致溢位。

但如果使用 mid = left + (right - left) // 2，會先計算 right - left = 2147483647 - 2147483640 = 7，然後再加上 left，得到 2147483640 + 7 = 2147483643，這樣就避免了溢位問題。

因此，為了安全起見和避免潛在的整數溢位，通常會使用 mid = left + (right - left) // 2 而不是 mid = (right + left) // 2。

mid = left + (right - left) // 2 和 mid = (right + left) // 2為何出來的mid數字會是一樣的?

mid = left + (right - left) // 2 和 mid = (right + left) // 2 這兩個公式在沒有整數溢位的情況下，計算出來的 mid 數字確實是一樣的。讓我們來詳細解析一下這兩個公式：

  1. mid = left + (right - left) // 2：

    • 先計算 right - left。
    • 然後將這個結果整數除以 2。
    • 最後將這個結果加上 left。

  2. mid = (right + left) // 2：

    • 先計算 right + left。
    • 然後將這個結果整數除以 2。

我們可以用代數的方法來看這兩個公式：

公式 1: mid = left + (right - left) // 2

mid = left + (right - left) // 2
    = left + (right // 2 - left // 2)
    = (2 * left + right - left) // 2
    = (left + right) // 2

公式 2: mid = (right + left) // 2

mid = (right + left) // 2

可以看出這兩個公式本質上是等價的，在沒有整數溢位的情況下，計算出來的 mid 是一樣的。

但正如前面所提到的，mid = left + (right - left) // 2 的寫法可以避免在 right 和 left 非常大時出現整數溢位的問題。這是為什麼我們在實際編程中更傾向於使用這個寫法，而不是直接使用 mid = (right + left) // 2。


// 無條件捨去

// 是無條件捨去（floor division），會將結果向下取整。如果需要四捨五入，可以使用內建的 round() 函數。

  1. 無條件捨去：
result = 7 // 2
print(result)  # 輸出 3
  1. 四捨五入：
result = round(7 / 2)
print(result)  # 輸出 4

    3.浮點數：
# 使用浮點數除法
result = 7 / 2
print(result)  # 輸出 3.5

これは小さな秘密で、見せたくないです

d475ef7a-9cc1-4f08-92b6-75153a284a26





By at 沒有留言:
訂閱： 文章 (Atom)

事事順心
心想事成