---
# System prepended metadata

title: 【Leetcode - Python Data Structure & Algorithms 刷題記錄】(processing)

---

## 【Leetcode - Python Data Structure & Algorithms 刷題記錄】
:::info
* 題名 - 主題 - 難易度

-- 【7. Reverse Integer】整数反转 - Array - Medium

-- 【125. Valid Palindrome】验证回文串 - Array - Easy

--【206. Reverse Linked List】反转链表 - Linked List - Easy

--【876. Middle of the Linked List】链表的中间结点 - Linked List - Easy

-- 【234. Palindrome Linked List】回文链表 - Linked List - Easy

-- 【155. Mini Stack】最小栈 - Stack - Medium

-- 【700. Search in a Binary Search Tree】 二叉搜索树中的搜索 - Tree - Easy

-- 【98. Validate Binary Search Tree】 验证二叉搜索树 - Tree - Medium

-- 【104. Maximum Depth of Binary Tree】 二叉树的最大深度 - Tree - Easy
:::

PS 可以刷中國版 [力扣（LeetCode）](https://leetcode.cn/)，申請和美國版 [LeetCode](https://leetcode.com/) 帳號紀錄同步，從中國版買Premiere比較便宜~

按右上帳號圖
* ![](https://hackmd.io/_uploads/Bk7Oj7u16.png)
* ![](https://hackmd.io/_uploads/HkMoh7_1a.png)

中國版題目也能中英隨時切換 :+1: 
![](https://hackmd.io/_uploads/S1l-2Q_ka.png)
![螢幕擷取畫面 2023-12-22 153326](https://hackmd.io/_uploads/S1_CihGPT.png)


下次登入時，選最下面【已有美國版帳號】
![螢幕擷取畫面 2023-12-22 153109](https://hackmd.io/_uploads/SkrnshMvT.png)


### 【7. Reverse Integer】整数反转 - Array - Medium
#### 題目
```=
Example 1:

Input: x = 123
Output: 321
Example 2:

Input: x = -123
Output: -321
Example 3:

Input: x = 120
Output: 21
```
#### 解答
我的解
```=

class Solution:
    def reverse(self, x:int) -> int:
        if (2**31 - 1) < x < -(2**31):
            return 0
        if x < 0:
            return -self.reverse(-x)
        else:
            result = 0
            while x > 0:
                result = result * 10 + x % 10
                x //= 10
            return result
        
if __name__ == "__main__":
    solution_instance = Solution()
    print(solution_instance.reverse(1230))
    print(solution_instance.reverse(-1230))
```
> 網友解
```=
class Solution:
    def reverse(self, x: int) -> int:
        INT_MAX = 2**31 - 1
        INT_MIN = -(2**31)

        if INT_MIN <= x <= INT_MAX:
            result = 0
            sign = 1 if x > 0 else -1
            x = abs(x)

            while x > 0:
                pop = x % 10
                x //= 10

                if result > (INT_MAX - pop) // 10:
                    return 0  # 溢出，返回0

                result = result * 10 + pop

            return sign * result
        else:
            return 0  # 整數超出範圍

if __name__ == "__main__":
    solution_instance = Solution()
    print(solution_instance.reverse(1230))
    print(solution_instance.reverse(-1230))
    print(solution_instance.reverse(9646324351))
```

### 【125. Valid Palindrome】验证回文串 - Palidrome - Easy
#### 題目
```=
Example 1:

Input: s = "A man, a plan, a canal: Panama"
Output: true
Explanation: "amanaplanacanalpanama" is a palindrome.
Example 2:

Input: s = "race a car"
Output: false
Explanation: "raceacar" is not a palindrome.
Example 3:

Input: s = " "
Output: true
Explanation: s is an empty string "" after removing non-alphanumeric characters.
Since an empty string reads the same forward and backward, it is a palindrome.
```
#### 解答
我的解
但我沒考慮到標點符號、大小寫
```=
class Solution:
    def isPalindrome(self, s: str) -> bool:
        start_index = 0
        end_index = len(s) - 1

        while start_index < end_index:
            if s[start_index] != s[end_index]:
                return False
            start_index += 1
            end_index -= 1
        return True

    def is_palindrome_pythonic(self, s: str) -> bool:
        return s == s[::-1]


s = "abba"
solution_instance = Solution()
print(solution_instance.isPalindrome(s))
print(solution_instance.is_palindrome_pythonic(s))
```

>網友解
```=
class Solution:
    def isPalindrome(self, s: str) -> bool:
        if len(s) == 0:
            return True
        start = 0
        end = len(s) - 1
        
        while start < end:
            while start < end and not s[start].isalnum():
                start += 1
            while start < end and not s[end].isalnum():
                end -= 1
            if s[start].lower() != s[end].lower():
                return False
            start +=1
            end -=1
        return True

# 
if __name__ == "__main__":
    s = "A man, a plan, a canal: Panama"
    solution_instance = Solution()
    print(solution_instance.isPalindrome(s))
```


<br/>

### 206. Reverse Linked List】反转链表 - Linked List - Easy
```=
输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]
```

#### 解答
我的解
```=
class ListNode:
    def_init_(self, val=0, next=None):
        self.val = val
        self.next = next

class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if not head:
            return
        if head.next == None:
            return head

        prev = None
        curr = head
        after = curr.next

        while after:
            curr.next = prev
            prev = curr
            curr = after
            after = after.next

        curr.next = prev
        return curr
```

>網友解 (用遞迴)

```=
class ListNode:
    def_init_(self, val=0, next=None):
        self.val = val
        self.next = next
        
class Solution:
    def reverseList(seLf, head: Optional[ListNode]) -> Optional[ListNode]
        if not head:
            return None
            
    new_head = head
    if head.next:
        new_head = self.reverseList(head-head.next)
        head.next.next = head
        
    head.next = None
    return new_head
```


<br/>

### 【876. Middle of the Linked List】链表的中间结点 - Linked List - Easy

```=
输入：head = [1,2,3,4,5]
输出：3

输入：head = [1,2,3,4,5,6]
输出：4
```

#### 解答
```=
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class Solution:
    def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]:
        tortoise = hare = head
        while tortoise and hare and hare.next:
            tortoise = tortoise.next
            hare = hare.next.next
        return tortoise

if __name__ == "__main__":
    solution = Solution()
    head = ListNode(1, ListNode(2, ListNode(3, ListNode(4, ListNode(5, ListNode(6))))))
    
    result = solution.middleNode(head)
    
    print(result.val)
```

<br/>

### 【234. Palindrome Linked List】回文链表 - Linked List - Easy

```=
输入：head = [1,2,2,1]
输出：true

输入：head = [1,2]
输出：false
```

#### 解答
```=
class Solution:
    def isPalindrome(self, head: Optional[ListNode]) -> bool:
       
        tortoise = hare = head
        while hare.next and hare.next.next:
            tortoise = tortoise.next
            hare = hare.next.next

        cur = tortoise.next
        pre = None
        while cur:
            after = cur.next
            cur.next = pre
            pre = cur
            cur = after

        while pre:
            if head.val != pre.val:
                return False
            pre = pre.next
            head = head.next
        return True
```

<br/>

### 【155. Mini Stack】最小栈 - Stack - Medium

```=
输入：
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]

输出：
[null,null,null,null,-3,null,0,-2]

解释：
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin();   --> 返回 -3.
minStack.pop();
minStack.top();      --> 返回 0.
minStack.getMin();   --> 返回 -2.
```

#### 解答
我的解
```=
class MinStack:

    def __init__(self):
        self.items = []

    def push(self, val: int) -> None:
        self.items.append(val)

    def pop(self) -> None:
        if len(self.items) != 0:
            return self.items.pop()

    def top(self) -> int:
        if len(self.items) != 0:
            return self.items[-1]

    def getMin(self) -> int:
        if len(self.items) != 0:
            min_int = min(self.items)
            return min_int
```

>網友解
```=
class MinStack:
    def __init__(self):
        self.stack = []
        self.min_stack = []

    def push(self, val: int) -> None:
        self.stack.append(val)

        min_tmp = min(val, self.min_stack[-1] if self.min_stack else val)
        self.min_stack.append(min_tmp)
    
    def pop(self) -> None:
        self.stack.pop()
        self.min_stack.pop()
        
    def top(self) -> int:
        return self.stack[-1]
    
    def getMin(self) -> int:
        return self.min_stack[-1]
```

<br/>

### 【700. Search in a Binary Search Tree】 二叉搜索树中的搜索 - Tree - Easy

```=
输入：root = [4,2,7,1,3], val = 2
输出：[2,1,3]

输入：root = [4,2,7,1,3], val = 5
输出：[]
```

#### 解答
```=
class Solution:
    def searchBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
        if root is None:
            return None

        if val < root.val:
            return self.searchBST(root.left, val)

        elif val > root.val: 
            return self.searchBST(root.right, val)

        elif val == root.val: 
            return root
```

<br/>

### 【98. Validate Binary Search Tree】  验证二叉搜索树 - Tree - Medium

```=
输入：root = [2,1,3]
输出：true

输入：root = [5,1,4,null,null,3,6]
输出：false
解释：根节点的值是 5 ，但是右子节点的值是 4 
```

#### 解答
我的解
```=
from typing import Optional

class TreeNode:
    def __init__(self, value=0, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right

class Solution:
    def dfs(self, node):
        results = []

        def traversal(node):
            if node.left is not None:
                traversal(node.left)
            results.append(node.val)
            if node.right is not None:
                traversal(node.right)

        traversal(node)
        return results

    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        if not root:
            return True 
        
        i = 1
        results = self.dfs(root)
        for i in range(len(results) - 1):
            if results[i] >= results[i + 1]:
                return False
        return True
```


>網友解
```=
class TreeNode:
    def __init__(self, value=0, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right

class Solution:
    def dfs(self, current_node):
        results = []

        def traversal(current_node):
            if current_node.left is not None:
                traversal(current_node.left)
            results.append(current_node.val)
            if current_node.right is not None:
                traversal(current_node.right)

        traversal(current_node)
        return results

    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        if not root:
            return True 
        
        i = 1
        flag = 1
        results = self.dfs(root)
        while i in len(results):
            if results[i] <= results[i - 1]:
                flag = 0
                break
        return True if flag==1 else False
```

<br/>

### 【104. Maximum Depth of Binary Tree】 二叉树的最大深度 - Tree - Easy

```=
输入：root = [3,9,20,null,null,15,7]
输出：3

输入：root = [1,null,2]
输出：2
```
#### 解答
```=
class Node:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
    
        if root is None:
            return 0
        
        return 1 + max(self.maxDepth(root.left), self.maxDepth(root.right))
```