1. 鏈表

鏈表是最基本的數(shù)據(jù)結(jié)構(gòu)，面試官也常常用鏈表來考察面試者的基本能力幸乒，而且鏈表相關(guān)的操作相對(duì)而言比較簡(jiǎn)單懦底，也適合考察寫代碼的能力。鏈表的操作也離不開指針罕扎，指針又很容易導(dǎo)致出錯(cuò)聚唐。綜合多方面的原因，鏈表題目在面試中占據(jù)著很重要的地位腔召。

鏈表問題中的一個(gè)重要的方法叫雙指針法杆查。定義兩個(gè)指針，一個(gè)叫慢指針臀蛛，另一個(gè)叫快指針亲桦。通常慢指針每次向前移動(dòng)一個(gè)節(jié)點(diǎn)，而快指針每次向前移動(dòng)若干個(gè)節(jié)點(diǎn)浊仆。這個(gè)方法通常用于尋找鏈表中特定的位置客峭。比如找到鏈表的中點(diǎn)，可以讓快指針每次移動(dòng)兩個(gè)節(jié)點(diǎn)抡柿。這樣當(dāng)快指針到達(dá)鏈表末尾時(shí)舔琅，慢指針剛好在鏈表中間的位置。

鏈表結(jié)點(diǎn)聲明如下：

struct ListNode
{
    int value;
    ListNode * next;
    ListNode(int x) : value(x), next(NULL) {}
};

1.1 求單鏈表中結(jié)點(diǎn)的個(gè)數(shù)

這是最最基本的了沙绝，應(yīng)該能夠迅速寫出正確的代碼搏明，注意檢查鏈表是否為空。時(shí)間復(fù)雜度為O（n）闪檬。

int GetListLenght(ListNode* head)
{
    if(head == NULL)    return 0;
    ListNode* current = head;
    int len = 0;
    while(current != NULL)
    {
        len++;
        current = current->next;
    }
    return len;
}

1.2 將單鏈表反轉(zhuǎn)

從頭到尾遍歷原鏈表星著，每遍歷一個(gè)結(jié)點(diǎn)，將其摘下放在新鏈表的最前端粗悯。注意鏈表為空和只有一個(gè)結(jié)點(diǎn)的情況虚循。時(shí)間復(fù)雜度為O（n）。

ListNode* ReverseList(ListNode* head)
{
    if(head == NULL || head->next == NULL)    return head;
    ListNode* reverseHead = NULL;
    ListNode* current = head;
    while(current != NULL)
    {
        ListNode* temp = current;
        current = current->next;
        temp->next = reverseHead;
        reverseHead = temp;
    }
    return reverseHead;
}

1.3 查找單鏈表中的倒數(shù)第K個(gè)結(jié)點(diǎn)（k>0）

使用兩個(gè)指針，先讓前面的指針走到正向第k個(gè)結(jié)點(diǎn)横缔，這樣前后兩個(gè)指針的距離差是k-1铺遂，之后前后兩個(gè)指針一起向前走，前面的指針走到最后一個(gè)結(jié)點(diǎn)時(shí)茎刚，后面指針?biāo)附Y(jié)點(diǎn)就是倒數(shù)第k個(gè)結(jié)點(diǎn)襟锐。

ListNode * RGetKthNode(ListNode * head, unsigned int k)
{
    if(head == NULL)    return NULL;
    ListNode* aHead = head, behind = head;
    while(k>1)
    {
        if(aHead == NULL)    return NULL;
        aHead = aHead->next;
        k--;
    }
    while(aHead->next != NULL)
    {
        behind = behind->next;
        aHead = aHead->next;
    }
    return behind;
}

1.4 判斷一個(gè)單鏈表中是否有環(huán)

如果一個(gè)鏈表中有環(huán)，也就是說用一個(gè)指針去遍歷膛锭，是永遠(yuǎn)走不到頭的粮坞。因此，我們可以用兩個(gè)指針去遍歷初狰，一個(gè)指針一次走兩步莫杈，一個(gè)指針一次走一步，如果有環(huán)奢入，兩個(gè)指針肯定會(huì)在環(huán)中相遇筝闹。時(shí)間復(fù)雜度為O（n）。

bool HasCycle(ListNode* head)
{
    ListNode* fast = head,* slow = head;
    while(fast != NULL && fast->next != NULL)
    {
        fast = fast->next->next;
        slow = slow->next;
        if(fast == slow)    return true;
    }
    return false;
}

1.5 判斷一個(gè)單鏈表中是否有環(huán)腥光，如果存在关顷，求進(jìn)入環(huán)中的第一個(gè)節(jié)點(diǎn)

這題不光要求出是否有環(huán)，而且還需要得到這個(gè)環(huán)開始的節(jié)點(diǎn)柴我。譬如下面這個(gè)解寝，起點(diǎn)就是n2扩然。

        n6-----------n5
        |              |
n1------n2----n3----n4|

我們?nèi)匀豢梢允褂脙蓚€(gè)指針fast和slow艘儒，fast走兩步，slow走一步夫偶，判斷是否有環(huán)界睁，當(dāng)有環(huán)重合之后，譬如上面在n5重合了兵拢，那么如何得到n2呢翻斟？
首先我們知道，fast每次比slow多走一步说铃，所以重合的時(shí)候访惜，fast移動(dòng)的距離是slot的兩倍，我們假設(shè)n1到n2距離為a腻扇，n2到n5距離為b债热，n5到n2距離為c，fast走動(dòng)距離為a+ b+c+b幼苛，而slow為 a+b窒篱，有方程a+b+c+b=2x(a+b)，可以知道a=c，所以我們只需要在重合之后墙杯，一個(gè)指針從n1，而另一個(gè)指針從n5，都每次走一步揍障，那么就可以在n2重合了啤月。

ListNode* DetectCycle(ListNode* head)
{
    ListNode *slow = head, *fast = head;
    while(fast != NULL && fast->next != NULL)
    {
        fast = fast->next->next;
        slow = slow->next;
        if(fast == slow)
        {
            ListNode* slow2 = head;
            while(slow2 != slow)
            {
                slow2 = slow2->next;
                slow = slow->next;
            }
            return slow2;
        }
    }
    return NULL;
}

