(d) 把長(zhǎng)度為2的子數(shù)組合并妒穴、排序，并統(tǒng)計(jì)逆序?qū)Γ?/p>

在上圖（a）和（b）中摊崭，我們先把數(shù)組分解成兩個(gè)長(zhǎng)度為2的子數(shù)組，再把這兩個(gè)子數(shù)組分別拆成兩個(gè)長(zhǎng)度為1的子數(shù)組杰赛。接下來一邊合并相鄰的子數(shù)組呢簸，一邊統(tǒng)計(jì)逆序?qū)Φ臄?shù)目。在第一對(duì)長(zhǎng)度為1的子數(shù)組{7}乏屯、{5}中7大于5根时，因此（7,5）組成一個(gè)逆序?qū)ΑＭ瑯釉诘诙?duì)長(zhǎng)度為1的子數(shù)組{6}辰晕、{4}中也有逆序?qū)Γ?,4）蛤迎。由于我們已經(jīng)統(tǒng)計(jì)了這兩對(duì)子數(shù)組內(nèi)部的逆序?qū)Γ虼诵枰堰@兩對(duì)子數(shù)組 排序 如上圖（c）所示含友， 以免在以后的統(tǒng)計(jì)過程中再重復(fù)統(tǒng)計(jì)替裆。

接下來我們統(tǒng)計(jì)兩個(gè)長(zhǎng)度為2的子數(shù)組子數(shù)組之間的逆序?qū)Α：喜⒆訑?shù)組并統(tǒng)計(jì)逆序?qū)Φ倪^程如下圖如下圖所示窘问。

我們先用兩個(gè)指針分別指向兩個(gè)子數(shù)組的末尾辆童，并每次比較兩個(gè)指針指向的數(shù)字。如果第一個(gè)子數(shù)組中的數(shù)字大于第二個(gè)數(shù)組中的數(shù)字惠赫，則構(gòu)成逆序?qū)Π鸭⑶夷嫘驅(qū)Φ臄?shù)目等于第二個(gè)子數(shù)組中剩余數(shù)字的個(gè)數(shù)，如下圖（a）和（c）所示儿咱。如果第一個(gè)數(shù)組的數(shù)字小于或等于第二個(gè)數(shù)組中的數(shù)字庭砍，則不構(gòu)成逆序?qū)Τ【В鐖Db所示。每一次比較的時(shí)候怠缸，我們都把較大的數(shù)字從后面往前復(fù)制到一個(gè)輔助數(shù)組中诗轻，確保 輔助數(shù)組（記為copy） 中的數(shù)字是遞增排序的。在把較大的數(shù)字復(fù)制到輔助數(shù)組之后凯旭，把對(duì)應(yīng)的指針向前移動(dòng)一位概耻，接下來進(jìn)行下一輪比較。

過程：先把數(shù)組分割成子數(shù)組罐呼，先統(tǒng)計(jì)出子數(shù)組內(nèi)部的逆序?qū)Φ臄?shù)目鞠柄，然后再統(tǒng)計(jì)出兩個(gè)相鄰子數(shù)組之間的逆序?qū)Φ臄?shù)目。在統(tǒng)計(jì)逆序?qū)Φ倪^程中嫉柴，還需要對(duì)數(shù)組進(jìn)行排序厌杜。如果對(duì)排序算法很熟悉，我們不難發(fā)現(xiàn)這個(gè)過程實(shí)際上就是歸并排序计螺。

class Solution {
public:
    int InversePairs(vector<int> data) {
         int length=data.size();
        if(length<=0)
            return 0;
       //vector<int> copy=new vector<int>[length];
       vector<int> copy;
       for(int i=0;i<length;i++)
           copy.push_back(data[i]);
       long long count=InversePairsCore(data,copy,0,length-1);
       //delete[]copy;
       return count%1000000007;
    }
    long long InversePairsCore(vector<int> &data,vector<int> &copy,int start,int end)
    {
       if(start==end)
          {
            copy[start]=data[start];
            return 0;
          }
       int length=(end-start)/2;
       long long left=InversePairsCore(copy,data,start,start+length);
       long long right=InversePairsCore(copy,data,start+length+1,end); 
        
       int i=start+length;
       int j=end;
       int indexcopy=end;
       long long count=0;
       while(i>=start&&j>=start+length+1)
          {
             if(data[i]>data[j])
                {
                  copy[indexcopy--]=data[i--];
                  count=count+j-start-length;          //count=count+j-(start+length+1)+1;
                }
             else
                {
                  copy[indexcopy--]=data[j--];
                }          
          }
       for(;i>=start;i--)
           copy[indexcopy--]=data[i];
       for(;j>=start+length+1;j--)
           copy[indexcopy--]=data[j];       
       return left+right+count;
    }
};

