程序员面试题(C++ 实现) - Day4_综合

文章目录

- 说明
- 今日题目一览
- - 1. 树的子结构
  - 2. 二叉树的镜像
  - 3. 顺时针打印矩阵
  - 4. 包含min函数的栈
  - 5. 栈的压入、弹出序列

说明

以下题目均来自于牛客网
以下代码用 C++11 编写
以下代码均已编译通过(Compile by MINGW)
以下代码均有测试案例(Main function)
以下代码均已进行优化或部分优化(Optimize)
以下代码均有注释(Comment)
部分题目附有解析(Analysis)
如有错误或侵权，请联系博主

今日题目一览

树的子结构
二叉树的镜像
顺时针打印矩阵
包含min函数的栈
栈的压入、弹出序列

1. 树的子结构

问题描述

输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）

解析

首先要明确，B 树是 A 树的子结构的话，从 A 树找到和 B 的根节点的值相等的结点，由此开始，两者的左右子树必须要一模一样才算是子结构，这个一模一样有两层含义:

同为非空结点(空结点)
结点不为空的情况下二者的值必须相等

实现

/* 输入两棵二叉树A，B，判断B是不是A的子结构。 （ps：我们约定空树不是任意一个树的子结构）*/#include <iostream>using namespace std;struct TreeNode {
    int val;struct TreeNode *left;struct TreeNode *right;TreeNode(int x) :val(x), left(NULL), right(NULL) {
    }
};class Solution {
    
public:bool HasSubtree(TreeNode *pRoot1, TreeNode *pRoot2) {
    if(!pRoot1)return false; // A 树不能为空if(!pRoot2)return false; // 空树不是任何树的子树// 对于每一个结点，必须判断当前结点以及当前结点的左右子树return ( dfs(pRoot1, pRoot2)) ||HasSubtree(pRoot1->left, pRoot2) ||HasSubtree(pRoot1->right, pRoot2);}private:bool dfs(TreeNode *r1, TreeNode *r2) {
    if(!r2)return true;  // 如果 r2 是空的话，不管左子树是不是空，那么 r2 一定是 r1 的子树 (r1 >= r2)if(!r1)return false;  // 这种情况属于 r2 为空，r1 为空，那么肯定不是子树if(r1->val != r2->val) // 结点都不为空的话，就比较值是否相等return false;return dfs(r1->left, r2->left) && dfs(r1->right, r2->right); // 迭代}
};int main(int argc, char const *argv[]) {
    //测试用例略//return 0;
}

输出结果

无

更多有关树的内容请参考我的另一篇博客：树结构大全

2. 二叉树的镜像

问题描述

操作给定的二叉树，将其变换为源二叉树的镜像。

解析

二叉树的镜像定义：

源二叉树

8
/ \
6 10
/ \ /\
5 7 9 11

镜像二叉树

8
/ \
10 6
/ \ /\
11 9 7 5

所以问题就简单化了，就是简单的左右子树交换地址变量，然后迭代

实现

/* 操作给定的二叉树，将其变换为源二叉树的镜像。二叉树的镜像定义： 源二叉树8/ \6 10/ \ / \5 7 9 11镜像二叉树8/ \10 6/ \ / \11 9 7 5*/#include <iostream>using namespace std;struct TreeNode {
    int val;struct TreeNode *left;struct TreeNode *right;TreeNode(int x) :val(x), left(NULL), right(NULL) {
    }
};void Mirror1(TreeNode *pRoot) {
     // 简洁高效if (pRoot == NULL)return;TreeNode *pTmp;pTmp = pRoot->left;pRoot->left = pRoot->right;pRoot->right = pTmp;Mirror1(pRoot->left);Mirror1(pRoot->right);
}void Mirror2(TreeNode *pRoot) {
    if (pRoot->left) {
    Mirror2(pRoot->left);TreeNode *pTmp;pTmp = pRoot->left;pRoot->left = pRoot->right;pRoot->right = pTmp;}if (pRoot->right) {
    Mirror2(pRoot->right);TreeNode *pTmp;pTmp = pRoot->right;pRoot->right = pRoot->left;pRoot->left = pTmp;}
}int main(int argc, char const *argv[]) {
    /* code */return 0;
}

