## 【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比較便宜~
按右上帳號圖
* 
* 
中國版題目也能中英隨時切換 :+1:
下次登入時，選最下面【已有美國版帳號】
### 【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))
```
Sign in with Wallet
Connect another wallet