leetcode刷题,使用python
1, 相同的树—— 0110 递归 自顶向下的递归和自底向上的递归
给定一个二叉树，判断它是否是高度平衡的二叉树。
本题中，一棵高度平衡二叉树定义为：
一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。
from typing import Optional
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
# 自顶向下的递归
class Solution:
def isBalanced(self, root: Optional[TreeNode]) -> bool:
if not root:
return True
def height(root):
if not root:
return True
return max(height(root.left), height(root.right)) + 1
return abs(height(root.left) - height(root.right)) <= 1 and self.isBalanced(root.left) and self.isBalanced(root.right)
# 自底向上的递归
class Solution2:
def isBalanced(self, root: Optional[TreeNode]) -> bool:
def height(root):
if not root:
return 0
left = height(root.left)
right = height(root.right)
if left==-1 or right == -1 or abs(left-right)>1:
return -1
else:
return max(left, right) + 1
return True if height(root)>=0 else False
root = TreeNode(3)
a1 = TreeNode(9)
a2 = TreeNode(20)
a3 = TreeNode(15)
a4 = TreeNode(7)
root.left = a1
root.right = a2
a2.left = a3
a2.right = a4
S = Solution()
S2 = Solution2()
print(S.isBalanced(root))
print(S2.isBalanced(root))
2, Merge Two Sorted Lists —— 21 递归和迭代
You are given the heads of two sorted linked lists list1 and list2.
Merge the two lists in a one sorted list. The list should be made by splicing together the nodes of the first two lists.
Return the head of the merged linked list.
Example 1:
Input: list1 = [1,2,4], list2 = [1,3,4]
Output: [1,1,2,3,4,4]
Example 2:
Input: list1 = [], list2 = []
Output: []
Example 3:
Input: list1 = [], list2 = [0]
Output: [0]
from typing import List
from typing import Optional
# Definition for singly-linked list.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
# 迭代
class Solution:
def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
if not list1:
return list2
if not list2:
return list1
rest = ListNode(-1)
tmp = rest
first = list1
second = list2
ucFirst = 0
while first and second:
if first.val > second.val:
if ucFirst == 0:
ucFirst = 1
rest = tmp = second
else:
tmp.next = second
tmp = tmp.next
second = second.next
else:
if ucFirst == 0:
ucFirst = 1
rest = tmp = first
else:
tmp.next = first
tmp = tmp.next
first = first.next
if first:
tmp.next = first
if second:
tmp.next = second
return rest
# 递归
class Solution2:
def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
if not list1:
return list2
elif not list2:
return list1
elif list1.val > list2.val:
list2.next = self.mergeTwoLists(list1, list2.next)
return list2
else:
list1.next = self.mergeTwoLists(list1.next, list2)
return list1
list1 = ListNode(1)
list1.next = ListNode(2)
list1.next.next = ListNode(4)
while not list1:
print(list1.val)
list1 = list1.next
list2 = ListNode(1)
list2.next = ListNode(3)
list2.next.next = ListNode(4)
# S = Solution()
# list3 = S.mergeTwoLists(list1, list2)
#
# while list3:
# print(list3.val)
# list3 = list3.next
S2 = Solution2()
list3 = S2.mergeTwoLists(list1, list2)
while list3:
print(list3.val)
list3 = list3.next
3, Pow(x, n) —— 0050 递归
Implement pow(x, n), which calculates x raised to the power n
Example 1:
Input: x = 2.00000, n = 10
Output: 1024.00000
Example 2:
Input: x = 2.10000, n = 3
Output: 9.26100
Example 3:
Input: x = 2.00000, n = -2
Output: 0.25000
Explanation: 2-2 = 1/22 = 1/4 = 0.25
class Solution:
def quick_pow(self, x:float, n:int):
if n == 0:
return 1
y = self.quick_pow(x, n//2)
return y*y if n%2==0 else y*y*x
def myPow(self, x: float, n: int) -> float:
if n == 0:
return 1
return self.quick_pow(x, n) if n >= 0 else 1.0 /self.quick_pow(x, -n)
S = Solution()
print(S.myPow(2, -2))
4, Remove Linked List Elements —— 203 递归
Given the head of a linked list and an integer val, remove all the nodes of the linked list that has Node.val == val, and return the new head.
Example 1:
Input: head = [1,2,6,3,4,5,6], val = 6
Output: [1,2,3,4,5]
Example 2:
Input: head = [], val = 1
Output: []
Example 3:
Input: head = [7,7,7,7], val = 7
Output: []
from typing import List, Optional
# Definition for singly-linked list.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution:
def removeElements(self, head: Optional[ListNode], val: int) -> Optional[ListNode]:
if head is None:
return None
head.next = self.removeElements(head.next, val)
if head.val == val:
return head.next
else:
return head
S = Solution()
a0 = ListNode(1)
a1 = ListNode(2)
a2 = ListNode(6)
a3 = ListNode(3)
a4 = ListNode(4)
a5 = ListNode(5)
a6 = ListNode(6)
a0.next = a1
a1.next = a2
a2.next = a3
a3.next = a4
a4.next = a5
a5.next = a6
S.removeElements(a0, 6)
p = a0
while p is not None:
print(p.val)
p = p.next
5, Reverse Linked List —— 206 递归
Given the head of a singly linked list, reverse the list, and return the reversed list.
from typing import List, Optional
# Definition for singly-linked list.
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 or not head.next:
return head
tail = self.reverseList(head.next)
head.next.next = head
head.next = None
return tail
S = Solution()
a0 = ListNode(1)
a1 = ListNode(2)
a0.next = a1
p = S.reverseList(a0)
while p is not None:
print(p.val)
p = p.next
6, Power of Two —— 231 递归
Given an integer n, return true if it is a power of two. Otherwise, return false.
An integer n is a power of two, if there exists an integer x such that n == 2x.
Example 1:
Input: n = 1
Output: true
Explanation: 20 = 1
Example 2:
Input: n = 16
Output: true
Explanation: 24 = 16
Example 3:
Input: n = 3
Output: false
class Solution:
def isPowerOfTwo(self, n: int) -> bool:
if n == 1:
return True
elif n%2==1 or n==0:
return False
else:
return self.isPowerOfTwo(n//2)
S = Solution()
print(S.isPowerOfTwo(3))
7, Palindrome Linked List —— 234 递归
Given the head of a singly linked list, return true if it is a palindrome or false otherwise
# # Definition for singly-linked list.
from typing import Optional
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]:
# cur指向当前节点，pre指向前驱节点
cur = head
pre = None
while cur:
tmp = cur.next # 暂存next节点，因为该位置即将存放pre指向的数据
cur.next = pre
pre = cur
cur = tmp
return pre # 当while循环结束，cur为空即走到了最后，此时pre为转置后的头结点
def isPalindrome(self, head: Optional[ListNode]) -> bool:
# 如果链表为空或只有一个节点，则直接返回True
if not head or not head.next:
return True
fast, slow = head, head
# 快慢指针
while True:
if not fast.next: # 节点数为奇数，此时慢指针刚好到后半链表的第一个
break
elif not fast.next.next:
slow = slow.next # 节点数为偶数，此时慢指针还需要走一步才到后半链表的第一个
break
fast = fast.next.next
slow = slow.next
# 比较前半部分和反转后的后半部分是否相同
left = head
right = self.reverseList(slow)
while right:
if left.val != right.val:
return False
left = left.next
right = right.next
# 检查是否已经完全遍历了前半部分链表，并且后半部分链表也遍历完了
return True
# 示例使用
s = Solution()
# 构造一个链表 1 -> 2 -> 3 -> 2 -> 1
head = ListNode(1)
head.next = ListNode(2)
head.next.next = ListNode(3)
head.next.next.next = ListNode(2)
head.next.next.next.next = ListNode(1)
# 判断链表是否是回文链表
print(s.isPalindrome(head)) # 输出: True
head = ListNode(1)
head.next = ListNode(2)
head.next.next = ListNode(2)
head.next.next.next = ListNode(1)
print(s.isPalindrome(head)) # 输出: True
head = ListNode(1)
head.next = ListNode(0)
head.next.next = ListNode(1)
print(s.isPalindrome(head)) # 输出: True
8, Reorder List —— 143
You are given the head of a singly linked-list. The list can be represented as:
Reorder the list to be on the following form:
You may not modify the values in the list's nodes. Only nodes themselves may be changed.
Example 1:
Input: head = [1,2,3,4]
Output: [1,4,2,3]
Example 2:
Input: head = [1,2,3,4,5]
Output: [1,5,2,4,3]
from typing import Optional
# Definition for singly-linked list.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution:
def reorderList(self, head: Optional[ListNode]) -> None:
if head is None or head.next is None or head.next.next is None:
return head
fast, slow = head, head
prev_slow = head
# 快慢指针
while True:
if not fast.next: # 节点数为奇数，此时慢指针刚好到后半链表的第一个
break
elif not fast.next.next:
prev_slow = slow
slow = slow.next # 节点数为偶数，此时慢指针还需要走一步才到后半链表的第一个
break
fast = fast.next.next
prev_slow = slow
slow = slow.next
left = head
prev_slow.next = None # 断掉前面和后面链表之间的联系
right = self.reverseList(slow)
# while slow:
# print(slow.val)
# slow = slow.next
# print("=====")
# while left:
# print(left.val)
# left = left.next
# print("=====")
# while right:
# print(right.val)
# right = right.next
right_pre = head
while left and right:
right_pre = right
node1 = left.next
node2 = right.next
left.next = right
right.next = node1
left = node1
right = node2
if right:
right_pre.next = right
return head
# 辅助函数：反转链表
def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
# cur指向当前节点，pre指向前驱节点
cur = head
pre = None
while cur:
tmp = cur.next # 暂存next节点，因为该位置即将存放pre指向的数据
cur.next = pre
pre = cur
cur = tmp
return pre # 当while循环结束，cur为空即走到了最后，此时pre为转置后的头结点
S = Solution()
head = ListNode(1)
head.next = ListNode(2)
head.next.next = ListNode(3)
head.next.next.next = ListNode(4)
result = S.reorderList(head)
print("========================")
while result:
print(result.val)
result = result.next
head = ListNode(1)
head.next = ListNode(2)
head.next.next = ListNode(3)
head.next.next.next = ListNode(4)
head.next.next.next.next = ListNode(5)
result = S.reorderList(head)
print("========================")
while result:
print(result.val)
result = result.next
9, Decode String —— 394
Given an encoded string, return its decoded string.
The encoding rule is: k[encoded_string], where the encoded_string inside the square brackets is being repeated exactly k times. Note that k is guaranteed to be a positive integer.
You may assume that the input string is always valid; there are no extra white spaces, square brackets are well-formed, etc. Furthermore, you may assume that the original data does not contain any digits and that digits are only for those repeat numbers, k. For example, there will not be input like 3a or 2[4].
The test cases are generated so that the length of the output will never exceed 105.
Example 1:
Input: s = "3[a]2[bc]"
Output: "aaabcbc"
Example 2:
Input: s = "3[a2[c]]"
Output: "accaccacc"
Example 3:
Input: s = "2[abc]3[cd]ef"
Output: "abcabccdcdcdef"
# 在遍历输入的s过程中我们使用num（string）来记录数值k，res（string）来记录输出结果（解码后的string）。
#
# 见到digits的时候累计到num中(num += digit; num为string，因为存在10以上的数值），用python内置string.isdigit()判断
# 见到"["的时候记录累计的num，以及目前为止的res（返还值string）;并清空res， num，开始处理括号内部的string
# 见到character的时候， 累计到上一步被清空过后的res中。
# 见到"]"的时候，把第三步重复累积出的res * int(num) 累计到括号之前的string上。
# 输出res结果。
class Solution:
def decodeString(self, s: str) -> str:
res = ""
stack = []
num = ""
for c in s:
if c.isdigit():
num += c
elif c == "[":
stack.append((res, num))
res, num = "", ""
elif c == "]":
tmp, num = stack.pop()
res = tmp + res * int(num)
num = ""
else:
res += c
return res
S = Solution()
print(S.decodeString("3[a]2[bc]"))
print(S.decodeString("3[a2[c]]"))
print(S.decodeString("2[abc]3[cd]ef"))
