删除链表反转链表
思路见代码注释
# 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: ListNode) -> ListNode:
# 先创建一个None和一个头节点
pre, cur = None, head
while cur:
# nxt保存后续节点信息
nxt = cur.next
# 断开当前节点
cur.next = pre
pre = cur
cur = nxt
return pre
删除链表的倒数第N个节点
思路：题目的难度在于找到倒数第N个节点，让pre指针先走N个节点，然后cur指针和pre指针一块走。当pre==None时，cur指针在倒数第N+1的节点，所以只要删除下一个节点即可。
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
res = ListNode()
res.next = head
cur = res
pre = head
for i in range(n):
pre = pre.next
while pre:
pre = pre.next
cur = cur.next
cur.next = cur.next.next
return res.next
二分查找
思路：二分查找是最基础的查找算法很简单，但二分查找的变体很难。
class Solution:
def search(self, nums: List[int], target: int) -> int:
left, right = 0, len(nums)-1
while left <= right:
mid = left + (right - left) // 2
if nums[mid] == target:
return mid
elif nums[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1
搜索旋转排序的数组
思路：领悟代码含义（我知道我偷懒了）
class Solution:
def search(self, nums: List[int], target: int) -> int:
left, right = 0, len(nums) -1
while left <= right:
mid = left + (right - left) // 2
if nums[mid] == target:
return mid
if nums[0] <= nums[mid]:
if nums[0] <= target < nums[mid]:
right = mid - 1
else:
left = mid + 1
else:
if nums[mid] < target <= nums[len(nums) - 1]:
left = mid + 1
else:
right = mid - 1
return -1
补一下之前的二叉树
对称二叉树
思路见代码及代码注释
# 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 isSymmetric(self, root: TreeNode) -> bool:
# 递归
def search(left, right):
# 如果左右节点全空，返回Ture
if not left and not right:
return True
# 如果左右节点有一个不空，返回False
if not left or not right:
return False
# 如果两个节点相同，进入递归left， right
return left.val == right.val and search(left.left, right.right) and search(left.right, right.left)
# run
return search(root, root)
二叉树的最小深度
层序遍历，碰到第一个没有孩子节点的时候，就返回deep值。
# 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 minDepth(self, root: TreeNode) -> int:
deep = 0
if not root:
return deep
que = deque([root])
while que:
size = len(que)
deep += 1
for i in range(size):
node = que.popleft()
if node.left:
que.append(node.left)
if node.right:
que.append(node.right)
if node.left == None and node.right == None:
return deep
路经总和
思路见代码
# 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 hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
if not root:
return False
que = deque([[root, targetSum]])
while que:
node, rest = que.popleft()
if node.left is None and node.right is None and rest == node.val:
return True
if node.left:
que.append([node.left, rest - node.val])
if node.right:
que.append([node.right, rest - node.val])
return False
二叉搜索树中第K小的数
思路见代码和代码注释
# 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 kthSmallest(self, root: Optional[TreeNode], k: int) -> int:
# 因为是二叉搜索树，所以结点的左子树只包含小于当前结点的数
res = []
while res or root:
# 沿着根节点找到所有的左孩子
while root:
res.append(root)
root = root.left
# 挨个弹出
root = res.pop()
k -= 1
# 最左边的孩子满足k值
if k == 0:
return root.val
# 不够k值，那就去root右子树的左子树继续找，这样不需要遍历整棵树
root = root.right