1.6 合并兩個(gè)排好序的鏈表

利用附加頭結(jié)點(diǎn)簡(jiǎn)化操作

ListNode* MergeTowList(ListNode* head1, ListNode* head2)
{
    ListNode* dummy(0);
    ListNode* temp = &dummy;
    while(head1 != NULL && head2 != NULL)
    {
        int val1 = head1->value;
        int val2 = head2->value;
        if(val1 < val2)
        {
            temp->next = head1;
            temp = head1;
            head1 = head1->next;
        }
        else
        {
            temp->next = head2;
            temp = head2;
            head2 = head2->next;
        }
    }
    if(head1 != NULL)    temp->next = head1;
    else if(head2 != NULL)    temp->next = head2; 
    return dummy.next;
}

1.7 去除有序鏈表中的重復(fù)元素

ListNode *DeleteDuplicates(ListNode *head) {
    if (head == nullptr) return nullptr;
    for (ListNode *prev = head, *cur = head->next; cur; cur = prev->next) {
        if (prev->val == cur->val) {
            prev->next = cur->next;
            delete cur;
        } 
        else {
            prev = cur;
        }
    }
    return head;
}

1.8 判斷兩個(gè)單鏈表是否相交

如果兩個(gè)鏈表相交于某一節(jié)點(diǎn)，那么在這個(gè)相交節(jié)點(diǎn)之后的所有節(jié)點(diǎn)都是兩個(gè)鏈表所共有的嫉髓。也就是說低滩，如果兩個(gè)鏈表相交，那么最后一個(gè)節(jié)點(diǎn)肯定是共有的岩喷。先遍歷第一個(gè)鏈表恕沫，記住最后一個(gè)節(jié)點(diǎn)，然后遍歷第二個(gè)鏈表纱意，到最后一個(gè)節(jié)點(diǎn)時(shí)和第一個(gè)鏈表的最后一個(gè)節(jié)點(diǎn)做比較婶溯，如果相同，則相交偷霉，否則不相交迄委。時(shí)間復(fù)雜度為O(len1+len2)，因?yàn)橹恍枰粋€(gè)額外指針保存最后一個(gè)節(jié)點(diǎn)地址类少，空間復(fù)雜度為O(1)叙身。參考代碼如下：

bool IsIntersected(ListNode* head1, ListNode* head2)
{
    if(head1 == NULL || head2 == NULL)    return false;
    ListNode* tail1 = head1;
    while(tail1->next != NULL)    tail1 = tail1->next;
    ListNode* tail2 = head2;
    while(tail2->next != NULL)    tail2 = tail2->next;
    return tail1 == tail2;
}

1.9 求兩個(gè)單鏈表相交的第一個(gè)節(jié)點(diǎn)

對(duì)第一個(gè)鏈表遍歷，計(jì)算長(zhǎng)度len1硫狞，同時(shí)保存最后一個(gè)節(jié)點(diǎn)的地址信轿。對(duì)第二個(gè)鏈表遍歷，計(jì)算長(zhǎng)度len2残吩，同時(shí)檢查最后一個(gè)節(jié)點(diǎn)是否和第一個(gè)鏈表的最后一個(gè)節(jié)點(diǎn)相同财忽，若不相同，不相交泣侮，結(jié)束即彪。

兩個(gè)鏈表均從頭節(jié)點(diǎn)開始，假設(shè)len1大于len2活尊，那么將第一個(gè)鏈表先遍歷len1-len2個(gè)節(jié)點(diǎn)隶校，此時(shí)兩個(gè)鏈表當(dāng)前節(jié)點(diǎn)到第一個(gè)相交節(jié)點(diǎn)的距離就相等了，然后一起向后遍歷蛹锰，知道兩個(gè)節(jié)點(diǎn)的地址相同深胳。時(shí)間復(fù)雜度，O(len1+len2)宁仔。參考代碼如下：

ListNode* FindFirstCommonNode( ListNode *head1, ListNode *head2) {
    if(head1 == NULL && head2 == NULL)    return NULL;
    int len1=0,len2=0;
    ListNode* list1 = head1;
    ListNode* list2 = head2;
    while(list1 != NULL){
        list1 = list1->next;
        len1++;
    }
    while(list2 != NULL){
        list2 = list2->next;
        len2++;
    }
    
    int interval;
    ListNode* longList;
    ListNode* shortList;
    if(len1>=len2){
        interval = len1-len2;
        longList = head1;
        shortList = head2;
    }
    else{
        interval = len2-len1;
        longList = head2;
        shortList = head1;
    }
    
    for(int i=0;i<interval;i++)    longList = longList->next;
    
    while(longList != NULL && shortList != NULL && longList != shortList){
        longList = longList->next;
        shortList = shortList->next;
    }
    
    return longList;
}

2. 二叉樹

樹是一種比較重要的數(shù)據(jù)結(jié)構(gòu)稠屠，尤其是二叉樹峦睡。二叉樹是一種特殊的樹，在二叉樹中每個(gè)節(jié)點(diǎn)最多有兩個(gè)子節(jié)點(diǎn)权埠，一般稱為左子節(jié)點(diǎn)和右子節(jié)點(diǎn)（或左孩子和右孩子）榨了，并且二叉樹的子樹有左右之分，其次序不能任意顛倒攘蔽。二叉樹是遞歸定義的龙屉，因此，與二叉樹有關(guān)的題目基本都可以用遞歸思想解決满俗，當(dāng)然有些題目非遞歸解法也應(yīng)該掌握转捕，如非遞歸遍歷節(jié)點(diǎn)等等。

二叉樹節(jié)點(diǎn)定義如下：

struct BinaryTreeNode
{
    int value;
    BinaryTreeNode* left;
    BinaryTreeNode* right;
    BinaryTreeNode(int x) : value(x), left(NULL), right(NULL) {}
};

2.1 求二叉樹中的結(jié)點(diǎn)個(gè)數(shù)

遞歸解法：

