作者：TeddyZhang，公衆号：算法工程師之路
Day 15, C/C++知識點走起~
1
程式設計題
【劍指Offer】最小的K個數
輸入n個整數，找出其中最小的K個數。例如輸入4,5,1,6,2,7,3,8這8個數字，則最小的4個數字是1,2,3,4,。
思路：
很多人都覺得這個問題是一個排序問題，但我覺得不一定要排序啊，可以使用堆結構（最小堆），首先将所有的元素都壓入到最小堆中，每次彈出最小值就好了，一共彈出k個數。
直接使用STL庫中的堆結構，也就是優先級隊列！代碼就非常簡潔了！
class Solution {
public:
vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
priority_queue<int, vector<int>, greater<int>> pq;
vector<int> res;
if(input.size() < k) return res; // 傳回數值記憶體大于輸入記憶體，則傳回空
for(auto i: input){
pq.push(i);
}
while(k--){
res.push_back(pq.top());
pq.pop();
}
return res;
}
};
複制
當然，隻會用庫在面試官面前是不行的，接下來我們手動使用vector實作一個最小堆!
文章連結: 從底層實作堆結構和堆排序
這裡面我将上面文章中的最大堆改成了最小堆，右一個細節就是：heapify中有一個left+1的邊界，如果不滿足這個邊界，那麼必須傳回left，而不是left+1。
class Solution {
public:
void heapInsert(vector<int>& list, int index){
while(list[index] < list[(index-1)/]){
swap(list[index], list[(index-1)/]); // 與根節點交換
index = (index-1)/; // 目前位置更新
}
}
// 改變某個值，仍然是最小堆結構
void heapify(vector<int>& list, int index, int heapSize){
int left = index*+;
while(left < heapSize){
int mini = (left + ) < heapSize && list[left] > list[left+]
? left + : left;
// 這個判斷錯誤時隻能是left，由于left+1可能出了索引範圍
mini = list[mini] < list[index] ? mini : index;
if(mini == index){
break;
}
swap(list[mini], list[index]);
index = mini;
left = index*+;
}
}
vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
vector<int> res;
if(input.size() == ) return res;
if(input.size() < k) return res;
for(int i = ;i < input.size(); i++){
heapInsert(input, i);
}
int heapSize = input.size();
while(k--){
res.push_back(input[]);
swap(input[], input[--heapSize]);
heapify(input, , heapSize);
}
return res;
}
};
複制
【劍指Offer】連續子數組的最大和
HZ偶爾會拿些專業問題來忽悠那些非計算機專業的同學。今天測試組開完會後,他又發話了:在古老的一維模式識别中,常常需要計算連續子向量的最大和,當向量全為正數的時候,問題很好解決。但是,如果向量中包含負數,是否應該包含某個負數,并期望旁邊的正數會彌補它呢？例如:{6,-3,-2,7,-15,1,2,2},連續子向量的最大和為8(從第0個開始,到第3個為止)。給一個數組，傳回它的最大連續子序列的和，你會不會被他忽悠住？(子向量的長度至少是1)
思路：
周遊這個數組，設定一個累加變量sum，如果sum < 0，那麼sum + array[i] 必定小于sum，是以此時sum在本階段為最大連續子序列，周遊到下一個時，sum更新為array[i]，表示重新開啟一個連續子序列！将各個階段的sum求最大值即可！
class Solution {
public:
int FindGreatestSumOfSubArray(vector<int> array) {
int res = INT_MIN; // 整型的最小值
int sum = ;
for(int i = ; i < array.size(); i++) {
if(sum < ) {
sum = array[i]; // 如果sum小于0，則sum+array[i] < array[i]
} else {
sum += array[i];
}
if(sum > res) {
res = sum;
}
}
return res;
}
}; 複制
2
概念題
【C/C++】malloc和new的差別？
- malloc和free是标準庫函數，支援覆寫；new和delete是運算符，并且支援重載。
- malloc僅僅配置設定記憶體空間，free僅僅回收空間，不具備調用構造函數和析構函數功能，用malloc配置設定空間存儲類的對象存在風險；new和delete除了配置設定回收功能外，還會調用構造函數和析構函數。
- malloc和free傳回的是void類型指針（必須進行類型轉換），new和delete傳回的是具體類型指針。
int *a = (int *)malloc(sizeof(int)); //需要顯示指定開辟記憶體大小，且需要強制類型轉換
int *a = new int;
複制
【C/C++】面向對象的三大特性都有哪些？
- 封裝性：資料和代碼捆綁在一起，避免外界幹擾和不确定性通路。一般使用類進行封裝！
- 繼承性：讓某種類型對象獲得另一個類型對象的屬性和方法。
- 多态性：同一事物表現出不同僚物的能力，即向不同對象發送同一消息，不同的對象在接收時會産生不同的行為（重載實作編譯時多态，虛函數實作運作時多态），其實質為父類指針指向子類對象，當傳遞不同對象時，同一個函數的運作結果也不同。
【C/C++】多态原了解析
- 當父類中有了虛函數後，内部結構就發生了變化
- 内部多了一個vfptr（虛函數表指針）,并指向vftable(虛函數表)
- 如果父類中有vfptr，那麼子類繼承的話會繼承vfptr，vftable，在建立對象，即構造函數中會将虛函數表指針vfptr指向自己的虛函數表vftable，此時，如果函數發生了重寫，那麼在多态時會對原來虛函數表中的函數進行替換，然後就造成了同樣一個函數當傳入父類和子類時，其函數運作行為是不同的！
3
資源分享
歡迎關注我的個人公衆号 （算法工程師之路），公衆号内有大量視訊資料和電子書資料以及算法筆記，回複關鍵字即可擷取！
公衆号簡介：分享算法工程師必備技能，談談那些有深度有意思的算法，主要範圍：C++資料結構與算法/深度學習（CV），立志成為Offer收割機！堅持分享算法題目和解題思路（Day By Day)
号外，算法刷題群已經建立，但由于人數超出限制，無法掃碼添加，可以加号主微信（Leopard7319538）說明來意，可以加入到算法刷題群，每天2道程式設計題3道概念題，晚9點打卡，我們一起堅持下去！！！
完