本文由玉剛說(shuō)寫作平臺(tái)提供寫作贊助，版權(quán)歸玉剛說(shuō)所有。
原作者：Jiantao
版權(quán)聲明：未經(jīng)玉剛說(shuō)許可，不得以任何形式轉(zhuǎn)載。

數(shù)據(jù)結(jié)構(gòu)和算法有多重要？

我想有追求的程序員都不會(huì)放過(guò)它的。 打個(gè)比方，在金庸的武俠世界里，數(shù)據(jù)結(jié)構(gòu)和算法它就像一門上乘的內(nèi)功心法，一旦掌握了它，各種武功信手拈來(lái)，毫無(wú)壓力（張無(wú)忌就是一個(gè)典型的例子）；對(duì)于程序員來(lái)說(shuō)，它能決定你在技術(shù)這條道路上能走多遠(yuǎn)近范。

本文主要涉及數(shù)組斥杜、字符串缰儿、List這幾個(gè)數(shù)據(jù)結(jié)構(gòu)瞪浸，然后通過(guò)解答和分析幾道常見的面試題，從中分享一些我的學(xué)習(xí)心得和解題套路，希望對(duì)你有幫助丐巫。

題目1：翻轉(zhuǎn)句子

題目： 給定一個(gè)英文句子，每個(gè)單詞之間都是由一個(gè)或多個(gè)空格隔開，請(qǐng)翻轉(zhuǎn)句子中的單詞順序（包括空格的順序）赡茸，但單詞內(nèi)字符的順序保持不變辙纬。例如輸入"www google com "昂儒，則應(yīng)輸出" com google www"沟使。

如果你經(jīng)常關(guān)注算法相關(guān)文章，這道題應(yīng)該會(huì)比較熟悉拾酝，各種博客和書籍上都有出現(xiàn)燕少，不熟悉也沒(méi)關(guān)系，現(xiàn)在我們就一起來(lái)嘗試解答下蒿囤。這里要注意題意和網(wǎng)上流傳的題目有個(gè)不同點(diǎn)：網(wǎng)上基本都是單詞間有且只有一個(gè)空格客们。而此題需要考慮一個(gè)或多個(gè)空格的情況。

解題思路

試想一下材诽，如果將整個(gè)字符串翻轉(zhuǎn)底挫，結(jié)果是句子是反轉(zhuǎn)了，但單詞內(nèi)的字符順序也翻轉(zhuǎn)了脸侥。如果要保證單詞內(nèi)順序不變建邓，只需要再將每個(gè)單詞翻轉(zhuǎn)一下就滿足要求了。

由于題中“www google com ”字符串較長(zhǎng)睁枕，我就以" hello world"為例分析下這個(gè)過(guò)程官边，請(qǐng)看下圖。

yugang-v1-0-solution.png

注：（1）字符串" hello world"初始狀態(tài)，注意首字符是空格跳仿。 （2）將" hello world"整個(gè)句子翻轉(zhuǎn)后的樣子诡渴。可以看出不僅翻轉(zhuǎn)了句子中單詞的順序(包括空格)塔嬉，連單詞內(nèi)的字符順序也翻轉(zhuǎn)了玩徊。(3) 定義兩個(gè)指針p1租悄、p2都指向句子的首字符。 （4）首字符d恩袱，不是空格泣棋，此時(shí)p1指針不動(dòng)，p2指針向右移動(dòng)1位畔塔，指向字符 l潭辈。（移動(dòng)p2指針目的：檢查單詞的結(jié)束位置。） （5）由于第二個(gè)字符為 l 澈吨，也不是空格把敢，p2繼續(xù)向右移動(dòng)1位。（6）多次移動(dòng)后谅辣，p2指針在第一個(gè)空格處停下來(lái)修赞，此時(shí)就能得知p2-1為該單詞的結(jié)束位置。（7）反轉(zhuǎn)兩個(gè)指針（p1桑阶、p2-1）中間的字符串柏副。（8）交換后，重置兩個(gè)指針位置p1=p2++蚣录。以此類推割择，繼續(xù)尋找下一個(gè)單詞并翻轉(zhuǎn)，直到指針移動(dòng)到句子末尾就結(jié)束循環(huán)萎河。

此思路的關(guān)鍵是：1. 實(shí)現(xiàn)一個(gè)函數(shù)/方法荔泳，翻轉(zhuǎn)字符串中的一段。 2. 判斷并獲取句子中的單詞虐杯，注意空格玛歌。

測(cè)試用例

• 功能測(cè)試：多個(gè)單詞、1個(gè)單詞厦幅、單詞間只有一個(gè)空格沾鳄、單詞間有多個(gè)空格。
• 特殊輸入測(cè)試：空字符确憨、字符串中只有空格、null對(duì)象（指針）瓤的。

編碼實(shí)現(xiàn)

• Java代碼

/**
 * @param chars 原字符串
 * @param start 大于等于0
 * @param end   小于 length
 * @return
 */
private char[] v1_0_reverse(char[] chars, int start, int end) {

    // str 判斷null休弃， 索引有效值判斷
    if (chars == null || start < 0 || end >= chars.length || start >= end) {
        return chars;
    }

    while (start < end) {
        // 收尾字符互換，直到替換完成圈膏。
        char temp = chars[start];
        chars[start] = chars[end];
        chars[end] = temp;
        start++;
        end--;
    }
    return chars;
}