输出结果

无

更多有关树的内容请参考我的另一篇博客：树结构大全

3. 顺时针打印矩阵

问题描述

输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字，

例如，如果输入如下4 X 4矩阵：

| 1 2 3 4 |
| 5 6 7 8 |
| 9 10 11 12 |
| 13 14 15 16 |

打印出数字：

1,2,3,4,8,12,16,15,14,13,9,5,6,7,11,10.

解析

这个暂且没又简单的方法，就是先按照行输出，到边界再按列输出，遇到边界再换为行，依次进行下去…

实现

/* 输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字，例如，如果输入如下4 X 4矩阵：| 1 2 3 4 || 5 6 7 8 || 9 10 11 12 || 13 14 15 16 |打印出数字： 1,2,3,4,8,12,16,15,14,13,9,5,6,7,11,10.*/#include <iostream>
#include <vector>using namespace std;vector<int> printMatrix(vector<vector<int> > matrix) {
    int row = matrix.size();int col = matrix[0].size();vector<int> result;if(row == 0 || col == 0)return result;int left = 0, right = col - 1, top = 0, btm = row - 1;while(left <= right && top <= btm) {
    for(int i = left; i <= right; i++)result.push_back(matrix[top][i]);  // 1 2 3 4 6 7if(top < btm)for(int i = top + 1; i <= btm; i++)result.push_back(matrix[i][right]); // 8 12 16 11if(top < btm && left < right)for(int i = right - 1; i >= left; i--)result.push_back(matrix[btm][i]);  // 15 14 13 10if(top + 1 < btm && left < right)for(int i = btm - 1; i >= top + 1; i--)result.push_back(matrix[i][left]);  // 3 5left++; right--; top++; btm--;}return result;
}vector<vector<int> > createMatrix() {
    vector<vector<int> > vec;for(int i = 0; i < 4; ++i) {
    vector<int> vec_son;for(int j = 1; j <= 4; ++j) {
    vec_son.push_back(4 * i + j);}vec.push_back(vec_son);}return vec;
}void Print(vector<vector<int> > &vec) {
    for(int i = 0; i < vec.size(); ++i) {
    for(int j = 0; j < vec[i].size(); j++)cout << vec[i][j] << " ";cout << endl;}}int main(int argc, char const *argv[]) {
    //Testvector<vector<int> > vec = createMatrix();Print(vec);vector<int> v = printMatrix(vec);for(int i = 0; i < v.size(); i++)cout << v[i] << " ";return 0;
}

输出结果

1  2  3  4
5  6  7  8
9  10  11  12
13  14  15  16
1 2 3 4 8 12 16 15 14 13 9 5 6 7 11 10

4. 包含min函数的栈

问题描述

定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的min函数
（时间复杂度应为O（1））。

解析

建立两个 stack1、stack2，其中，stack1 用来存取新 push 进来的元素，stack2 用来存储“stack1 对应位置”的最小值。

每当stack1 push 进来新元素后就和 stack2.top() 的元素进行比较，如果小于 stack2.top() 的值，就将新值添加到 stack2，否则将 stack2.back() 的元素再次添加到 stack2。

上面的解释可以用下面的这个图来说明：

push ============ >
StackInt 11 9 6 20 18 2
StackMin 11 9 6 6 6 2
< ============= pop

这样做的目的是为了保证 stack1.pop() 出元素后，stack2 中仍能正确对应 stack1 中所有值的最小值

实现

/* 定义栈的数据结构， 请在该类型中实现一个能够得到栈中所含最小元素的min函数 （时间复杂度应为O（1））。*/#include <iostream>
#include <stack>using namespace std;class MyStack {
    
public:void push(int value) {
    StackInt.push(value);if(StackMin.empty())  // 注意逻辑StackMin.push(value);else if(StackMin.top() < value)StackMin.push(StackMin.top());elseStackMin.push(value);}void pop() {
    if(!StackInt.empty()) {
    StackInt.pop();StackMin.pop();}}int top() {
    return StackInt.top();}int min() {
    return StackMin.top();}
