剑指Offer总结

最近快要面试了,再刷一遍剑指Offer,看大家分享刷LeetCode和剑指Offer的时候都是有模板的,如果按照随机顺序刷,很容易忘记而且不容易总结刷题思路。所以常常把一类题放到一块一起刷。

《剑指Offer》有如下优点:

  • 很可能在面试中出现原题(至少在微软面试经常能遇到原题)
  • 题量少,但是涵盖的内容较全,性价比较高
  • 能培养一个良好的刷题习惯

缺点是:

  • 题目较少,刷着容易过拟合
  • 动态规划的题比较少,因此需要在力扣上专项训练。

数据结构类题目

LinkedList

面试题06-从尾到头打印链表:stack(想到并写出了利用栈的方法,但是没想到递归的方法,但实际上两者需要内存大致相同)

面试题18-删除链表的节点:双指针,头结点处理时可以使用哑点或者特殊处理

面试题22-链表中倒数第k个结点:双指针(没想起思路)

面试题24-反转链表:三个指针。注意pre指针的初始化,另外最终返回的是pre指针

面试题25-合并两个排序的链表:双指针,哑点的使用(要注意基于递归的写法,建议练习)

面试题35-复杂链表的复制:(想到并写出了利用map的方法,但是没想到节省空间的方法)

面试题52-两个链表的第一个公共节点(想到并写出了利用栈的方法,但是没想到双指针法)

链表测试用例:

  1. 特殊输入测试(输入的链表头结点指针为NULL)
  2. 普通链表(输入的链表有多个节点;输入的链表只有一个节点)

套路:

  1. 哑点的使用
  2. 双指针、三指针等用法

Tree

面试题07-重建二叉树:递归(想到递归,终止判断条件和递归时子函数传参有误,根源在于对于迭代器和重建二叉树过程理解不到位)

面试题26-树的子结构:两个递归(有大概思路,但是代码没想到是两个递归,需注意递归终止条件)

面试题27-二叉树的镜像:递归(掌握,建议练习)

面试题32-1 -从上往下打印二叉树:队列(掌握)

面试题32-2 -从上往下打印二叉树 2:队列(掌握)

面试题32-3 -从上往下打印二叉树 3:两个栈(想到了使用<algorithm>reverse方法,但是没想到使用两个栈或者双边队列)

面试题33-二叉搜索树的后序遍历序列:后序遍历特点(未想起思路,代码需要这是一个递归过程)

面试题34-二叉树中和为某一值的路径:深度优先遍历,前序、中序、后序,这里用到了前序(想到了思路,但是不会写代码)

面试题36-二叉搜索树与双向链表:递归(没想到思路,第二遍仍然没有写出来代码,建议练习)

面试题55-1-二叉树的深度:递归(写的代码比较复杂)

面试题55-2-平衡二叉树:后序遍历(只想到了递归的方法,莫名其妙写成了后序遍历,建议练习)

面试题28-对称的二叉树:递归(有大致思路,但写不出具体代码)

面试题37-序列化二叉树:递归(有大致思路,但写不出具体代码,第二遍对于str库还不是很了解)

面试题54-二叉搜索树的第k大节点:中序遍历,右根左(掌握)

面试题68 - I-二叉搜索树的最近公共祖先:遍历(没有想到简单思路,第二遍代码写的复杂了,可以使用非递归的形式)

面试题68 - II-二叉树的最近公共祖先:遍历(没有想到思路,第二遍仍然没有想到简单思路)

二叉树测试用例:

  1. 普通二叉树(完全二叉树、非完全二叉树)
  2. 特殊二叉树(所有节点都没有右子节点的二叉树、所有节点都没有左子节点的二叉树、只有一个节点的二叉树)
  3. 特殊输入测试(二叉树的根节点指针为NULL;输入不满足题意)

看到二叉搜索树,就要想到前序、中序、后序遍历方式。其中中序遍历是按照从小到大的顺序排列的。

套路:

  • 尝试将递归语句放到if条件中,可以

Stack & Queue

面试题09-用两个栈实现队列:栈(想出来的思路不是最优解)

面试题30-包含min函数的栈:辅助栈(push函数有点小问题)

面试题31-栈的压入、弹出序列:辅助栈(没有想到思路,第二遍仍没有写出来最优解,建议练习)

面试题58-1-翻转单词顺序istringstream的使用(没有想到最优解,第二遍仍然不会用这个库,建议记忆)

面试题59-1-滑动窗口的最大值:双边队列(没有想到,第二遍仍然没有想到)

Heap

面试题40-最小的K个数:最小堆,priority_queue的使用(没有想起来思路,第二遍对于该库还不是很熟悉)

面试题41-数据流中的中位数:最大堆最小堆(没有想到思路,第二遍对库还不是很熟悉)

Hash Table

面试题50-第一个只出现一次的字符:哈希表(想到了思路,但不会写代码。第二遍没有想出来是两遍遍历)

面试题12-矩阵中的路径(BFS):回溯(能想到思路,代码不是很熟,第二遍代码仍然有问题,建议练习)