• 如果二叉樹為空唆垃，節(jié)點(diǎn)個(gè)數(shù)為0
• 如果二叉樹不為空五芝，二叉樹節(jié)點(diǎn)個(gè)數(shù) = 左子樹節(jié)點(diǎn)個(gè)數(shù) + 右子樹節(jié)點(diǎn)個(gè)數(shù) + 1

int GetNodeNumber(BinaryTreeNode* root)
{
    if(root == NULL)    return 0;
    return GetNodeNumber(root->left) + GetNodeNumber(root->right) + 1;
}

2.2 求二叉樹的深度

遞歸解法：

• 如果二叉樹為空，二叉樹的深度為0
• 如果二叉樹不為空辕万，二叉樹的深度 = max(左子樹深度枢步， 右子樹深度) + 1

int GetDeepth(BinaryTreeNode* root)
{
    if(root == NULL)    return 0;
    int depthLeft = GetDeepth(root->left);
    int depthRight = GetDeepth(root->right);
    return depthLeft > depthRight ? (depthLeft + 1) : (depthRight + 1);
}

2.3 前序遍歷，中序遍歷渐尿，后序遍歷

前序遍歷遞歸解法：如果二叉樹為空醉途，空操作；如果二叉樹不為空砖茸，訪問根節(jié)點(diǎn)隘擎，前序遍歷左子樹，前序遍歷右子樹凉夯。中序遍歷遞歸解法：如果二叉樹為空货葬，空操作；如果二叉樹不為空恍涂，中序遍歷左子樹宝惰，訪問根節(jié)點(diǎn)，中序遍歷右子樹再沧。后序遍歷遞歸解法：如果二叉樹為空，空操作尊残；如果二叉樹不為空炒瘸，后序遍歷左子樹，后序遍歷右子樹寝衫，訪問根節(jié)點(diǎn)顷扩。

void preOrderTraverse(BinaryTreeNode* root)
{
    if(root == NULL)    return;
    visit(root);
    PreOrderTraverse(root->left); // 前序遍歷左子樹  
    PreOrderTraverse(root->right); // 前序遍歷右子樹
}

void InOrderTraverse(BinaryTreeNode* root)
{
    if(root == NULL)    return;
    InOrderTraverse(root->left); // 中序遍歷左子樹 
    visit(root); // 訪問根節(jié)點(diǎn) 
    InOrderTraverse(root->right); // 中序遍歷右子樹  
}

void PostOrderTraverse(BinaryTreeNode * root)  
{  
    if(root == NULL)    return;  
    PostOrderTraverse(root->left); // 后序遍歷左子樹  
    PostOrderTraverse(root->right); // 后序遍歷右子樹  
    Visit(root); // 訪問根節(jié)點(diǎn)  
} 

2.4 層次遍歷

相當(dāng)于廣度優(yōu)先搜索，使用隊(duì)列實(shí)現(xiàn)慰毅。隊(duì)列初始化隘截，將根節(jié)點(diǎn)壓入隊(duì)列。當(dāng)隊(duì)列不為空，進(jìn)行如下操作：彈出一個(gè)節(jié)點(diǎn)婶芭，訪問东臀，若左子節(jié)點(diǎn)或右子節(jié)點(diǎn)不為空，將其壓入隊(duì)列犀农。

void LevelTraverse(BinaryTreeNode* root)
{
    if(root == NULL) return ;
    queue<BinaryTreeNode*> que;
    que.push(root);
    while(!que.empty())
    {
        BinaryTreeNode* tempNode = que.front();
        que.pop();
        visit(tempNode);
        if(root->left != NULL)    que.push(tempNode->left);
        if(root->right != NULL)    que.push(tempNode->right);
    }
    return ;
}

2.5 求二叉樹第K層的節(jié)點(diǎn)個(gè)數(shù)

遞歸解法：

• 如果二叉樹為空或者k<1返回0
• 如果二叉樹不為空并且k==1惰赋，返回1
• 如果二叉樹不為空且k>1，返回左子樹中k-1層的節(jié)點(diǎn)個(gè)數(shù)與右子樹k-1層節(jié)點(diǎn)個(gè)數(shù)之和

int GetNodeNumKthLevel(BinaryTreeNode* root, int k)
{
    if(root == NULL || k<1)    return 0;
    if(k == 1)    return 1;
    int numLeft = GetNodeNumKthLevel(root->left, k-1);
    int numRight = GetNodeNumKthLevel(root->right,k-1);
    return numLeft + numRight;
}

2.6 求二叉樹中葉子節(jié)點(diǎn)的個(gè)數(shù)

遞歸解法：

• 如果二叉樹為空呵哨，返回0赁濒；
• 如果二叉樹不為空且左右子樹為空，返回1孟害；
• 如果二叉樹不為空拒炎，且左右子樹不同時(shí)為空，返回左子樹中葉子節(jié)點(diǎn)個(gè)數(shù)加上右子樹中葉子節(jié)點(diǎn)個(gè)數(shù)挨务。

int GetLeafNodeNum(BinaryTreeNode * root)  
{  
    if(root == NULL)  return 0;  
    if(root->left == NULL && root->right == NULL)  return 1;  
    int numLeft = GetLeafNodeNum(root->left); // 左子樹中葉節(jié)點(diǎn)的個(gè)數(shù)  
    int numRight = GetLeafNodeNum(root->right); // 右子樹中葉節(jié)點(diǎn)的個(gè)數(shù)  
    return (numLeft + numRight);  
}

2.7 判斷兩棵二叉樹是否結(jié)構(gòu)相同

不考慮數(shù)據(jù)內(nèi)容枝冀。結(jié)構(gòu)相同意味著對(duì)應(yīng)的左子樹和對(duì)應(yīng)的右子樹都結(jié)構(gòu)相同。遞歸解法如下：

• 如果兩棵二叉樹都為空耘子，返回真
• 如果兩棵二叉樹一棵為空果漾，另一棵不為空，返回假
• 如果兩棵二叉樹都不為空谷誓，如果對(duì)應(yīng)的左子樹和右子樹都同構(gòu)返回真绒障，其他返回假

