程序员面试题(C++ 实现) - Day1

说明

---

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

今日题目一览

---

1. 二维数组中的查找
2. 替换空格
3. 从尾到头打印链表
4. 重建二叉树
5. 用两个栈实现队列

1. 二维数组中的查找

---

问题描述

在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

解析

先与每行的第一个数字作比较，一旦大于等于该数字，再与该行的在最后一个数字比较，如果小于该数字，则选定该行，然后在该行依次进行比较查询；否则不存在该整数

实现

/* 在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。 请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。 */#include <iostream>
#include <vector>using namespace std;bool Find(int target, const vector<vector<int> > &array) {
    if (array.empty())return false;if (target < array[0][0])return false;int _length = array.size();for (int i = 0; i < _length; i++) {
    if (array[i].empty())continue;else if(target >= array[i][0]) {
      // 选定该行if (target <= array[i][array[i].size() - 1]) {
     // 是否小于该行的最后一个数字for (int j = array[i].size() - 1; j >= 0; j--) {
    if (target == array[i][j])return 1;else if (target > array[i][j])break;}} else {
    continue;}} elsereturn false;}return false;
}int main(int argc, char const *argv[]) {
    // Testvector<vector<int> > vec;for(int i = 0; i < 10; i++) {
    vector<int> vecson;for(int j = 0; j < 7; j++) {
    vecson.push_back(i + j);cout << i + j << " ";}vec.push_back(vecson);cout << endl;}int target = 13;cout << "Is the target exist in array? " <<((Find(target, vec) == false) ? "False" : "True") << endl;return 0;
}

输出结果

6  7  8  9  10  11  12  
7  8  9  10  11  12  13  
8  9  10  11  12  13  14  
9  10  11  12  13  14  15  
Is the target exist in array?  True

2. 替换空格

---

问题描述

请实现一个函数，将一个字符串中的每个空格替换成“%20”。例如，当字符串为We Are Happy，则经过替换之后的字符串为We%20Are%20Happy。

解析

暂且没有太好的算法，目前只是通过指针来实现

更多请参考我的另一篇博客：C/C++文件 / 字符串 操作大全

实现

/* 请实现一个函数，将一个字符串中的每个空格替换成“%20”。 例如，当字符串为We Are Happy. 则经过替换之后的字符串为We%20Are%20Happy。*/#include <iostream>
#include <stdio.h>using namespace std;void replaceSpace(char *str, int length) {
    if(str == NULL)return ;int CountOfBlanks = 0;int Originallength = 0;for(int i = 0; str[i] != '\0'; i++) {
    Originallength++;if(str[i] == ' ')++CountOfBlanks;}int len = Originallength + 2 * CountOfBlanks;  //因为 %20 比 空格 多两个字符if(len + 1 > length)return ;char *pStr1 = str + Originallength; //复制结束符‘\0’char *pStr2 = str + len;while(pStr1 < pStr2) {
    if(*pStr1 == ' ') {
    *pStr2-- = '0';*pStr2-- = '2';*pStr2-- = '%';} else {
    *pStr2-- = *pStr1;}--pStr1;}
}int main(int argc, char const *argv[]) {
    //Testchar p[] = "AA BB CC ";printf("替换前：%s\n", p);replaceSpace(p, 50);printf("替换后：%s\n", p);return 0;
}

输出结果

替换前：AA BB CC 
替换后：AA%20BB%20CC%20

3. 从尾到头打印链表

---

问题描述

输入一个链表，按链表值从尾到头的顺序返回一个ArrayList。

解析

使用栈的 LIFO (Last in First out)性质来实现

如果有对链表的基本操作不熟悉的，请参考我的另一篇博文：

更多请参考我的另一篇博客：链表大全

实现

/* 输入一个链表，按链表值从尾到头的顺序返回一个ArrayList。*/#include <vector>
#include <stack>
#include <iostream>
#include <stdlib.h>using namespace std;// 定义节点
struct ListNode {
    int val;struct ListNode *next;ListNode(int x) :val(x), next(NULL) {
    }
};// 创建链表
struct ListNode *createList() {
    struct ListNode *head = new ListNode(0);struct ListNode *ret = head;for(int i = 1; i < 10; i++) {
    struct ListNode *p = new ListNode(i);ret->next = p;ret = ret->next;}return head;
}// 删除链表
void deleteList(struct ListNode *list) {
    struct ListNode *p = list;while(p != NULL) {
    list = p->next;free(p);p = list;}free(p);
}// 打印链表
void printList(ListNode *head) {
    while(head != NULL) {
    cout << head->val << " ";head = head->next;}cout << endl;
}// 从尾部打印链表
vector<int> printListFromTailToHead(struct ListNode *const head) {
    vector <int> result;stack<int> arr;struct ListNode *p = head;while(p != NULL) {
    arr.push(p->val);p = p->next;}int len = arr.size();for(int i = 0; i < len; i++) {
    result.push_back(arr.top());arr.pop();}return  result;
}int main(int argc, char const *argv[]) {
    //Teststruct ListNode *head = createList();cout << "原始列表:\n";printList(head);cout << "逆序打印列表:\n";vector<int> v(printListFromTailToHead(head));for(int i = 0; i < v.size(); i++)cout << v[i] << " ";deleteList(head);return 0;
}