private String v1_0_solution(String sentence) {
    if (sentence == null || sentence.isEmpty()) {
        return sentence;
    }

    int length = sentence.length();
    // 第一步翻轉(zhuǎn)所有字符
    char[] chars = v1_0_reverse(sentence.toCharArray(), 0, length - 1);
    System.out.println(new String(chars));

    // 第二步翻轉(zhuǎn)每個(gè)單詞（重點(diǎn)：怎么找到單詞）
    int start = 0, end = 0;
    while (start < length) {
        if (chars[start] == ' ') {
            // 遇到空格就向右邊繼續(xù)查找
            start++;
            end++;
        } else if (end == length || chars[end] == ' ') {
            // 遇到空格或者已經(jīng)到了字符串末尾塔猾，此時(shí)翻轉(zhuǎn)找到的單詞內(nèi)部字符，這里需要注意end-1
            chars = v1_0_reverse(chars, start, end - 1);
            System.out.println(new String(chars));
            // 重新制定檢查索引start
            start = end++;
        } else {
            // end加1稽坤，為了檢查單詞是否結(jié)束
            end++;
        }
    }
    return new String(chars);
}

• C++ 代碼實(shí)現(xiàn)

// 反轉(zhuǎn)字符串
void Reverse(char *pBegin, char *pEnd)
{
    if(pBegin == NULL || pEnd == NULL)
        return;

    while(pBegin < pEnd)
    {
        char temp = *pBegin;
        *pBegin = *pEnd;
        *pEnd = temp;

        pBegin ++, pEnd --;
    }
}

// 翻轉(zhuǎn)句子中單詞順序丈甸，但保證單詞內(nèi)字符順序不變糯俗。
char* ReverseSentence(char *pData)
{
    if(pData == NULL)
        return NULL;

    char *pBegin = pData;

    char *pEnd = pData;
    while(*pEnd != '\0')
        pEnd ++;
    pEnd--;

    // 翻轉(zhuǎn)整個(gè)句子
    Reverse(pBegin, pEnd);

    // 翻轉(zhuǎn)句子中的每個(gè)單詞
    pBegin = pEnd = pData;
    while(*pBegin != '\0')
    {
        if(*pBegin == ' ')
        {
            pBegin ++;
            pEnd ++;
        }
        else if(*pEnd == ' ' || *pEnd == '\0')
        {
            Reverse(pBegin, --pEnd);
            pBegin = ++pEnd;
        }
        else
        {
            pEnd ++;
        }
    }
    return pData;
}

如果你在面試的時(shí)候遇到這道題，并且很容易就想到了這個(gè)算法睦擂，有經(jīng)驗(yàn)的面試官就會(huì)在這道題基礎(chǔ)上加點(diǎn)難度得湘，繼續(xù)考查面試者。so顿仇，第二道題來(lái)了：

題目：接上題淘正，面試官繼續(xù)提問(wèn)，我們得到的" com google www"需要被用作一個(gè)URL的參數(shù)臼闻，所以這里需要的處理是去掉開頭結(jié)尾的無(wú)效空格鸿吆，并將兩個(gè)單詞中間的每一個(gè)空格都替換為"%20"。例如" com google www"應(yīng)被轉(zhuǎn)換為"com%20%20google%20www"述呐，請(qǐng)給出轉(zhuǎn)換函數(shù)惩淳。

解題思路

• 第一步去掉收尾的無(wú)效空格；比如" com google www"去掉后得到"com google www"乓搬。
• 第二步將兩個(gè)單詞中間的每一個(gè)空格都替換為"%20"黎泣。

還是以" hello world"為例，簡(jiǎn)單分析下解題過(guò)程缤谎，請(qǐng)看下圖抒倚。

反轉(zhuǎn)字符串02.png

注：（1）字符串" hello world"托呕，這里注意首字符是空格。 （2）剔除首尾空格后频敛。 （3）對(duì)原字符串進(jìn)行擴(kuò)容项郊。newLen = len + 2 x blackCount；這里解釋下新數(shù)組的長(zhǎng)度是如何計(jì)算的斟赚，由于是將每一個(gè)空格都替換為"%20",就相當(dāng)于原來(lái)占一個(gè)字符替換后要占三個(gè)字符着降，換言之，每一個(gè)空格就會(huì)多出兩個(gè)字符長(zhǎng)度拗军，所以就有前面的表達(dá)式任洞。 （4） 定義兩個(gè)指針p1、p2发侵，分別指向len-1和newLen-1位置交掏。 （5）判斷p1指針是否指向空格，如果是則在p2處開始插入字符“%20”刃鳄，不是則將p1指向的值復(fù)制給p2并將兩個(gè)指針往左移動(dòng)一位盅弛。這里將p1指向的字符 d 賦值給p2，并將兩個(gè)指針向左移動(dòng)一位。 （6）將p1指向的字符 l 賦值給p2挪鹏，并移動(dòng)指針见秽。 （7）多次賦值和移動(dòng)后，p1指向了第一個(gè)空格讨盒。 （8）在p2處依次插入字符 0 解取、 2 、 % 催植，并指針p2向左移動(dòng)三位肮蛹，結(jié)束后將p1向左移動(dòng)一位，此時(shí)p1创南、p2重合結(jié)束循環(huán)伦忠。

測(cè)試用例

• 功能測(cè)試：前后有無(wú)空格情況、中間一個(gè)或多個(gè)空格情況稿辙。
• 特殊輸入測(cè)試：空字符昆码、字符串中只有空格、null對(duì)象（指針）邻储。

編碼實(shí)現(xiàn)

• Java代碼

