萬能的頭文件<bits/stdc++.h>
#include<bits/stdc++.h>包含了目前c++所包含的所有頭文件?。。。?/p>
i++和++i的區(qū)別？哪個效率更高？
i++ 就是i = i + 1 ，但是表達式是i+1之前的值，首先它把這個值保存到一個副本中。
++i 就是 i= i+1 ，它不需要保存到副本中，因此效率更高一些。
inline和宏的區(qū)別?
1、內斂函數在編譯時展開，宏在預編譯時展開
2、在編譯時內斂函數會嵌入到目標代碼中，宏只是一個簡單的文本替換
3、內斂函數會進行安全檢查，宏不會
4、宏不是函數，inline是一個函數
5、inline可以不展開，宏必須展開
簡述內斂函數？
內斂函數是在類聲明體內定義的函數或在類的實現部分定義的，其前用inline修飾，它將簡單的函數內嵌到調用它的函數代碼中，這樣做節(jié)省了調用函數的開銷。
普通函數的調用要經過“保存現場、轉到被調函數執(zhí)行、執(zhí)行完畢返回調用處、恢復現場”這一過程，產生時空開銷。
內聯函數是通過代碼膨脹來執(zhí)行的，在內聯函數調用處復制函數代碼，這樣省去了普通函數調用的時空開銷，提高了程序執(zhí)行效率，但是由于代碼復制增加了內存開銷，所以內聯函數應當是小函數、執(zhí)行耗時短的函數。
select和epoll的區(qū)別？
select是通過輪詢的方式找到讀取或寫入的數據流對他們進行操作。具有O(n)的無差別輪詢復雜度，處理的流越多無差別的輪詢時間就越長。
poll和select沒什么太大的差別，它將用戶傳入的數組拷貝到內核空間，查找每個fd對應的設備狀態(tài)。它沒有最大連接數的限制，因為它是基于鏈表存儲的。時間復雜度O(n)。
epoll是基于事件驅動的，哪個流發(fā)生I/O事件會直接通知。時間復雜度O(1)。
select，poll，epoll都是IO多路復用的機制。I/O多路復用就通過一種機制，可以監(jiān)視多個描述符，一旦某個描述符就緒（一般是讀就緒或者寫就緒），能夠通知程序進行相應的讀寫操作。但select，poll，epoll本質上都是同步I/O，因為他們都需要在讀寫事件就緒后自己負責進行讀寫，也就是說這個讀寫過程是阻塞的，而異步I/O則無需自己負責進行讀寫，異步I/O的實現會負責把數據從內核拷貝到用戶空間。??
水平觸發(fā):如果文件描述符已經就緒可以非阻塞的執(zhí)行IO操作了,此時會觸發(fā)通知。允許在任意時刻重復檢測IO的狀態(tài)。select,poll就屬于水平觸發(fā)。
?邊緣觸發(fā):如果文件描述符自上次狀態(tài)改變后有新的IO活動到來,此時會觸發(fā)通知。在收到一個IO事件通知后要盡可能多的執(zhí)行IO操作，因為如果在一次通知中沒有執(zhí)行完IO那么就需要等到下一次新的IO活動到來才能獲取到就緒的描述符。信號驅動式IO就屬于邊緣觸發(fā)。
1、 time_wait的作用
TIME_WAIT狀態(tài)存在的理由：
1）可靠地實現TCP全雙工連接的終止
保證客戶端發(fā)送的最后一個ACK報文能夠到達服務器，因為這個ACK報文可能丟失，站在服務器的角度看來，我已經發(fā)送了FIN+ACK報文請求斷開了，客戶端還沒有給我回應，應該是我發(fā)送的請求斷開報文它沒有收到，于是服務器又會重新發(fā)送一次，而客戶端就能在這個2MSL時間段內收到這個重傳的報文，接著給出回應報文，并且會重啟2MSL計時器。
2）允許老的報文在網絡中消逝
防止類似與“三次握手”中提到了的“已經失效的連接請求報文段”出現在本連接中?？蛻舳税l(fā)送完最后一個確認報文后，在這個2MSL時間中，就可以使本連接持續(xù)的時間內所產生的所有報文段都從網絡中消失。這樣新的連接中不會出現舊連接的請求報文。
2、大量TIME_WAIt造成的影響
在高并發(fā)短連接的TCP服務器上，當服務器處理完請求后立刻主動正常關閉連接。這個場景下會出現大量socket處于TIME_WAIT狀態(tài)。如果客戶端的并發(fā)量持續(xù)很高，此時部分客戶端就會顯示連接不上。
為什么我們要關注這個高并發(fā)短連接呢？有兩個方面需要注意：
高并發(fā)可以讓服務器在短時間范圍內同時占用大量端口，而端口有個0~65535的范圍，并不是很多，刨除系統(tǒng)和其他服務要用的，剩下的就更少了。
在這個場景中，短連接表示“業(yè)務處理+傳輸數據的時間?遠遠小于?TIMEWAIT超時的時間”的連接。
TCP處于TIMEWAIT狀態(tài)時，別的請求過來后，沒有空閑的端口可供tcp連接，大大影響服務器響應請求。?長連接業(yè)務的服務就不需要考慮TIMEWAIT狀態(tài)。同時，假如你對服務器業(yè)務場景非常熟悉，你會發(fā)現，在實際業(yè)務場景中，一般長連接對應的業(yè)務的并發(fā)量并不會很高。
3、TIME_WAIT狀態(tài)如何避免
首先服務器可以設置SO_REUSEADDR套接字（so_reuseaddr）選項來通知內核，如果端口忙，但TCP連接位于TIME_WAIT狀態(tài)時可以重用端口。在一個非常有用的場景就是，如果你的服務器程序停止后想立即重啟，而新的套接字依舊希望使用同一端口，此時SO_REUSEADDR選項就可以避免TIME_WAIT狀態(tài)。
堆和棧的區(qū)別？
1、生長方向：堆自下向上，棧自上向下；
2、分配方式：堆手動分配，棧自動分配；
3、分配大?。憾押艽?，棧很小；
4、碎片化：堆易產生，棧不會產生。
數組第k小的數
#include <iostream>
using namespace std;
int findK(int arrayNum[], int p, int r, int k) {
/**
*在數組arrayNum[p:r]中查找第k（k > 0)個元素（下標為p+k-1)
* p <= r && 0 < k && k <= p - r +1 （合法輸入說明）
*漸進時間復雜度/平均時間復雜度 O(N)
*/
int i = p, j = r, key = arrayNum[i];
while (i < j) {
while (arrayNum[i] <= key)
++i;
while (arrayNum[j] >= key)
--j;
if (i < j)
{
swap(arrayNum[i++], arrayNum[j--]);
}
}//循環(huán)結束后 i = j,其實前面這些語句就是快排的一次劃分
int lefts = i - p + 1;
if (lefts == k)
return arrayNum[i];//找到中位數了
if (lefts > k) //比關鍵字小的數的個數大于k，則中位數在左邊
return findK(arrayNum, p, i - 1, k);
else
return findK(arrayNum, i + 1, r, k - lefts);
}
int main()
{
int tmp[11] = { 3, 4 , 5, 2, 4, 6,0, 8, 1,324 };
cout << "請輸入要查找第幾個最小數,數字要小于等于10" << endl;
int m = 0;
cin >> m;
int result = 0;
result = findK(tmp, 0, 10, m);
cout << "結果為" << result << endl;
return 0;
}
Top-K問題
1、直接全部排序（只適用于內存夠的情況）
當數據量較小的情況下，內存中可以容納所有數據。則最簡單也是最容易想到的方法是將數據全部排序，然后取排序后的數據中的前K個。
這種方法對數據量比較敏感，當數據量較大的情況下，內存不能完全容納全部數據，這種方法便不適應了。即使內存能夠滿足要求，該方法將全部數據都排序了，而題目只要求找出top K個數據，所以該方法并不十分高效，不建議使用。
2、快速排序的變形 （只使用于內存夠的情況）
這是一個基于快速排序的變形，因為第一種方法中說到將所有元素都排序并不十分高效，只需要找出前K個最大的就行。
這種方法類似于快速排序，首先選擇一個劃分元，將比這個劃分元大的元素放到它的前面，比劃分元小的元素放到它的后面，此時完成了一趟排序。
如果此時這個劃分元的序號index剛好等于K，那么這個劃分元以及它左邊的數，剛好就是前K個最大的元素；如果index > K，那么前K大的數據在index的左邊，那么就繼續(xù)遞歸的從index-1個數中進行一趟排序；如果index < K，那么再從劃分元的右邊繼續(xù)進行排序，直到找到序號index剛好等于K為止。再將前K個數進行排序后，返回Top
K個元素。這種方法就避免了對除了Top K個元素以外的數據進行排序所帶來的不必要的開銷。
3、最小堆法
這是一種局部淘汰法。先讀取前K個數，建立一個最小堆。然后將剩余的所有數字依次與最小堆的堆頂進行比較，如果小于或等于堆頂數據，則繼續(xù)比較下一個；否則，刪除堆頂元素，并將新數據插入堆中，重新調整最小堆。當遍歷完全部數據后，最小堆中的數據即為最大的K個數。
4、分治法
將全部數據分成N份，前提是每份的數據都可以讀到內存中進行處理，找到每份數據中最大的K個數。此時剩下NK個數據，如果內存不能容納NK個數據，則再繼續(xù)分治處理，分成M份，找出每份數據中最大的K個數，如果M*K個數仍然不能讀到內存中，則繼續(xù)分治處理。直到剩余的數可以讀入內存中，那么可以對這些數使用快速排序的變形或者歸并排序進行處理。
5、Hash法
如果這些數據中有很多重復的數據，可以先通過hash法，把重復的數去掉。這樣如果重復率很高的話，會減少很大的內存用量，從而縮小運算空間。處理后的數據如果能夠讀入內存，則可以直接排序；否則可以使用分治法或者最小堆法來處理數據。
6、隊列
可以將前K個數據放入有序隊列中，剩余的數據依次與隊列中的數據比較，如果比隊列中的最小值小或等于，則繼續(xù)，否則，就替換，調整有序隊列。遍歷結束后，隊列中的數據就是前K大的元素。
講一下哈希算法，有什么用；解決哈希沖突的方法？
哈希算法，用于將任意長度的二進制值串映射為固定長度的二進制值串，映射之后得到的二進制值就是哈希值（散列值）。
哈希表就是一種以 鍵-值(key-indexed) 存儲數據的結構。
用于文件校驗、數字簽名、鑒權協議。
解決哈希沖突的方法
1、開放地址法
用開放定址法解決沖突的做法是：當沖突發(fā)生時，使用某種探查(亦稱探測)技術在散列表中形成一個探查(測)序列。沿此序列逐個單元地查找，直到找到給定 的關鍵字，或者碰到一個開放的地址(即該地址單元為空)為止（若要插入，在探查到開放的地址，則可將待插入的新結點存人該地址單元）。查找時探查到開放的 地址則表明表中無待查的關鍵字，即查找失敗。
2、拉鏈法
拉鏈法解決沖突的做法是：將所有關鍵字為同義詞的結點鏈接在同一個單鏈表中。若選定的散列表長度為m，則可將散列表定義為一個由m個頭指針組成的指針數 組T[0..m-1]。凡是散列地址為i的結點，均插入到以T[i]為頭指針的單鏈表中。T中各分量的初值均應為空指針。在拉鏈法中，裝填因子α可以大于 1，但一般均取α≤1。
3、再散列法
再散列法其實很簡單，就是再使用哈希函數去散列一個輸入的時候，輸出是同一個位置就再次散列，直至不發(fā)生沖突位置
下面我在介紹另一種解決哈希表的方法，開鏈法，也叫哈希桶。下面我介紹一下這種方法的思路。
? ?基本思路：
? ? 1.先給一個數組，這個數組中存的是指針數組，每個指針數組都指向一個數組。
? ? 2.用元素除以存儲指針數組的數組的大小。
? ? 3.余數與指針數組下標相同的，都鏈到數組指針指向的這一個數組。
我在進一步用圖表示一下：
代碼如下：
static關鍵字？
static修飾的內置類型變量分為靜態(tài)全局變量和靜態(tài)局部變量，靜態(tài)變量內存分配在 .data段。靜態(tài)變量只初始化一次，未初始化的靜態(tài)變量會默認初始化為0。靜態(tài)全局變量只在本文件可見，外部文件無法訪問。而靜態(tài)局部變量只在定義的作用域內可見，但他們的生存周期都是整個程序運行時期。
static修飾的函數為靜態(tài)函數，靜態(tài)函數主要是起到函數的隱藏作用，static修飾的函數只允許在當前文件中使用，在其他文件中無法找到該函數的地址。
static修飾的數據成員屬于類的組成部分，static修飾的數據成員不在棧上分配內存而在.data段分配內存，static修飾的數據成員不能通過調用構造函數來進行初始化，因此static修飾的數據成員必須在類外進行初始化且只會初始化一次。
static修飾的成員方法為靜態(tài)成員方法，靜態(tài)成員方法可以在類內或類外定義，但必須在類內聲明；static成員方法沒有this指針，所以不能直接引用非static數據成員或調用類的非static成員方法，只能調用類的static成員數據和static成員方法；static成員不是任何對象的組成，不依賴對象的調用所以static成員方法不能被聲明為const，因為const只限定該類的對象；static成員方法不能同時被聲明為虛函數。
extern關鍵字
extern可以置于變量或者函數前，以標示變量或者函數的定義在別的文件中，提示編譯器遇到此變量和函數時在其他模塊中尋找其定義。此外extern也可用來進行鏈接指定。
extern有兩個作用：
第一個,當它與"C"一起連用時，如: extern "C" void fun(int a, int b);則告訴編譯器在編譯fun這個函數名時按著C的規(guī)則去翻譯相應的函數名而不是C++的。
第二，當extern不與"C"在一起修飾變量或函數時，如在頭文件中: extern int g_Int;?它的作用就是聲明函數或全局變量的作用范圍的關鍵字，其聲明的函數和變量可以在本模塊活其他模塊中使用，記住它是一個聲明不是定義!也就是說B模塊(編譯單元)要是引用模塊(編譯單元)A中定義的全局變量或函數時，它只要包含A模塊的頭文件即可,在編譯階段，模塊B雖然找不到該函數或變量，但它不會報錯，它會在連接時從模塊A生成的目標代碼中找到此函數。
紅黑樹（Red Black Tree） 是一種自平衡二叉查找樹，是在計算機科學中用到的一種數據結構，典型的用途是實現關聯數組。
紅黑樹的性質
性質1. 節(jié)點是紅色或黑色。
性質2. 根節(jié)點是黑色。
性質3 每個葉節(jié)點（NIL節(jié)點，空節(jié)點）是黑色的。
性質4 每個紅色節(jié)點的兩個子節(jié)點都是黑色。(從每個葉子到根的所有路徑上不能有兩個連續(xù)的紅色節(jié)點)
性質5. 從任一節(jié)點到其每個葉子的所有路徑都包含相同數目的黑色節(jié)點。
C++的STL中。如map和set都是用紅黑樹實現的
301 redirect: 301 代表永久性轉移(Permanently Moved)
?302 redirect: 302 代表暫時性轉移(Temporarily Moved )
301表示舊地址A的資源已經被永久地移除了（這個資源不可訪問了），搜索引擎在抓取新內容的同時也將舊的網址交換為重定向之后的網址；
302表示舊地址A的資源還在（仍然可以訪問），這個重定向只是臨時地從舊地址A跳轉到地址B，搜索引擎會抓取新的內容而保存舊的網址。
