leetcode剑指offer合集+题解
一、用两个栈实现队列
题目
解题思路
维护两个栈,一个维护插入,一个维护删除。需要删除的时候可以把插入栈里的元素全部倒进删除栈里,注意只有删除栈为空了,才会倒,否则会破坏元素的顺序。很巧妙。
AC代码
1 | class CQueue |
二、包含min函数的栈
题目
为栈新增功能,$O(1)$得到栈中最小值。
解题思路
如果当前压入的元素不是最小值,那么它一定不会作为最小值。所以我们只需要开一个辅助单调栈维护好每个“在压入时是最小值”的元素。
AC代码
1 | class MinStack |
三、从尾到头打印链表
题目
解题思路
简单题,可以遍历一遍reverse,或者递归回溯打印。
AC代码
1 | class Solution |
四、反转链表
题目
解题思路
遍历并反转即可。
AC代码
1 | class Solution |
五、复杂链表的复制
题目
解题思路
模拟一遍即可。
AC代码
1 | class Solution |
六、替换空格
题目
解题思路
无
AC代码
1 | class Solution |
七、左旋转字符串
题目
解题思路
无
AC代码
1 | class Solution |
八、数组中重复的数字
题目
解题思路
无
AC代码
1 | class Solution |
九、I. 在排序数组中查找数字
题目
解题思路
无
AC代码
1 | class Solution |
十、II. 0~n-1中缺失的数字
题目
解题思路
无
AC代码
1 | class Solution |
十一、二维数组中的查找
题目
解题思路
遍历每一列,采用二分,时间复杂度$O(nlogm)$
官方题解:从右上角出发,边走边选择,时间复杂度$O(nlogm)$
AC代码
1 | class Solution |
十二、旋转数组的最小数字
题目
解题思路
判断一下转折位置和corner test
即可。
AC代码
1 | class Solution |
十三、第一个只出现一次的字符
题目
解题思路
无
AC代码
1 | class Solution |
十四、I. 从上到下打印二叉树
题目
解题思路
遍历一遍即可。、好吧,其实可以直接BFS。
AC代码
1 | class Solution |
十五、从上到下打印二叉树 II
题目
剑指 Offer 32 - II. 从上到下打印二叉树 II
解题思路
同上一题
AC代码
1 | class Solution |
十六、从上到下打印二叉树 III
题目
解题思路
对奇数深度的reverse一下即可。
也可以使用deque。
AC代码
1 | class Solution |
十七、树的子结构
题目
解题思路
枚举A树上的一个节点作为根,和B数进行递归比较。
AC代码
1 | class Solution |
十八、二叉树的镜像
题目
解题思路
遍历树并交换所有左右儿子即可。
AC代码
1 | class Solution |
十九、对称的二叉树
题目
解题思路
双指针即可。
AC代码
1 | class Solution |
二十、斐波那契数列
题目
解题思路
略
AC代码
1 | class Solution |
二十一、青蛙跳台阶问题
题目
解题思路
略
AC代码
1 | class Solution |
二十二、股票的最大利润
题目
解题思路
维护前缀最小值。
AC代码
1 | class Solution |
二十三、连续子数组的最大和
题目
解题思路
当sum为负数时,丢弃肯定是最优的。
AC代码
1 | class Solution |
二十四、礼物的最大价值
题目
解题思路
动态规划。
AC代码
1 | class Solution |
二十五、把数字翻译成字符串
题目
解题思路
动态规划。
1 | dp[i] = (val <= 25 && val >= 10 ? |
AC代码
1 | class Solution |
二十六、最长不含重复字符的子字符串
题目
解题思路
尺取
AC代码
1 | class Solution |
二十七、删除链表的节点
题目
解题思路
略
AC代码
1 | class Solution |
二十八、链表中倒数第k个节点
题目
解题思路
维护size = k 的队列。
双指针更优。
AC代码
1 | class Solution |
二十九、合并两个排序的链表
题目
解题思路
双指针。
AC代码
1 | class Solution |
三十、两个链表的第一个公共节点
题目
解题思路
哈希表记录。
AC代码
1 | class Solution |
三十一、调整数组顺序使奇数位于偶数前面
题目
解题思路
略
AC代码
1 | class Solution |
三十二、和为s的两个数字
题目
解题思路
哈希表。
可以使用双指针。
AC代码
1 | class Solution |
三十三、翻转单词顺序
题目
解题思路
可以双指针。
AC代码
1 | class Solution |
三十四、矩阵中的路径
题目
解题思路
dfs即可。
AC代码
1 | class Solution |
三十五、机器人的运动范围
题目
解题思路
dfs、bfs都可以。
AC代码
1 | class Solution |
三十六、二叉树中和为某一值的路径
题目
解题思路
dfs即可。
AC代码
1 |
|
三十七、二叉搜索树与双向链表
题目
解题思路
中序遍历一遍即可。
AC代码
1 | class Solution |
三十八、二叉搜索树的第k大节点
题目
解题思路
中序遍历时先遍历右儿子即可。
AC代码
1 | class Solution |
三十九、把数组排成最小的数
题目
解题思路
a + b > b + a 则进行交换。
AC代码
1 | class Solution |
四十、扑克牌中的顺子
题目
解题思路
成立条件:
- 没有重复的扑克牌
- 去掉0,最大值减最小值 < 5
AC代码
1 | class Solution |
四十一、最小的k个数
题目
解题思路
排序即可。
AC代码
1 | class Solution |
四十二、数据流中的中位数
题目
解题思路
对顶堆。
AC代码
1 | class MedianFinder |
四十三、二叉树的深度
题目
解题思路
递归回溯统计。
AC代码
1 | class Solution |
四十四、平衡二叉树
题目
解题思路
递归求深度即可。
AC代码
1 | class Solution |
四十五、求1+2+…+n
题目
解题思路
递归。
题解还有快速乘。
AC代码
1 | class Solution |
四十六、二叉搜索树的最近公共祖先
题目
解题思路
根据二叉搜索树的性质,left->val < now->val < right->val
如果p->val == now->val
,now就是LCA,并且和p为同一节点;
如果q->val == now->val
,now就是LCA,并且和q为同一节点;
如果p->val > now->val && q->val < now->val
,now就是LCA;
如果p->val < now->val && q->val > now->val
,now就是LCA;
如果p->val < now->val && q->val < now->val
,向左递归;
如果p->val > now->val && q->val > now->val
,向右递归;
AC代码
1 | class Solution |
四十七、二叉树的最近公共祖先
题目
解题思路
先遍历一次,把所有结点的父亲用哈希表存下来。
然后两个结点都向根节点移动,第一个相遇的节点就是LCA。
AC代码
1 | class Solution |
四十八、重建二叉树
题目
给出先序遍历和中序遍历,求后序遍历。
解题思路
先序遍历顺序为[根结点][左子树][右子树]
中序遍历顺序为[左子树][根结点][右子树]
思路:
- 对于所有的子树,先序遍历的第一个结点为根结点。
- 找到中序遍历中的根结点,可以得到左子树和右子树的 size。
- 这样一直递归划分左右子树,递归到叶结点返回即可。
AC代码
1 | class Solution |
四十九、数值的整数次方
题目
解题思路
快速幂,注意n为负数的情况。
AC代码
1 | class Solution |
五十、二叉搜索树的后序遍历序列
题目
解题思路
后序遍历的遍历结构为[左子树][右子树][根结点]
二叉搜索树的特点是根结点大于左子树的所有值,小于右子树的所有值
AC代码
1 | class Solution |
五十一、二进制中1的个数
题目
解题思路
位运算。
AC代码
1 | class Solution |
五十二、不用加减乘除做加法
题目
解题思路
用 & 操作找出进位。
用 ^ 操作找出除去非进位的加和结果。
循环相加到无进位即可。
AC代码
1 | class Solution |
五十三、数组中数字出现的次数
题目
解题思路
考虑将两个数分成两组,并分别将两组值异或起来,即可得到两个数。
先将所有值进行异或,可以得到这两个数的异或值res。找到res为1的某个位,因为两个数异或值为1,那么必然有一个数这个位上为0,另一个数这个位上为1。按照这一位进行分组即可。
AC代码
1 | class Solution |
五十四、数组中数字出现的次数 II
题目
剑指 Offer 56 - II. 数组中数字出现的次数 II
解题思路
把每个数每一位拆出来,出现次数不是3的倍数的位就是这个数的位。
tips:其实两个数的异或也是这个原理,把3改成2即可。
AC代码
1 | class Solution |
五十五、数组中出现次数超过一半的数字
题目
解题思路
按位拆分
AC代码
1 | class Solution |
五十六、构建乘积数组
题目
解题思路
特判0即可。
AC代码
1 | class Solution |
五十七、剪绳子
题目
解题思路
猜想尽可能等分是最优的。
好像经过证明,最多分成三段。
AC代码
1 | class Solution |
五十八、和为s的连续正数序列
题目
解题思路
枚举起点。
可以解方程O1,数学不好放弃。
AC代码
1 | class Solution |
五十九、圆圈中最后剩下的数字
题目
解题思路
AC代码
1 |
六十、顺时针打印矩阵
题目
解题思路
模拟
AC代码
1 | class Solution |
六十一、栈的压入、弹出序列
题目
解题思路
模拟
AC代码
1 |
|
六十二、表示数值的字符串
题目
解题思路
AC代码
1 |
六十三、把字符串转换成整数
题目
解题思路
模拟
AC代码
1 | class Solution |
六十四、滑动窗口的最大值
题目
解题思路
单调队列。
如果队首的元素的距离和当前元素的距离超过窗口大小,应该弹出队列。
如果当前的元素大于队尾的元素,那么队尾的元素肯定不会作为最大值贡献了,也应该弹出队列。
AC代码
1 | class Solution |
六十五、队列的最大值
题目
解题思路
维护单调队列
AC代码
1 | class MaxQueue |
六十六、序列化二叉树
题目
解题思路
(原来只要能解密出自己加密的字符串就行… …
把所有叶子结点悬挂两个null即可。
AC代码
1 | class Codec |
六十七、字符串的排列
题目
解题思路
事实证明,STL的next_permutation才是yyds。
AC代码
1 | class Solution |
六十八、正则表达式匹配
题目
解题思路
好恶心的题,情况太多了。
wa了七次,勉强算是ac吧。
AC代码
1 | class Solution |
六十九、丑数
题目
解题思路
简单思路:堆维护
优秀的思路:动态规划,dp[i]表示第i个丑数,一个丑数肯定是由前一个数乘2/3/5得来的,并且dp[i-1]是正确的,那么dp[i]一定要大于dp[i-1]。
AC代码
1 | class Solution |
七十、n个骰子的点数
题目
解题思路
简单的动态规划。可以用滚动数组优化。
AC代码
1 | class Solution |
七十一、打印从1到最大的n位数
题目
解题思路
据说应该考虑大数。
AC代码
1 | class Solution |
七十二、数组中的逆序对
题目
解题思路
树状数组求逆序对板子题。
AC代码
1 |
|
七十三、剪绳子 II
题目
解题思路
有个结论,将绳子尽可能切成若干个3的长度,如果最后剩余1,$2\times2 > 1\times3$,因此将一个3分成2更优。
(具体证明还没看)
AC代码
1 | class Solution |
七十四、1~n 整数中 1 出现的次数
题目
解题思路
数位DP。对!limit
进行记忆化,会更快。
AC代码
1 | class Solution |
七十五、数字序列中某一位的数字
题目
解题思路
AC代码
1 |
待完成:
- 五十九:约瑟夫环
- 六十二:字符串数值类型判读
- 七十五:数字序列中某一位