- 剑指 Offer 15. 二进制中1的个数
- 剑指 Offer 18. 删除链表的节点
- 剑指 Offer 21. 调整数组顺序使奇数位于偶数前面
- 剑指 Offer 22. 链表中倒数第k个节点
- 剑指 Offer 24. 反转链表
- 剑指 Offer 25. 合并两个排序的链表
- 剑指 Offer 27. 二叉树的镜像
- 剑指 Offer 28. 对称的二叉树
- 剑指 Offer 29. 顺时针打印矩阵
- 剑指 Offer 30. 包含min函数的栈
- 剑指 Offer 32 打印二叉树
- 剑指 Offer 39. 出现次数超过一半的数字
- 剑指 Offer 40. 最小的k个数
- 剑指 Offer 42. 连续子数组的最大和
剑指 Offer 15. 二进制中1的个数
输入一个整数（以二进制串形式），输出该数二进制表示中 1 的个数。例如，把 9 表示成二进制是 1001，有 2 位是 1。因此，如果输入 9，则该函数输出 2。
输入：00000000000000000000000000001011
输出：3
# 简单思路，二进制转化，随后统计
n = 99
res = []
while n > 0:
res.append(n % 2)
n = n // 2
binary = []
while res:
binary.append(res.pop())
print(binary)
count = 0
for i in range(len(binary)):
if binary[i] == 1:
count += 1
print(count)
[1, 1, 0, 0, 0, 1, 1]
4
剑指 Offer 18. 删除链表的节点
链表中节点的值互不相同
给定单向链表的头指针和一个要删除的节点的值，定义一个函数删除该节点。
返回删除后的链表的头节点。
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def deletNode(self, head, val):
if head.val == val:
return head.next
pred = head
while pred.next:
if pred.next.val == val:
pred.next = pred.next.next
return head
else:
pred = pred.next
剑指 Offer 21. 调整数组顺序使奇数位于偶数前面
输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有奇数位于数组的前半部分，所有偶数位于数组的后半部分。
nums = [1,6,2,5,3,4]
res = []
for i in nums:
if i % 2:
res.append(i)
for j in nums:
if j % 2 == 0:
res.append(j)
print(res)
[1, 5, 3, 6, 2, 4]
剑指 Offer 22. 链表中倒数第k个节点
本题从1开始计数，即链表的尾节点是倒数第1个节点。例如，一个链表有6个节点，从头节点开始，它们的值依次是1、2、3、4、5、6。这个链表的倒数第3个节点是值为4的节点。
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def getKthFromEnd(self, head, k):
nodelist = []
current = head
while current:
nodelist.append(current)
current = current.next
for i in range(k - 1):
nodelist.pop()
return nodelist.pop()
剑指 Offer 24. 反转链表
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def reverseList(self, head):
pre, cur = None, head
while cur:
tmp = cur.next
cur.next = pre
pre = cur
cur = tmp
return pre
剑指 Offer 25. 合并两个排序的链表
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def mergeTwoLists(self, l1, l2):
start = ListNode()
node = start
while (l1 or l2):
# 只有一个
if not (l1 and l2):
node.next = l1 or l2
break
# 都非空，比大小
elif l1.val < l2.val:
node.next = l1
l1 = l1.next
else:
node.next = l2
l2 = l2.next
node = node.next
return start.next
剑指 Offer 27. 二叉树的镜像
请完成一个函数，输入一个二叉树，该函数输出它的镜像。
# 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):
return self.mirror(root)
def mirror(self, node):
if node: # 非空
if node.left and node.right: # 左右都有
node.right, node.left = self.mirror(node.left), self.mirror(node.right)
elif node.left: # 只有一边
node.left, node.right = None, self.mirror(node.left)
elif node.right: # 只有一边
node.right, node.left = None, self.mirror(node.right)
return node
# 解法二（更简洁）
def mirrorTree(self, root):
if root:
# 关键点在于先左右子节点交换！！！，就不用考虑赋值None了
root.left, root.right = root.right, root.left
if root.left:
root.left = self.mirrorTree(root.left)
if root.right:
root.right = self.mirrorTree(root.right)
return root
剑指 Offer 28. 对称的二叉树
# 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):
if not root: # none，直接返回T
return True
else:
return self.ifmatch(root.left, root.right)
def ifmatch(self, a, b):
if (not a) and (not b): # 都是none
return True
elif a and b and a.val == b.val: # 都存在且数值相等，对子节点递归！
return self.ifmatch(a.left, b.right) and self.ifmatch(a.right, b.left)
# 只有一个存在或者数值不相等
return False
剑指 Offer 29. 顺时针打印矩阵
按照从外向里以顺时针的顺序依次打印出每一个数字。
第一步，p维矩阵
输入：matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12],[13,14,15,16]]
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
输出：[1,2,3,6,9,8,7,4,5]
def printmatrix(res, matrix):
p = len(matrix)
# 停止条件
if p == 1:
res.append(matrix)
return
for i in range(0, p):
res.append(matrix[0][i])
for i in range(1, p - 1):
res.append(matrix[i][p - 1])
for i in range(1, p):
res.append(matrix[p - 1 ][p - i])
for i in range(1, p):
res.append(matrix[p - i][0])
if p >= 3:
return printmatrix(res, [x[1: len(matrix)-1] for x in matrix[1:len(matrix)-1]])
res = []
matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12],[13,14,15,16]]
printmatrix(res, matrix)
print(res)
[1, 2, 3, 4, 8, 12, 16, 15, 14, 13, 9, 5, 6, 7, 11, 10]
第二步，m x n 维矩阵
1 2 3 4
5 6 7 8
9 10 11 12
6 7 行
class Solution:
def printmatrix(self, res, matrix):
# 空
if (not matrix) or (not matrix[0]):
return
# 非空
m, n = len(matrix), len(matrix[0])
# 向量
if m == 1:
res += matrix[0]
return
if n ==1:
res += [x[0] for x in matrix]
return
# 矩阵
for i in range(0, n):
res.append(matrix[0][i])
for i in range(1, m):
res.append(matrix[i][n - 1])
for i in range(1, n):
res.append(matrix[m - 1][n - i -1])
for i in range(1, m - 1):
res.append(matrix[m - i -1][0])
# 递归
self.printmatrix(res, [x[1: (n-1)] for x in matrix[1:(m-1)]])
return
def spiralOrder(self, matrix):
res = []
self.printmatrix(res, matrix)
return res
matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]
s = Solution()
s.spiralOrder(matrix)
[1, 2, 3, 4, 8, 12, 11, 10, 9, 5, 6, 7]
剑指 Offer 30. 包含min函数的栈
class MinStack:
def __init__(self):
self.stack = []
self.mins = [] # 存每次push之后最小值的栈
def push(self, x: int) -> None:
self.stack.append(x)
if not self.mins or x <= self.mins[-1]:
self.mins.append(x)
def pop(self) -> None:
x = self.stack.pop()
tmp = self.mins.pop()
if tmp != x:
self.mins.append(tmp)
def top(self) -> int:
tmp = self.stack.pop()
self.stack.append(tmp)
return tmp
def min(self) -> int:
tmp = self.mins.pop()
self.mins.append(tmp)
return tmp
s = MinStack()
s.push(-3),s.push(0),s.push(-2)
s.min(),s.pop(),s.top(),s.min()
(-3, None, 0, -3)
剑指 Offer 32 打印二叉树
这个部分的关键在于理解——队列的思想！
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
# 定义测试用例
t1 = TreeNode(3)
t2 = TreeNode(9)
t3 = TreeNode(20)
t1.left = t2; t1.right = t3
t4 = TreeNode(15)
t5 = TreeNode(7)
t6 = TreeNode(0)
t2.left = t4; t2.right = t5; t3.right = t6
从上到下、每一层从左到右
def print_tree(root):
res = []
if not root: # root 是空
return res
nodelist = [root]
while nodelist:
current = nodelist.pop(0)
res.append(current.val)
if current.left:
nodelist.append(current.left)
if current.right:
nodelist.append(current.right)
return res
print_tree(t1)
[3, 9, 20, 15, 7, 0]
每一层打印到一行
# 将本层全部节点打印到一行，并将下一层全部节点加入队列，以此类推，即可分为多行打印。
def print_row(root):
row_list = [root]
res = []
while row_list:
row_res = [] # 本层的打印结果
n = len(row_list) # 本层有多少节点
for i in range(n):
cur = row_list.pop(0)
row_res.append(cur.val)
if cur.left:
row_list.append(cur.left)
if cur.right:
row_list.append(cur.right)
res.append(row_res)
return res
print_row(t1)
[[3], [9, 20], [15, 7, 0]]
之字形顺序打印二叉树
即第一行按照从左到右的顺序打印，第二层按照从右到左的顺序打印，第三行再按照从左到右的顺序打印，其他行以此类推。
def print_row(root):
row_list = [root]
res = []
row = 1 # 记录z字，即打印顺序
while row_list:
row_res = [] # 本层的打印结果
n = len(row_list) # 本层有多少节点
for i in range(n):
cur = row_list.pop(0)
row_res.append(cur.val)
if cur.left:
row_list.append(cur.left)
if cur.right:
row_list.append(cur.right)
if row % 2 == 0:
row_res.reverse()
res.append(row_res)
row += 1
return res
print_row(t1)
[[3], [20, 9], [15, 7, 0]]
剑指 Offer 39. 出现次数超过一半的数字
数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。
# 解法一：字典计数
nums = [1, 0, 0, 2, 2, 3, 2, 2, 2, 5, 4, 2, 2]
d = dict()
for num in nums:
if num in d.keys():
d[num] += 1
else:
d[num] = 1
for k in d.keys():
if d[k] > (len(nums)/2):
print(k)
# 解法二：摩尔投票，技巧性
votes = 0
for num in nums:
if votes == 0:
x = num
if num == x:
votes += 1
else:
votes -= 1
if votes != 0:
print(x)
2
2
剑指 Offer 40. 最小的k个数
输入整数数组 arr ，找出其中最小的 k 个数。例如，输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。
class Solution:
def getLeastNumbers(self, arr: List[int], k: int) -> List[int]:
if k == 0:
return list()
hp = [-x for x in arr[:k]]
heapq.heapify(hp)
for i in range(k, len(arr)):
if -hp[0] > arr[i]:
heapq.heappop(hp)
heapq.heappush(hp, -arr[i])
ans = [-x for x in hp]
return ans
- 我们用一个大根堆实时维护数组的前k最小值
- 从第 k+1 个数开始遍历，如果当前遍历到的数比大根堆的堆顶的数要小，就把堆顶的数弹出，再插入当前遍历到的数。最后将大根堆里的数存入数组返回即可。
- 注意：Python 语言中是小根堆，因此要对数组中所有的数取其相反数，才能使用小根堆维护前 k 小值。
剑指 Offer 42. 连续子数组的最大和
输入一个整型数组，数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。
输入: nums = [-2,1,-3,4,-1,2,1,-5,4]
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大为 6。
动态规划
当前最大 = max(当前值加上前一个最大，当前值）
nums = [-2,1,-3,4,-1,2,1,-5,4]
max_list = nums
for i in range(1, len(nums)):
max_list[i] = max(max_list[i-1] + nums[i], nums[i])
print(max(max_list))
6