C++面試常見算法題與參考答案總結(jié)
發(fā)布時(shí)間：2019-11-20 14:10:21 作者：devil_08 
我要評(píng)論
我要評(píng)論這篇文章主要介紹了C++面試常見算法題與參考答案,總結(jié)分析了C++面試中遇到的常見算法題與相應(yīng)的參考答案,需要的朋友可以參考下
題目一（數(shù)組中查找）
在一個(gè)二維數(shù)組中，每一行都按照從左到右遞增的順序排序，每一列都按照從上到下遞增的順序排序。請(qǐng)完成一個(gè)函數(shù)，輸入這樣的一個(gè)二維數(shù)組和一個(gè)整數(shù)，判斷數(shù)組中是否含有該整數(shù)。
class Solution {
public:
bool Find(int target, 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;
}
}
else return false;
}
return false;
}
};
題目二（替換空格）
請(qǐng)實(shí)現(xiàn)一個(gè)函數(shù)，將一個(gè)字符串中的空格替換成“%20”。例如，當(dāng)字符串為We Are Happy.則經(jīng)過替換之后的字符串為We%20Are%20Happy。
class Solution {
public:
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;
if(len+1>length)
return ;
char*pStr1=str+Originallength;//復(fù)制結(jié)束符‘\0’
char*pStr2=str+len;
while(pStr1<pStr2)
{
if(*pStr1==' ')
{
*pStr2--='0';
*pStr2--='2';
*pStr2--='%';
}
else
{
*pStr2--=*pStr1;
}
--pStr1;
}
}
};
題目三（打印鏈表）
輸入一個(gè)鏈表，從尾到頭打印鏈表每個(gè)節(jié)點(diǎn)的值。
/**
* struct ListNode {
* int val;
* struct ListNode *next;
* ListNode(int x) :
* val(x), next(NULL) {
* }
* };
*/
class Solution
{
public:
vector<int> printListFromTailToHead(ListNode* head)
{
vector <int> result;
stack<int> arr;
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;
}
};
題目四（重建二叉樹）
輸入某二叉樹的前序遍歷和中序遍歷的結(jié)果，請(qǐng)重建出該二叉樹。假設(shè)輸入的前序遍歷和中序遍歷的結(jié)果中都不含重復(fù)的數(shù)字。例如輸入前序遍歷序列{1,2,4,7,3,5,6,8}和中序遍歷序列{4,7,2,1,5,3,8,6}，則重建二叉樹并返回。
/**
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
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;
//創(chuàng)建根節(jié)點(diǎn)，根節(jié)點(diǎn)肯定是前序遍歷的第一個(gè)數(shù)
TreeNode* head=new TreeNode(pre[0]);
//找到中序遍歷根節(jié)點(diǎn)所在位置,存放于變量gen中
int gen=0;
for(int i=0;i<inlen;i++)
{
if (in[i]==pre[0])
{
gen=i;
break;
}
}
//對(duì)于中序遍歷，根節(jié)點(diǎn)左邊的節(jié)點(diǎn)位于二叉樹的左邊，根節(jié)點(diǎn)右邊的節(jié)點(diǎn)位于二叉樹的右邊
//利用上述這點(diǎn)，對(duì)二叉樹節(jié)點(diǎn)進(jìn)行歸并
for(int i=0;i<gen;i++)
{
left_in.push_back(in[i]);
left_pre.push_back(pre[i+1]);//前序第一個(gè)為根節(jié)點(diǎn)
}
for(int i=gen+1;i<inlen;i++)
{
right_in.push_back(in[i]);
right_pre.push_back(pre[i]);
}
//和shell排序的思想類似，取出前序和中序遍歷根節(jié)點(diǎn)左邊和右邊的子樹
//遞歸，再對(duì)其進(jìn)行上述所有步驟，即再區(qū)分子樹的左、右子子數(shù)，直到葉節(jié)點(diǎn)
head->left=reConstructBinaryTree(left_pre,left_in);
head->right=reConstructBinaryTree(right_pre,right_in);
return head;
}
};
題目五（用兩個(gè)棧實(shí)現(xiàn)隊(duì)列）
用兩個(gè)棧來實(shí)現(xiàn)一個(gè)隊(duì)列，完成隊(duì)列的Push和Pop操作。 隊(duì)列中的元素為int類型。
class Solution{
public:
int cou = 0;
void push(int node) {
stack1.push_back(node);
stack2.push_back(cou++);
}
int pop() {
int i = 0;
while(stack2[i] == -1)
{
i++;
}
stack2[i] = -1;
return stack1[i];
}
private:
vector<int> stack1;//存數(shù)
vector<int> stack2;//地址
};
題目六（旋轉(zhuǎn)數(shù)組的最小數(shù)字）
把一個(gè)數(shù)組最開始的若干個(gè)元素搬到數(shù)組的末尾，我們稱之為數(shù)組的旋轉(zhuǎn)。 輸入一個(gè)非遞減排序的數(shù)組的一個(gè)旋轉(zhuǎn)，輸出旋轉(zhuǎn)數(shù)組的最小元素。 例如數(shù)組{3,4,5,1,2}為{1,2,3,4,5}的一個(gè)旋轉(zhuǎn)，該數(shù)組的最小值為1。 NOTE：給出的所有元素都大于0，若數(shù)組大小為0，請(qǐng)返回0。
#include <iostream>
#include <vector>
#include <string>
#include <stack>
#include <algorithm>
using namespace std;
class Solution {
public:
int minNumberInRotateArray(vector<int> rotateArray) {
int size = rotateArray.size();
if(size == 0){
return 0;
}//if
int left = 0,right = size - 1;
int mid = 0;
// rotateArray[left] >= rotateArray[right] 確保旋轉(zhuǎn)
while(rotateArray[left] >= rotateArray[right]){
// 分界點(diǎn)
if(right - left == 1){
mid = right;
break;
}//if
mid = left + (right - left) / 2;
// rotateArray[left] rotateArray[right] rotateArray[mid]三者相等
// 無(wú)法確定中間元素是屬于前面還是后面的遞增子數(shù)組
// 只能順序查找
if(rotateArray[left] == rotateArray[right] && rotateArray[left] == rotateArray[mid]){
return MinOrder(rotateArray,left,right);
}//if
// 中間元素位于前面的遞增子數(shù)組
// 此時(shí)最小元素位于中間元素的后面
if(rotateArray[mid] >= rotateArray[left]){
left = mid;
}//if
// 中間元素位于后面的遞增子數(shù)組
// 此時(shí)最小元素位于中間元素的前面
else{
right = mid;
}//else
}//while
return rotateArray[mid];
}
private:
// 順序?qū)ふ易钚≈?
int MinOrder(vector<int> &num,int left,int right){
int result = num[left];
for(int i = left + 1;i < right;++i){
if(num[i] < result){
result = num[i];
}//if
}//for
return result;
}
};
int main(){
Solution s;
//vector<int> num = {0,1,2,3,4,5};
//vector<int> num = {4,5,6,7,1,2,3};
vector<int> num = {2,2,2,2,1,2};
int result = s.minNumberInRotateArray(num);
// 輸出
cout<<result<<endl;
return 0;
}
題目七（斐波那契數(shù)列）
大家都知道斐波那契數(shù)列，現(xiàn)在要求輸入一個(gè)整數(shù)n，請(qǐng)你輸出斐波那契數(shù)列的第n項(xiàng)。
n<=39
class Solution {
public:
int Fibonacci(int n) {
if(n == 0){
return 0;
}
if(n == 1){
return 1;
}
int a = 0,b = 1;
int m = 0;
int i;
for(i = 2;i <= n;i++){
m = a + b;
a = b;
b = m;
}
return m;
}
};
題目八（跳臺(tái)階）
一只青蛙一次可以跳上1級(jí)臺(tái)階，也可以跳上2級(jí)。求該青蛙跳上一個(gè)n級(jí)的臺(tái)階總共有多少種跳法。
class Solution {
public:
int jumpFloor(int n) {
int f=1,g=2;
n--;
while(n--)
{
g+=f;
f=g-f;
}
return f;
}
};
題目九（變態(tài)跳臺(tái)階）
一只青蛙一次可以跳上1級(jí)臺(tái)階，也可以跳上2級(jí)……它也可以跳上n級(jí)。求該青蛙跳上一個(gè)n級(jí)的臺(tái)階總共有多少種跳法。
class Solution {
public:
int jumpFloorII(int number) {
if(number==0)
return number;
int total=1;
for(int i=1;i<number;i++)
total*=2;
return total;
}
};
題目十（矩形覆蓋）
我們可以用2*1的小矩形橫著或者豎著去覆蓋更大的矩形。請(qǐng)問用n個(gè)2*1的小矩形無(wú)重疊地覆蓋一個(gè)2*n的大矩形，總共有多少種方法？
class Solution {
public:
int rectCover(int number) {
if (number <= 0) {
return number;
}
int f1 = 1;
int f2 = 2;
int f3;
for (int i = 3; i <= number; i++) {
f3 = f1 + f2;
f1 = f2;
f2 = f3;
}
return f3;
}
};
相關(guān)文章
- 這篇文章主要介紹了騰訊公司c++面試小結(jié)，小編覺得挺不錯(cuò)的，現(xiàn)在分享給大家，也給大家做個(gè)參考。一起跟隨小編過來看看吧2020-03-02
這篇文章主要介紹了 C++ 面試題目(整理自?？途W(wǎng)),小編覺得挺不錯(cuò)的，現(xiàn)在分享給大家，也給大家做個(gè)參考。一起跟隨小編過來看看吧2020-02-13華為校招 C++崗面試經(jīng)歷總結(jié)【筆試+一面+二面+Offer】
這篇文章主要介紹了華為校招 C++崗面試經(jīng)歷,總結(jié)分析了華為校招C++崗位的筆試題,以及一面、二面到最終拿到Offer的經(jīng)歷與相關(guān)經(jīng)驗(yàn)感想,需要的朋友可以參考下2019-11-28- 這篇文章主要介紹了C++必備面試題與參考答案,結(jié)合大量經(jīng)典實(shí)例總結(jié)分析了C++面試過程中經(jīng)常遇到的各種概念、原理、算法相關(guān)問題及參考答案,需要的朋友可以參考下2019-10-31
- 這篇文章主要介紹了C/C++經(jīng)典面試題(附答案)，小編覺得挺不錯(cuò)的，現(xiàn)在分享給大家，也給大家做個(gè)參考。一起跟隨小編過來看看吧2019-10-23
- 這篇文章主要介紹了C/C++求職者必備的20道面試題與參考答案,總結(jié)分析了C/C++相關(guān)的常見概念、原理、知識(shí)點(diǎn)與注意事項(xiàng),需要的朋友可以參考下2019-10-10
騰訊的外包c(diǎn)++面試經(jīng)歷總結(jié)
這篇文章主要介紹了騰訊的外包c(diǎn)++面試經(jīng)歷,總結(jié)記錄了一次騰訊C++面試的經(jīng)歷,包括面試的流程、面試題目與相應(yīng)的參考答案,需要的朋友可以參考下2019-09-29- 這篇文章主要介紹了阿里面試必會(huì)的20道C++面試題與參考答案,涉及C++指針、面向?qū)ο?、函?shù)等相關(guān)特性與使用技巧,需要的朋友可以參考下2019-09-26
- 這篇文章主要介紹了經(jīng)典C++筆試題目與參考答案,總結(jié)分析了C++常見的各種面試題目,包含C++常見知識(shí)點(diǎn)、技術(shù)難點(diǎn)、算法等,需要的朋友可以參考下2019-09-10
- 這篇文章主要介紹了華為筆試算法面試題與參考答案,結(jié)合實(shí)例形式分析了基于C++的字符串轉(zhuǎn)換、判斷、排序等算法相關(guān)操作技巧,需要的朋友可以參考下2019-09-05
