1. 位運算符有：
&(按位與)繁堡、|(按位或)沈善、^(按位異或)、~ (按位取反)椭蹄。
其中闻牡，按位取反運算符是單目運算符，其余均為雙目運算符绳矩。
位運算符的優(yōu)先級從高到低罩润，依次為~、&翼馆、^割以、|金度，
其中~的結(jié)合方向自右至左，且優(yōu)先級高于算術(shù)運算符严沥，其余運算符的結(jié)合方向都是自左至右猜极，且優(yōu)先級低于關(guān)系運算符。
2. 二維數(shù)組作為函數(shù)參數(shù)正確寫法如下所示：
void Func(int array[3][10]);
void Func(int array[ ][10]);
因為數(shù)組的行數(shù)無關(guān)緊要消玄，所以還可以寫成如下形式：
void Func(int (*array)[10]); // 注意 *array 需要用括號括起來跟伏。
這種形式的聲明參數(shù)是一個指針，它指向具有10個元素的一維數(shù)組莱找。因為[]的優(yōu)先級比*的優(yōu)先級高酬姆，故 *array 必須用括號括起來，否則變成了
void Func（int *array[10]);
這時候參數(shù)相當于是聲明了一個數(shù)組奥溺，該數(shù)組有10個元素辞色，其中每個元素都是一個指向整型對象的指針。
當使用 int** numbers 作為形參時浮定，需要兩次 new：
int** numbers = new int*[rows]; // 二維數(shù)組用到二維指針
numbers[i] = new int[columns]; //每一行開辟columns列int類型內(nèi)存空間
3.用 new 新建結(jié)點
可以提供BinaryTreeNode(int x): m_nValue(x), m_pLeft(NULL), m_pRight(NULL){}形式的語句來快速創(chuàng)建賦值結(jié)點：BinaryTreeNode *root = new BinaryTreeNode(8);
struct BinaryTreeNode {
int m_nValue;
BinaryTreeNode* m_pLeft;
BinaryTreeNode* m_pRight;
BinaryTreeNode(int x): m_nValue(x), m_pLeft(NULL), m_pRight(NULL){}
};
4.HashMap
class Solution {
public:
vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
map<int,int>m;
int n1=nums1.size(),n2=nums2.size();
for(int i=0;i<n1;i++) m[nums1[i]]++;
vector<int>res;
for(int i=0;i<n2;i++)
{
if(m[nums2[i]]!=0)
{
res.push_back(nums2[i]);
m[nums2[i]]=0;
}
}
return res;
}
};
5. 快速排序時間復(fù)雜度
為了分析快速排序的時間復(fù)雜度相满，請先看下面的主定理：
主定理: T [n] = aT[n/b] + f (n)
其中 a >= 1 and b > 1 是常量 并且 f (n) 是一個漸近正函數(shù)， 為了使用這個主定理桦卒，您需要考慮下列三種情況：
快速排序的每一次劃分把一個 問題分解成兩個子問題立美，其中的關(guān)系可以用下式表示：
T[n] = 2T[n/2] + O(n) 其中O(n)為PARTITION()的時間復(fù)雜度，對比主定理方灾，
T [n] = aT[n/b] + f (n)
我們的快速排序中：a = 2, b = 2, f(n) = O(n)
那么為什么還有最壞情況呢建蹄？
考慮如下極端情況，
T[n] = T[n-1] + T[1] + O(n),
問題來了裕偿，這一次的劃分白玩了洞慎，劃分之后一邊是一個，一邊是n-1個嘿棘，這種極端情況的時間復(fù)雜度就是O(n2).
排序算法中的快速排序的時間復(fù)雜度即 O（n log n）劲腿，它通過平均時間復(fù)雜度為 O（log n）的算法將數(shù)組中的一個元素放在正確的地方，而它需要放置 n 個元素鸟妙，所以時間復(fù)雜度既 O（n log n）焦人。
5. 虛函數(shù)
- 如果沒有使用關(guān)鍵字
virtual，程序?qū)⒏鶕?jù)引用類型或指針類型選擇方法 - 如果使用了關(guān)鍵字
virtual重父，程序?qū)⒏鶕?jù)引用或指針指向的對象的類型來選擇方法
6. http 的 POST 和 GET 有什么區(qū)別?
根據(jù) HTTP 協(xié)議的定義 GET 類型的請求是冪等的, 而 POST 請求是有副作用的, 也就是說 GET 用于獲取一些資源, 而 POST 用于改變一些資源, 這可能會創(chuàng)建新的資源或更新已有的資源.
POST 請求比 GET 請求更加的安全, 因為你不會把信息添加到 URL 上的查詢字符串上. 所以使用 GET 來收集密碼或者一些敏感信息并不是什么好主意.
最后, POST 請求比 GET 請求也可以傳輸更多的信息.
7. 什么是 Binary search tree, 它的時間復(fù)雜度是多少?
二叉搜索樹是一棵以二叉樹來組織的, 它搜索的時間復(fù)雜度 O(h)O(h) 與樹的高度成正比, 最壞的運行時間是 Θ(lgn).
8. static作用花椭？
（1）函數(shù)體內(nèi) static 變量的作用范圍為該函數(shù)體，不同于 auto 變量房午，該變量的內(nèi)存只被分配一次个从，因此其值在下次調(diào)用時仍維持上次的值；
（2）在模塊內(nèi)的 static 全局變量可以被模塊內(nèi)所用函數(shù)訪問，但不能被模塊外其它函數(shù)訪問嗦锐；
（3）在模塊內(nèi)的 static 函數(shù)只可被這一模塊內(nèi)的其它函數(shù)調(diào)用，這個函數(shù)的使用范圍被限制在聲明它的模塊內(nèi)沪曙；
（4）在類中的 static 成員變量屬于整個類所擁有奕污，對類的所有對象只有一份拷貝；
（5）在類中的 static 成員函數(shù)屬于整個類所擁有液走，這個函數(shù)不接收 this 指針碳默，因而只能訪問類的static 成員變量。
9. 插入排序
一種改進方法缘眶，可以將找位置和移位合并起來嘱根，每次a[i]先和a[i-1]進行比較，如果a[i]>a[i-1]說明已經(jīng)有序不需要找巷懈，反之该抒，將大于a[i]的元素一邊進行后移，一邊查找插入位置顶燕，代碼如下：
void insertSort2(int a[], int length) {
for (int i = 1; i < length; i++) {
int temp = a[i];
//將找位置與數(shù)據(jù)后移合并
if (a[i] < a[i - 1]) {
int j;
for (j = i-1; j >= 0 && a[j] > temp; j--) {
a[j+1] = a[j];
}
a[j+1] = temp;
}
}
}
我在網(wǎng)上也看到過另一種改進方法凑保，將數(shù)據(jù)后移用交換函數(shù)替代，這樣寫代碼十分簡潔：
void insertSort3(int a[], int length) {
for (int i = 1; i < length; i++) {
for (int j = i-1; j >= 0 && a[j] > a[j+1]; j--) {
//用交換代替數(shù)據(jù)后移
swap(a[j], a[j+1]);
}
}
}
10. 冒泡排序
當我們需要排序的數(shù)組基本有序時涌攻，上面的代碼還會做出很多不必要的查找判斷欧引，降低了代碼的執(zhí)行效率。下面我們進行第一步優(yōu)化恳谎，我們先定義一個標志flag芝此，用來判斷本次排序中是否發(fā)生交換，如果沒有發(fā)生交換因痛，說明排序已經(jīng)完成婚苹，我們不需要再做不必要的循環(huán)判斷，代碼為：
void bubbleSort(int array[], int length) {
bool flag = true;//判斷是否發(fā)生交換
while (flag) {
flag = false;
for (int j = 1; j < length; j++) {
if (array[j-1] > array[j]) {
swap(array[j-1], array[j]);
flag = true;
}
}
length --;
}
}
再做進一步優(yōu)化婚肆，如果有數(shù)組前面幾個是無序的租副，而后面的元素都已經(jīng)是有序的，那我們就可以記錄下無序的位置较性，下次排序判斷時用僧，只需要從數(shù)組頭部遍歷到該位置就可以了，這樣可以省去遍歷后面的元素赞咙，提高了代碼的執(zhí)行效率责循。代碼為：
void bubbleSort(int array[], int length)
{
int flag = length;
while (flag > 0) {
int k = flag;
flag = 0;
for (int j = 1; j < k; j++) {
if (array[j - 1] > array[j]) {
swap(array[j - 1], array[j]);
flag = j;
}
}
}
}
該方法和第二種的區(qū)別就是：先判斷有沒有交換，若有交換我也只遍歷無序的區(qū)域攀操。
11.快速排序
void quickSortRecursive(int array[], int start, int end) {
if (start >= end)
return;
//從數(shù)列中挑出一個元素院仿，稱為"基準"。
int mid = array[end];
int left = start;
int right = end - 1;
while (left < right) {
//從左開始找，找到大于等于 mid 的數(shù)停止歹垫。
while (array[left] < mid && left < right) left++;
//從右開始找剥汤，找到小于 mid 的數(shù)停止。
while (array[right] >= mid && right > left) right--;
//交換left和right位置的數(shù)
swap(array[left], array[right]);
}
//使 left 位置數(shù)小于它左邊的數(shù)排惨，大于它右邊的數(shù)吭敢。
if (array[left] >= array[end])
swap(array[left], array[end]);
else
left++;
// 遞歸地把小于基準值元素的子數(shù)列和大于基準值元素的子數(shù)列排序
quickSortRecursive(array, start, left - 1);
quickSortRecursive(array, left + 1, end);
}
12. 選擇排序
//選擇排序 平均時間復(fù)雜度O(n^2) 額外空間復(fù)雜度O(1)
void selectionSort(int array[], int length) {
int i, j, min;
for (i = 0; i < length; i++) {
//找到最小元素存放到起始位置。
min = i;
for (j = i + 1; j < length; j++)
if (array[j] < array[min])
min = j;
swap(array[i], array[min]);
}
}
13. 堆排序
void max_heapify(int arr[], int start, int end) {
//建立父節(jié)點指標和子節(jié)點指標
int dad = start;
int son = dad * 2 + 1;
while (son <= end) { //若子節(jié)點指標在範圍內(nèi)才做比較
if (son + 1 <= end && arr[son] < arr[son + 1]) //先比較兩個子節(jié)點大小暮芭，選擇最大的
son++;
if (arr[dad] > arr[son]) //如果父節(jié)點大於子節(jié)點代表調(diào)整完畢鹿驼，直接跳出函數(shù)
return;
else { //否則交換父子內(nèi)容再繼續(xù)子節(jié)點和孫節(jié)點比較
swap(&arr[dad], &arr[son]);
dad = son;
son = dad * 2 + 1;
}
}
}
void heap_sort(int arr[], int len) {
int i;
//初始化，i從最後一個父節(jié)點開始調(diào)整
for (i = len / 2 - 1; i >= 0; i--)
max_heapify(arr, i, len - 1);
//先將第一個元素和已排好元素前一位做交換辕宏，再從新調(diào)整畜晰，直到排序完畢
for (i = len - 1; i > 0; i--) {
swap(&arr[0], &arr[i]);
max_heapify(arr, 0, i - 1);
}
}