每日算法题：Day 3
文章和资源同步更新至微信公众号：算法工程师之路
Day 3，继续加油，数据结构知识点！
1
编程题
【剑指Offer】用堆栈实现队列
用两个栈来实现一个队列，完成队列的Push和Pop操作。队列中的元素为int类型。
思路： 我们使用两个栈来进行交换数据，一个为插入栈，另一个为弹出栈，对于插入栈来说，只进行插入数据，而弹出栈进行弹出，如果弹出栈为空了，那么我们就将插入栈中所有数据压入到弹出栈中，这样就可以有队列“先进先出”的性质了
class Solution
{
public:
void push(int node) {
stack1.push(node);
}
int pop() {
if(stack2.size() <= )
{
while(stack1.size())
{
int tmp = stack1.top();
stack1.pop();
stack2.push(tmp);
}
}
int head = stack2.top();
stack2.pop();
return head;
}
//一个栈用于插入，另一个栈用于删除，如果删除栈为空，那么将插入栈数据push进删除栈
private:
stack<int> stack1;
stack<int> stack2;
};
【剑指Offer】旋转数组的最小值
把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个非减排序的数组的一个旋转，输出旋转数组的最小元素。例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。
思路： 既然题目都说明了这个是旋转数组，所以肯定不能使用一般数组的找最小值的方法。题中说将非减序列旋转之后就会产生两个非减序列，我们只要找到这两个非减序列的最左边的值，然后比较大小就行了，下面代码有两种方式，顺序查找和二分查找（尽量使用二分，效率高）
（顺序查找）
class Solution {
public:
int minNumberInRotateArray(vector<int> rotateArray) {
if(rotateArray.size() == )
return ;
int res1 = rotateArray[];
int res2 = ;
for(int i = ;i < rotateArray.size() - ; i++){
if(rotateArray[i] > rotateArray[i+]){
res2 = rotateArray[i+];
break;
}
}
return min(res1, res2);
}
};
（二分查找）
class Solution {
public:
int minNumberInRotateArray(vector<int> rotateArray) {
if(rotateArray.size() == )
return ;
int left = , mid = , right = rotateArray.size()-1;
while(left < right){
if(rotateArray[left] < rotateArray[right])
return rotateArray[left]; // 这种情况最前面的一定最小
mid = left + (right - left) / ;
if (rotateArray[left] < rotateArray[mid]){
left = mid+;
}else if(rotateArray[left] > rotateArray[mid]){
right = mid;
}else{
left++;
}
}
return rotateArray[left];
}
};2
概念题
【数据结构】设有一棵二叉树，其叶结点数为n0，度为1的结点数为n1，度为2的结点数为n2，则n0与n2满足关系
解答这个问题之前，首先要了解，一棵树节点的度是什么，如果一个节点有两个孩子，则该节点度为2，如果只有一个孩子，则度为1，如果是叶节点，没有孩子，则度为0。 对于一棵二叉树而言，其节点总数n=n0+n1+n2,不存在度为3的节点n3。又可以表示为节点总数n=2n2+1n1+0*n0+1,即总度数+1。最后化简得到n2 = n0 - 1 (很重要的性质)
哈夫曼树没有度为1的节点！！！
【数据结构】如何将一颗数变成对应的二叉树？其后序遍历是对应二叉树的什么序？
树——>二叉树： 1-加线：在所有的兄弟节点之间加一条线，G与H不是兄弟节点 2-去线：对树中每个结点，只保留它与第一个孩子节点的连线，删除它与其他孩子节点之间的连线。 3-层次调整：以树的根节点为轴心，将整颗树顺时针旋转一定的角度，使之结构层次分明。
树的后序遍历是对应二叉树的中序遍历 树的前序遍历是对应二叉树的前序遍历
【数据结构】平衡二叉树和二叉搜索树是什么？其速度谁快
平衡二叉树：它是一棵空树或者它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。 二叉搜索树： （1）若左子树不空，则左子树所有的结点的值均小于或者等于它的根结点的值； （2）若右子树不空，则右子树上所有结点的值均大于或者等于它的根结点的值； （3）左、右子树也分别为二叉排序树
由于二叉树的查找速度取决于树的深度，因此平衡二叉树的速度最快，因为各类树中，平衡二叉树的深度最小！
3
资源分享
欢迎关注我的个人公众号 （算法工程师之路），回复"左神算法基础CPP"即可获得大量算法源码，并实时更新！希望大家多多支持哦~
公众号简介：分享算法工程师必备技能，谈谈那些有深度有意思的算法，主要范围：C++数据结构与算法/深度学习（CV），立志成为Offer收割机！坚持分享算法题目和解题思路（Day By Day)
完
▼