输出结果

原始列表:
0 1 2 3 4 5 6 7 8 9 
逆序打印列表:
9 8 7 6 5 4 3 2 1 0

4. 重建二叉树

---

问题描述

输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。
假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。

解析

主要利以下内容：

• 根节点肯定是前序遍历的第一个数
• 分治思想

分治算法参考博客：五大常用算法之一：分治算法

如果有对二叉树的基本操作不熟悉的，请参考我的另一篇博文：

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

实现

/* 输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。 假设输入的前序遍历和中序遍历的结果中都不含重复的数字。 例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。*/#include <vector>
#include <queue>
#include <iostream>using namespace std;struct TreeNode {
    int val;TreeNode *left;TreeNode *right;TreeNode(int x) : val(x), left(NULL), right(NULL) {
    }
};// 重建二叉树
struct TreeNode *reConstructBinaryTree(vector<int> pre, vector<int> in) {
    int inlen = in.size();if(inlen == 0)return NULL;vector<int> left_pre, right_pre, left_in, right_in;//创建根节点，根节点肯定是前序遍历的第一个数TreeNode *head = new TreeNode(pre[0]);//找到中序遍历根节点所在位置,存放于变量gen中int gen = 0;for(int i = 0; i < inlen; i++) {
    if (in[i] == pre[0]) {
    gen = i;break;}}//对于中序遍历，根节点左边的节点位于二叉树的左边，根节点右边的节点位于二叉树的右边//利用上述这点，对二叉树节点进行归并for(int i = 0; i < gen; i++) {
    left_in.push_back(in[i]);left_pre.push_back(pre[i + 1]); //前序第一个为根节点}for(int i = gen + 1; i < inlen; i++) {
    right_in.push_back(in[i]);right_pre.push_back(pre[i]);}//和shell排序的思想类似，取出前序和中序遍历根节点左边和右边的子树//递归，再对其进行上述所有步骤，即再区分子树的左、右子子数，直到叶节点head->left = reConstructBinaryTree(left_pre, left_in);head->right = reConstructBinaryTree(right_pre, right_in);return head;
}// 打印二叉树
vector<vector<int> > Print(TreeNode *pRoot) {
    vector<vector<int> > Value;if (pRoot == NULL)return Value;queue<TreeNode * > queNode;queNode.push(pRoot);vector<int> subValue;                               //辅助数组，保存当前层所有的结点值int nextLevels = 0;                                 //用来统计下一层的结点数int currentLevels = 1;                              //用来标记当前层剩余的没有打印的结点数while (!queNode.empty()) {
    TreeNode *pNode = queNode.front();queNode.pop();subValue.push_back(pNode->val);if (pNode->left != NULL) {
    queNode.push(pNode->left);++nextLevels;}if (pNode->right != NULL) {
    queNode.push(pNode->right);++nextLevels;}--currentLevels;if (currentLevels == 0) {
                               //如果当前层结点已全部打印完毕Value.push_back(subValue);subValue.clear();                           //清空，开始存下一层结点currentLevels = nextLevels;                 //下一层要打印的结点数nextLevels = 0;                             //置0，开始统计下一层结点数}}return Value;
}void plr(TreeNode *pRoot) {
    if(pRoot != NULL) {
    cout << pRoot->val << endl;if(pRoot->left != NULL)cout << "left " << pRoot->left->val << endl;if(pRoot->right != NULL)cout << "right " << pRoot->right->val << endl;}
}int main(int argc, char const *argv[]) {
    // Test// 创建 vec_pre vec_inint arr_pre[8] = {
    1, 2, 4, 7, 3, 5, 6, 8};vector<int> vec_pre(arr_pre, arr_pre + 8);int arr_in[8] = {
    4, 7, 2, 1, 5, 3, 8, 6};vector<int> vec_in(arr_in, arr_in + 8);struct TreeNode *head = reConstructBinaryTree(vec_pre, vec_in);vector<vector<int> > list(Print(head));for(int i = 0; i < list.size(); i++) {
    for(int j = 0; j < list[i].size(); j++) {
    cout << list[i][j] << " ";}cout << endl;}return 0;
}

