python leetcode-note2
2023-05-17 本文已影响0人
robertzhai
771. 宝石与石头
class Solution:
def numJewelsInStones(self, jewels: str, stones: str) -> int:
counter = Counter(stones)
ret = 0
for word in jewels:
ret += counter[word]
return ret
2. 两数相加
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
if l1 is None:
return l2
if l2 is None:
return l1
sum = 0
head = None
tail = None
while (l1 is not None) and (l2 is not None):
sum += l1.val + l2.val
if tail is None:
head = ListNode(sum%10,None)
tail = head
else:
tail.next = ListNode(sum%10,None)
tail = tail.next
sum //= 10
l1 = l1.next
l2 = l2.next
while l1 is not None :
sum += l1.val
tail.next = ListNode(sum%10,None)
tail = tail.next
sum //= 10
l1 = l1.next
while l2 is not None :
sum += l2.val
tail.next = ListNode(sum%10,None)
tail = tail.next
sum //= 10
l2 = l2.next
if sum > 0 :
tail.next = ListNode(sum,None)
tail = tail.next
return head
61. 旋转链表
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def rotateRight(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
if head is None:
return None
nums = []
while head is not None:
nums.append(head.val)
head = head.next
n = len(nums)
k %= n
self.reverse(nums,0,n-1)
self.reverse(nums,0,k-1)
self.reverse(nums,k,n-1)
head = ListNode(nums[0],None)
tail = head
for i in range(1,n):
tail.next = ListNode(nums[i],None)
tail = tail.next
return head
def reverse(self,nums :List[int], l:int, r:int):
while l < r:
nums[l],nums[r] = nums[r],nums[l]
l += 1
r -= 1
or
class Solution:
def rotateRight(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
if head is None or k == 0:
return head
n = 1
tail = head
while tail.next :
tail = tail.next
n += 1
tail.next = head
k %= n
step = n - k
while step > 0:
tail = tail.next
step -= 1
head = tail.next
tail.next = None
return head
82. 删除排序链表中的重复元素 II
class Solution:
def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:
if head is None:
return head
# 增加一个假头部节点
dummy_head = ListNode(-200,head)
cur = dummy_head
while cur.next and cur.next.next :
if cur.next.val == cur.next.next.val:
val = cur.next.val
while cur.next and cur.next.val == val:
cur.next = cur.next.next
else:
cur = cur.next
return dummy_head.next
83. 删除排序链表中的重复元素
class Solution:
def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:
if head is None:
return head
cur = head
while cur.next:
if cur.val == cur.next.val:
cur.next = cur.next.next
else:
cur = cur.next
return head
92. 反转链表 II
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def reverseBetween(self, head: Optional[ListNode], left: int, right: int) -> Optional[ListNode]:
n = right - left
if n == 0 :
return head
dummyNode = ListNode(0, head)
head,tail = dummyNode,head
slow,fast = None,None
i = 1
while i < left:
head = tail
tail = tail.next
i += 1
while n > 0:
slow = tail.next
fast = slow.next
slow.next = head.next
head.next = slow
tail.next = fast
n -= 1
return dummyNode.next
142. 环形链表 II
class Solution:
def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
s = set()
cur = head
while cur:
if cur in s :
return cur
s.add(cur)
cur = cur.next
return None
or
image.png
class Solution:
def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
slow,fast = head,head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow is fast:
p = head
while p is not slow:
p = p.next
slow = slow.next
return slow
return None
143. 重排链表
class Solution:
def reorderList(self, head: Optional[ListNode]) -> None:
"""
Do not return anything, modify head in-place instead.
"""
if head is None:
return
nodes = []
cur = head
while cur:
nodes.append(cur)
cur = cur.next
left, right = 0, len(nodes) - 1
while left < right:
nodes[left].next = nodes[right]
left += 1
if left == right:
break
nodes[right].next = nodes[left]
right -= 1
nodes[left].next = None
return
147. 对链表进行插入排序
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def insertionSortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
if head is None:
return head
dummyNode = ListNode(0, head) // 方便修改head指针
tail = head
cur = tail.next
prev = None
while cur:
if cur.val >= tail.val:
tail = cur
else :
prev = dummyNode
while prev.next.val < cur.val:
prev = prev.next
tail.next = cur.next
cur.next = prev.next
prev.next = cur
cur = tail.next
return dummyNode.next
965. 单值二叉树
class Solution:
def isUnivalTree(self, root: Optional[TreeNode]) -> bool:
if root is None:
return True
if root.left and root.val != root.left.val:
return False
if root.right and root.val != root.right.val:
return False
return self.isUnivalTree(root.left) and self.isUnivalTree(root.right)
958. 二叉树的完全性检验
https://www.jianshu.com/p/9c9ff516f2e0
queue: https://www.cnblogs.com/lincappu/p/12890761.html
import queue
q = queue.SimpleQueue() # 创建 SimpleQueue 队列
for i in range(3):
q.put(i) # 在队列中依次插入0、1、2元素
for i in range(3):
print(q.get()) # 依次从队列中取出插入的元素，数据元素输出顺序为0、1、2
code
import queue
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def isCompleteTree(self, root: Optional[TreeNode]) -> bool:
if root is None:
return True
// bfs
q = queue.SimpleQueue()
q.put(root)
findEmptyNode = False # 第一个empty node
while True:
total = q.qsize()
if total == 0:
break
while total >0:
total -= 1
front = q.get()
if front is None and (not findEmptyNode):
findEmptyNode = True
elif front is not None :
if findEmptyNode:
return False
else:
q.put(front.left)
q.put(front.right)
return True
872. 叶子相似的树
Optional : 这个参数除了给定的默认值外还可以是None https://blog.csdn.net/weixin_54227557/article/details/123095398
class Solution:
def leafSimilar(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> bool:
nodes1 ,nodes2 = [], []
self.dfs(root1,nodes1)
self.dfs(root2, nodes2)
return nodes1 == nodes2
def dfs(self, root: Optional[TreeNode], nodes: List[int]):
if root is None:
return
self.dfs(root.left, nodes)
if root.left is None and root.right is None:
nodes.append(root.val)
self.dfs(root.right, nodes)
