剑指Offer算法

总结整理，剑指Offer上笔刷的算法习题

算法题

数组和矩阵

• 【简单】数组中重复的数字
• 【简单】替换空格
• 【简单】第一个只出现一次的字符位置
• 【中等】二维数组中的查找
• 【较难】顺时针打印矩阵

栈、队列、堆

• 【简单】两个栈实现队列
• 【中等】最小的k个数
• 【中等】数据流中的中位数
• 【中等】栈的压入、弹出序列
• 【中等】字符流中的第一个不重复的字符
• 【较难】滑动窗口的最大值
• 【较难】包含min函数的栈

双指针

• 【中等】和为S的两个数字
• 【中等】和为S的连续正数序列
• 【中等】左旋转字符串
• 【较难】翻转单词顺序列

链表

• 【简单】合并两个排序的链表
• 【简单】两个链表的第一个公共结点
• 【简单】从尾到头打印链表
• 【中等】链表中倒数第K个结点
• 【中等】反转链表
• 【中等】链表中环的入口结点
• 【较难】删除链表中重复的结点
• 【较难】复杂链表的复制

树

• 【简单】从上往下打印二叉树
• 【简单】二叉树的镜像
• 【简单】二叉树的深度
• 【简单】判断是不是平衡二叉树
• 【中等】把二叉树打印成多行
• 【中等】重建二叉树
• 【中等】二叉树的下一个结点
• 【中等】二叉查找树的第K个结点
• 【中等】二叉搜索树的后序遍历序列
• 【较难】树的子结构
• 【困难】对称的二叉树
• 【简单】二叉树中和为某一值的路径(一)
• 【中等】二叉树中和为某一值的路径(二)
• 【中等】二叉树中和为某一值的路径(三)
• 【中等】二叉搜索树与双向链表
• 【较难】序列化二叉树
• 【简单】二叉搜索树的最近公共祖先
• 【中等】在二叉树中找到两个节点的最近公共祖先

综合类型

贪心思想

• 【中等】剪绳子
• 【较难】剪绳子（进阶版）

二分查找

• 【简单】旋转数组的最小数字
• 【中等】数字在升序数组中出现的次数

分治

• 【中等】数值的整数次方

排列

• 【中等】调整数组顺序使奇数位于偶数前面
• 【中等】数组中的逆序对
• 【较难】把数组排成最小的数

动态规划

• 【入门】斐波那契数列
• 【简单】跳台阶 要么跳一阶，要么跳两阶
• 【简单】连续子数组的最大和
• 【简单】构建乘积数组
• 【中等】变态跳台阶 找规律 可跳任意阶
• 【中等】矩形覆盖
• 【较难】丑数

数学问题

• 【简单】数组中出现次数超过一半的数字
• 【中等】圆圈中最后剩下的数 约瑟夫问题
• 【中等】从1到n整数中1出现的次数

位运算

• 【中等】二进制中1的个数
• 【中等】数组中只出现一次的两个数字

其他分类

• 【简单】不用加减乘除做加法
• 【中等】扑克牌顺子
• 【较难】把字符串转换成整数

参考资料

• 牛客网：https://www.nowcoder.com/exam/oj/ta?tpId=13