bool StructureCmp(BinaryTreeNode * root1, BinaryTreeNode * root2)  
{  
    if(root1 == NULL && root2 == NULL) // 都為空，返回真  
        return true;  
    else if(root1 == NULL || root2 == NULL) // 只有一個(gè)為空捍歪，返回假  
        return false;  
    bool resultLeft = StructureCmp(root1->left, root2->left); // 比較對(duì)應(yīng)左子樹   
    bool resultRight = StructureCmp(root1->right, root2->right); // 比較對(duì)應(yīng)右子樹  
    return (resultLeft && resultRight);  
} 

2.8 判斷二叉樹是不是平衡二叉樹

平衡二叉樹：
遞歸解法：

• 如果二叉樹為空户辱，返回真
• 如果二叉樹不為空，如果左子樹和右子樹都是AVL樹并且左子樹和右子樹高度相差不大于1糙臼，返回真庐镐，其他返回假

bool IsAVL(BinaryTreeNode * root, int & height)  
{  
    if(root == NULL) // 空樹，返回真  
    {  
        height = 0;  
        return true;  
    }  
    int heightLeft;  
    bool resultLeft = IsAVL(root->left, heightLeft);  
    int heightRight;  
    bool resultRight = IsAVL(root->right, heightRight);  
    // 左子樹和右子樹都是AVL变逃，并且高度相差不大于1必逆，返回真  
    if(resultLeft && resultRight && abs(heightLeft - heightRight) <= 1) 
    {  
        height = max(heightLeft, heightRight) + 1;  
        return true;  
    }  
    else  
    {  
        height = max(heightLeft, heightRight) + 1;  
        return false;  
    }  
}

2.9 求二叉樹的鏡像

遞歸解法：

• 如果二叉樹為空，返回空
• 如果二叉樹不為空揽乱，求左子樹和右子樹的鏡像名眉，然后交換左子樹和右子樹

BinaryTreeNode* Mirror(BinaryTreeNode* root)
{
    if(root == NULL)    return NULL;
    BinaryTreeNode* mLeft = Mirror(root->left); // 求左子樹鏡像
    BinaryTreeNode* mRight = Mirror(root->right); // 求右子樹鏡像
    // 交換左子樹和右子樹
    root->left = mRight;
    root->right = mLeft;
    return root;
}

2.10 迭代的遍歷算法

//利用棧進(jìn)行遞歸前序遍歷
void PreorderTraversal(BinaryTreeNode* root)
{
    stack<const BinaryTreeNode*> s;
    if(root != NULL)    s.push(root);
    while(!s.empty())
    {
        const BinaryTreeNode* temp = s.top();
        s.pop();
        visit(temp);
        if(temp->right != NULL) s.push(temp->right);
        if(temp->left != NULL) s.push(temp->left);
    }
}

void InOrderTraversal(BinaryTreeNode* root)
{
    stack<const BinaryTreeNode*> s;
    const BinaryTreeNode* temp = root;
    while(!s.empty() || temp !=NULL)
    {
        if(temp != NULL){
            s.push(temp);
            temp = temp->left;
        }
        else{
            temp = s.top();
            s.pop();
            visit(temp);
            temp = temp->right;
        }
    }
}

void PostOrderTraversal(BinaryTreeNode* root)
{
    stack<const BinaryTreeNode*> s;
    const BinaryTreeNode* temp = root, * pre = NULL;
    do{
        while(temp != NULL){
            s.push(temp);
            temp = temp->left;
        }
        pre = NULL;
        while(!s.empty()){
            temp = s.top();
            s.pop();
            //如果該結(jié)點(diǎn)的右子節(jié)點(diǎn)不存在或已被訪問，就訪問它
            if(temp->right == pre){
                visit(temp);
                pre = temp;
            }
            else{
                s.push(temp);
                temp = temp->right;
                break;
            }
        }
    }while(!s.empty());
}

2.11 判斷是否存在一條從root到其中一個(gè)葉子節(jié)點(diǎn)的路徑的和等于給定的值

直接使用深度優(yōu)先遍歷求解

bool DFS(int target, int sum, BinaryTreeNode* root)
{
    if(root == NULL)    return false;
    sum += root->value;
    if(root->left == NULL && root->right == NULL)
    {
        if(sum == target)    return true;
        else return false;
    }
    bool leftPart = DFS(target,sum,root->left);
    bool rightPart = DFS(target,sum,root->right);
    return leftPart || rightPart;
}

bool hasPathSum(BinaryTreeNode* root,int sum)
{
    if(root == NULL)    return false;
    return DFS(sum,0,root);
}

3. 字符串操作與算法

3.1 字符串匹配算法

3.1.1 樸素的匹配算法

就是所謂的暴力匹配凰棉。假設(shè)文本T長(zhǎng)度為m损拢，模式串P長(zhǎng)度為n，算法從文本第1位從左向右開始與模式串P進(jìn)行匹配撒犀，無(wú)論是否匹配成功福压，模式串都后移1位開始繼續(xù)進(jìn)行重新匹配掏秩，總共進(jìn)行m-n+1次匹配。算法極其簡(jiǎn)單荆姆，因此效率極其有限蒙幻，時(shí)間復(fù)雜度為O(m*n)，故不常被用胞枕。

void NaiveMatch(const char* T,const char* P)
{
    int m = strlen(T);
    int n = strlen(P);
    for(int i=0;i<m-n;i++){
        int j;
        for(j=0;j<n;j++)
            if(T[i+j] != P[j])    break;
        if(j==n)    cout<<i<<" ";
    }
    cout<<endl;
}

3.1.2 Horspool算法

int* HorspoolTable(const char *P)  
{  
    int n = strlen(P);  
    int *ht = new int[256];  
    for (int i=0; i<256; i++)  
        ht[i] = n;  
    for (int i=0; i<n-1; i++)  
        ht[(int)P[i]] = n - i - 1;  
    return ht;  
}  
  
