[C++知识库]小米手机面经

1. 问你职业规划，看与目前岗位的匹配度

2. 询问项目，看具体做了什么方向 integer和int的区别

3. integar和int的区别
   1.Integer是int的包装类，int则是java的一种基本数据类型
   2.Integer变量必须实例化后才能使用，而int变量不需要
   3.Integer实际是对象的引用，当new一个Integer时，实际上是生成一个指针指向此对象
   4.而int则是直接存储数据值 Integer的默认值是null，int的默认值是0

4. const的用途

   1.const全局/局部变量：保证变量不改变

   2.const指针/引用：指针变量和变量指针，非const引用只能绑定非const对象，const引用可以绑定任何对象

   3.const修饰函数参数：放置函数体内可能会修改参数原始对象。因此，有三种情况讨论，
   a. 函数参数为值传递，本身就是形参，并不会修改原始对象，故不需要const
   b. 函数参数为指针，指针传递只会进行浅拷贝，可以加上顶层const防止指针指向被修改，加上底层const防止指向对象被修改
   c.函数参数为引用：添加一个const，即可减小拷贝开销，又可以防止修改底层引用的对象

   4.const修饰函数返回值：可以有效防止因用户错误造成的意外，可以防止外部object的内部成员进行修改。

   5.const成员函数和数据成员：
   a.const对象只能访问const成员函数，而非const对象可以访问任意的成员函数，包括const成员函数
   b.const对象的成员是不能修改的，而通过指针维护的对象确实可以修改的
   c.const成员函数不可以修改对象的数据，不管对象是否有const
   d.类的常数据成员：类的数据成员不能再任何函数中被复制或修改，但必须***在构造函数中使用初始化列表的方式赋初值***

   6.const修饰类对象：该对象内的任何成员变量都不能被修改，因此不能调用该对象的任何非const成员函数

class A
{
 public:
    void funcA() {}
    void funcB() const {}
};

int main
{
    const A a;
    a.funcB();    // 可以
    a.funcA();    // 错误

    const A* b = new A();
    b->funcB();    // 可以
    b->funcA();    // 错误
}

5. final
   1.修饰类：说明类不能被继承
   2.修饰变量：如果是基本数据类型的变量，则其数值一旦在初始化之后便不能更改；如果是引用类型的变量，则在对其初始化之后便不能再让其指向另一个对象（但它指向的对象内容可以变）。
   3.final和static的区别：static表示只保存一份副本，而final的作用是用来保证变量不可变。

6. 二叉搜索树的后序遍历序列
   1.递归

class Solution {
public:
    bool VerifySquenceOfBST(vector<int> sequence) {
        int n = sequence.size();
        if(n == 0) return false;    // 注意审题, 约定空树不是二叉搜索树
        return check(sequence, 0, n - 1);
    }
 
    bool check(vector<int>& sequence, int l, int r){
        if(l >= r) return true;    // 若当前子树只有一个节点
 
        int root = sequence[r];    // 当前子树的根节点
 
        // 划分出右子树
        int j = r - 1;
        while(j >= 0 && sequence[j] > root) j--;
 
        // 检查左子树是不是存在大于根节点的数
        for(int i = l; i <= j; i++){
            if(sequence[i] > root) return false;
        }
 
        // 分治法检查左子树和右子树
        return check(sequence, l, j) && check(sequence, j + 1, r - 1);
    }
};

时间复杂度：O(n^2), n为二叉树节点的个数, 当树为链式时时间复杂度最坏为O(n^2)
空间复杂度：O(n), 当树为链式结构时, 递归深度为n

2.栈
题目中的要点在于两点：后序遍历与二叉搜索树。我们模拟后序遍历的过程，来判断每时每刻的状态是否满足二叉搜索树。
从后往前遍历，就顺序变成了根->右子树->左子树，由于右子树>根>左子树，所以当该序列有下降时，说明当前已经来到了左子树，（因为每个二叉搜索树的右子树一定大于根，所以在没到左子树的情况下，必定是升序的情况，一旦不满足升序，说明已经到了左子树。）找到大于当前值的最小值，该值为局部树的根节点。初始时，令根节点root无穷大，则当前树为该根节点的左子树。遍历过程中，逐步缩小root的值，因为所有的操作都是在当前根节点root的左子树中进行的，所以保证遍历的值小于root即可满足判断条件，否则为false；

class Solution {
public:
  bool VerifySquenceOfBST(vector<int> sequence) {
      if(sequence.size()==0)
          return false;
      stack<int> s;
      int root=1000000;
      //序列从后往前遍历，即根->右子树->左子树的顺序。
      for(int i=sequence.size()-1;i>=0;i--){
          //不满足二叉搜索树所表现出来的特征，即存在左子树中节点值大于根节点。
          if(sequence[i]>root)
              return false;
          //找到栈中大于当前值sequence[i]的最小值 即为root
          while(!s.empty()&&sequence[i]<s.top()){
              root=s.top();
              s.pop();
          }
          s.push(sequence[i]);
      }
      return true;
  }  
};

图解复杂度分析：
时间复杂度：O(n),遍历数组序列。
空间复杂度：O(n),入栈最大数目n。

7. 判断二叉树是否为平衡二叉树