private:stack<int> StackInt;stack<int> StackMin;
};int main(int argc, char const *argv[]) {
    //Test/*eg：push ====================== >StackInt 11 9 6 20 18 2StackMin 11 9 6 6 6 2< ======================= pop*/MyStack ms;int array[6] = {
    11, 9, 6, 20, 18, 2};for(int i = 0; i < sizeof(array) / sizeof(int); i++)ms.push(array[i]);for(int i = sizeof(array) / sizeof(int) - 1; i >= 0; i--) {
    cout << ms.min() << " ";ms.pop();}return 0;
}

输出结果

2 6 6 6 9 11

5. 栈的压入、弹出序列

问题描述

输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。（注意：这两个序列的长度是相等的）

解析

首先要理解为什么入栈顺序是 1,2,3,4,5，会出现 4,5,3,2,1 的出栈顺序(示意图中 1 代表出栈)：

1 - 2 - 3 - 4 - 4 - 5 - 5 - 3 - 2 - 1

所以造成这样的原因是因为有些元素提前出栈(出栈的元素不会再次入栈)

再看看为什么 4,3,5,1,2 为什么不可能是出栈顺序：

1 - 2 - 3 - 4 - 4 - 3 - 5 - 5 ，再往下走肯定是 2 先出栈，1 再出栈，所以错就错在 1 和 2 的顺序

懂得上面的道理后，我们来看怎么实现这个功能：

我们可以建立一个 vector 类型的辅助栈来实现这个过程，代码比较好理解，这里不做太多的解释，大概用图描述一下辅助 vector 的变化：

pushV 1 2 3 4 5

popV 4 5 3 2 1

v 1
v 1 2
v 1 2 3
v 1 2 3 4
v 1 2 3
v 1 2 3 5
v 1 2 3
v 1 2
v 1
v

判断标志就是 v 最后为不为空，空的话就是正确的出栈顺序！！！

实现

/* 输入两个整数序列，第一个序列表示栈的压入顺序， 请判断第二个序列是否可能为该栈的弹出顺序。 假设压入栈的所有数字均不相等。 例如序列1,2,3,4,5是某栈的压入顺序， 序列4,5,3,2,1是该压栈序列对应的一个弹出序列， 但4,3,5,1,2就不可能是该压栈序列的弹出序列。 （注意：这两个序列的长度是相等的）*/#include <iostream>
#include <stack>
#include <vector>using namespace std;// 方法一
bool IsPopOrder1(vector<int> pushV, vector<int> popV) {
    if(pushV.size() == 0) return false;vector<int> stack;for(int i = 0, j = 0 ; i < pushV.size();) {
    stack.push_back(pushV[i++]);while(j < popV.size() && stack.back() == popV[j]) {
    stack.pop_back();j++;}}return stack.empty();
}// 方法二
bool IsPopOrder2(vector<int> pushV, vector<int> popV) {
    stack<int> st;//辅助栈int id = 0;for(int i = 0; i < popV.size(); ++i) {
    while(st.empty() || st.top() != popV[i]) {
    st.push(pushV[id++]);if(id > pushV.size()) {
    return false;}}st.pop();}if(st.empty()) // 判断条件就是最后有没有剩下的return true;elsereturn false;
}int main(int argc, char const *argv[]) {
    //Testvector<int> pushV;pushV.push_back(1); pushV.push_back(2); pushV.push_back(3);pushV.push_back(4); pushV.push_back(5);vector<int> popV;popV.push_back(4); popV.push_back(5); popV.push_back(1);popV.push_back(2); popV.push_back(3);cout << boolalpha << ((IsPopOrder1(pushV, popV) == 1) ? true : false) << endl;return 0;
}

输出结果

false

推荐一篇博客，作者提出了一种比较巧妙的想法，有喜欢者可以自行实现一下：栈 - 关于出栈序列

该文章的想法很独特，提出了后出先入逆序原则

亦即：对于入栈顺序为 1 2 3 4，出栈顺序为 3 1 2 4 的情况：

选择任意元素 e ，这里选择 3
比 3 后出栈的有三个元素 1 2 4
1 2 4 中比 3 先入栈的有两个元素 1 2
但是 1 2 是正序的，而不是逆序的

===> 所以这个序列不是合法出栈序列

有木有很惊艳~~~