void Horspool(const char *T, const char *P)  
{  
    int m = strlen(T);  
    int n = strlen(P);  
    int *ht = HorspoolTable(P);  
  
    int i=0, k=n-1;  
    while (i<=m-n)  
    {  
        for (k=n-1; k>=0 && T[i+k]==P[k]; k--) ;  
  
        if (k==-1)  
            cout<<i<<" ";  
        i = i + ht[(int)T[i+n-1]];  
    }  
    cout<<endl;  
    delete []ht;  
}  

3.2 將字符串轉(zhuǎn)換為整數(shù)

需考慮各種條件杆煞，如空字符，正負(fù)號(hào)腐泻，非法輸入等問題决乎，還要考慮超出int范圍的問題。下面的代碼中派桩，若是非法輸入构诚，則輸出0，也沒考慮超出范圍的問題铆惑。若要考慮非法輸入范嘱，可設(shè)置一個(gè)全局變量。

int StrToInt(string s)
{
    int result = 0;
    //判斷是否為空字符串
    if(s.empty())    return result;
    int flag = 0;
    for(int i=0;i<s.size();i++){
        if(i == 0){
            //正負(fù)號(hào)判斷
            if(s[i] == '+')    flag = 1;
            else if(s[i] == '-')    flag = -1;
            else if(s[i] >= '0' && s[i] <= '9'){
                result = s[i] - '0';
                flag = 1;
            }
            else break;
        }
        else{
            if(s[i] >= '0' && s[i] <= '9')
                result = result*10 + (s[i] - '0');
            //非法輸入返回0
            else{
                result = 0;
                break;
            }
        }
    }
    return flag*result;
}

4. 排序算法總結(jié)

4.1 冒泡排序

基本思想：每次比較兩個(gè)相鄰的元素员魏，如果他們的順序錯(cuò)誤就把他們交換過來丑蛤。

時(shí)間復(fù)雜度：

• 最好的情況下，待排序記錄已經(jīng)有序撕阎，只需要一趟排序就可以完成受裹，所以冒泡排序的最好時(shí)間復(fù)雜度為 O(n)。
• 最壞的情況下虏束，待排序記錄反序棉饶，這時(shí)需要 n - 1 趟排序，每趟排序需要比較 n - i 次比較操作镇匀，這時(shí)比較和移動(dòng)的次數(shù)達(dá)到最大值照藻，所以冒泡排序的最壞時(shí)間復(fù)雜度為 O(n ^ 2)。
• 平均時(shí)間復(fù)雜度為 O(n ^ 2)汗侵。因?yàn)樗苿?dòng)的次數(shù)較多幸缕，其平均時(shí)間性能還不如直接插入排序。

void bubble_sort(int s[],int n)
{
    for (int i=0;i<n;i++)
    {
        for (int j=n-1;j>i;j--)
        {
            if (s[j-1]>s[j])
            {
                swap(s[j-1],s[j]);
            }
        }
    }
}

冒泡排序的優(yōu)化：在算法中增加一個(gè)標(biāo)志exchange晃择，用以標(biāo)識(shí)本趟冒泡結(jié)果是否發(fā)生了交換冀值；如果沒有發(fā)生交換則exchange=false，表示全部元素已經(jīng)排好宫屠，因而可以結(jié)束算法；如果exchange=true滑蚯，表示本趟有元素發(fā)生交換浪蹂，還需執(zhí)行下一趟排序抵栈。

void new_bubble_sort(int s[],int n)
{
    bool exchange;
    for (int i=0;i<n;i++)
    {
        exchange = false;
        for (int j=n-1;j>i;j--)
        {
            if (s[j-1]>s[j])
            {
                swap(s[j-1],s[j]);
                exchange =true;
            }
        }
        if(exchange == false)   return;
    }
}

4.2 插入排序

基本思想：每次將一個(gè)待排序元素按其大小插入到前面已經(jīng)排好的序列中的適當(dāng)位置，直至元素全部插入為止

時(shí)間復(fù)雜度分析： 直接插入排序算法主要進(jìn)行有兩個(gè)操作坤次，查找比較古劲，移動(dòng)記錄。這兩個(gè)操作均和記錄長(zhǎng)度n相關(guān)缰猴。其平均時(shí)間復(fù)雜度為O(n^2)产艾。這在排序算法里面算慢的，但是當(dāng)記錄較少時(shí)滑绒，它的效率還是可以不錯(cuò)的闷堡。

空間復(fù)雜度分析：直接插入排序只需要一個(gè)元素的輔助空間，用于元素的位置交換O(1)疑故。

直接插入排序是穩(wěn)定排序杠览。它在元素基本有序的情況下（接近最好情況），比較和移動(dòng)的次數(shù)都較少纵势，效率是很高的踱阿。

4.2.1 直接插入排序

void insert_sort(int s[],int n)
{
    for (int i=1;i<n;i++)
    {
        if (s[i]<s[i-1])
        {
            int temp = s[i], j=i-1;
            do 
            {
                s[j+1] = s[j];
                j--;
            } 
            while (j>=0 && temp<s[j]);
            s[j+1] = temp;
        }
    }
}

4.2.2 二分插入排序

利用二分查找，查找待插入元素應(yīng)插入前面有序序列的位置钦铁。

4.3 選擇排序

4.3 直接選擇排序

基本思想：每次（第i次）在后面待排序元素中選出排序碼最小的元素软舌，作為有序元素序列的第i個(gè)元素。待n-2趟作完牛曹，待排序元素只剩下1個(gè)佛点，就不用排序了。

時(shí)間復(fù)雜度分析：無(wú)論待排序記錄的初始狀態(tài)如何躏仇，在第i趟排序中選出最小關(guān)鍵字的記錄恋脚，需做n-i次比較，因此焰手，總的比較次數(shù)為：n*(n-1) /2=O(n^2)糟描，當(dāng)待排序記錄的初始狀態(tài)為正序時(shí)，移動(dòng)次數(shù)為 0书妻；當(dāng)初始狀態(tài)為反序時(shí)船响，每趟排序均要執(zhí)行交換操作，總的移動(dòng)次數(shù)取最大值3 *(n-1)躲履。所以见间，直接選擇排序的平均時(shí)間復(fù)雜度為O(n^2)。

