offer
Leetcode 59. 螺旋矩阵 II && 剑指 Offer 29. 顺时针打印矩阵
这两个题非常相似，但是前者较为简单，后者较难。 由于前者访问的矩阵是方阵，因此可以通过迭代去做（因为方阵每次迭代，长和宽缩水的大小是一样的，但是矩阵不可以，因为矩阵最后一次迭代，长和宽的缩水不一定一样） class Solution { public: vector<vector<int>> gen ......
【剑指Offer】12、数值的整数次方
# 【剑指Offer】12、数值的整数次方 **题目描述：** 给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。 **解题思路：** 本题看似比较简单，是一个简单的指数运算，但需要完整的考虑到所有情况。首先，对于底数，如果底数为0，则0的 ......
【剑指Offer】10、矩形覆盖
# 【剑指Offer】10、矩形覆盖 **题目描述：** 我们可以用2 X 1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个2 X 1的小矩形无重叠地覆盖一个2 X n的大矩形，总共有多少种方法？ **解题思路：** 我们可以以2 X 8的矩形为例。 =1；当有两级台阶时，f(2)=f(2-1)+f(2-2)；一般情况下，当有n级台阶 ......
剑指 Offer 68 - I. 二叉搜索树的最近公共祖先（简单）
题目：  ``` class Solution { public: TreeNode* lowestCommonAnc ......
【剑指Offer】8、跳台阶
# 【剑指Offer】8、跳台阶 **题目描述：** 一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。 **解题思路：** 首先考虑最简单的情况，如果只有1级台阶，显然只有一种跳法。如果有两级台阶，就有两种跳法：一种是分两次跳，一 ......
【剑指Offer】7、斐波那契数列
# 【剑指Offer】7、斐波那契数列 **题目描述：** 大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0）。假设n<=39。 **解题思路：** 斐波那契数列：0,1,1,2,3,5,8........ 总结起来就是：第一项是0，第二项是1，后续 ......
【剑指Offer】21、栈的压入、弹出序列
# 【剑指Offer】21、栈的压入、弹出序列 **题目描述：** 输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1 ......
《剑指Offer》-40-最小的 K 个数
如果直接调用 sort API 然后要几个打印几个就没意思了，应该是和某个排序的内部过程结合 首先排除O(^N2^)的低效率排序算法，最先想到的其实是堆排序，小根堆，但是需要额外的空间 其次像快排、归并这样的也不合适…… 我想到了可以这样，快排第一轮划分之后，将部分舍去…… 应该就是这样了，堆排序或 ......
剑指 Offer 55 - I. 二叉树的深度（简单）
题目：  ``` class Solution { public: void traversal(TreeNode* ......
剑指 Offer 54. 二叉搜索树的第k大节点
方法一： 由于是有序的平衡二叉树，因此是中序。根据dfs中序迭代求得递增排序后，再反转就可求得结果。 class Solution { public: vector<int> tmp; int kthLargest(TreeNode* root, int k) { // if(root != NUL ......
【剑指Offer】20、包含min函数的栈
# 【剑指Offer】20、包含min函数的栈 **题目描述：** 定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的min函数（时间复杂度应为O（1））。 **解题思路：** 解法一：使用两个stack，一个为数据栈，另一个为辅助栈。数据栈用于存储所有数据，每次压栈的最小元素（之前的 ......
【剑指Offer】5、用两个栈实现队列
# 【剑指Offer】5、用两个栈实现队列 **题目描述：** 用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型。 **解题思路：** 本题的基本意图是：用两个后入先出的栈来实现先入先出的队列。对于这个问题，我们可以通过一个实例来进行具体分析。不难得出相应的规律：有 ......
【剑指Offer】66、机器人的运动范围
# 【剑指Offer】66、机器人的运动范围 **题目描述：** 地上有一个m行和n列的方格。一个机器人从坐标0,0的格子开始移动，每一次只能向左，右，上，下四个方向移动一格，但是不能进入行坐标和列坐标的数位之和大于k的格子。 例如，当k为18时，机器人能够进入方格（35,37），因为3+5+3+7 ......
剑指 Offer 36. 二叉搜索树与双向链表
本题比较重要的有两点： 1.一般认为有序的二叉搜索树，都是中序遍历。 2.中序遍历的递归顺序，得到的就是排好序的，就是链表的顺序，因此只需管遍历的过程中的链表指向即可。 class Solution { public: // pre将来指向尾节点，head指向头节点 Node *pre = null ......
剑指 Offer 16. 数值的整数次方（中等）
题目  ``` class Solution { public: double traversal(double ......
剑指 Offer 34. 二叉树中和为某一值的路径
dfs class Solution { public: vector<vector<int>> res; vector<int> tmp; void dfs(TreeNode *node, int target) { if(node == nullptr ) return; target -= n ......
【剑指Offer】65、矩阵中的路径
# 【剑指Offer】65、矩阵中的路径 **题目描述：** 请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向左，向右，向上，向下移动一个格子。如果一条路径经过了矩阵中的某一个格子，则之后不能再次进入这个格子。 例如 ......
【剑指Offer】62、二叉搜索树的第k个结点
# 【剑指Offer】62、二叉搜索树的第k个结点 **题目描述：** 给定一棵二叉搜索树，请找出其中的第k小的结点。例如（5，3，7，2，4，6，8） 中，按结点数值大小顺序第三小结点的值为4。 **解题思路：** 本题实际上比较简单，主要还是考察对树的遍历的理解，只要熟练掌握了树的三种遍历方式及 ......
【剑指Offer】61、序列化二叉树
# 【剑指Offer】61、序列化二叉树 **题目描述：** 请实现两个函数，分别用来序列化和反序列化二叉树。 **解题思路：** 序列化是指将结构化的对象转化为字节流以便在网络上传输或写到磁盘进行永久存储的过程。反序列化是指将字节流转回结构化的对象的过程，是序列化的逆过程。 受第4题：重建二叉树的 ......
剑指 Offer 07. 重建二叉树（中等）
题目：  ``` class Solution { //本题思路：利用中序遍历，从前序遍历中找到左、右子树的根节点 ......
《剑指Offer》-31-栈的压入、弹出序列
经典的选择题，但是这里要求用代码实现 我们可以根据 pop 结果去模拟这个过程，如果能够拟合，就是 true 什么情况下拟合成功？ 两个指针都指向了数组末尾，同时栈空 太复杂了，条件能否简化一点？ 什么时候拟合失败？ pushed 指针指向末尾全部压入栈中，但是poped 数组指针卡住了，不匹配导致 ......
《剑指Offer》-16-数值的整数次方
将 n 次相乘的幂运算转化为 log2N 次平方运算，并且采用**递归**算法 原书给出的==最优算法本身不处理负数，是外层函数处理的== ```cpp double myPow(double x, int n) { double res = pow(x, abs(n)); if (n > 1);/ ......
【剑指Offer】60、把二叉树打印成多行
# 【剑指Offer】60、把二叉树打印成多行 **题目描述：** 从上到下按层打印二叉树，同一层结点从左至右输出。每一层输出一行。 **解题思路：** 本题可类比第22题：从上往下打印二叉树[https://www.cnblogs.com/bujidao1128/p/17627566.html]( ......
【剑指Offer】59、按之字形顺序打印二叉树
# 【剑指Offer】59、按之字形顺序打印二叉树 **题目描述：** 请实现一个函数按照之字形打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右至左的顺序打印，第三行按照从左到右的顺序打印，其他行以此类推。 **解题思路：** 这道题仍然是二叉树的遍历，相当于层次遍历，可以和第22题：从上 ......
【剑指Offer】58、对称的二叉树
# 【剑指Offer】58、对称的二叉树 **题目描述：** 请实现一个函数，用来判断一颗二叉树是不是对称的。注意，如果一个二叉树同此二叉树的镜像是同样的，定义其为对称的。 **解题思路：** 本题判断一棵树是不是对称的，和第18题可以对比分析：二叉树的镜像，和LeetCode第101题：101. ......
剑指 Offer 37. 序列化二叉树（困难）
题目：  ``` class Codec { public: void rserialize(TreeNode* r ......
【剑指Offer】39、平衡二叉树
# 【剑指Offer】39、平衡二叉树 **题目描述：** 输入一棵二叉树，判断该二叉树是否是平衡二叉树。这里的定义是：如果某二叉树中任意结点的左、右子树的深度相差不超过1，那么它就是一棵平衡二叉树。 **解题思路：** 首先对于本题我们要正确理解，一般情况下，平衡二叉树就是AVL树，它首先是二叉搜 ......
【剑指Offer】57、二叉树的下一个结点
# 【剑指Offer】57、二叉树的下一个结点 **题目描述：** 给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。 **解题思路：** 本题解决起来并不是很困难，主要是分析清楚所有可能的不同情况。对于中序遍历序列 ......
【剑指Offer】38、二叉树的深度
**题目描述：** 输入一棵二叉树，求该树的深度。从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度。 **解题思路：** 本题相对比较简单。根据二叉树深度的定义，我们有以下理解：如果一棵树只有一个结点，那么它的深度为1。如果根结点只有左子树而没有右子树，那么树 ......