若干数据结构 && 算法面试题【四】（更新ing)
这是我的第三个面试题汇总。
想看之前的内容请移步
http://zhweizhi.blog.51cto.com/10800691/1763237
若干数据结构 && 算法面试题【一】更新完毕
http://zhweizhi.blog.51cto.com/10800691/1775780
若干数据结构 && 算法面试题【二】更新完毕
http://zhweizhi.blog.51cto.com/10800691/1787562
若干数据结构 && 算法面试题【三】更新完毕
另外我的全部刷题代码都在这里
https://github.com/HonestFox/BrushQuestion
//第四篇啦终于放暑假啦可以安安心心学习啦 (●ˇˇ●)
//因为刚开始刷题的时候还没有接触过二叉树，所以只要遇到二叉树的问题就跳过了
//慢慢的居然积压了这么多，
//如今题总算快刷完了 接下来的这些问题主要是 二叉树相关的面试题了
————————————————————————————————————————
一、带环链表中环的入口
题目描述:
一个链表中包含环请找出该链表的环的入口结点。
分析
· 首先用两个指针 Fast 和 SlowFast每次走两步Slow每次走一步这样最终这两个指针会在环内相遇相遇时让它们停下来;
· 这时设Slow走的步数为s则Fast走的步数为2s 此外Fast肯定比Slow多走一个环长 r所以 s = r
· 设起点到环入口点这一段的长度为x 则相遇时Slow在环内走了 r - x, 那么相遇点继续走也就是后半部分到环入口的距离为 r - (r - x) = x 可以看出x刚好也是起点到环入口的举例
· 所以再让两个指针分别从pHead 和 相遇点开始每次走一步直到两个指针相交这时的交点就是环的入口
·
代码
ListNode* EntryNodeOfLoop(ListNode* pHead)
{
if (pHead == NULL || pHead->next == NULL || pHead->next->next == NULL)
{
return NULL;
}
if (pHead->next == pHead)
{
return pHead;
}
ListNode *FastNode = pHead;
ListNode *SlowNode = pHead;
while (FastNode != SlowNode || FastNode == pHead)
{
FastNode = FastNode->next->next;
SlowNode = SlowNode->next;
if (SlowNode == pHead)
{
return pHead;;
}
}
ListNode *pos = FastNode;
ListNode *cur = pHead;
while (FastNode != cur)
{
FastNode = FastNode->next;
cur = cur->next;
}
return cur;
}
github:
https://github.com/HonestFox/BrushQuestion/blob/master/55_%E9%93%BE%E8%A1%A8%E4%B8%AD%E7%8E%AF%E7%9A%84%E5%85%A5%E5%8F%A3%E7%BB%93%E7%82%B9
二、二叉树的下一个结点
题目描述:
给定一个二叉树和其中的一个结点请找出中序遍历顺序的下一个结点并且返回。
注意树中的结点不仅包含左右子结点同时包含指向父结点的指针。
github:
https://github.com/HonestFox/BrushQuestion/blob/master/56_%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E4%B8%8B%E4%B8%80%E4%B8%AA%E8%8A%82%E7%82%B9
三、对称的二叉树
题目描述
请实现一个函数用来判断一颗二叉树是不是对称的。注意如果一个二叉树同此二叉树的镜像是同样的定义其为对称的。
github
https://github.com/HonestFox/BrushQuestion/blob/master/57_%E5%AF%B9%E7%A7%B0%E7%9A%84%E4%BA%8C%E5%8F%89%E6%A0%91
四、把二叉树打印成多行
题目描述
从上到下按层打印二叉树，同一层结点从左至右输出。每一层输出一行。
github：
https://github.com/HonestFox/BrushQuestion/blob/master/58_%E6%8A%8A%E4%BA%8C%E5%8F%89%E6%A0%91%E6%89%93%E5%8D%B0%E6%88%90%E5%A4%9A%E8%A1%8C
五、之字形打印二叉树
题目描述
请实现一个函数按照之字形打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右至左的顺序打印，第三行按照从左到右的顺序打印，其他行以此类推。
github：
https://github.com/HonestFox/BrushQuestion/blob/master/59_%E4%B9%8B%E5%AD%97%E5%BD%A2%E6%89%93%E5%8D%B0%E4%BA%8C%E5%8F%89%E6%A0%91
六、序列化与反序列化二叉树
github：
https://github.com/HonestFox/BrushQuestion/blob/master/60_%E5%BA%8F%E5%88%97%E5%8C%96%E4%BA%8C%E5%8F%89%E6%A0%91
七、求二叉树中两个节点最近的公共祖先结点
struct TreeNode
{
public:
TreeNode(int val)
:_val(val)
, _left(NULL)
, _right(NULL)
{}
public:
int _val;
TreeNode *_left;
TreeNode *_right;
};
可以访问父节点的话：
首先，假设如果这颗二叉树的结点可以有指向父节点的指针，那么问题可以转化为对一颗三叉链，给定两个结点求他们最近的公共祖先结点。
所以，如果对上图这颗树的 5结点 和 8结点求他们的公共祖先结点，我们可以获得他们到根节点的链表形式路径，并且这两个链表肯定是相交的。它们分别是： 8 -> 4 -> 2 -> 1 以及 5 -> 2 -> 1
这样，问题就转化成：寻找两个链表的第一处交点。
时间复杂度O(log2(N) * 5) = O(log2(N)
如果这棵树是搜索树的话：
我们知道，对于一颗二叉搜索树的每个结点都满足：左子树的所有结点的值都小于当前结点，右子树的所有节点的值都大于当前结点。
因此，如果给定两个结点，就可以从根节点开始，判断当前结点的值和两个目标节点的值的大小关系：
1、如果当前结点的值比其中一个要找的结点小，比另一个要找的结点大，则说明要找的两个结点分别在这个结点的左右子树中，所以当前结点一定是要找的结点。
2、如果当前结点比要找的两个结点都大，则说明两个结点都在当前结点的左子树，那么就在左子树里面继续找。
3、如果当前结点比要找的两个结点都小，反之。
现在将这棵树限制为一颗普通的二叉树：
这时，就没法再利用数值上的关系来确定结点在当前结点的左树中还是右树中了...不过，还是可以用这种思路，只不过在确定目标节点的位置时，需要遍历来找。
代码中，我用的实际上时前序遍历，对每一个结点 都可以看成一个单独的问题，先判断当前结点的左结点和右结点有没有要找的结点，如果有，直接返回当前结点，如果没有，就在其左子树和右子树里继续找，如果左子树和右子树都找到了，则说明当前结点就是要找的结点；如果只有其中一侧找到了，则将找到的那一侧的子树视为一个新的子问题。（都没找到？）
具体的代码实现如下：
class BinaryTree()
{
public:
TreeNode* GetNearRoot_2(TreeNode *Node1, TreeNode *Node2)
{
return _GetNearRoot_2(_root, Node1, Node2);
}
protected:
TreeNode* _GetNearRoot_2(TreeNode *root, TreeNode *Node1, TreeNode *Node2)
{
if (root == NULL || Node1 == NULL || Node2 == NULL)
{
return NULL;
}
if (root->_left == Node1 || root->_right == Node1 || root->_left == Node2 || root->_right == Node2)
{
return root;
}
TreeNode *pLeft = _GetNearRoot_2(root->_left, Node1, Node2);
TreeNode *pRight = _GetNearRoot_2(root->_right, Node1, Node2);
if (pLeft != NULL && pRight != NULL) //左右都不为空，说明分别在根节点的 左右 子树 ，则肯定他们的最近父节点就是根节点
{
return root;
}
else if (pLeft != NULL)
{
return pLeft;
}
else if (pRight != NULL)
{
return pRight;
}
}
protected:
TreeNode *_root;
}
其实可以看出，我用递归实现需要注意的就是，找到了以后，要将当前结点传递回上层的递归，这里我用返回值的方式向上传递。
（举例子说明 --2）
采用这种方法，思路比较简单，代码坑比较多。
时间复杂度为 O(N) * O(N)
比较高效的方法：
其实，可以观察到，从根节点到目标结点，都有一条唯一的路径。因此从根节点到我们要找的两个结点，就有两条路径，并且这两条路径的起点肯定相同（都是根结点），那么我们可以在这两条路径中找出它们分开的结点，也就是我们要找的结点了。
代码：
class BinaryTree
{
public:
typedef vector<vector <TreeNode*> > PathVec;
TreeNode* GetNearRoot_3(TreeNode *Node1, TreeNode *Node2)
{
//获取两条路径
PathVec path;
path.resize(2);
path[0] = _GetPath(Node1);
path[1] = _GetPath(Node2);
//找开始不同的结点的前一个结点
TreeNode *DifferentNode = _GetDivide(path);
return DifferentNode;
}
protected:
//获得从根节点到Node的路径
vector<TreeNode*> _GetPath(TreeNode *Node)
{
vector<TreeNode*> ret;
_PrevOrder(_root, Node, ret);
return ret;
}
void _PrevOrder(TreeNode *root, TreeNode *Node, vector<TreeNode*> &ret)
{
if (root == NULL)
{
return;
}
ret.push_back(root);
if (root == Node)
{
return;
}
else if (root->_left == NULL && root->_right == NULL)
{
ret.pop_back();
return;
}
_PrevOrder(root->_left, Node, ret);
if (*(ret.end() - 1) == Node)
{
return;
}
_PrevOrder(root->_right, Node, ret);
if (*(ret.end() - 1) == Node)
{
return;
}
ret.pop_back();
}
//从路径中找出分离点
TreeNode* _GetDivide(PathVec path)
{
int i = 0;
while (i < path[0].size() && i < path[1].size() && (path[0])[i] == (path[1])[i])
{
++i;
}
if (i > 0 && i == path[0].size() || i == path[1].size()) //如果两个结点在同一颗子树，会出现这种情况
{
--i;
}
return path[0][i - 1];
}
protected:
TreeNode *_root;
};
两条路径，并且这两条路径的起点肯定相同（都是根结点），那么我们可以在这两条路径中找出它们分开的结点，也就是我们要找的结点了。
时间复杂度： O(N * 2 + log2(N) * 2) = O(N)
空间复杂度： O(log2(N) * 2) = O(log2(N))
github：
https://github.com/HonestFox/BrushQuestion/blob/master/61_%E6%B1%82%E4%BA%8C%E5%8F%89%E6%A0%91%E4%B8%AD%E4%B8%A4%E4%B8%AA%E8%8A%82%E7%82%B9%E6%9C%80%E8%BF%91%E7%9A%84%E5%85%AC%E5%85%B1%E7%A5%96%E5%85%88%E8%8A%82%E7%82%B9
八、判断一颗二叉树是否为平衡二叉树
github：
https://github.com/HonestFox/BrushQuestion/blob/master/62_%E5%88%A4%E6%96%AD%E4%B8%80%E9%A2%97%E4%BA%8C%E5%8F%89%E6%A0%91%E6%98%AF%E5%90%A6%E4%B8%BA%E5%B9%B3%E8%A1%A1%E4%BA%8C%E5%8F%89%E6%A0%91
九、求二叉树中最远两个节点的距离
github：
https://github.com/HonestFox/BrushQuestion/blob/master/63_%E6%B1%82%E4%BA%8C%E5%8F%89%E6%A0%91%E4%B8%AD%E6%9C%80%E8%BF%9C%E4%B8%A4%E4%B8%AA%E8%8A%82%E7%82%B9%E7%9A%84%E8%B7%9D%E7%A6%BB
十、由前序遍历和中序遍历重建二叉树
github：
https://github.com/HonestFox/BrushQuestion/blob/master/64_%E9%87%8D%E5%BB%BA%E4%BA%8C%E5%8F%89%E6%A0%91%EF%BC%88STL%EF%BC%89
十一、二叉搜索树的第k个节点
github：
https://github.com/HonestFox/BrushQuestion/blob/master/65_%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91%E7%9A%84%E7%AC%ACK%E4%B8%AA%E7%BB%93%E7%82%B9
十二、判断一个序列是否为二叉树的后序遍历序列
github：
https://github.com/HonestFox/BrushQuestion/blob/master/66_%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E5%90%8E%E5%BA%8F%E9%81%8D%E5%8E%86%E5%BA%8F%E5%88%97
十三、数据流中的中位数
（8.30恢复更新 ）
（开学了 /(ㄒoㄒ)/~~）
题目描述：
如何得到一个数据流中的中位数？
如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。
如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。
分析：
思路1：讨论区都在用堆做，但其实用哈希的思想也可以做的，只要考虑清楚如下两点：
1、重复的数字怎么处理
2、绝对值相等但符号相反的数字怎么处理
代码如下，
#include <iostream>
#include <vector>
using namespace std;
/*
题目描述：
如何得到一个数据流中的中位数？
如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。
如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。
*/
struct Pos
{
int _count = 0; //记录该位置下标对应数据出现的次数 （为什么要这个变量？因为有可能有重复的数据）
bool _IsExist = false; //记录是否存在
};
class Solution
{
public:
void Insert(int num)
{
if (num < 0)
{
num *= -1;
_Insert(_Nvec, num, -1);
++_NSize;
}
else
{
_Insert(_Pvec, num, 1);
++_PSize;
}
}
double GetMedian()
{
int size = _PSize + _NSize;
int pos = _PSize - _NSize; //size pos 奇偶性一定是相同的
int symbol = 1;
if (pos < 0)
{
symbol = -1;
pos *= -1;
}
double ret = 0;
if (pos % 2 == 0) //偶数
{
if (symbol == 1)
{
ret = ((double)_GetIndexVal(_Pvec, pos / 2) + (double)_GetIndexVal(_Pvec, pos / 2 - 1)) / 2;
}
else
{
ret = ((double)_GetIndexVal(_Nvec, pos / 2) + (double)_GetIndexVal(_Nvec, pos / 2 - 1) ) / 2;
}
}
else //奇数
{
if (symbol == 1)
{
ret = _GetIndexVal(_Pvec, pos / 2);
}
else
{
ret = _GetIndexVal(_Nvec, pos / 2);
}
}
ret *= symbol;
return ret;
}
protected:
void _Insert(vector<Pos> &vec, int num, int symbol = 1)
{
//判断容量
if (num >= vec.size())
{
vec.resize(num * 2 + 1);
}
//生成结点
Pos pos;
pos._IsExist = true;
++pos._count;
//插入
vec[num] = pos;
}
int _GetIndexVal( vector<Pos> vec, int pos) //pos表示第几个元素
{
int index = 0;
while (pos >= 0)
{
while (pos >= 0 && vec[index]._IsExist && vec[index]._count > 0)
{
--vec[index]._count;
--pos;
if (vec[index]._count == 0)
{
vec[index]._IsExist = false;
}
}
if (pos < 0)
{
break;
}
++index;
}
return index;
}
protected:
vector<Pos> _Pvec; //存放正数的数组
vector<Pos> _Nvec; //存放负数的数组
int _PSize = 0; //正数的数目
int _NSize = 0; //负数的数目
};
int main()
{
Solution s;
s.Insert(-1);
s.Insert(-2);
s.Insert(-3);
s.Insert(-4);
s.Insert(1);
s.Insert(2);
double ret = s.GetMedian();
cout << ret << endl;
return 0;
}
github： https://github.com/HonestFox/BrushQuestion/blob/master/67_%E6%95%B0%E6%8D%AE%E6%B5%81%E4%B8%AD%E7%9A%84%E4%B8%AD%E4%BD%8D%E6%95%B0
(9.3恢复更新)
十四、将功赎罪
github：
https://github.com/HonestFox/BrushQuestion/blob/master/68_%E5%B0%86%E5%8A%9F%E8%B5%8E%E7%BD%AA
十五、矩阵中的路径
github：
https://github.com/HonestFox/BrushQuestion/blob/master/69_%E7%9F%A9%E9%98%B5%E4%B8%AD%E7%9A%84%E8%B7%AF%E5%BE%84