面试题13-机器人的运动范围(DFS):回溯(代码不是很熟练)

具体算法类题目

斐波那契数列

面试题10-1-斐波拉契数列:循环、递归(没有想到数字溢出的情况,第二遍仍然没有考虑到)

面试题10-2-青蛙跳台阶问题:循环、递归(掌握)

搜索算法

面试题04-二维数组中的查找:右上角开始(能想到思路,但是代码不太会写)

面试题11-旋转数组的最小数字:二分查找(思路也不是最优解,写出来的代码未完全覆盖所有测试用例)

面试题53-1-在排序数组中查找数字 I:二分查找(能想到思路,建议练习,注意)

面试题53-II-0~n-1中缺失的数字:二分查找(能想到思路,但是没有注意到缺失数字在数组末尾的情况,第二遍仍然没有注意到,建议练习)

全排列

面试题38-字符串的排列:递归(能想到思路,建议练习)

动态规划

面试题42-连续子数组的最大和:DP(掌握,但不知道方法是DP)

面试题19-正则表达式匹配:递归(未想到思路,第二遍思路仍然不清晰,建议练习)

面试题47-礼物的最大价值:DP(没写出来递推公式)

面试题48-最长不含重复字符的子字符串:DP(有思路但没想到转换为公式)

面试题60-n个骰子的点数:DP(没想出来状态表达式,且代码容易写错)

贪婪算法

面试题14-I-剪绳子:贪婪算法(没有想到思路)

面试题14-II-剪绳子:贪婪算法(没有想到思路,第二遍不会解决大数问题,建议练习)

回溯

面试题12-矩阵中的路径(BFS):回溯(能想到思路,代码不是很熟)

面试题13-机器人的运动范围(DFS):回溯(代码不是很熟练)

排序

面试题51-数组中的逆序对:归并排序(只想到了暴力求解的方法,经典建议练习)

面试题53-I-在排序数组中查找数字 I:二分查找

面试题40-最小的K个数:最小堆(没有想起来思路)

位运算

面试题15-二进制中1的个数:位运算(没有考虑到n&n-1)

面试题16-数值的整数次方:位运算(没有想到最优解,且测试用例想的不齐全,第二遍没有想到递归)

面试题56-1-数组中数字出现的次数:异或性质(没有想到最优解)

面试题56-2-数组中数字出现的次数 II:位运算(没有想到这个思路,第二遍仍然没有想出来解法)

面试题65-不用加减乘除做加法:位运算(没有想到思路,且没有考虑到负数的情况,第二遍仍然没有考虑到)

其他算法

面试题03-数组中重复的数字:元素交换(只想到基于map的思路,不是最优解)

面试题05-替换空格:从后向前移位(有思路,但是代码写的有问题)

面试题17-打印从1到最大的n位数:大数问题(代码写的有问题,第二遍代码仍然不熟悉)

面试题20-表示数值的字符串:主要考察代码的完整性(思路不是很清晰)

面试题21-调整数组顺序使奇数位于偶数前面:(有思路,但是写出来的代码不是最优的)

面试题39-数组中出现次数超过一半的数字:(只想到基于map的思路,不是最优解)

面试题43- 1~n整数中1出现的次数:一位一位的按照当前值为0,1,其他计算1出现次数(没有想到最优解,第二遍仍然没有想到最优解)

面试题44-数字序列中某一位的数字:找规律(能想到思路,但是无法正确转换为代码,第二遍仍是,建议练习)

面试题45-把数组排成最小的数:自定义排序(思路有,但无法转换为具体的公式,第二遍不会使用C++自定义排序)

面试题46-把数字翻译成字符串:循环(思路和官方思路稍有不同)

面试题49-丑数:空间换时间(没有理解题意,第二遍仍然没有写出来代码)

面试题57-1-和为s的两个数字:双指针(掌握)

面试题57-2-和为S的连续正数序列:前后指针(没有写出来最优解,第二遍没有写出来简便代码,建议练习)

面试题58-2-左旋转字符串:字符翻转(使用C++ string字符串切割拼接更简单,第二遍仍然没有写出来简单代码)

面试题61-扑克牌中的顺子:0的个数与中间元素的个数(没有抽象出具体问题,第二遍没有注意到相等的情况)

面试题62-圆圈中最后剩下的数:约瑟夫环(没有推出递推公式,第二遍仍然没有思路,建议练习)

面试题63-股票的最大利润:抽象建模(掌握)

面试题64-求1+2+…+n:发散思维(没有想法方法,第二遍仍然没有想到思路)

面试题66-构建乘积数组:矩阵(没有想到简便方法,建议练习)

面试题67-把字符串转换成整数:考虑问题的全面性、isdigit的使用(没有想到简洁代码的写法,第二遍没有想到函数库的使用)

注意事项

  • 每道题都要知道最优思路
  • 要会写结构体的定义和主函数
  • 每个算法都要分析时间、空间复杂度;想到所有的测试用例
------ 本文结束------
坚持原创技术分享,您的支持将鼓励我继续创作!

欢迎关注我的其它发布渠道