输出结果

1 
2 3 
4 5 6 
7 8 

5. 用两个栈实现队列

---

问题描述

用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型。

解析

利用栈的 LIFO性质(Last in First out)

实现

注：这个版本有很多细节没有注意起来，参考第二个完美版本，但是比较复杂

/* 用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型。*/#include <iostream>
#include <stack>using namespace std;class Queue {
    
public:void push(int node) {
    stack1.push(node);}int pop() {
    int res;if (stack2.size() > 0) {
    res = stack2.top();stack2.pop();} else if(stack1.size() > 0) {
    while (stack1.size() > 0) {
    int ele = stack1.top();stack1.pop();stack2.push(ele);}res = stack2.top();stack2.pop();}return res;}private:stack<int> stack1;stack<int> stack2;
};int main(int argc, char const *argv[]) {
    // TestQueue s;for(int i = 0; i < 10; i++)s.push(i);for(int i = 0; i < 10; i++)cout << s.pop() << " ";return 0;
}

输出结果

0  1  2  3  4  5  6  7  8  9

完美版本(细节优化)

首先定义一个栈 stack 类，将 stack 的属性和方法都封装起来，然后实现一个队列 queue 类，将 stack 类的对象作为 queue 的成员，并在 queue 类中实现接口。这样设计相当于在 stack 类的外面加了一层封装，将其转换为队列的实现。在设计模式中，这种设计被称为适配器模式。

#include "malloc.h"
#include "iostream"using namespace std;#define STACKINCREMENT 10
#define STACK_INIT_SIZE 10class stack {
    
public :int *base;int *top;int stacksize;bool initStack() {
    base = (int *)malloc(STACK_INIT_SIZE * sizeof(int));if(!base) return false;  /*分配空间失败*/top = base;stacksize = STACK_INIT_SIZE;return true;            /*初始化栈成功*/}bool Push(int e) {
    if(top - base >= stacksize) {
    /*栈满，追加空间*/base = (int *)realloc(base, (stacksize +STACKINCREMENT) * sizeof(int));if(!base) return false;   /*存储分配失败*/top = base + stacksize;stacksize = stacksize + STACKINCREMENT; /*设置栈的最大容量*/}*top = e;  /*放入数据*/top++;return true;}bool Pop(int &e) {
    if(top == base) return false;  /*栈空，非法操作*/e = *--top;return true;}~stack() {
    if (base != NULL) {
    free(base);             /*析构函数，释放堆内存空间*/}}
};class queue {
    stack s1, s2;    /*定义两个栈s1和s2，用它们实现一个队列*/public :bool  initQueue() {
    if (s1.initStack() && s2.initStack() )  {
       /*初始化队列，调用stack的初始化*/return true;}return false;}bool EnQueue(int x) {
    if (s1.Push(x)) {
    return true;        /*入队列，将x压入栈s1*/}return false;}bool DeQueue(int &x) {
    int e;if (s2.base == s2.top) {
    /*栈s2为空的情况*/if (s1.top == s1.base) {
    return false;} else {
    while (s1.Pop(e)) {
    s2.Push(e);}}}s2.Pop(x);       /*出队列，从栈s2中取出数据*/return true;}bool IsEmptyQueue() {
    if (s1.base == s1.top && s2.base == s2.top) {
    return true;    /*队列为空*/} else {
    return false;   /*队列不为空*/}}int getCount() {
    return s1.top - s1.base + s2.top - s2.base; /*计算两个栈当前容量之和*/}
};int main() {
    int i, x = 0, e;queue q;q.initQueue();      /*初始化一个队列*/for (i = 0; i < 10; i++) {
    q.EnQueue(x);           /*入队列操作，0~9*/x++;}for (i = 0; i < 5; i++) {
    if (q.DeQueue(e)) {
    cout << e << " ";   /*出队列操作，连续出队列5次，并打印在屏幕上*/}}/*输出当前队列中元素的个数*/cout << "\nThe number of elements in the queue is " << q.getCount() << endl;for (i = 0; i < 10; i++) {
    q.EnQueue(x);               /*入队列操作，10~19*/x++;}for (i = 0; i < 15; i++) {
    if (q.DeQueue(e)) {
         /*出队列操作，连续出队列15次，并打印在屏幕上*/cout << e << " ";}}/*输出当前队列中元素的个数*/cout << "\nThe number of elements in the queue is " << q.getCount() << endl;/*打印当前队列是否为空*/if (q.IsEmptyQueue()) {
    cout << "The queue is empty" << endl;} else {
    cout << "The queue is NOT empty" << endl;}getchar();
}

联系博主

---

邮箱：Neverland_LY@163.com