非穩(wěn)定排序工猜。

void select_sort(int s[],int left,int right)
{
    for (int i=left;i<right;i++)
    {
        int min = i;
        for (int j=i+1;j<=right;j++)
        {
            if(s[j]<s[min]) min = j;
        }
        if(min != i)    swap(s[i],s[min]);
    }
}

4.3.2 堆排序

堆實(shí)際上是一棵完全二叉樹米诉，對(duì)于最大堆，其任何一非葉節(jié)點(diǎn)的關(guān)鍵字不小于其左右子節(jié)點(diǎn)的關(guān)鍵字篷帅。堆排序就是利用大最大堆堆頂記錄的是最大關(guān)鍵字這一特性史侣，使得每次從無(wú)序中選擇最大記錄變得簡(jiǎn)單拴泌。其基本思想為：

• 將初始待排序關(guān)鍵字序列(R1,R2....Rn)構(gòu)建成最大堆，此堆為初始的無(wú)序區(qū)惊橱；
• 將堆頂元素R[1]與最后一個(gè)元素R[n]交換蚪腐，此時(shí)得到新的無(wú)序區(qū)(R1,R2,......Rn-1)和新的有序區(qū)(Rn),且滿足R[1,2...n-1]<=R[n];
• 由于交換后新的堆頂R[1]可能違反堆的性質(zhì)，因此需要對(duì)當(dāng)前無(wú)序區(qū)(R1,R2,......Rn-1)調(diào)整為新堆税朴，然后再次將R[1]與無(wú)序區(qū)最后一個(gè)元素交換回季，得到新的無(wú)序區(qū)(R1,R2....Rn-2)和新的有序區(qū)(Rn-1,Rn)。不斷重復(fù)此過程直到有序區(qū)的元素個(gè)數(shù)為n-1正林，則整個(gè)排序過程完成泡一。

堆排序是采用的二叉堆進(jìn)行排序的，二叉堆就是一棵二叉樹卓囚，它需要遍歷的次數(shù)就是二叉樹的深度瘾杭，而根據(jù)完全二叉樹的定義，它的深度至少是lg(N+1)哪亿。最多是多少呢粥烁？由于二叉堆是完全二叉樹，因此蝇棉，它的深度最多也不會(huì)超過lg(2N)讨阻。因此，遍歷一趟的時(shí)間復(fù)雜度是O(N)篡殷，而遍歷次數(shù)介于lg(N+1)和lg(2N)之間钝吮；因此得出它的時(shí)間復(fù)雜度是O(N*lgN)。

4.4 快速排序

時(shí)間復(fù)雜度分析：

• 最壞情況：每次劃分選取的基準(zhǔn)都是當(dāng)前無(wú)序區(qū)中關(guān)鍵字最小(或最大)的記錄板辽，劃分的結(jié)果是基準(zhǔn)左邊的子區(qū)間為空(或右邊的子區(qū)間為空)奇瘦，而劃分所得的另一個(gè)非空的子區(qū)間中記錄數(shù)目，僅僅比劃分前的無(wú)序區(qū)中記錄個(gè)數(shù)減少一個(gè)劲弦。此時(shí)耳标，時(shí)間復(fù)雜度為 O(n ^ 2)。
• 最好情況：每次劃分所取的基準(zhǔn)都是當(dāng)前無(wú)序區(qū)的"中值"記錄邑跪，劃分的結(jié)果是基準(zhǔn)的左次坡、右兩個(gè)無(wú)序子區(qū)間的長(zhǎng)度大致相等』總的關(guān)鍵字比較次數(shù)：0(nlgn)砸琅。
• 盡管快速排序的最壞時(shí)間為 O(n ^ 2)，但就平均性能而言轴踱，它是基于關(guān)鍵字比較的內(nèi)部排序算法中速度最快者症脂，快速排序亦因此而得名。它的平均時(shí)間復(fù)雜度為 O(nlgn)。

空間復(fù)雜度分析：快速排序需要一個(gè)棧來實(shí)現(xiàn)遞歸摊腋。若每次劃分較為均勻（也就是對(duì)半分沸版，基準(zhǔn)值總是中值）嘁傀，則其遞歸樹的高度為O(lgn)兴蒸，故遞歸后需棧空間為O(lgn)细办。最壞情況下橙凳，遞歸樹的高度為O(n)，所需的椥ψ玻空間為O(n)岛啸。

int partition(int s[],int low,int high)
{
    int key = s[high];
    int piv = low;
    for (int i=low;i<high;i++)
    {
        if (s[i]<=key)
        {
            swap(s[piv],s[i]);
            piv++;
        }
    }
    swap(s[piv],s[high]);
    return piv;
}

void quick_sort(int s[],int left,int right)
{
    if (left<right)
    {
        int piv = partition(s,left,right);
        quick_sort(s,left,piv-1);
        quick_sort(s,piv+1,right);
    }
}

4.5 歸并排序

歸并排序是采用分治法的一個(gè)非常典型的應(yīng)用，它要做兩件事情：

• “分”, 就是將數(shù)組盡可能的分茴肥，一直分到原子級(jí)別坚踩；
• “并”，將原子級(jí)別的數(shù)兩兩合并排序瓤狐，最后產(chǎn)生結(jié)果瞬铸。

至于二個(gè)有序數(shù)列合并，只要比較二個(gè)數(shù)列的第一個(gè)數(shù)础锐，誰(shuí)小就先取誰(shuí)安放到臨時(shí)隊(duì)列中嗓节，取了后將對(duì)應(yīng)數(shù)列中這個(gè)數(shù)刪除，直到一個(gè)數(shù)列為空皆警，再將另一個(gè)數(shù)列的數(shù)據(jù)依次取出即可拦宣。

void merge(int* array, int tempArray, int left, int middle, int right)
{
    for(int i=left;i<=right;i++)    tempArray[i] = array[i];
    int s1 = left, s2 = mid +1, temp = left;
    while(s1 <=mid && s2 <= right)
    {
        if(tempArray[s1] <= tempArray[s2])
            array[temp++] = tempArray[s1++];
        else    array[temp++] = tempArray[s2++];
    }
    while(s1 <= mid) array[temp++] = tempArray[s1++];
    while(s2 <= right) array[temp] = tempArray[s2++];
}