36.兩個(gè)鏈表的第一個(gè)公共結(jié)點(diǎn)

• 題目：輸入兩個(gè)鏈表夯尽，找出它們的第一個(gè)公共結(jié)點(diǎn)。
• 思路：兩個(gè)單鏈表如果存在第一個(gè)公共結(jié)點(diǎn)登馒，則后續(xù)結(jié)點(diǎn)一定都公共匙握，因?yàn)榻Y(jié)點(diǎn)里包含next指針，如果第一個(gè)公共結(jié)點(diǎn)相同陈轿，則next必然相同圈纺，所以第一個(gè)公共結(jié)點(diǎn)后鏈表合并。

找出2個(gè)鏈表的長(zhǎng)度麦射，然后讓長(zhǎng)的先走兩個(gè)鏈表的長(zhǎng)度差蛾娶，然后再一起走
（因?yàn)?個(gè)鏈表用公共的尾部）

class Solution {
public:
    ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) {
        int len1 = findListLenth(pHead1);
        int len2 = findListLenth(pHead2);
        if(len1 > len2){
            pHead1 = walkStep(pHead1,len1 - len2);
        }else{
            pHead2 = walkStep(pHead2,len2 - len1);
        }
        while(pHead1 != NULL){
            if(pHead1 == pHead2) return pHead1;
            pHead1 = pHead1->next;
            pHead2 = pHead2->next;
        }
        return NULL;
    }
     
    int findListLenth(ListNode *pHead1){
        if(pHead1 == NULL) return 0;
        int sum = 1;
        while(pHead1 = pHead1->next) sum++;
        return sum;
    }
     
    ListNode* walkStep(ListNode *pHead1, int step){
        while(step--){
            pHead1 = pHead1->next;
        }
        return pHead1;
    }
};

37.數(shù)字在排序數(shù)組中出現(xiàn)的次數(shù)

• 題目：統(tǒng)計(jì)一個(gè)數(shù)字在排序數(shù)組中出現(xiàn)的次數(shù)。
  例如輸入排序數(shù)組{1,2,3,3,3,3,4,5}和數(shù)字3潜秋，由于3在數(shù)組中出現(xiàn)了4才蛔琅，因此輸出4。
• 思路：使用二分法找到排序數(shù)組中所求數(shù)字的第一個(gè)和最后一個(gè)位置峻呛，即可知道所求數(shù)字的個(gè)數(shù)罗售。

因?yàn)閐ata中都是整數(shù)，所以可以稍微變一下杀饵，不是搜索k的兩個(gè)位置莽囤，而是搜索k-0.5和k+0.5
這兩個(gè)數(shù)應(yīng)該插入的位置，然后相減即可切距。

class Solution {
public:
    int GetNumberOfK(vector<int> data ,int k) {
        return biSearch(data, k+0.5) - biSearch(data, k-0.5) ;
    }
private:
    int biSearch(const vector<int> & data, double num){
        int s = 0, e = data.size()-1;     
        while(s <= e){
            int mid = (e - s)/2 + s;
            if(data[mid] < num)
                s = mid + 1;
            else if(data[mid] > num)
                e = mid - 1;
        }
        return s;
    }
};

38.二叉樹的深度

• 題目：輸入一棵二叉樹朽缎，求該樹的深度。從根結(jié)點(diǎn)到葉結(jié)點(diǎn)依次經(jīng)過的結(jié)點(diǎn)（含根、葉結(jié)點(diǎn)）形成樹的一條路徑话肖，最長(zhǎng)路徑的長(zhǎng)度為樹的深度北秽。
• 思路：遞歸判斷當(dāng)前是否為深度最大值（遞歸NB）