private String v1_1_solution(String sentence) {
    if (sentence == null || sentence.isEmpty()) {
        return sentence;
    }

    // 去掉字符串收尾的空格
    sentence = trim(sentence);
    int len = sentence.length();
    char[] chars = sentence.toCharArray();
    int count = getSpaceCount(sentence);
    int newLen = 2 * count + len;
    // 擴(kuò)容赋咽，內(nèi)部使用System.arraycopy 方法實(shí)現(xiàn)。
    chars = Arrays.copyOf(chars, newLen);

    int index = len - 1;
    int newIndex = newLen - 1;
    while (index >= 0 && newIndex > index) {
        if (chars[index] == ' ') {
            chars[newIndex--] = '0';
            chars[newIndex--] = '2';
            chars[newIndex--] = '%';
        } else {
            chars[newIndex--] = chars[index];
        }
        index--;
    }

    return new String(chars);
}

/**
 * 剔除字符串收尾的空格
 *
 * @param origin
 * @return
 */
private String trim(String origin) {
    char[] chars = origin.toCharArray();
    int length = chars.length;
    int st = 0;
    while (st < length && chars[st] == ' ') {
        st++;
    }

    while (st < length && chars[length - 1] == ' ') {
        length--;
    }

    // 如果收尾有空格吨娜，就截取生成新的字符串
    if (st > 0 || length < chars.length) {
        origin = new String(chars, st, (length - st));
    }
    return origin;
}

private int getSpaceCount(String sentence) {
    char[] chars = sentence.toCharArray();
    int count = 0;
    for (char c : chars) {
        if (c == ' ') {
            count++;
        }
    }
    return count;
}

• C++實(shí)現(xiàn)

/* 去掉收尾空格:將原字符串截取后返回新字符串 */
void trim(char *strIn, char *strOut){
    int i = 0;
    int j = strlen(strIn) - 1;

    while(strIn[i] == ' ')
        ++i;

    while(strIn[j] == ' ')
        --j;
    strncpy(strOut, strIn + i , j - i + 1);
    strOut[j - i + 1] = '\0';
}

/*length 為字符數(shù)組string的總?cè)萘?/
void replaceBlank(char string[], int length)
{
    if(string == NULL && length <= 0)
        return;

    /*originalLength 為字符串string的實(shí)際長(zhǎng)度*/
    int originalLength = 0;
    int numberOfBlank = 0;
    int i = 0;
    while(string[i] != '\0')
    {
        ++ originalLength;

        if(string[i] == ' ')
            ++ numberOfBlank;

        ++ i;
    }

    /*newLength 為把空格替換成'%20'之后的長(zhǎng)度*/
    int newLength = originalLength + numberOfBlank * 2;
    if(newLength > length)
        return;

    int indexOfOriginal = originalLength;
    int indexOfNew = newLength;
    while(indexOfOriginal >= 0 && indexOfNew > indexOfOriginal)
    {
        if(string[indexOfOriginal] == ' ')
        {
            string[indexOfNew --] = '0';
            string[indexOfNew --] = '2';
            string[indexOfNew --] = '%';
        }
        else
        {
            string[indexOfNew --] = string[indexOfOriginal];
        }

        -- indexOfOriginal;
    }
}

題目2：調(diào)整數(shù)組中元素順序

題目： 給定一個(gè)整數(shù)數(shù)組脓匿，請(qǐng)實(shí)現(xiàn)一個(gè)函數(shù)來(lái)調(diào)整數(shù)組中數(shù)字的順序，使得所有奇數(shù)都位于偶數(shù)之前宦赠。

解題思路

此題比較簡(jiǎn)單陪毡，我最先想到的解法是這樣：我們維護(hù)兩個(gè)指針(索引)，一個(gè)指針指向數(shù)組的第一個(gè)數(shù)字勾扭，稱之為頭指針毡琉，向右移動(dòng)；一個(gè)指針指向最后一個(gè)數(shù)字妙色，稱之為尾指針桅滋，向左移動(dòng)。

yugang-dsaa-v2.0.png

注：（1）初始化兩個(gè)指針P1、P2洗贰，分別指向數(shù)組的頭部和尾部找岖。（2）由上一步得知，指針P1指向的數(shù)字是偶數(shù)2敛滋，而P2指向的數(shù)字是奇數(shù)5许布，滿足條件，我們交換這兩個(gè)數(shù)字绎晃。（3） P1繼續(xù)向右移動(dòng)直到指向偶數(shù)6蜜唾，P2繼續(xù)向左移動(dòng)直到指向奇數(shù)7。（4）交換兩個(gè)指針指向的數(shù)字庶艾。（5）P1袁余，P2繼續(xù)移動(dòng)后重疊，表明所有奇數(shù)已位于偶數(shù)前面了咱揍。

循環(huán)結(jié)束條件：兩個(gè)指針重疊時(shí)或P2指針移動(dòng)到了P1指針的前面颖榜，此時(shí)退出循環(huán)。
可以看出此算法煤裙，一次循環(huán)搞定掩完，所以時(shí)間復(fù)雜度O(n), 由于在原數(shù)組上操作，所以空間復(fù)雜度O(1)硼砰。

測(cè)試用例

• 功能測(cè)試：全是奇數(shù)且蓬、全是偶數(shù)、奇偶數(shù)存在但已排好序/未排好序题翰。
• 特殊輸入測(cè)試： null對(duì)象恶阴、數(shù)組元素為0、有負(fù)數(shù)情況遍愿。

編碼

• Java實(shí)現(xiàn)