void merge_sort(int* array, int* tempArray, int left, int right)
{
    if(left >= right)    return ;
    int mid = left + (right - left)/2;
    int tempArray = new int[right-left+1];
    merge_sort(array,tempArray,left,mid);
    merge_sort(array,tempArray,mid+1,right);
    merge(array,tempArray,left,mid,right);
}

5. 查找算法總結(jié)

5.1 順序查找

設(shè)想有一個(gè)1M的數(shù)據(jù)，我們?nèi)绾卧诶锩嬲业轿覀兿胍哪莻€(gè)數(shù)據(jù)信姓。此時(shí)數(shù)據(jù)本身沒有特征鸵隧，所以我們需要的那個(gè)數(shù)據(jù)可能出現(xiàn)在數(shù)組的各個(gè)位置，可能在數(shù)據(jù)的開頭位置意推，也可能在數(shù)據(jù)的結(jié)束位置豆瘫。這種性質(zhì)要求我們必須對(duì)數(shù)據(jù)進(jìn)行遍歷之后才能獲取到對(duì)應(yīng)的數(shù)據(jù)。

int find(int array[], int len, int val)
{
    if(array == NULL && length == 0)    return -1;
    for(int i=0;i<len;i++){
        if(val == array[i])
            return i;
    }
    return -1;
}

分析：由于我們不清楚這個(gè)數(shù)據(jù)判斷究竟需要多少次左痢。但是靡羡，我們知道，這樣一個(gè)數(shù)據(jù)查找最少需要1次俊性，那么最多需要n次略步，平均下來可以看成是（1+n）/2，差不多是n的一半定页。我們把這種比較次數(shù)和n成正比的算法復(fù)雜度記為o（n）趟薄。

5.2 二分查找

如果數(shù)據(jù)排列地非常整齊，那結(jié)果會(huì)是什么樣的呢典徊？就像在生活中杭煎，如果平時(shí)不注意收拾整齊恩够，那么找東西的時(shí)候非常麻煩，效率很低羡铲；但是一旦東西放的位置固定下來蜂桶，所有東西都?xì)w類放好，那么結(jié)果就不一樣了也切，我們就會(huì)形成思維定勢(shì)扑媚，這樣查找東西的效率就會(huì)非常高。那么雷恃，對(duì)一個(gè)有序的數(shù)組疆股，我們應(yīng)該怎么查找呢？二分法就是最好的方法倒槐。

int BinaryFind(int array[], int len, int val)
{
    if(array == NULL && length == 0)    return -1;
    int start = 0, end = len-1, middle=0;
    while(start<=end){
        middle = start + (end - start)/2;
        if(val == array[middle])    return middle;
        else if(val > array[middle])    start = middle+1;
        else end = middle-1;
    }
    return -1;
}

分析：上面我們說到普通的數(shù)據(jù)查找算法復(fù)雜度是o（n）旬痹。那么我們可以用上面一樣的方法判斷一下算法復(fù)雜度。這種方法最少是1次讨越，那么最多需要多少次呢两残？我們發(fā)現(xiàn)最多需要log（n+1）/log（2）即可。

5.3 二叉搜索樹

二叉搜索樹是二分查找的二叉樹實(shí)現(xiàn)谎痢，二叉搜索樹每個(gè)結(jié)點(diǎn)都有作為搜索依據(jù)的關(guān)鍵碼磕昼，所有結(jié)點(diǎn)的關(guān)鍵碼互不相同；左子樹（若存在）上的所有結(jié)點(diǎn)的關(guān)鍵碼都小于根結(jié)點(diǎn)的關(guān)鍵碼节猿；右子樹（若存在）上的所有結(jié)點(diǎn)的關(guān)鍵碼都大于根結(jié)點(diǎn)的關(guān)鍵碼票从；左子樹和右子樹也是二叉搜索樹。

如果對(duì)一棵二叉搜索樹進(jìn)行中序遍歷滨嘱，可以按從小到大的順序峰鄙，將各結(jié)點(diǎn)關(guān)鍵碼排列起來，所以也稱為二叉排序樹太雨。

平衡二叉樹是一種高度平衡的二叉搜索樹吟榴，是為了提高二叉搜索樹的效率，減少樹的平均搜索長(zhǎng)度囊扳。其具有以下性質(zhì)：其左右子樹都是平衡二叉樹吩翻，且左子樹和右子樹的高度之差的絕對(duì)值不超過1。如過它有n個(gè)結(jié)點(diǎn)锥咸，其高度可保持在O(log2n)狭瞎。

typedef struct _NODE
{
    int data;
    struct _NODE* left;
    struct _NODE* right;
}NODE;

const NODE* find_data(const NODE* pNode, int data){
    if(NULL == pNode)
        return NULL;

    if(data == pNode->data)
        return pNode;
    else if(data < pNode->data)
        return find_data(pNode->left, data);
    else
        return find_data(pNode->right, data);        
}

5.4 Hash表

typedef struct _LINK_NODE
{
    int data;
    struct _LINK_NODE* next;
}LINK_NODE;

LINK_NODE* hash_find(LINK_NODE* array[], int mod, int data)
{
    int index = data % mod;
    if(NULL == array[index])
        return NULL;

    LINK_NODE* pLinkNode = array[index];
    while(pLinkNode){
        if(data == pLinkNode->data)
            return pLinkNode;
        pLinkNode = pLinkNode->next;
    }

    return pLinkNode;
}

分析：hash表因?yàn)椴恍枰判颍贿M(jìn)行簡(jiǎn)單的歸類搏予，在數(shù)據(jù)查找的時(shí)候特別方便熊锭。查找時(shí)間的大小取決于mod的大小。mod越小，那么hash查找就越接近于普通查找碗殷；那么hash越大呢精绎，那么hash一次查找成功的概率就大大增加。

