剑指offer题目整理

剑指offer题目整理

依据解题方法划分：
一、根据数据结构划分
1.链表
O(1)时间内删除链表的某个节点：将要删除链表的下一个节点复制到本节点，本节点指针与下一个节点的指针指向的内容互换。头节点直接删除，尾节点扔需遍历。
反转链表：增加一个pre，一个cur，一个next
2.树
3.栈
从尾到头打印链表：元素插入栈，判断栈不为空则打印
两个栈实现队列：尾插，直接插入即可。头删，栈1数据转栈2，删除栈2顶部
包含min函数的栈：定义两个栈，一个存数据，一个存该数据对应的最小值。
栈的压入d出序列：构造辅助栈，压入元素，与pop相同则d出。注意边界条件，待压入为空时，辅助栈为空时，不相等时。true的条件为待pop的队列为空，辅助栈为空，即待push的队列也为空。
二叉树的后序遍历：取后序遍历的倒序，根，右，左。单调栈压入根节点，应依次增大。出现小则都小于原根节点，不满足则false。
4.队列
层序遍历二叉树:d出一个根节点，压入其左右子节点至队列的末尾，即可实现层序遍历。

5.字符串
表示数值的字符串：（1）空格（2）判断int（3）判断uint，即+和-
6.数组
二维数组中的查找：根据题目特点划定范围，自边角查找到中心
7.vector
顺时针打印矩阵：画图分解，分治思想，判断循环起始和结束条件。判断1234步四种压数据的条件。
8.map
数组中重复的数字：利用map
复杂链表的赋值：map

二、根据算法划分：
1.双指针
替换空格：尾部双指针向前复制
奇数位于偶数前面：双指针一前一后，前偶后奇，交换
链表中倒数第k个节点：双指针从前遍历
环的入口节点：（1）快慢指针判断环是否存在，存在返回节点必为环内节点（2）计数环节点数目，快慢指针重走链表
2.递归
斐波那契数列：
从尾到头打印链表：递归到尾部
重建二叉树：利用树的特性，前序遍历为根节点，中序遍历中寻找根节点，左侧为左子树，右侧为右子树
打印从1到最大的n位数：数字转为字符串防止越界，递归遍历至最低位再打印
数值的整数次方：0次方，负数次方，正数次方，结合递归，负数最终蜕化为-1
正则表达式匹配：结合分治思想，分为（1）直接忽略下一个*（2）当前匹配，字符+1，跳过下一个*（3）当前匹配，仅字符+1（4）顺序比较下一个，其中方式3通过第二次递归来实现，省略代码。
合并两个排序链表：递归比较
树的子结构：递归比较左子树，右子树
树的镜像：递归寻找叶节点
判断树是否对称：判断前序遍历和对称前序遍历，即右中左，是否对称，对称则二叉树是对称的。1树左对2树右，1树右对2树左
二叉树的后序遍历：注意划分mid，左右根，判断右子树存在情况下，若出现小于根节点的值，直接返回报错。
二叉树中和为某一值的路径：判断叶节点，判断和，push后需pop
序列化和反序列化二叉树：前序遍历，输入字符串处理，list存放，反序递归
（1）dfs
二叉搜索树与双向链表：dfs寻找最左，pre记录，然后找右节点

3.函数调用
从尾到头打印链表：压入vector，然后调用reverse函数
4.分治思想
（1）全排列思想：
字符串的全排列：判定条件为前后元素相同则不换，分为1和其后的部分
字符串的全组合：
遍历从1到n所有的子串，当求长度为m(1≤m≤n)的组合时，可以把那个字符分成两部分：第一个字符和其余所有的字符。
(1)组合包含第一个字符，则下一步在剩余字符里选取m-1个字符。
(2)组合不包含第一个字符，则下一步在剩余的n-1个字符中选取m个字符。
皇后棋盘：全排列思想，判定条件为对角线
正方体三面和相同：判定条件修改为三面和相同
5.查找方法
（1）二分
旋转数组的最小数字：首尾指针判断数字大小，不断取中点
6.排序
7.位运算
二进制整数中多少个1：(n - 1) & n
8.回溯法
矩阵中的路径：二维vector，判断是否已访问过，是否存在路径
机器人的运动范围：(x,y)坐标采用pair来组合，二维vector判断是否已访问过，判断和
9.动态规划
剪绳子：temp=result2[j] * result2[i -j],整理公式，j最大为i的一半
10.贪心
剪绳子2：采用贪心，优先3，其次2，因为4=2*2
11.dfs

赋值运算符函数