private int[] v2_0_solution(int[] nums) {
     if (nums == null || nums.length <= 1) {
         return nums;
     }
     int st = 0;
     int end = nums.length - 1;

     while (st < end) {
         // find even number
         if (isOdd(nums[st])) {
             st++;// 奇數(shù)存淫，索引右移
         } else if (!isOdd(nums[end])) {
             end--;// 偶數(shù)，索引左移
         } else {
             // 奇偶數(shù)互換
             int temp = nums[st];
             nums[st] = nums[end];
             nums[end] = temp;
             st++;
             end--;
         }
     }
     return nums;
 }

 // 與1做按位運(yùn)算沼填，不為0就是奇數(shù)桅咆，反之為偶數(shù)
 private boolean isOdd(int n) {
     return (n & 1) != 0;
 }

• C++實(shí)現(xiàn)

// 互換
void swap(int* num1, int* num2)
{
    int temp = *num1;
    *num1 = *num2;
    *num2 = temp;
}

//判斷是否為奇數(shù)
bool isOdd(int data)
{
    return (data & 1) != 0;
}

//奇偶互換
void oddEvenSort(int *pData, unsigned int length)
{
    if (pData == NULL || length == 0)
        return;

    int *pBegin = pData;
    int *pEnd = pData + length - 1;

    while (pBegin < pEnd)
    {
        //如果pBegin指針指向的是奇數(shù)，正常坞笙，向右移
        if (isOdd(*pBegin))  
        {
            pBegin++;
        }
        //如果pEnd指針指向的是偶數(shù)岩饼，正常，向左移
        else if (!isOdd(*pEnd))
        {
            pEnd--;
        }
        else
        {
            //否則都不正常薛夜，交換
            swap(pBegin, pEnd);
        }
    }
}

有經(jīng)驗(yàn)的面試官又來(lái)了籍茧，題目難度需要升下級(jí)，??~

題目： 接上題梯澜，面試官會(huì)繼續(xù)要求改造此函數(shù)使其能夠保證原先輸入數(shù)組的奇數(shù)內(nèi)部順序以及偶數(shù)內(nèi)部順序寞冯，即如果輸入為{2，1，3吮龄，6俭茧，4，7漓帚，8母债，5}，則輸出應(yīng)為{1尝抖，3毡们，7，5昧辽，2衙熔，6，4奴迅，8}青责，奇數(shù)之間的相互順序和偶數(shù)之間的相互順序不得被改變。

解題思路

要想保證原數(shù)組內(nèi)元素的順序取具，可使用O(n)的temp數(shù)組空間按順序緩存偶數(shù)脖隶，奇數(shù)依次放到原數(shù)組前面，最后將temp中偶數(shù)取出放在原數(shù)組后面暇检。

yugang-dsaa-v2-1.png

注： 變量解釋：st為即將插入的奇數(shù)在原數(shù)組中的索引块仆，evenCount為緩存的偶數(shù)個(gè)數(shù)构蹬。（1）初始化和原數(shù)組相同長(zhǎng)度的數(shù)組temp，指針p1指向首個(gè)元素悔据，st=eventCount=0庄敛。 （2）將p1指向的偶數(shù) 2 放入在temp中，evenCount自加1科汗。 （3）由于p1指針向右移動(dòng)一位指向的是奇數(shù) 1 藻烤，所以將p1指向的值賦值給Array[st]，此時(shí)還st=0头滔，賦值完成后st自加1怖亭。 （8）依次邏輯，直到循環(huán)結(jié)束時(shí)坤检，已完成原數(shù)組中奇數(shù)元素按順序插入到了頭部兴猩，偶數(shù)按順序緩存在了temp數(shù)組中，即圖中狀態(tài)早歇。

上圖展示了偶數(shù)按順序緩存到temp數(shù)組中倾芝，奇數(shù)按順序放到原數(shù)組前面讨勤。最后將temp數(shù)組中的偶數(shù)依次按序放在原數(shù)組后面，這個(gè)過(guò)程較簡(jiǎn)單蛀醉，就沒(méi)體現(xiàn)到圖中悬襟，具體請(qǐng)看下面代碼實(shí)現(xiàn)衅码。

測(cè)試用例

同上一題拯刁。這里就省略了。

編碼

• Java實(shí)現(xiàn)

private int[] v2_1_solution(int[] nums) {
     if (nums == null || nums.length <= 1) {
         return nums;
     }

     int st = 0;
     int evenCount = 0;
     int[] temp = new int[nums.length];
     for (int i = 0; i < nums.length; i++) {
         if (!isOdd(nums[i])) {
             evenCount += 1;
             temp[evenCount - 1] = nums[i];
         } else {
             if (st < i) {
                 // 將奇數(shù)依次放在原數(shù)組前面
                 nums[st] = nums[i];
             }
             st++;
         }
     }

     if (evenCount > 0) {
         for (int i = st; i < nums.length; i++) {
             nums[i] = temp[i - st];
         }
     }
     return nums;
}

• C++實(shí)現(xiàn)

void v2_1_solution(int* nums,unsigned int len)
{
     if (!nums || len <= 1) {
         return;
     }
     int st = 0;
     int evenCount = 0;
     // 申請(qǐng)的內(nèi)存空間temp
     int temp[len];
     for (int i = 0; i < len; i++) {
         if (!isOdd(nums[i])) {
             evenCount += 1;
             temp[evenCount - 1] = nums[i];
         } else {
             if (st < i) {
                 // 將奇數(shù)依次放在原數(shù)組前面
                 nums[st] = nums[i];
             }
            st++;
         }
     }
     // 將temp中偶數(shù)取出放在原數(shù)組后面
     if (evenCount > 0) {
         for (int i = st; i < len; i++) {
             nums[i] = temp[i - st];
         }
     }
 }