class Solution {
public:
    int TreeDepth(TreeNode* pRoot)
    {
    if(!pRoot) return 0 ;
            return max(1+TreeDepth(pRoot->left), 1+TreeDepth(pRoot->right));
    }
};

39.平衡二叉樹

• 題目：輸入一棵二叉樹，判斷該二叉樹是否是平衡二叉樹最筒。
• 知識(shí)點(diǎn)：平衡二叉樹（Balanced Binary Tree）具有以下性質(zhì)：它是一棵空樹或它的左右兩個(gè)子樹的高度差的絕對(duì)值不超過1贺氓，并且左右兩個(gè)子樹都是一棵平衡二叉樹。
• 思路：同上題思路床蜘，依然可以使用遞歸判斷辙培，加上子樹深度差小于1這個(gè)條件即可。
  這種做法有很明顯的問題邢锯，在判斷上層結(jié)點(diǎn)的時(shí)候扬蕊，會(huì)多次重復(fù)遍歷下層結(jié)點(diǎn)，增加了不必要的開銷丹擎。如果改為從下往上遍歷尾抑，如果子樹是平衡二叉樹，則返回子樹的高度蒂培；如果發(fā)現(xiàn)子樹不是平衡二叉樹再愈，則直接停止遍歷，這樣至多只對(duì)每個(gè)結(jié)點(diǎn)訪問一次护戳。

class Solution {
public:
bool IsBalanced(TreeNode *root, int & dep){
        if(root == NULL){
            return true;
        }
        int left = 0;
        int right = 0;
        if(IsBalanced(root->left,left) && IsBalanced(root->right, right)){
            int dif = left - right;
            if(dif<-1 || dif >1)
                return false;
            dep = (left > right ? left : right) + 1;
            return true;
        }
        return false;
    }
    bool IsBalanced_Solution(TreeNode* pRoot) {
        int dep = 0;
        return IsBalanced(pRoot, dep);
    }
};

40.數(shù)組中只出現(xiàn)一次的數(shù)字

• 題目：一個(gè)整型數(shù)組里除了兩個(gè)數(shù)字之外翎冲，其他的數(shù)字都出現(xiàn)了兩次。請(qǐng)寫程序找出這兩個(gè)只出現(xiàn)一次的數(shù)字媳荒。
• 思路：

此題考察的是異或運(yùn)算的特點(diǎn)：即兩個(gè)相同的數(shù)異或結(jié)果為0府适。
此題用了兩次異或運(yùn)算特點(diǎn)：
（1）第一次使用異或運(yùn)算，得到了兩個(gè)只出現(xiàn)一次的數(shù)相異或的結(jié)果肺樟。
（2）因?yàn)閮蓚€(gè)只出現(xiàn)一次的數(shù)肯定不同，即他們的異或結(jié)果一定不為0逻淌，一定有一個(gè)位上有1么伯。另外一個(gè)此位上沒有1，我們可以根據(jù)此位上是否有1卡儒，將整個(gè)數(shù)組重新劃分成兩部分田柔，一部分此位上一定有1，另一部分此位上一定沒有1骨望，然后分別對(duì)每部分求異或硬爆，因?yàn)閯澐趾蟮膬刹糠钟羞@樣的特點(diǎn)：其他數(shù)都出現(xiàn)兩次，只有一個(gè)數(shù)只出現(xiàn)一次擎鸠。因此缀磕，我們又可以運(yùn)用異或運(yùn)算，分別得到兩部分只出現(xiàn)一次的數(shù)。

異或：

class Solution {
public:
    void FindNumsAppearOnce(vector<int> data,int* num1,int *num2) {
        int diff=accumulate(data.begin(),data.end(),0,bit_xor<int>());
        diff&=-diff;  //即找到最右邊1-bit
        *num1=0;*num2=0;
        for (auto c:data) {
            if ((c&diff)==0) *num1^=c;
            else *num2^=c;
        }
    }
};

哈希表：

class Solution {
public:
   void FindNumsAppearOnce(vector<int> data, int* num1, int *num2) {
    unordered_map<int, int> map;
    for (int i = 0; i < data.size(); i++)
        map[data[i]]++;
    vector<int>v;
    for (int i = 0; i < data.size(); i++)
        if (map[data[i]]== 1)
            v.push_back(data[i]);
    *num1 = v[0]; *num2 = v[1];
    }
};