| 序号 | 题目 | 难易程度 | 思路 | 备注 |
|---|---|---|---|---|
| 3 | 数组中重复的数字 | 1、桶排序；2、二分法。 | 多写几遍 | |
| LeetCode 第 287 题：寻找重复数。 | ||||
| 4 | 二维数组的查找 | 从右上角或者左下角开始找。 | ||
| 6 | 从尾到头打印链表 | 重点理解：在回溯的时候打印。或者用栈。 | ||
| 7 | 重建二叉树 | 递归，算好偏移量，拿具体例子分析不会出错。 | ||
| LeetCode 第 105 题、LeetCode 第 106 题。 | ||||
| 8 | 二叉树的下一个结点 | 关键在于讨论是否有右子树。 | ||
| 9 | 用两个栈实现队列 | 重要 | 得用两个栈，一定是 stack2 空，才做“翻转”。 | 多写几遍 |
| 用队列实现栈 | 重要 | 用一个队列就可以了。 | ||
| 10 | 斐波拉契数列数列 | ==思考如何与快速幂扯上关系。== | ||
| 基础斐波拉契数列 | 滚动数组，a , b = a + b , a。 |
|||
| 变态跳台阶 | 1、动态规划；2、归纳出通项公式。 | |||
| ==矩阵求法== | 重要 | |||
| 11 | ==旋转数组中的最小数字== | 重要 | 1、二分法；2、分治。 | |
| 12 | 矩阵中的路径 | 重要 | floodfill，理解状态重置，先占位置，如果不符合要求，要把状态重置。 | |
| LeetCode 第 79 题：单词搜索。 | ||||
| 13 | 机器人的运动范围 | 重要 | BFS，只要分析不是，就可以 mark 为 True。 | |
| 14 | 剪绳子 | 重要 | 1、动态规划；2、贪心算法。 | 要会画树形图。 |
| LeetCode 第 343 题：整数分割。 | ||||
| 15 | 二进制中 |
重要 | 位运算。n & (n - 1) 把最低位的 |
|
Python 中写法有点不大一样：预处理：n = n & 0xFFFFFFFF。 |
||||
| 16 | 数值的整数次方 | 特别重要 | 快速幂，“递归”和“循环”都要会做。 | |
| LeetCode 第 50 题。“循环”的代码记住就可以了。 | ||||
| 17 | 打印从 1 到最大的 n 位数 | |||
| 18 | 删除链表中的结点 | 注意两个结点非空一起判断。 | ||
| LeetCode 第 82 题：保留 1 个 | ||||
| LeetCode 第 83 题：相同不保留 | ||||
| 19 | 正则表达式匹配 | 困难 | 动态规划。 | |
| 20 | 表示数值的字符串 | 困难 | ||
| 21 | 调整数组使得奇数位于偶数之前 | 两路快排，l > r 才停止，掌握更通用的写法。 |
||
| 22 | 链表中倒数第 k 个结点 | 快慢指针。 | ||
| 23 | 链表中环的入口结点 | |||
| 24 | 反转链表 | |||
| 25 | 合并排序的链表 | |||
| 26 | 树的子结构 | |||
| 27 | 翻转二叉树 | |||
| 28 | 判断一棵二叉树是否对称 | 使用双端队列。 | ||
| 29 | 顺时针打印矩阵 | |||
| 30 | 包含 min 函数的栈 | 设置辅助栈，只有元素比当前所有都小的时候，才 push。 | ||
| 31 | 栈的压入、弹出序列 | |||
| 32 | 不分行从上往下打印二叉树 | |||
| 分行从上往下打印二叉树 | ||||
| 之字形打印二叉树 | ||||
| 33 | 二叉搜索树的后序遍历序列 | 易错 | 递归。 | |
| 34 | 二叉树中和为某一值的路径 | 重要 | 回溯，注意状态要重置。 | |
| 35 | 复杂链表的复制 | |||
| 36 | 二叉搜索树与双向链表 | 重点 | 1、递归返回 tuple；2、分治。 | |
| 37 | 序列化二叉树 | 易错 | 前序遍历，定义好分隔符和空结点表示。 | |
| 38 | 字符串的排列 | 重要 | 掌握如何去掉重复。 | |
| 39 | 数组中超过一半的数字 | |||
| 40 | 最小的 K 个数 | 快排，严格小于的才放到前面，堆。 | ||
| 41 | 数据流中的中位数 | 堆。 | ||
| 42 | 连续子数组的最大和 | 重要 | 状态：以某个数结尾的。最后要拉通求一遍。 | |
| 43 | 从 1 到 n 整数中 1 出现的次数 | 困难 | ||
| 44 | 数字序列中某一位的数字 | 困难 | ||
| 45 | 把数组排成最小的数 | |||
| 46 | 把数字翻译成字符串 | |||
| LeetCode 第 91 题：解码方法。 | ||||
| 47 | 礼物的最大价值 | |||
| 48 | 最长不重复字符串的子字符串 | 1、滑动窗口；2、动态规划；3、隔板法。 | ||
| LeetCode 第 3 题：最长不重复字符串 | ||||
| 49 | 丑数 | |||
| 50 | 字符串中第一个只出现一次的字符 | |||
| 字符流中第一个只出现一次的字符 | ||||
| 51 | 逆序对 | |||
| 52 | 两个链表的第一个公共结点 | 记住写法。 | ||
| 53 | 数字在排序数组中出现的次数 | 二分法。 | ||
| 54 | 二叉搜索树的第 |
|||
| 55 | 二叉树的深度 | |||
| 平衡二叉树 | ||||
| 56 | 数组中只出现一次的两个数字 | |||
| 0 到 n-1 中缺失的数字 | ||||
| 数组中数值和下标相等的元素 | ||||
| 数组中唯一只出现一次的数字 | ||||
| 57 | 和为 S 的两个数字 | |||
| 和为 S 的连续正数序列 | ||||
| 58 | 翻转单词顺序列 | |||
| 左旋转字符串 | ||||
| 59 | 滑动窗口最大值 | 重要 | ||
| 60 |
|
|||
| 61 | 扑克牌顺子 | |||
| 62 | 圆圈中最后剩下的数 | |||
| 63 | 股票的最大利润 | 有一些扩展问题。 | ||
| 64 | 求 1 + 2 + 3 + ... + n | |||
| 65 | 不用加减乘除做加法 | |||
| 66 | 构建乘积数组 | |||
| 67 | 把字符串转换成整数 | |||
| 68 | 树中两个节点的最近公共祖先 |
第 3 题：数组中重复的数字（桶排序，抽屉原理）
传送门：AcWing：数组中重复的数字。
给定一个长度为
的整数数组
nums，数组中所有的数字都在的范围内。
数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。
请找出数组中任意一个重复的数字。
注意：如果某些数字不在
；
样例：
给定
nums = [2, 3, 5, 4, 3, 2, 6, 7]。返回
或
。
思路1：最容易想到用哈希表判重。在 不超过
的时候，使用位运算可以实现
空间复杂度判重。
思路2：排序以后，再遍历一遍就知道哪个重复了。
思路3：“抽屉原理”。这道题实际上是要求我们使用桶排序的思想（一个萝卜一个坑），找出重复的数字。
Python 代码：这个解法会修改原始数组
class Solution(object):
def duplicateInArray(self, nums):
"""
:type nums: List[int]
:rtype int
"""
size = len(nums)
if size < 2:
return -1
# 先统一检查数字是不是越界了
for i in range(size):
if nums[i] < 0 or nums[i] > size - 1:
return -1
for i in range(size):
# nums[i] 应该在 i 的位置上
while i != nums[i]:
# 发现要交换的那个数和自己一样，就可以返回了
if nums[i] == nums[nums[i]]:
return nums[i]
self.__swap(nums, i, nums[i])
return -1
def __swap(self, nums, index1, index2):
if index1 == index2:
return
temp = nums[index1]
nums[index1] = nums[index2]
nums[index2] = temp
思路4：下面的问题可以不修改数组找出重复的数字，即使用“二分法”。
LeetCode 第 287 题：寻找重复数
传送门：287. 寻找重复数。
给定一个包含 n + 1 个整数的数组 nums，其数字都在 1 到 n 之间（包括 1 和 n），可知至少存在一个重复的整数。假设只有一个重复的整数，找出这个重复的数。
示例 1:
输入:
[1,3,4,2,2]
输出: 2示例 2:
输入:
[3,1,3,4,2]
输出: 3说明：
- 不能更改原数组（假设数组是只读的）。
- 只能使用额外的
的空间。
- 时间复杂度小于
。
- 数组中只有一个重复的数字，但它可能不止重复出现一次。
思路：分治法，用二分去做，是对“数”做二分，而不是对“索引”做二分。
Python 代码：使用了二分法的模板，要定位的“数”根据题意在 和
之间
class Solution:
def findDuplicate(self, nums):
"""
【不修改数组找出重复的数字】
给定一个包含 n + 1 个整数的数组 nums，
其数字都在 1 到 n 之间（包括 1 和 n），
可知至少存在一个重复的整数。
假设只有一个重复的整数，找出这个重复的数。
:type nums: List[int]
:rtype: int
"""
left = 1
right = len(nums) - 1
while left < right:
# 取中点有两种方式，偏左和偏右
mid = left + (right - left + 1) // 2 # 4
count = 0
for num in nums:
if num < mid:
count += 1
if count < mid:
# 比 4 小的个数，最多就只能是 3
# 所以重复的肯定不是 [1,2,3]，不能排除 4
# 因为左边不变，所以取中点的时候，就要偏右
left = mid
else:
# 比 4 小的个数，达到 4 或者更多
# 重复的就落在 [1,2,3]
right = mid - 1
# 跳出循环肯定是因为 start = end
return left
参考资料：《剑指 Offer》（第 2 版）第 3 题：数组中重复的数字。
第 4 题：二维数组中的查找
同 LeetCode 第 240 题，LeetCode 传送门：搜索二维矩阵 II，AcWing：二维数组中的查找，牛客网传送门：二维数组中的查找。
在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。
请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
样例：
输入数组：
[ [1,2,8,9]， [2,4,9,12]， [4,7,10,13]， [6,8,11,15] ]如果输入查找数值为 7，则返回 true，
如果输入查找数值为 5 ，则返回 false。
分析：有点像 LeetCode 上岛屿的问题，特别之处：从右上角开始找，或者从左下角开始找，为什么不能选左上或者右下开始，因为不能缩小查找范围。首先选取数组中右上角的数字。如果该数字等于要查找的数字，查找过程结束；如果该数字大于要查找的数组，剔除这个数字所在的列；如果该数字小于要查找的数字，剔除这个数字所在的行。也就是说如果要查找的数字不在数组的右上角，则每一次都在数组的查找范围中剔除一行或者一列，这样每一步都可以缩小查找的范围，直到找到要查找的数字，或者查找范围为空。
[图片上传失败...(image-54ad66-1549813200679)]
Python 代码：从右上角开始找，一个一个地找。小了向下面走，大了向左边走
class Solution(object):
def searchArray(self, array, target):
rows = len(array)
if rows == 0:
return False
cols = len(array[0])
if rows > 0 and cols > 0:
row = 0
col = cols - 1
# 注意：在横纵坐标都有意义的时候，才可以搜索，因此用 and
while row < rows and col >= 0:
if target == array[row][col]:
return True
elif target < array[row][col]:
# [4, 5, 6, 12, 13] 找 7
col -= 1
else:
# [7]
# [8]
# [12] 找 9
row += 1
# 全部走完都找不到，就说明没有
return False
说明：其实不管是每行还是每列，都是有序数组，所以可以使用二分法。我写了个二分法，只是作为练习。但是二分法不能保证一次写对，所以不建议在面试的时候写。
Python 代码：（了解即可）
# 4、二维数组中的查找
class Solution(object):
# 二分法查找规律
# 1、从右到左，找第 1 个小于或者等于 target 的数
# 2、从上到下，找第 1 个大于或者等于 target 的数
def searchArray(self, array, target):
"""
:type array: List[List[int]]
:type target: int
:rtype: bool
"""
rows = len(array)
if rows == 0:
return False
cols = len(array[0])
col = cols - 1
row = 0
while row < rows and col >= 0:
# print('row', row, 'col', col, array[row][0])
# 1、从右到左，找第 1 个小于或者等于 target 的数
if col == 0 and array[row][0] > target:
return False
l = 0
r = col
while l < r:
mid = l + (r - l + 1) // 2
if array[row][mid] <= target:
l = mid
else:
assert array[row][mid] > target
r = mid - 1
col = l
# 2、从上到下，找第 1 个大于或者等于 target 的数
if row == rows - 1 and array[rows - 1][col] < target:
return False
l = row
r = rows - 1
while l < r:
mid = l + (r - l) // 2
if array[mid][col] >= target:
r = mid
else:
assert array[mid][col] < target
l = mid + 1
row = l
if array[row][col] == target:
return True
return False
if __name__ == '__main__':
array = [[1, 2, 8, 9],
[2, 4, 9, 12],
[4, 7, 10, 13],
[6, 8, 11, 15]]
target = 16
solution = Solution()
result = solution.searchArray(array, target)
print(result)
LeetCode 第 74 题：搜索二维矩阵
传送门：搜索二维矩阵。
编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性：
- 每行中的整数从左到右按升序排列。
- 每行的第一个整数大于前一行的最后一个整数。
示例 1:
输入: matrix = [ [1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 50] ] target = 3 输出: true示例 2:
输入: matrix = [ [1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 50] ] target = 13 输出: false
Python 代码1：“标准的”二分法
class Solution(object):
def searchMatrix(self, matrix, target):
"""
:type matrix: List[List[int]]
:type target: int
:rtype: bool
"""
m = len(matrix)
if m == 0:
return False
n = len(matrix[0])
if n == 0:
return False
left = 0
# 这里一定要记得减 1
right = m * n - 1
while left <= right:
mid = left + (right - left) // 2
# 定位到矩阵中
num = matrix[mid // n][mid % n]
if num == target:
return True
elif num < target:
left = mid + 1
else:
right = mid - 1
return False
Python 代码2：“神奇的”二分法模板
class Solution(object):
def searchMatrix(self, matrix, target):
"""
:type matrix: List[List[int]]
:type target: int
:rtype: bool
"""
m = len(matrix)
if m == 0:
return False
n = len(matrix[0])
# [[]] 针对这种情况，要特判
if n == 0:
return False
l = 0
r = m * n - 1
while l < r:
mid = l + (r - l) // 2
if matrix[mid // n][mid % n] < target:
l = mid + 1
else:
r = mid
# 这个模板在退出循环的时候 l == r 成立，但是有可能存在不满足条件的时候
# 所以要单独判断
return matrix[l // n][l % n] == target
第 6 题：从尾到头打印链表
传送门：AcWing：从尾到头打印链表。
输入一个链表的头结点，按照 从尾到头 的顺序返回节点的值。
返回的结果用数组存储。
样例：
输入：
[2, 3, 5]
返回：[5, 3, 2]
思路1：首先应该想到，使用栈作为辅助。
Python 代码1：Python 中的列表有可以在指定位置插入元素，我们就每次在索引 处插入元素好了
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution(object):
def printListReversingly(self, head):
"""
:type head: ListNode
:rtype: List[int]
"""
p = head
stack = []
while p:
stack.append(p.val)
p = p.next
return stack[::-1]
Python 代码2：
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution(object):
def printListReversingly(self, head):
"""
:type head: ListNode
:rtype: List[int]
"""
p = head
stack = []
while p:
stack.insert(0, p.val)
p = p.next
return stack
思路2：使用递归，关键在于递归函数的编写，特别注意：在回溯的时候，添加当前结点的值到结果集中。
Python 代码：
class Solution(object):
def printListReversingly(self, head):
"""
:type head: ListNode
:rtype: List[int]
"""
res = []
self.helper(res, head)
return res
def helper(self, res, listnode):
if listnode is None:
return
# 应该先判断下一个结点是否为空，如果不为空，则递归调用，在回溯的时候，才添加到结果中
if listnode.next:
self.helper(res, listnode.next)
# 这一步特别关键：回溯时添加
res.append(listnode.val)
思考下面这个写法为什么是错的。
拿具体的测试用例就可以很容易想明白，不能使用 if else 语句。
第 7 题：重建二叉树（递归）
同 LeetCode 第 105 题，传送门：从前序与中序遍历序列构造二叉树。
传送门：AcWing：重建二叉树。
输入一棵二叉树前序遍历和中序遍历的结果，请重建该二叉树。
注意:
- 二叉树中每个节点的值都互不相同；
- 输入的前序遍历和中序遍历一定合法；
样例：
给定：
前序遍历是：[3, 9, 20, 15, 7]
中序遍历是：[9, 3, 15, 20, 7]返回：
[3, 9, 20, null, null, 15, 7, null, null, null, null]
返回的二叉树如下所示：3 / \ 9 20 / \ 15 7
思路：递归重建。二叉树的 DFS 有如下三种遍历方式：
- 前序遍历：先访问根结点，再访问左子结点，最后访问右子结点。
- 中序遍历：先访问左子结点，再访问根结点，最后访问右子结点。
- 后序遍历：先访问左子结点，再访问右子结点，最后访问根结点。
本题为前序遍历和中序遍历，最少需要两种遍历方式，才能重建二叉树。
关键：前序遍历数组的第 个数（索引为
）的数一定是二叉树的根结点，于是可以在中序遍历中找这个根结点的索引，然后把“前序遍历数组”和“中序遍历数组”分为两个部分，就分别对应二叉树的左子树和右子树，分别递归完成就可以了。
注意：1、编写递归方法的时候，先写特殊情况；
2、索引是多少不好判断的时候，干脆就用一个具体的例子，就比如我上面画的这个图，把具体的数换成我们使用的变量，这样思考的难度会降低，而且还不容易出错。
Python 代码：
class TreeNode(object):
def __init__(self, x):
self.val = x
self.left = None
self.right = None
class Solution(object):
def buildTree(self, preorder, inorder):
"""
返回构造的 TreeNode 根结点
:type preorder: List[int]
:type inorder: List[int]
:rtype: TreeNode
"""
# 在编码过程中，一定要保证 len(pre) == len(tin)，否则逻辑一定不正确
if len(preorder) == 0:
return None
if len(preorder) == 1:
# 这里要返回结点，而不是返回具体的数
return TreeNode(preorder[0])
root = TreeNode(preorder[0])
# 直接得到在中序遍历中的位置，下面算好偏移量就好了，如果容易算错，记得拿具体例子
pos = inorder.index(preorder[0])
root.left = self.buildTree(preorder[1:pos + 1], inorder[:pos])
root.right = self.buildTree(preorder[pos + 1:], inorder[pos + 1:])
return root
类似问题：LeetCode 第 106 题。
LeetCode 第 106 题：从中序与后序遍历序列构造二叉树
传送门：106. 从中序与后序遍历序列构造二叉树。
根据一棵树的中序遍历与后序遍历构造二叉树。
注意:
你可以假设树中没有重复的元素。例如，给出
中序遍历 inorder =
[9,3,15,20,7]
后序遍历 postorder =[9,15,7,20,3]返回如下的二叉树：
3 / \ 9 20 / \ 15 7
思路：二叉树的问题，在纸上写写画画更形象。
Python 代码：
class TreeNode(object):
def __init__(self, x):
self.val = x
self.left = None
self.right = None
class Solution:
def buildTree(self, inorder, postorder):
"""
:type inorder: List[int]
:type postorder: List[int]
:rtype: TreeNode
"""
assert len(inorder) == len(postorder)
if len(inorder) == 0:
return None
if len(inorder) == 1:
# 这里要返回结点，而不是返回具体的数
return TreeNode(inorder[0])
# 最后一个结点是根结点
root = TreeNode(postorder[-1])
pos = inorder.index(postorder[-1])
root.left = self.buildTree(inorder[:pos], postorder[:pos])
root.right = self.buildTree(inorder[pos + 1:], postorder[pos:-1])
return root
# 用于验证的方法
def validate(node):
if node is None:
return
validate(node.left)
print(node.val, end=' ')
validate(node.right)
if __name__ == '__main__':
inorder = [9, 3, 15, 20, 7]
postorder = [9, 15, 7, 20, 3]
solution = Solution()
root = solution.buildTree(inorder, postorder)
validate(root)
第 8 题：二叉树的下一个结点
传送门：AcWing：二叉树的下一个结点。
给定一棵二叉树的其中一个节点，请找出中序遍历序列的下一个节点。
注意：
- 如果给定的节点是中序遍历序列的最后一个，则返回空节点;
- 二叉树一定不为空，且给定的节点一定不是空节点；
样例：
假定二叉树是：
[2, 1, 3, null, null, null, null]， 给出的是值等于 2 的节点。则应返回值等于3的节点。
解释：该二叉树的结构如下，2 的后继节点是 3 。
2 / \ 1 3
思路：用《算导》中提出的方法，画图分析，把要分类讨论的情况分析清楚，编码就很容易了。这道题的关键在于：看是否有右子树。
画个清楚的图帮助理解：
Python 代码：
class Solution(object):
def inorderSuccessor(self, q):
"""
:type q: TreeNode
:rtype: TreeNode
"""
if q is None:
return None
# 分类讨论1：如果这个结点有右子树，返回这个右子树的最小者
if q.right:
node = q.right
while node.left:
node = node.left
return node
# 分类讨论2：如果这个结点没有右子树，向上追溯，追到父亲结点的左结点是自己
while q.father:
if q.father.left == q:
return q.father
q = q.father
return None
第 9-1 题：用两个栈实现队列
传送门：AcWing：用两个栈实现队列。
请用栈实现一个队列，支持如下四种操作：
- push(x) – 将元素x插到队尾；
- pop() – 将队首的元素弹出，并返回该元素；
- peek() – 返回队首元素；
- empty() – 返回队列是否为空；
注意：
- 你只能使用栈的标准操作：
push to top，peek/pop from top,size和is empty；- 如果你选择的编程语言没有栈的标准库，你可以使用list或者deque等模拟栈的操作；
- 输入数据保证合法，例如，在队列为空时，不会进行
pop或者peek等操作；样例
MyQueue queue = new MyQueue(); queue.push(1); queue.push(2); queue.peek(); // returns 1 queue.pop(); // returns 1 queue.empty(); // returns false
注意：下面这个逻辑是错的，应该是只要 stack2 是空的，才把 stack1 的元素全部搬到 stack2，这里要小心。
def __shift(self):
if self.stack1:
while self.stack1:
self.stack2.append(self.stack1.pop())
Python 代码：
class MyQueue(object):
def __init__(self):
"""
Initialize your data structure here.
"""
self.stack1 = []
self.stack2 = []
def push(self, x):
"""
Push element x to the back of queue.
:type x: int
:rtype: void
"""
self.stack1.append(x)
def __shift(self):
if len(self.stack2) == 0:
while self.stack1:
self.stack2.append(self.stack1.pop())
def pop(self):
"""
Removes the element from in front of queue and returns that element.
:rtype: int
"""
self.__shift()
return self.stack2.pop()
def peek(self):
"""
Get the front element.
:rtype: int
"""
self.__shift()
return self.stack2[-1]
def empty(self):
"""
Returns whether the queue is empty.
:rtype: bool
"""
return len(self.stack1) == 0 and len(self.stack2) == 0
# Your MyQueue object will be instantiated and called as such:
# obj = MyQueue()
# obj.push(x)
# param_2 = obj.pop()
# param_3 = obj.peek()
# param_4 = obj.empty()
第 9-2 题：用队列实现栈
同 LeetCode 第 225 题。
传送门：225. 用队列实现栈
使用队列实现栈的下列操作：
- push(x) -- 元素 x 入栈
- pop() -- 移除栈顶元素
- top() -- 获取栈顶元素
- empty() -- 返回栈是否为空
注意:
- 你只能使用队列的基本操作-- 也就是
push to back,peek/pop from front,size, 和is empty这些操作是合法的。- 你所使用的语言也许不支持队列。 你可以使用 list 或者 deque（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。
- 你可以假设所有操作都是有效的（例如, 对一个空的栈不会调用 pop 或者 top 操作）。
Python 代码：
class MyStack:
def __init__(self):
"""
Initialize your data structure here.
"""
self.queue = []
def push(self, x):
"""
Push element x onto stack.
:type x: int
:rtype: void
"""
self.queue.append(x)
# 将队列中前面已经逆序的元素放在 x 元素后面，使得整体逆序
for _ in range(len(self.queue) - 1):
ele = self.queue.pop(0)
self.queue.append(ele)
def pop(self):
"""
Removes the element on top of the stack and returns that element.
:rtype: int
"""
if self.queue:
return self.queue.pop(0)
def top(self):
"""
Get the top element.
:rtype: int
"""
if self.queue:
return self.queue[0]
def empty(self):
"""
Returns whether the stack is empty.
:rtype: bool
"""
return len(self.queue) == 0
# Your MyStack object will be instantiated and called as such:
# obj = MyStack()
# obj.push(x)
# param_2 = obj.pop()
# param_3 = obj.top()
# param_4 = obj.empty()
第 10 题：跳台阶（斐波拉契数列、滚动变量）
传送门：AcWing：跳台阶。
输入一个整数
假定从
开始，第
)
样例：
输入整数
返回
。
思路：这题的数据范围很小，我们直接模拟即可。当数据范围很大时，就需要采用其他方式了，可以参考求解斐波那契数列的若干方法。
时间复杂度：总共需要计算 次，所以时间复杂度是
。
Python 代码1：用两个变量滚动式往后计算， 表示第
项，
表示第
项。则令
表示第
项，然后让
、
顺次往后移一位。
class Solution(object):
def Fibonacci(self, n):
"""
:type n: int
:rtype: int
"""
if n == 0:
return 0
if n == 1:
return 1
a = 0
b = 1
while n:
c = a + b
# “滚动变量”：接下来重新定义 a 和 b
a = b
b = c
n -= 1
return a
Python 代码2：Python 语法糖，了解即可
class Solution(object):
def Fibonacci(self, n):
"""
:type n: int
:rtype: int
"""
if n == 0:
return 0
if n == 1:
return 1
a = 0
b = 1
while n:
a , b = a + b , a
n -= 1
return a
Python 代码3：
class Solution:
def climbStairs(self, n):
"""
:type n: int
:rtype: int
"""
a = 0
b = 1
while n:
a , b = b , a + b
n -= 1
return b
参考资料：面试官问你斐波那契数列的时候不要高兴得太早。书上斐波拉契数列数列空间更省的写法，P76。
第 10-2 题：变态跳台阶
传送门：牛客网：变态跳台阶。
一只青蛙一次可以跳上
级台阶，也可以跳上
Python 代码：因为青蛙一次可以跳任意台阶，我们就让它跳 阶，所以初始值设置为
。
class Solution:
def jumpFloorII(self, number):
if number == 0:
return 1
if number == 1:
return 1
dp = [1 for _ in range(number + 1)]
dp[0] = 0
dp[1] = 1
for i in range(2, number + 1):
for j in range(1, i):
dp[i] += dp[j]
return dp[number]
思路2：
当 时，结果为
；
当 时，结果为
；
当 时，结果为
；
……
以此类推，使用数学归纳法不难发现，跳法 。
Python 代码：
class Solution:
def jumpFloorII(self, number):
# write code here
if number <= 2:
return number
total = 1
for _ in range(1, number):
total *= 2
return total
第 10-3 题：斐波拉契数列矩阵求法
参考资料：求解斐波那契数列的若干方法。
（本节完）