題目3：利用數(shù)組實(shí)現(xiàn)一個(gè)簡(jiǎn)易版的List

題目：請(qǐng)利用數(shù)組實(shí)現(xiàn)一個(gè)簡(jiǎn)易版的List逝段，需要實(shí)現(xiàn)poll和push兩個(gè)接口垛玻，前者為移除并獲得隊(duì)頭元素，后者為向隊(duì)尾添加一個(gè)元素奶躯，并要求能夠自動(dòng)擴(kuò)容帚桩。

解題思路

還是以“hello world”為例，作圖分析下嘹黔。

用數(shù)組實(shí)現(xiàn)List.png

注：（1） 初始化List账嚎，數(shù)組默認(rèn)容量len為8，size=0儡蔓。（容量小一點(diǎn)方便作圖郭蕉，實(shí)際容量看需求而定。） （2） 隊(duì)尾添加字符 h 喂江，size++召锈。 （3）添加len-1個(gè)字符后，size指向數(shù)組最后一個(gè)位置获询。 （4）如果再添加字符 O 涨岁，由于size++滿足條件：大于等于len，此時(shí)需要先對(duì)List先擴(kuò)容吉嚣，擴(kuò)容后梢薪，再進(jìn)行添加字符操作。 （5） 接著繼續(xù)添加尝哆，直到“hello world”都push到List中秉撇。 （6）這是一個(gè)poll過(guò)程，可以看出即獲取了對(duì)頭元素 h 较解，并且整個(gè)數(shù)組中元素向左移動(dòng)一位來(lái)實(shí)現(xiàn)移除效果畜疾。

關(guān)于擴(kuò)容：每次擴(kuò)容多少？上圖例子是變?yōu)樵瓉?lái)的2倍印衔。像ArrayList則是這樣 int newCapacity = oldCapacity + (oldCapacity >> 1)啡捶，可以看出擴(kuò)容后大小 = 原來(lái)大小 + 原來(lái)大小/2。所以擴(kuò)容多少由你自己決定奸焙。

此題關(guān)鍵是在怎么實(shí)現(xiàn)poll和push兩個(gè)接口上瞎暑。

• push（添加元素）：按索引添加到數(shù)組中彤敛，size大于等于數(shù)組長(zhǎng)度時(shí)就先擴(kuò)容。
• poll（獲取并移動(dòng)對(duì)頭元素）：移動(dòng)數(shù)組并置空最后一個(gè)元素了赌。

測(cè)試用例

• 功能測(cè)試： 添加墨榄、移除元素
• 特殊測(cè)試： 添加大量數(shù)據(jù)（測(cè)試擴(kuò)容）、移除所有元素勿她、null數(shù)據(jù)

編碼

• Java實(shí)現(xiàn)

private static final int DEFAULT_CAPACITY = 16;
private Object[] elementData;
// 實(shí)際存儲(chǔ)的元素?cái)?shù)量
//  The size of the List (the number of elements it contains).
private int size;

public CustomList() {
    elementData = new Object[DEFAULT_CAPACITY];
}

public CustomList(int initialCapacity) {
    if (initialCapacity > 0) {
        this.elementData = new Object[initialCapacity];
    } else if (initialCapacity == 0) {
        this.elementData = new Object[DEFAULT_CAPACITY];
    } else {
        throw new IllegalArgumentException("Illegal Capacity: " +
                initialCapacity);
    }
}

/**
 * 移除并獲得隊(duì)頭元素
 *
 * @return
 */
public Object poll() {
    if (size <= 0){
        throw new IndexOutOfBoundsException(" list is empty .");
        }
    // 獲取隊(duì)頭第一個(gè)元素
    Object oldValue = elementData[0];

    // 數(shù)組元素左移一位 & 最后一位元素置空
    System.arraycopy(elementData, 1, elementData, 0, size - 1);
    elementData[--size] = null; // clear to let GC do its work

    return oldValue;
}

/**
 * 向隊(duì)尾添加一個(gè)元素
 *
 * @param item
 */
public void push(Object item) {
    ensureExplicitCapacity(size + 1);  // Increments modCount!!
    elementData[size++] = item;
}

@Override
public String toString() {
    return Arrays.toString(elementData);
}

// 這里擴(kuò)容參考的ArrayList袄秩，具體實(shí)現(xiàn)請(qǐng)點(diǎn)擊文末源代碼鏈接前往查看。
private void ensureExplicitCapacity(int minCapacity) {
    // 期望的最小容量大于等于現(xiàn)有數(shù)組的長(zhǎng)度逢并，則進(jìn)行擴(kuò)容
    if (minCapacity - elementData.length >= 0)
        grow(minCapacity);
}

• C++實(shí)現(xiàn)

class List { 
  private: 
    int expansionSize = 16;//每次擴(kuò)容個(gè)數(shù)
    int elemsSize = 0;//數(shù)組長(zhǎng)度
    int dataIndex = -1;//最后一位元素下標(biāo)
    T* elems;          //元素 
 
  public: 
    List(){
        elemsSize = 0;
        dataIndex = -1;
    }
    List(int initialCapacity){
        if (initialCapacity<=0) { 
            throw out_of_range("initialCapacity must > 0"); 
        }
        elemsSize = initialCapacity;
        elems = new T[initialCapacity];
    }
    void push(T const&);  // 入棧
    T poll();             // 出棧
    int size();
    ~List(){
        if(elemsSize>0){
            delete []elems;
        }
    }
}; 
 
