秋招已過，各大廠的面試題分享一波附C++實現

C++ 桶排序 · 發表 2018-11-21 19:57:00

摘要：資料結構和演算法是面試的一座大山，尤其去面試大廠更是必不可少！簡單說明一下為啥喜歡考資料結構和演算法，首先，演算法有用也沒用，如果是中小型企業的簡單業務邏輯，可能用不到啥演算法，但大廠一定會用到，都知道資料庫底層會用到紅黑樹、B++樹等，去oracle公司，那資料結構一定要玩轉，再加入想去阿里...

資料結構和演算法是面試的一座大山，尤其去面試大廠更是必不可少！簡單說明一下為啥喜歡考資料結構和演算法，首先，演算法有用也沒用，如果是中小型企業的簡單業務邏輯，可能用不到啥演算法，但大廠一定會用到，都知道資料庫底層會用到紅黑樹、B++樹等，去oracle公司，那資料結構一定要玩轉，再加入想去阿里，百萬資料量，不會演算法去優化，可能阿里早倒閉，但小長資料量會比較少，用演算法就沒什麼必要了。

一、桶排序應用-求最大差值

1、題目

給定一個數組，求如果排序之後，相鄰兩數的最大差值，要求時間複雜度O（N），且要求不能用基於比較的排序。

2、思路分析

桶排序應該都知道吧，跟計數排序和基數排序都是非比較排序，像快排、歸併都是比較排序。其實，桶排序是一種思想，具體實現是計數排序和基數排序。

接下來直接來分析題目，如下：

如果有N個數，準備N+1個桶，

遍歷找到最小值和最大值

假如，有9個數，準備10個桶，中間必定存在最少一個空桶，說明最大差值一定不在一個桶內，但不一定在空桶兩邊。

舉例子如下：

三個數，四個桶，最大差值19

19 空桶 30 49

3、程式碼實現

如下：


#include<iostream>
#include<vector>
#include<climits>
using namespace std;

class Solution{
public:
int maxGap(vector<int> &nums){
if(nums.size() < 2)
return 0;

int len = nums.size();
int min_index = INT_MAX;
int max_index = INT_MIN;

//找出陣列的最大值和最小值
for(int i=0;i<nums.size();i++){
min_index = min(min_index,nums[i]);
max_index = max(max_index,nums[i]);
}
if(min_index == max_index)
return 0;

bool *hasNum = new bool[len+1]; //每個桶是否被訪問過
int *maxs = new int[len+1]; //最大值陣列
int *mins = new int[len+1]; //最小值陣列

int bid = 0;
for(int i = 0;i<len;i++){
bid = bucket(nums[i],len,min_index,max_index);//形成桶
mins[bid] = hasNum[bid] ? min(mins[bid],nums[i]) : nums[i]; //給最大值桶賦值
maxs[bid] = hasNum[bid] ? max(maxs[bid],nums[i]) : nums[i] ;//給最小值桶賦值 
hasNum[bid] = true;
}

int res = 0;
int lastMax = maxs[0];
for(int i=1;i<len;i++){
if(hasNum[i]){
res = max(res,mins[i]-lastMax);
lastMax = maxs[i];
}
}

return res;
}
private:
int bucket(int num,int len,int min1,int max1){
return (int) ((num-min1)*len/(max1-min1));
}
};

int main()
{
int temp[] = {11,2,44,50,67};
vector<int> nums(temp,temp+5);
cout << "max:" << Solution().maxGap(nums) << endl;

return 0;
}

View Code

二、用資料實現固定大小的佇列和棧

1、題目

用資料實現固定大小的佇列和棧

2、思路分析

佇列和和棧的特性分別是：先進先出和先進後出，思路分析見下圖：

圖上，標註的很明白了，有不明白的歡迎留言

3、程式碼實現

首先是陣列實現棧，程式碼如下：

#include<iostream>
#include<vector>
using namespace std;

class ArrayStack{
private:
int index;//插入位置的下標
int *arr;
int maxSize;

public:
ArrayStack(int initSize){
if(initSize < 0)
throw "The initSize is less than 0";
arr = new int[initSize];
index = 0;
maxSize = initSize;
}

void push(int num){ //壓入棧
if(index == maxSize)
throw "The stack is full";
arr[index++] = num;
}
int pop(){
if(index == 0)
throw "The stack is empty";
return arr[--index];
}
};

int main()
{
ArrayStack stack1 = ArrayStack(3);
stack1.push(2);
stack1.push(3);
stack1.push(1);
cout << "num:" << stack1.pop() << endl;

return 0;
}

用陣列實現佇列，程式碼如下：

#include<iostream>
#include<vector>
using namespace std;

class ArrayQueue{
private:
int *arr;
int size;
int start;//彈出下標
int end;//插入下標
int maxSize;//陣列最大值
public:
ArrayQueue(int initSize)
{
if(initSize < 0)
throw "The initSize is less than 0";

arr = new int[initSize];
size = 0;
start = 0;
end = 0;
maxSize = initSize;
}

void push(int num){
if(size == maxSize)
throw "the queue is full";
size++;
arr[end] = num;
end = end==maxSize-1?0:end+1;//讓end可以在陣列中迴圈跑
}
int pop(){
if(0 == size)
throw "the queue is empty";
size--;
int tmp = start;
start = start==maxSize-1?0:start+1; //跟end一樣在陣列中迴圈跑
return arr[tmp];
}

};

int main()
{
ArrayQueue arrQueue = ArrayQueue(3);
arrQueue.push(1);
arrQueue.push(2);
cout << "num:" << arrQueue.pop() << endl;

return 0;
}

三、實現特殊的棧 O(1)返回最小元素

1、題目

實現一個特殊的棧，在實現棧的基本功能上，再實現返回棧中最小元素的操作。

【要求】

pop、push和getMin操作的時間複雜度都是O(1)
設計的棧型別可以使用現成的棧結構

2、思路

直接上圖，如下：

3、程式碼實現

程式碼如下：


#include<iostream>
#include<vector>
#include<stack>
using namespace std;

class GetMinStack{
private:
stack<int> stackData;
stack<int> stackMin;
public:
void push(int num){
if(stackMin.empty()){
stackMin.push(num);
}else if(num <= getmin()){
stackMin.push(num);
}
stackData.push(num);


}

int pop(){
if(stackData.empty())
throw "the empty";
int value = stackData.top();
stackData.pop();
if(value == getmin()){
stackMin.pop();
}
return value;

}

int getMin(){//獲取最小值
if(stackMin.empty())
throw "the stackMin is empty";
return stackMin.top();
}

int getmin(){
if(stackMin.empty())
throw "the stack is empty";
return stackMin.top();
}

};

int main()
{
GetMinStack minStack = GetMinStack();
minStack.push(1);
minStack.push(3);
minStack.push(2);
cout << "pop num:" << minStack.pop() << endl;
cout << "min num:" << minStack.getMin() << endl;


return 0;
}

View Code

會繼續分享面經和演算法，希望持續關注！

秋招已過，各大廠的面試題分享一波 附C++實現

一、桶排序應用-求最大差值

1、題目

2、思路分析

3、程式碼實現

二、用資料實現固定大小的佇列和棧

1、題目

2、思路分析

3、程式碼實現

三、實現特殊的棧 O(1)返回最小元素

1、題目

2、思路

3、程式碼實現

您可能也會喜歡…

秋招已過，各大廠的面試題分享一波附C++實現