剑指 Offer 03. 数组中重复的数字
题目
image.png
代码详情
class Solution:
def findRepeatNumber(self, nums: List[int]) -> int:
nums_set = set()
for i in nums:
if i not in nums_set:
nums_set.add(i)
else:
return i
剑指 Offer 04. 二维数组中的查找
题目
image.png
代码详情
class Solution:
def findNumberIn2DArray(self, matrix: List[List[int]], target: int) -> bool:
row = len(matrix)
if row <= 0:
return False
col = len(matrix[0])
r = 0
c = col-1
while r < row and c >= 0:
if matrix[r][c] > target:
c -= 1
elif matrix[r][c] < target:
r += 1
else :
return True
return False
剑指 Offer 06. 从尾到头打印链表
题目
image.png
代码详情
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def reversePrint(self, head: ListNode) -> List[int]:
res = []
pHead = head
stack = []
while pHead is not None:
stack.insert(0, pHead.val)
pHead = pHead.next
return stack
剑指 Offer 07. 重建二叉树
题目
image.png
代码详情
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
if len(preorder) <= 0 or len(inorder) <= 0:
return None
root = TreeNode(preorder[0])
i = inorder.index(preorder[0])
root.left = self.buildTree(preorder[1:i+1], inorder[:i])
root.right = self.buildTree(preorder[i+1:], inorder[i+1:])
return root
剑指 Offer 09. 用两个栈实现队列
题目
image.png
代码详情
class CQueue:
def __init__(self):
self.stack1 = []
self.stack2 = []
def appendTail(self, value: int) -> None:
self.stack1.append(value)
def deleteHead(self) -> int:
if len(self.stack2) <= 0:
if len(self.stack1) <= 0:
return -1
else:
while self.stack1:
self.stack2.append(self.stack1.pop())
return self.stack2.pop()
else:
return self.stack2.pop()
# Your CQueue object will be instantiated and called as such:
# obj = CQueue()
# obj.appendTail(value)
# param_2 = obj.deleteHead()
剑指 Offer 10- I. 斐波那契数列
题目
image.png
代码详情
# 非递归形式
class Solution:
def fib(self, n: int) -> int:
a, b = 0, 1
while n > 0:
a, b = b, a + b
n -= 1
return a % 1000000007
剑指 Offer 10- II. 青蛙跳台阶问题
题目
image.png
代码详情
class Solution:
def numWays(self, n: int) -> int:
a, b = 1, 1
while n > 0:
a, b = b, a + b
n -= 1
return a % 1000000007
剑指 Offer 11. 旋转数组的最小数字
题目
image.png
代码详情
class Solution:
def minArray(self, numbers: List[int]) -> int:
l = 0
r = len(numbers) -1
while l < r:
m = (l + r) // 2
if numbers[m] > numbers[r]:
l = m + 1
elif numbers[m] < numbers[r]:
r = m
else:
r = r - 1
return numbers[l]
剑指 Offer 12. 矩阵中的路径
题目
image.png
代码详情
class Solution:
def exist(self, board: List[List[str]], word: str) -> bool:
def dfs(row, col, k):
if not (0 <= row < len(board)) or not (0 <= col < len(board[0])) or board[row][col] != word[k]:
return False
if k == len(word) -1:
return True
tmp, board[row][col] = board[row][col], "/"
res = dfs(row + 1, col, k +1 ) or dfs(row -1, col, k +1) or dfs(row, col + 1, k+1) or dfs(row, col - 1, k +1)
board[row][col] = tmp
return res
for i in range(len(board)):
for j in range(len(board[0])):
if (dfs(i, j, 0)):
return True
return False
剑指 Offer 13. 机器人的运动范围
题目
image.png
代码详情
class Solution {
public int movingCount(int m, int n, int k) {
//临时变量visited记录格子是否被访问过
boolean[][] visited = new boolean[m][n];
return dfs(0, 0, m, n, k, visited);
}
public int dfs(int i, int j, int m, int n, int k, boolean[][] visited) {
//i >= m || j >= n是边界条件的判断，k < sum(i, j)判断当前格子坐标是否
// 满足条件，visited[i][j]判断这个格子是否被访问过
if (i >= m || j >= n || k < sum(i, j) || visited[i][j])
return 0;
//标注这个格子被访问过
visited[i][j] = true;
//沿着当前格子的右边和下边继续访问
return 1 + dfs(i + 1, j, m, n, k, visited) + dfs(i, j + 1, m, n, k, visited);
}
//计算两个坐标数字的和
private int sum(int i, int j) {
int sum = 0;
while (i != 0) {
sum += i % 10;
i /= 10;
}
while (j != 0) {
sum += j % 10;
j /= 10;
}
return sum;
}
}
剑指 Offer 14- I. 剪绳子
题目
image.png
代码详情
剑指 Offer 18. 删除链表的节点
题目
image.png
代码详情
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def deleteNode(self, head: ListNode, val: int) -> ListNode:
myHead = ListNode(0)
myHead.next = head
pre = myHead
p = head
while p:
if p.val == val:
pre.next = p.next
break
else:
pre = p
p = p.next
return myHead.next
剑指 Offer 21. 调整数组顺序使奇数位于偶数前面
题目
image.png
代码详情
class Solution:
def exchange(self, nums: List[int]) -> List[int]:
if len(nums) <= 1:
return nums
left = 0
right = len(nums) - 1
key = nums[right]
while left < right:
while left < right and nums[left] % 2 != 0:
left += 1
nums[right] = nums[left]
while left < right and nums[right] % 2 == 0:
right -= 1
nums[left] = nums[right]
nums[left] = key
return nums
剑指 Offer 22. 链表中倒数第k个节点
题目
image.png
代码详情
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def getKthFromEnd(self, head: ListNode, k: int) -> ListNode:
first = head
second = head
while k > 0 and first:
first = first.next
k -= 1
while first:
first = first.next
second = second.next
return second
剑指 Offer 24. 反转链表
题目
image.png
代码详情
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def reverseList(self, head: ListNode) -> ListNode:
p = head
pre = None
while p:
tmp = p.next
p.next = pre
pre = p
p = tmp
return pre
剑指 Offer 25. 合并两个排序的链表
题目
image.png
代码详情
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
cur = myHead = ListNode(0)
while l1 and l2:
if l1.val < l2.val:
cur.next, l1 = l1, l1.next
else:
cur.next, l2 = l2, l2.next
cur = cur.next
cur.next = l1 if l1 else l2
return myHead.next
剑指 Offer 26. 树的子结构
题目
image.png
代码详情
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def isSubStructure(self, A: TreeNode, B: TreeNode) -> bool:
if not B:
return False
if not A:
return False
if A.val == B.val and self.test(A.left, B.left) and self.test(A.right, B.right):
return True
return self.isSubStructure(A.left, B) or self.isSubStructure(A.right, B)
def test(self, a, b):
if not b:
return True
if not a or a.val != b.val:
return False
return self.test(a.left, b.left) and self.test(a.right, b.right)
剑指 Offer 27. 二叉树的镜像
题目
image.png
代码详情
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def mirrorTree(self, root: TreeNode) -> TreeNode:
if root is None:
return None
p = root
p.left, p.right = p.right, p.left
self.mirrorTree(p.left)
self.mirrorTree(p.right)
return root
剑指 Offer 28. 对称的二叉树
题目
image.png
代码详情
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def isSymmetric(self, root: TreeNode) -> bool:
if not root:
return True
return self.test(root.left, root.right)
def test(self, left, right):
if left is None and right is None:
return True
if left is None or right is None or left.val != right.val:
return False
return self.test(left.left, right.right) and self.test(left.right, right.left)
剑指 Offer 29. 顺时针打印矩阵
题目
image.png
代码详情
class Solution:
def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
if not matrix: return []
# 标志上下左右的边界
l, r, t, b, res = 0, len(matrix[0]) - 1, 0, len(matrix) - 1, []
while True:
for i in range(l, r + 1): res.append(matrix[t][i]) # left to right
t += 1
if t > b: break
for i in range(t, b + 1): res.append(matrix[i][r]) # top to bottom
r -= 1
if l > r: break
for i in range(r, l - 1, -1): res.append(matrix[b][i]) # right to left
b -= 1
if t > b: break
for i in range(b, t - 1, -1): res.append(matrix[i][l]) # bottom to top
l += 1
if l > r: break
return res
剑指 Offer 31. 栈的压入、弹出序列
题目
image.png
代码详情
class Solution:
def validateStackSequences(self, pushed: List[int], popped: List[int]) -> bool:
tmp = []
for i in range(len(pushed)):
tmp.append(pushed[i])
while len(popped) > 0 and len(tmp) > 0 and popped[0] == tmp[-1]:
tmp.pop()
popped.pop(0)
return len(tmp) == 0
剑指 Offer 32 - I. 从上到下打印二叉树
题目
image.png
代码详情
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def levelOrder(self, root: TreeNode) -> List[int]:
if root is None:
return []
queue = [root]
res = []
while queue:
node = queue.pop(0)
res.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
return res
剑指 Offer 32 - II. 从上到下打印二叉树 II
题目
image.png
代码详情
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def levelOrder(self, root: TreeNode) -> List[List[int]]:
if root is None:
return []
queue = [root]
res = []
while queue:
tmp = []
for i in range(len(queue)):
node = queue.pop(0)
tmp.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
res.append(tmp)
return res
剑指 Offer 33. 二叉搜索树的后序遍历序列
题目
image.png
代码详情
class Solution:
def verifyPostorder(self, postorder: List[int]) -> bool:
if not postorder:
return True
root = postorder[-1]
for i in range(len(postorder)):
if postorder[i] > root:
break
for j in range(i, len(postorder) - 1):
if postorder[j] < root:
return False
left = right = True
if i > 0:
left = self.verifyPostorder(postorder[:i])
if i < len(postorder) -1:
right = self.verifyPostorder(postorder[i:len(postorder) -1])
return left and right
剑指 Offer 34. 二叉树中和为某一值的路径
题目
image.png
代码详情
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def pathSum(self, root: TreeNode, sum: int) -> List[List[int]]:
if root is None:
return []
if root is not None and root.left is None and root.right is None and root.val == sum:
return [[root.val]]
left = self.pathSum(root.left, sum - root.val)
right = self.pathSum(root.right, sum - root.val)
res = []
for i in left + right:
res.append([root.val] + i)
return res
剑指 Offer 40. 最小的k个数
题目
image.png
代码详情
剑指 Offer 42. 连续子数组的最大和
题目
image.png
代码详情
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
if not nums:
return 0
# 动态规划，填充数据，dp[i]代表前一个数字的最大连续和
dp = [0 for _ in range(len(nums))]
dp[0] = nums[0]
for i in range(1, len(nums)):
if dp[i - 1] > 0:
dp[i] = dp[i - 1] + nums[i]
else:
dp[i] = nums[i]
print(dp)
return max(dp)
剑指 Offer 48. 最长不含重复字符的子字符串
题目
image.png
代码详情
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
tmp_dict = {}
i = -1
res = 0
tmp = 0
for j in range(len(s)):
i = max(tmp_dict.get(s[j], -1), i)
tmp_dict[s[j]] = j
tmp = tmp + 1 if tmp < j -i else j -i
res = max(res, tmp)
return res
剑指 Offer 54. 二叉搜索树的第k大节点
题目
image.png
代码详情
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def kthLargest(self, root: TreeNode, k: int) -> int:
if root is None:
return None
tmp = []
self.test(root, tmp)
return tmp[k-1]
def test(self, root, tmp):
if root is None:
return
self.test(root.right, tmp)
tmp.append(root.val)
self.test(root.left, tmp)
剑指 Offer 55 - I. 二叉树的深度
题目
image.png
代码详情
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def maxDepth(self, root: TreeNode) -> int:
if root is None:
return 0
left = self.maxDepth(root.left)
right = self.maxDepth(root.right)
return (left if left > right else right) + 1
剑指 Offer 55 - II. 平衡二叉树
题目
image.png
代码详情
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def isBalanced(self, root: TreeNode) -> bool:
def recur(root):
if root is None:
return 0
left = recur(root.left)
if left == -1:
return -1
right = recur(root.right)
if right == -1:
return -1
return max(left, right) + 1 if abs(left - right) <= 1 else -1
return recur(root) != -1
剑指 Offer 56 - I. 数组中数字出现的次数
题目
image.png
代码详情
class Solution:
def singleNumbers(self, nums: List[int]) -> List[int]:
tmp = {}
for i in nums:
if i not in tmp:
tmp[i] = 0
tmp[i] += 1
res = []
for k, v in tmp.items():
if v == 1:
res.append(k)
return res
剑指 Offer 57. 和为s的两个数字
题目
image.png
代码详情
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
if not nums:
return []
i, j = 0, len(nums) -1
while i < j:
tmp = nums[i] + nums[j]
if tmp > target:
j -= 1
if tmp < target:
i += 1
if tmp == target:
return [nums[i], nums[j]]
剑指 Offer 57 - II. 和为s的连续正数序列
题目
image.png