6. 二分查找的變種

6.1 給定一個(gè)有序（非降序）數(shù)組A锌妻，可含有重復(fù)元素代乃，求最小的i使得A[i]等于target，不存在則返回-1

此題也就是求target在數(shù)組中第一次出現(xiàn)的位置从祝。這里可能會(huì)有人想先直接用原始的二分查找襟己，如果不存在直接返回-1，如果存在牍陌，然后再順序找到這個(gè)等于target值區(qū)間的最左位置，這樣的話员咽，最壞情況下的復(fù)雜度就是O（n）了毒涧，沒有完全發(fā)揮出二分查找的優(yōu)勢(shì)。這里的解法具體過程請(qǐng)參考實(shí)現(xiàn)代碼與注釋贝室。

int searchFirstPos(int A[], int n, int target)  
{  
    if(n <= 0) return -1;  
    int low = 0, high = n-1;  
    while(low < high)  
    {  
        int mid = low+((high-low)>>1);  
        if(A[mid] < target)  
            low = mid+1;  
        else // A[mid] >= target  
            high = mid;  
    }  
    /*  
    循環(huán)過程中契讲，當(dāng)low大于0時(shí)，A[low-1]是小于target的滑频，因?yàn)锳[mid] < target時(shí)捡偏， 
    low=mid+1；當(dāng)high小于n-1時(shí)峡迷，A[high]是大于等于target的银伟，因?yàn)锳[mid] >= target時(shí)， 
    high = mid绘搞；循環(huán)結(jié)束時(shí)彤避，low 等于 high，所以夯辖，如果A[low](A[high])等于target琉预， 
    那么low(high)就是target出現(xiàn)的最小位置，否則target在數(shù)組中不存在蒿褂。 
    */  
    if(A[low] != target)  
        return -1;  
    else  
        return low;  
}  

6.2 給定一個(gè)有序（非降序）數(shù)組A圆米，可含有重復(fù)元素，求最大的i使得A[i]等于target啄栓，不存在則返回-1

int searchLastPos(int A[], int n, int target)  
{     
    if(n <= 0) return -1;  
    int low = 0, high = n-1;  
    while(low < high)  
    {  
        /* 
        這里中間位置的計(jì)算就不能用low+((high-low)>>1)了娄帖，因?yàn)楫?dāng)low+1等于high 
        且A[low] <= target時(shí)，會(huì)死循環(huán)谴供；所以這里要使用low+((high-low+1)>>1)块茁， 
        這樣能夠保證循環(huán)會(huì)正常結(jié)束。 
        */  
        int mid = low+((high-low+1)>>1);  
        if(A[mid] > target)  
            high = mid-1;  
        else // A[mid] <= target  
            low = mid;  
    }  
    /*  
    循環(huán)過程中，當(dāng)high小于n-1時(shí)数焊，A[high+1]是大于target的永淌，因?yàn)锳[mid] > target時(shí)， 
    high=mid-1佩耳；當(dāng)low大于0時(shí)遂蛀，A[low]是小于等于target的，因?yàn)锳[mid] <= target時(shí)干厚， 
    low = mid李滴；循環(huán)結(jié)束時(shí)，low 等于 high蛮瞄，所以所坯，如果A[high](A[low])等于target， 
    那么high(low)就是target出現(xiàn)的最大位置挂捅，否則target在數(shù)組中不存在芹助。 
    */  
    if(A[high] != target)  
        return -1;  
    else  
        return high;  
}

6.3 給定一個(gè)有序（非降序）數(shù)組A，可含有重復(fù)元素闲先，求target在數(shù)組中出現(xiàn)的次數(shù)

求出第一次出現(xiàn)位置和最后一次出現(xiàn)位置状土。由于前面都已實(shí)現(xiàn)，這里不多解釋伺糠。

int count(int A[], int n, int target)  
{  
    int firstPos = searchFirstPos(A, n, target); // 第一次出現(xiàn)位置  
    if(firstPos == -1)  
        return 0;  
    int lastPos = searchLastPos(A, n, target);  // 最后一次出現(xiàn)位置  
    return lastPos-firstPos+1;  // 出現(xiàn)次數(shù)  
}

7. 數(shù)學(xué)相關(guān)的算法

7.1 計(jì)算最大公約數(shù)

輾轉(zhuǎn)相除法
例1 .求兩個(gè)正數(shù)8251和6105的最大公因數(shù).
（分析：輾轉(zhuǎn)相除→余數(shù)為零→得到結(jié)果）
8251＝6105×1＋2146
顯然8251與6105的最大公因數(shù)也必是2146的因數(shù),同樣6105與2146的公因數(shù)也必是8251的因數(shù),所以8251與6105的最大公因數(shù)也是6105與2146的最大公因數(shù).
6105＝2146×2＋1813
2146＝1813×1＋333
1813＝333×5＋148
333＝148×2＋37
148＝37×4＋0
則37為8251與6105的最大公因數(shù).

利用輾轉(zhuǎn)相除法求最大公因數(shù)的步驟如下：
第一步：用較大的數(shù)m除以較小的數(shù)n得到一個(gè)商q0和一個(gè)余數(shù)r0蒙谓；
第二步：若r0＝0,則n為m,n的最大公因數(shù)；若r0≠0,則用除數(shù)n除以余數(shù)r0得到一個(gè)商q1和一個(gè)余數(shù)r1训桶；
第三步：若r1＝0,則r1為m,n的最大公因數(shù)累驮；若r1≠0,則用除數(shù)r0除以余數(shù)r1得到一個(gè)商q2和一個(gè)余數(shù)r2；
……
依次計(jì)算直至rn＝0,此時(shí)所得到的rn－1即為所求的最大公因數(shù).

//遞歸版本
int gcd(int a,int b) 
{ 
    int g; 
    if(b==0) 
        g=a; 
    else 
        g=gcd(b,a%b); 
    return g; 
}
//迭代版本
int gcd(int a, int b)
{
    int c;
    if(a<b) swap(a,b);
    while(b != 0){
        c = a%b;
        a = b;
        b = c;
    }
    return a;
}