template <class T>
void List<T>::push (T const& elem) 
{ 
    if(elemsSize <= 0){//初始化數(shù)組
        elemsSize = expansionSize;
        elems = new T[elemsSize];
    }
    if(dataIndex+1 >= elemsSize){//數(shù)組擴(kuò)容
        elemsSize += expansionSize;
        T* newElems = new T[elemsSize];
        for(int i=0;i<=dataIndex;i++){
            newElems[i] = elems[i];
        }
        delete[]elems;
        elems = newElems;
    }
    dataIndex++;
    elems[dataIndex] = elem;
} 
 
template <class T>
T List<T>::poll () 
{ 
    if (dataIndex<0) { 
        throw out_of_range("List<>::poll(): empty List"); 
    }
    T poll = elems[0]; //獲取第一位
    for(int i=1;i<=dataIndex;i++){//后面元素向左移
        elems[i-1] = elems[i];
    }
    dataIndex--;
    return poll;
} 

template <class T>
int List<T>::size () 
{ 
    return dataIndex+1;
}

題目4：數(shù)組中出現(xiàn)次數(shù)超過(guò)一半的數(shù)

題目： 一個(gè)整數(shù)數(shù)組中有一個(gè)數(shù)字出現(xiàn)的次數(shù)超過(guò)了數(shù)組長(zhǎng)度的一半之剧，請(qǐng)找出這個(gè)數(shù)字。如輸入一個(gè)長(zhǎng)度為9的數(shù)組{1砍聊，2背稼，3，2玻蝌，2蟹肘，2，5俯树，4帘腹，2}，由于2出現(xiàn)了5次聘萨，超過(guò)了數(shù)組長(zhǎng)度的一半竹椒，因此應(yīng)輸出2。

解題思路

如果我們將數(shù)組排序米辐，那么排序后位于數(shù)組中間的的數(shù)字一定是那個(gè)出現(xiàn)次數(shù)超過(guò)數(shù)組長(zhǎng)度一半的數(shù)字胸完。這個(gè)數(shù)就是統(tǒng)計(jì)學(xué)上的中位數(shù)。

此題關(guān)鍵在于快速排序算法翘贮，我們一起看看下面這張圖赊窥，來(lái)理解下快排的思想。

Sorting_quicksort_anim.gif

圖 4.0 快速排序過(guò)程動(dòng)圖狸页，圖片來(lái)源Wikipedia锨能。

快速排序使用分治法（Divide and conquer）策略來(lái)把一個(gè)序列（list）分為兩個(gè)子序列（sub-lists）。

• 步驟為：

  • 從數(shù)列中挑出一個(gè)元素芍耘，稱為"基準(zhǔn)"（pivot）址遇，
  • 重新排序數(shù)列，所有比基準(zhǔn)值小的元素?cái)[放在基準(zhǔn)前面斋竞，所有比基準(zhǔn)值大的元素?cái)[在基準(zhǔn)后面（相同的數(shù)可以到任何一邊）倔约。在這個(gè)分區(qū)結(jié)束之后，該基準(zhǔn)就處于數(shù)列的中間位置坝初。這個(gè)稱為分區(qū)（partition）操作浸剩。
  • 遞歸地（recursively）把小于基準(zhǔn)值元素的子數(shù)列和大于基準(zhǔn)值元素的子數(shù)列排序钾军。

遞歸到最底部時(shí)，數(shù)列的大小是零或一绢要，也就是已經(jīng)排序好了吏恭。這個(gè)算法一定會(huì)結(jié)束，因?yàn)樵诿看蔚牡╥teration）中重罪，它至少會(huì)把一個(gè)元素?cái)[到它最后的位置去樱哼。

測(cè)試用例

• 存在（或者不存在）次數(shù)超過(guò)數(shù)組長(zhǎng)度一半的數(shù)。
• 特殊用例： null蛆封、空元素唇礁、 只有一個(gè)數(shù)。

編碼

• Java實(shí)現(xiàn)

private int v4_0_solution(int[] array) {
     if (array == null || array.length < 1) {
         throw new IllegalArgumentException(" array is empty. ");
     }

     int head = 0;
     int tail = array.length - 1;
     // 快速排序
     qSort(array, head, tail);
     int middle = array.length >> 1;
     int result = array[middle];
     // 判斷中位數(shù)是否為超過(guò)數(shù)組長(zhǎng)度一半的數(shù)惨篱。
     if (checkMoreThanHalf(array, result)) {
         return result;
     } else {
         throw new IllegalArgumentException("not find the number.");
     }
}

public void qSort(int[] arr, int head, int tail) {
    // 參數(shù)合法性及結(jié)束條件
    if (head >= tail || arr == null || arr.length <= 1) {
        return;
    }
    // 取中間數(shù)為基準(zhǔn)值
    int i = head, j = tail, pivot = arr[(head + tail) / 2];
    while (i <= j) {
        // 處理大于等于基準(zhǔn)數(shù)情況
        while (arr[i] < pivot) {
            ++i;
        }
        while (arr[j] > pivot) {
            --j;
        }
        // 直接互換，沒(méi)有基準(zhǔn)數(shù)歸位操作
        if (i < j) {
            swap(arr, i, j);
            ++i;
            --j;
        } else if (i == j) {
            ++i;
        }
    }
    // 遞歸處理基準(zhǔn)數(shù)分隔的兩個(gè)子數(shù)列围俘。
    qSort(arr, head, j);
    qSort(arr, i, tail);
} 
 
private boolean checkMoreThanHalf(int[] nums, int number) {
     int times = 0;
     for (int i = 0; i < nums.length; i++) {
         if (nums[i] == number) {
             times++;
         }
     }
     return times * 2 > nums.length;
}

• C++ 實(shí)現(xiàn)

// 快速排序：遞歸方式 參考Wikipedia
void quick_sort_recursive(int arr[], int start, int end) {
    if (start >= end)
        return;
    int mid = arr[end];
    int left = start, right = end - 1;
    while (left < right) {
        while (arr[left] < mid && left < right)
            left++;
        while (arr[right] >= mid && left < right)
            right--;
        std::swap(arr[left], arr[right]);
    }
    if (arr[left] >= arr[end])
        std::swap(arr[left], arr[end]);
    else
        left++;
    quick_sort_recursive(arr, start, left - 1);
    quick_sort_recursive(arr, left + 1, end);
}

int main()
{
    //存在出現(xiàn)次數(shù)超過(guò)數(shù)組長(zhǎng)度一半的數(shù)字
    //int data[] = {1, 2, 3, 2, 2, 2, 5, 4, 2};
    //不存在出現(xiàn)次數(shù)超過(guò)數(shù)組長(zhǎng)度一半的數(shù)字
    //int data[] = {4, 5, 1, 6, 2, 7, 3, 8};
    // 出現(xiàn)次數(shù)超過(guò)數(shù)組長(zhǎng)度一半的數(shù)字都出現(xiàn)在數(shù)組的前/后半部分
    int data[] = {2, 2, 2, 2, 2, 1, 3, 4, 5};
    //int data[] = {1, 3, 4, 5, 2, 2, 2, 2, 2};
    int len = sizeof(data)/sizeof(int);
    printf("length =  %d \n", len);
    quick_sort_recursive(data, 0, len -1);
    for(int i=0;i<len;i++){
       printf(" %d ", data[i]);
    }
    printf("\n");
    int middle = len >> 1;
    int result = data[middle];
    if(CheckMoreThanHalf(data, len, result)){
       printf("the number is  %d ", result);
    }else{
        printf("not find the number.");
    }
    return 0;
}

有經(jīng)驗(yàn)的面試官又來(lái)了砸讳，題目難度需要升下級(jí)，??~

題目：這個(gè)題目有很多變種界牡，其中一個(gè)引申為輸入的是一個(gè)對(duì)象數(shù)組簿寂，該對(duì)象無(wú)法比較大小，只能利用equals()方法比較是否相等宿亡，此時(shí)該如何解（若要用到O(n)的輔助空間常遂，能否避免？）挽荠。

解題思路

數(shù)組中有一個(gè)元素出現(xiàn)的次數(shù)超過(guò)數(shù)組長(zhǎng)度的一半克胳，也就是說(shuō)它出現(xiàn)的次數(shù)比其他所有元素出現(xiàn)次數(shù)的和還要多。

因此我們可以考慮在遍歷數(shù)組的時(shí)候保存兩個(gè)值： 一個(gè)是數(shù)組中的一個(gè)元素圈匆， 一個(gè)是次數(shù)漠另。當(dāng)我們遍歷到下一個(gè)元素的時(shí)候，如果下一個(gè)元素和我們之前保存的元素相等（equals返回true）跃赚，則次數(shù)加1笆搓；如果下一個(gè)元素和我們之前保存的不相等，則次數(shù)減1纬傲。如果次數(shù)為0满败，我們需要保存下一個(gè)元素，并把次數(shù)設(shè)為1叹括。由于我們要找的數(shù)字出現(xiàn)的次數(shù)比其他所有數(shù)字出現(xiàn)的次數(shù)之和還要多算墨，那么要找的數(shù)字肯定是最后一次把次數(shù)設(shè)為1時(shí)對(duì)應(yīng)的那個(gè)元素。

怎么樣簡(jiǎn)單吧领猾，還是畫張圖來(lái)理解一下米同。

數(shù)組中出現(xiàn)次數(shù)超過(guò)一半的數(shù).png

注：雖然途中數(shù)組元素類型是整型，但其思想適用于任何類型面粮。（1） 數(shù)組初始狀態(tài)少孝，times只是一個(gè)標(biāo)記變量，默認(rèn)為0熬苍， result為最后一次設(shè)置times=1時(shí)的那個(gè)元素稍走，默認(rèn)為NULL。（2）開始循環(huán)柴底，i=0時(shí)婿脸，times設(shè)置為1，并將第一個(gè)元素 1 賦值給result變量柄驻。 （3）i=1時(shí)狐树，由于此時(shí)Array[i]的值為 2 ，不等于result鸿脓，所以times--抑钟，操作后times等于0，result不變野哭。（4）i=2時(shí)在塔，由于此時(shí)times==0，所以重新設(shè)置times=1拨黔，result= Array[2]= 3 蛔溃。（5）i=3時(shí)，和（3）類似篱蝇，由于此時(shí)Array[i]的為2贺待，不等于result，所以times--态兴，操作后times等于0狠持，result不變還是等于3。（6）依次邏輯瞻润，一直遍歷到末尾喘垂，即i=8時(shí)，邏輯同上绍撞，可以求出times=1正勒，result=2；ok傻铣，循環(huán)結(jié)束章贞。

到這里得出result=2，那這個(gè)2是不是我們要找的那個(gè)元素呢非洲？ 答案是：不一定鸭限。 如果輸入數(shù)組中存在次數(shù)超過(guò)超過(guò)數(shù)組長(zhǎng)度一半的數(shù)蜕径，那result就是那個(gè)數(shù)，否則就不是败京。所以兜喻，我們還需要對(duì)這個(gè)數(shù)進(jìn)行檢查，檢查過(guò)程請(qǐng)參看下方代碼。

此思路：空間復(fù)雜度O(1),時(shí)間復(fù)雜度O(n)。

編碼

• Java實(shí)現(xiàn)

private Object v4_1_solution(Object[] objects) {
    if (objects == null || objects.length < 1) {
        throw new IllegalArgumentException(" array is empty. ");
    }
    // 假設(shè)第一個(gè)元素就是超過(guò)長(zhǎng)度一半的那個(gè)
    Object result = objects[0];
    int times = 1;

    // 從第二個(gè)元素開始遍歷
    for (int i = 1; i < objects.length; i++) {
        if (times == 0) {
            // 重新設(shè)置
            result = objects[i];
            times = 1;
        } else if (objects[i].equals(result)) {
            times++;
        } else {
            times--;
        }
    }
    if (checkMoreThanHalf(objects, result)) {
        return result;
    } else {
        throw new IllegalArgumentException(" array is invalid ");
    }
}

private boolean checkMoreThanHalf(Object[] objects, Object obj) {
    int times = 0;
    for (int i = 0; i < objects.length; i++) {
        if (objects[i].equals(obj)) {
            times++;
        }
    }
    return times * 2 > objects.length;
}

// 測(cè)試類缘薛，重點(diǎn)在于實(shí)現(xiàn)了equals和hashcode方法。
private static class TestObject {
    String unique;

    public TestObject(String unique) {
        this.unique = unique;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;

        TestObject that = (TestObject) o;

        return unique != null ? unique.equals(that.unique) : that.unique == null;
    }

    @Override
    public int hashCode() {
        return unique != null ? unique.hashCode() : 0;
    }

    @Override
    public String toString() {
        return "TestObject{" +
                "unique='" + unique + '\'' +
                '}';
    }
}

• C++實(shí)現(xiàn)

template <class T>
class Array {
  private:
    bool checkMoreThanHalf(T *objects,unsigned int len,T obj)
 {
     unsigned int times = 0;
     for (int i = 0; i < len; i++) {
         if (objects[i] == obj) {
             times++;
         }
     }
     return times * 2 > len;
 };
  public:
    T v4_1_solution(T *objects,unsigned int len);
};

template <class T>
T Array<T>::v4_1_solution (T *objects,unsigned int len)
{
     if (!objects || len < 1) {
         throw out_of_range(" array is empty. ");
     }
     // 假設(shè)第一個(gè)元素就是超過(guò)長(zhǎng)度一半的那個(gè)
     T result = objects[0];
     if(len == 1){
        return result;
     }
     int times = 1;
     // 從第二個(gè)元素開始遍歷
     for (int i = 1; i < len; i++) {
         if (times == 0) {
             // 重新設(shè)置
             result = objects[i];
             times = 1;
         } else if (objects[i] == result) {
             times++;
         } else {
             times--;
         }
     }
     if (checkMoreThanHalf(objects,len, result)) {
         return result;
     } else {
         throw out_of_range(" array is invalid ");
     }
}

學(xué)習(xí)心得&解題套路

細(xì)心的讀者可能發(fā)現(xiàn)了遂铡，文中解題過(guò)程大致是這樣的：分析思路->測(cè)試用例->編碼->調(diào)試并通過(guò)測(cè)試。你可能會(huì)問(wèn)怎樣才能很好的掌握算法編程呢晶姊？我的建議是：有事沒(méi)事刷道題吧扒接。勤加練習(xí)，終成大神帽借。哈哈珠增，請(qǐng)輕拍。

• 關(guān)于解題思路（詳見劍指offer）

  • 畫圖讓抽象問(wèn)題形象化
  • 舉例讓抽象問(wèn)題具體化
  • 分解讓復(fù)雜問(wèn)題簡(jiǎn)單化

• 學(xué)習(xí)資源(信息大爆炸砍艾，好資源很重要)

  • 各種數(shù)據(jù)結(jié)構(gòu)及算法書籍： 大話數(shù)據(jù)結(jié)構(gòu)、劍指offer巍举、算法導(dǎo)論等等脆荷。
  • 在線編程：LeetCode、虐妹酰客網(wǎng)蜓谋、七月在線

• 菜鳥練手推薦：C++在線工具

總結(jié)

現(xiàn)在去大公司面試，都會(huì)有算法題炭分，所以不是你想不想掌握它桃焕，而是公司會(huì)通過(guò)它把一部分人淘汰掉，說(shuō)的可能有點(diǎn)嚇人捧毛，但現(xiàn)實(shí)就是這樣操作的观堂。文中所有代碼均編譯運(yùn)行并通過(guò)測(cè)試用例檢查，由于篇幅限制呀忧，代碼沒(méi)有貼全师痕，完整的可運(yùn)行代碼請(qǐng)點(diǎn)擊鏈接獲取： https://github.com/yangjiantao/DSAA而账。 由于作者水平有限胰坟，文中錯(cuò)誤之處在所難免，敬請(qǐng)讀者指正泞辐。

編程能力就像任何其他技能一樣笔横，也是一個(gè)可以通過(guò)刻意練習(xí)大大提高的竞滓。 --- 摘抄至LeetCode。