# 心得 - 先想思路，再动手写代码 - 从前往后，从后往前，从上到下，从下到上 - 一个指针、两个指针、多个指针。快慢指针、从开头或结尾开始的指针、先走几步的指针 - 遍历寻找某个值可以考虑二分法（基于BF（暴力算法）） - 二进制问题可以尝试n&=n-1 - 能不取模就不取模 - 删除单链表的元素必须知道pre - 链表尽量用带头结点的 - 数组可以考虑双指针，一前一后、一个开头一个结尾等等 ## 2. 基础知识 ### 2.2 编程语言 #### 二、实现单例模式 ##### 考点 - 多线程，同步锁 - 静态构造函数 ##### 解法 1. 利用静态构造函数 缺点：第一次使用类的时候就会创建单例变量，还可以继续改进 2. 按需创建实例 创建一个内部类，增加静态变量 不需要加锁 #### 2.3 数据结构 ##### 2.3.1 数组 #### 三、数组中重复的数字 ##### 考点 算法复杂度分析 ##### 解法 1. 修改原数组（0到n-1） - 排序 - 哈希表 - 重排，交换位置 注意判断下标和元素是否相等应该用while循环，因为可能换到的不是自己的位置，虽然两个循环，但是每个元素最多交换两次即可找到自己的位置 时间O（n）空间O（1） 2. 不修改原数组（1到n） 时间O（nlogn）空间O（1） 划分范围，统计次数，大于一定重复，小于可能重复（找不出来） #### 四、二维数组中的查找 ##### 考点 二维数组 ##### 解法 从右上角/左下角开始遍历，删除列或者行 2.3.2 字符串 五、替换空格 ##### 考点 复杂度优化 从后往前 双指针 ##### 解法 从后往前遍历 双指针 2.3.3 链表 六、逆序打印链表 ##### 考点 递归 递归过深可能导致栈溢出，而且效率没有遍历高，因为函数出栈入栈消耗比较大，要记录各种变量，重复计算比较多 遍历 栈 ##### 解法 问面试官允不允许修改原链表 不允许用栈（遍历）、递归 允许的话可以逆置链表 2.3.4 树 七、重建二叉树 八、二叉树的下一个节点 2.3.5 栈和队列 九、用两个栈实现队列 补充：用两个队列实现栈 2.4 算法和数据操作 2.4.1 递归和循环 十、斐波那契数列 补充 2.4.2 查找和排序 十一、旋转数组的最小数字 2.4.3 回溯法（暂时跳过） 2.4.4 动态规划与贪婪算法（暂时跳过） 十四、剪绳子 2.4.5 位运算 十五、二进制中1的个数 3. 高质量的代码 3.1 面试官谈代码质量 3.2 代码的规范性 3.3 代码的完整性 十六、数值的整数次方 十七、打印从1到最大的n位数 十八、删除列表的节点 十九、正则表达式匹配（没看懂，先跳过） 二十、表示数值的字符串（又是字符串，继续跳过） 二十一、调整数组顺序 3.4 代码的鲁棒性 二十二、链表中倒数第k个节点 ##### 考点 ##### 解法 快指针先走k-1步，然后慢指针再走，快指针走到结尾，慢指针指的就是倒数第k个节点 二十三、链表中环的入口节点 ##### 解法 快慢指针，一个走一步，一个走两步，可以拿到相交的节点，可能是入口也可能是出口 确定环内节点个数k 用两个指针，一个先走k步，另一个再从头开始，两个速度相同，第一个走到头，第二个指向的节点即为入口节点 二十四、反转链表 ##### 解法 新链表头插法 多个指针，遍历一遍，核心代码：current.next=pre 记得用指针保存断开后的链表 二十五、合并两个排序的链表 ##### 解法 并转串 注意最后可能有链表没合并完 补充 合并k个 最小堆：二叉树，根节点是最小的，每次取出根节点都要重新构建最小堆 二十六、树的子结构 ##### 考点 树的遍历 指针 ##### 解法 遍历，找到根节点相同的，然后判断 4. 解决面试题的思路 4.1 面试官谈面试思路 先解释思路，再动手写代码 4.2 画图让抽象问题形象化 二十七、二叉树的镜像 二十八、对称的二叉树 二十九、顺时针打印矩阵 4.3 举例让抽象问题具体化 三十、包含min函数的栈 三十一、栈的压入弹出序列 三十二、从上到下打印二叉树 一、不分行 二、分行 三、之字形 三十三、二叉搜索树的后序遍历序列 三十四、二叉树中和为某一值的路径 ##### 解法 dfs，注意保存路径的时候new一个新的list 4.4 分解让复杂问题简单化 三十五、复杂链表的复制