剑指offer题目总结
链表题目
- 从尾到头打印链表
- 反转链表
- 合并两个排序的链表(递归/遍历)
- 两个链表的第一个公共节点(双指针/哈希表)
- 链表中环的入口节点(快慢指针/字典)
- 链表中倒数最后k个节点(快慢指针)
- 复杂链表的复制(1. 复制 2. 随机指针复制 3.打断两个链表) -手写可能出错
- 删除链表中的节点(简单遍历)
总结：简单遍历+快慢指针+哈希
树题目
- 二叉树的深度(简单递归/队列辅助层次遍历)
- 按之字顺序打印二叉树(层次遍历 + flag判断奇偶层)
- 二叉搜索树的第k个节点(深度优先遍历，结合二叉搜索树的特点)
- 重建二叉树(递归 + 结合前序中序遍历的特点)
- 树的子结构(递归，注意三种匹配情况)
- 二叉树的镜像(递归，左右子树镜像，交换)
- 从上往下打印二叉树(简单的层次遍历)
- 二叉搜索树的后序遍历序列(递归，后序遍历，根节点)
- 二叉树中和为某一值的路径1(递归，不需保存路径)
- 二叉树中和为某一值的路径2(递归，保存路径, dfs)
- 二叉搜索树与双向链表(中序遍历，维护一个pre_node)
- 判断是不是平衡二叉树(递归判断，专门写一个判断树深度的函数即可)
- 二叉树的下一个节点(获取中序遍历序列/分情况讨论)
- 对称的二叉树(递归，输入两棵树，左右子树是否match， 因为单一递归，同时只能到一部分，需要两部分同步递归)
- 把二叉树打印成多行(用队列实现树的BFS)
- 序列化二叉树(确定规则，指针遍历，节点值后面加符号来分割树节点)
- 二叉树中和为某一值的路径3(层次遍历 + dfs/借助哈希表，一次遍历)
- 在二叉树中找到两个节点的最近公共祖先(dfs+最后一个共同节点/递归)
- 二叉搜索树的最近公共祖先(简单递归，利用二叉搜索树的特点)
总结: 树的题目基本都是围绕递归遍历展开
- 几种遍历方式: 前序、中序、后序、层次
- 合理考虑递归边界，特殊情况
队列&栈
- 用两个栈实现队列(进行两次压栈操作即可)
- 包含min函数的栈(普通栈+最小栈)
- 栈的压入弹出序列(辅助栈模拟)
- 翻转单词序列(两次翻转/直接split+join)
- 滑动窗口的最大值(双向队列，维护前向最大值)
总结：数据结构特点的基础应用
搜索算法
- 数字在升序数组中出现的次数(二分查找 target-0.5 target+0.5)
- 二维数组中的查找(有序数组，从角落开始搜索)
- 旋转数组中的最小数字(二分查找，特殊情况考虑，注意等号)
- 字符串的排列(遍历)
- 数字序列中的某一位数字(模拟, 几位数字位数关系)
总结：二分搜索 or 模拟遍历
动态规划
- 连续子数组的最大和(一维dp, 可以不另外开辟数组)
- 连续子数组最大和(二)(一维dp,维护起始位置，可以不另外开辟数组)
- 跳台阶(斐波那契数列)
- 斐波那契数列
- 正则表达式匹配(二维dp)
- 跳台阶扩展问题($2^{n-1}$)
- 矩阵覆盖(斐波那契数列)
- 买股票的最好时机(一维dp)
- 礼物的最大价值(二维dp, 可以不另外开辟数组)
- 最长不含重复字符的子字符串(借助字典，1维dp)
- 把数字翻译成字符串(一维dp)
总结： 这类问题的关键在于
- 状态的定义
- 状态转移方程的形式
回溯
- 矩阵中的路径(dfs + 标志矩阵)
- 机器人的运动范围(dfs + 标志矩阵)
dfs + 标志矩阵
排序
- 数组中重复的数字(哈希/位置重排)
- 数组中的逆序对(归并排序)
- 最小的k个数
- 数据流中的中位数
总结：熟练掌握归并排序和快速排序
位运算
- 不用加减乘除做加法(异或运算获取非进位和，与运算加左移算子获取进位信息)
- 二进制中1的个数(n&n-1, 将低位1变为0，注意处理负数)
- 数值的整数次方(借助二进制运算实现快速幂)
- 数组中只出现一次的两个数字(异或运算的特点)
- 求1+2+…+n(通过与运算终止递归)
模拟
- 顺时针打印矩阵(简单模拟，通过边界控制循环结束)
- 扑克牌顺子(借助hash)
- 把字符串转换成整数(去空格，找符号，转换，取模)
- 表示数值的字符串
其他算法
- 构建乘积数组
- 第一个只出现一次的字符
- 替换空格
- 调整数组顺序使奇数位于偶数前面
- 数组中出现超过一半次数的数字
- 整数中1出现的次数
- 把数组排成最小的数
- 丑数
- 和为S的连续正数序列
- 和为S的两个数字
- 左旋转字符串
- 孩子们的游戏(约瑟夫环)
- 字符流中第一个不重复地字符
- 剪绳子
- 调整数组顺序使奇数位于偶数前面
- 剪绳子(进阶版)
- 打印从1到最大的n位数
python中常用数据结构模块
- 队列
queue.Queue()
Queue().qsize(): 返回队列的大小Queue().empty(): 如果队列为空返回True，反之返回FalseQueue().full(): 如果队列满了，返回True,反之返回FalseQueue().get(): 获取队列的第一个值，出队列Queue().put(): 写入队列- 题目: 从上往下打印二叉树
import queue class Solution: def PrintFromTopToBottom(self , root: TreeNode) -> List[int]: # write code here res = [] if not root: return res q = queue.Queue() q.put(root) while not q.empty(): cur_node = q.get() res.append(cur_node.val) if cur_node.left: q.put(cur_node.left) if cur_node.right: q.put(cur_node.right) return res
- 双向队列
collections.deque()
deque(): 创建deque().append(): 向队列中添加元素deque().pop(): 抛出最后一个元素deque().leftpop(): 抛出第一个元素deque().extend(): 添加list项到原deque()中deque().extendleft(): 添加list项到原deque()头部题目: 滑动窗口的最大值
from collections import deque class Solution: def maxInWindows(self , num: List[int], size: int) -> List[int]: # write code here res = [] dq = deque() if size > len(num) or not size: return [] for i in range(size): while len(dq) > 0 and num[dq[-1]] < num[i]: dq.pop() dq.append(i) for i in range(size, len(num)): res.append(num[dq[0]]) while len(dq) > 0 and dq[0] < i - size + 1: dq.popleft() while len(dq) > 0 and num[dq[-1]] < num[i]: dq.pop() dq.append(i) res.append(num[dq[0]]) return res
- 小根堆
heapq
heapq.heappush(pq, value)入堆heapq.heapreplace(pq,value)替换堆中元素heapq.pop(pq)出堆
collections.defaultdict()dict的一个子类，可以使创建的字典具有默认值，可以预先指定默认值类型：
在python中，可哈希的数据类型有：import collections mp = collections.defaultdict(list) # 默认值为[] mp = collections.defaultdict(int) # 默认值为0 mp = collections.defaultdict(lambda:999) # 默认值为999
- 数字类型(
int、float、bool), 字符串str、元组tuple
不可哈希的数据类型有:
