面試必備：數組和字元串

本文由玉剛說寫作平台提供寫作贊助原作者：Jiantao版權聲明：本文版權歸微信公眾號玉剛說所有

數據結構和演算法有多重要？

我想有追求的程序員都不會放過它的。

打個比方，在金庸的武俠世界裡，數據結構和演算法它就像一門上乘的內功心法，一旦掌握了它，各種武功信手拈來，毫無壓力（張無忌就是一個典型的例子），

對於程序員來說，它能決定你在技術這條道路上能走多遠。

本文主要涉及數組、字元串這幾個數據結構，然後通過解答和分析幾道常見的面試題，從中分享一些我的學習心得和解題套路，希望對你有幫助。

題目1：翻轉句子

題目： 給定一個英文句子，每個單詞之間都是由一個或多個空格隔開，請翻轉句子中的單詞順序（包括空格的順序），但單詞內字元的順序保持不變。例如輸入"www google com "，則應輸出" com google www"。

如果你經常關注演算法相關文章，這道題應該會比較熟悉，各種博客和書籍上都有出現，不熟悉也沒關係，現在我們就一起來嘗試解答下。這裡要注意題意和網上流傳的題目有個不同點：網上基本都是

單詞間有且只有一個空格，

而此題需要考慮

一個或多個空格的情況

。

解題思路

試想一下，如果將整個字元串翻轉，結果是句子是反轉了，但單詞內的字元順序也翻轉了。如果要保證單詞內順序不變，只需要再將每個單詞翻轉一下就滿足要求了。

由於題中「www google com 」字元串較長，我就以" hello world"為例分析下這個過程，請看下圖。

圖 1.0 翻轉句子，但保證句子中單詞內部字元順序。

註：（1）字元串" hello world"初始狀態，注意首字元是空格。 （2）將" hello world"整個句子翻轉後的樣子。可以看出不僅翻轉了句子中單詞的順序(包括空格)，連單詞內的字元順序也翻轉了。(3) 定義兩個指針p1、p2都指向句子的首字元。 （4）首字元d，不是空格，此時p1指針不動，p2指針向右移動1位，指向字元

l

。（

移動p2指針目的：檢查單詞的結束位置。

） （5）由於第二個字元為

l

，也不是空格，p2繼續向右移動1位。（6）多次移動後，p2指針在第一個空格處停下來，此時就能得知p2-1為該單詞的結束位置。（7）反轉兩個指針（p1、p2-1）中間的字元串。（8）交換後，重置兩個指針位置p1=p2++。以此類推，繼續尋找下一個單詞並翻轉，直到指針移動到句子末尾就結束循環。

此思路的關鍵是：

1. 實現一個函數/方法，翻轉字元串中的一段。 2. 判斷並獲取句子中的單詞，注意空格。

測試用例

• 功能測試：多個單詞、1個單詞、單詞間只有一個空格、單詞間有多個空格。

• 特殊輸入測試：空字元、字元串中只有空格、null對象（指針）。

編碼實現

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();    

// 第一步翻轉所有字元

    

char

[] chars = v1_0_reverse(sentence.toCharArray(), 

0

, length - 

1

);    System.

out

.println(

new

 String(chars));    

// 第二步翻轉每個單詞（重點：怎麼找到單詞）

    

int

 start = 

0

, end = 

0

;    

while

 (start < length) {        

if

 (chars[start] == 

" "

) {            

// 遇到空格就向右邊繼續查找

            start++;            end++;        } 

else

 

if

 (end == length || chars[end] == 

" "

) {            

// 遇到空格或者已經到了字元串末尾，此時翻轉找到的單詞內部字元，這裡需要注意end-1

            chars = v1_0_reverse(chars, start, end - 

1

);            System.

out

.println(

new

 String(chars));            

// 重新制定檢查索引start

            start = end++;        } 

else

 {            

// end加1，為了檢查單詞是否結束

            end++;        }    }    

return

 

new

 String(chars);}

C++ 代碼：

// 反轉字元串

void

 

Reverse

(

char

 *pBegin, 

char

 *pEnd)

{    

if

(pBegin == 

NULL

 || pEnd == 

NULL

)        

return

;    

while

(pBegin < pEnd)    {        

char

 temp = *pBegin;        *pBegin = *pEnd;        *pEnd = temp;        pBegin ++, pEnd --;    }}

// 翻轉句子中單詞順序，但保證單詞內字元順序不變。

char

* 

ReverseSentence

(

char

 *pData)

{    

if

(pData == 

NULL

)        

return

 

NULL

;    

char

 *pBegin = pData;    

char

 *pEnd = pData;    

while

(*pEnd != 

""

)        pEnd ++;    pEnd--;    

// 翻轉整個句子

    Reverse(pBegin, pEnd);    

// 翻轉句子中的每個單詞

    pBegin = pEnd = pData;    

while

(*pBegin != 

""

)    {        

if

(*pBegin == 

" "

)        {            pBegin ++;            pEnd ++;        }        

else

 

if

(*pEnd == 

" "

 || *pEnd == 

""

)        {            Reverse(pBegin, --pEnd);            pBegin = ++pEnd;        }        

else

        {            pEnd ++;        }    }    

return

 pData;}

如果你在面試的時候遇到這道題，並且很容易就想到了這個演算法，有經驗的面試官就會在這道題基礎上加點難度，繼續考查面試者。so，第二道題來了：

題目：接上題，面試官繼續提問，我們得到的" com google www"需要被用作一個URL的參數，所以這裡需要的處理是去掉開頭結尾的無效空格，並將兩個單詞中間的每一個空格都替換為"%20"。例如" com google www"應被轉換為"com%20%20google%20www"，請給出轉換函數。

解題思路

• 第一步去掉收尾的無效空格；比如" com google www"去掉後得到"com google www"。

• 第二步將兩個單詞中間的每一個空格都替換為"%20"。

還是以" hello world"為例，簡單分析下解題過程，請看下圖。

圖 1.1 剔除收尾無效空格，並將單詞間的每一個空格都替換為"%20"。

註：（1）字元串" hello world"，這裡注意首字元是空格。 （2）剔除首尾空格後。 （3）對原字元串進行擴容。

newLen = len + 2 x blackCount

；這裡解釋下新數組的長度是如何計算的，

由於是將每一個空格都替換為"%20"

,就相當於原來佔一個字元替換後要佔三個字元，換言之，每一個空格就會多出兩個字元長度，所以就有前面的表達式。 （4） 定義兩個指針p1、p2，分別指向len-1和newLen-1位置。 （5）判斷p1指針是否指向空格，如果是則在p2處開始插入字元「%20」，不是則將p1指向的值複製給p2並將兩個指針往左移動一位。這裡將p1指向的字元

d

賦值給p2，並將兩個指針向左移動一位。 （6）將p1指向的字元

l

賦值給p2，並移動指針。 （7）多次賦值和移動後，p1指向了第一個空格。 （8）在p2處依次插入字元

0

、

2

、

%

，並指針p2向左移動三位，結束後將p1向左移動一位，此時p1、p2重合結束循環。

測試用例

• 功能測試：前後有無空格情況、中間一個或多個空格情況。

• 特殊輸入測試：空字元、字元串中只有空格、null對象（指針）。

編碼實現

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;    

// 擴容，內部使用System.arraycopy 方法實現。

    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++代碼：

/* 去掉收尾空格:將原字元串截取後返回新字元串 */

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

] = 

""

;}

/*length 為字元數組string的總容量*/

void

 

replaceBlank

(

char

 

string

[], 

int

 length)

{    

if

(

string

 == 

NULL

 && length <= 

0

)        

return

;    

/*originalLength 為字元串string的實際長度*/

    

int

 originalLength = 

0

;    

int

 numberOfBlank = 

0

;    

int

 i = 

0

;    

while

(

string

[i] != 

""

)    {        ++ originalLength;        

if

(

string

[i] == 

" "

)            ++ numberOfBlank;        ++ i;    }    

/*newLength 為把空格替換成"%20"之後的長度*/

    

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：調整數組中元素順序

題目： 給定一個整數數組，請實現一個函數來調整數組中數字的順序，使得所有奇數都位於偶數之前。

解題思路

此題比較簡單，我最先想到的解法是這樣：我們維護兩個指針(索引)，一個指針指向數組的第一個數字，稱之為頭指針，向右移動；一個指針指向最後一個數字，稱之為尾指針，向左移動。

圖2.0  調整數組{2，1，3，6，4，7，8，5}使得奇數位於偶數前面的過程。

註：（1）初始化兩個指針P1、P2，分別指向數組的頭部和尾部。（2）由上一步得知，指針P1指向的數字是偶數

2

，而P2指向的數字是奇數

5

，滿足條件，我們交換這兩個數字。（3） P1繼續向右移動直到指向偶數6，P2繼續向左移動直到指向奇數7。（4）交換兩個指針指向的數字。（5）P1，P2繼續移動後重疊，表明所有奇數已位於偶數前面了。

循環結束條件：兩個指針重疊時或P2指針移動到了P1指針的前面，此時退出循環。可以看出此演算法，一次循環搞定，所以時間複雜度O(n), 由於在原數組上操作，所以空間複雜度O(1)。

測試用例

• 功能測試：全是奇數、全是偶數、奇偶數存在但已排好序/未排好序。

• 特殊輸入測試： null對象、數組元素為0、有負數情況。

編碼

Java代碼：

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++;

// 奇數，索引右移

         } 

else

 

if

 (!isOdd(nums[end])) {             end--;

// 偶數，索引左移

         } 

else

 {             

// 奇偶數互換

             

int

 temp = nums[st];             nums[st] = nums[end];             nums[end] = temp;             st++;             end--;         }     }     

return

 nums; } 

// 與1做按位運算，不為0就是奇數，反之為偶數

 

private

 boolean 

isOdd

(

int

 n

) 

{     

return

 (n & 

1

) != 

0

; }

C++代碼：

// 互換

void

 

swap

(

int

* num1, 

int

* num2)

{    

int

 temp = *num1;    *num1 = *num2;    *num2 = temp;}

//判斷是否為奇數

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指針指向的是奇數，正常，向右移

        

if

 (isOdd(*pBegin))          {            pBegin++;        }        

//如果pEnd指針指向的是偶數，正常，向左移

        

else

 

if

 (!isOdd(*pEnd))        {            pEnd--;        }        

else

        {            

//否則都不正常，交換

            swap(pBegin, pEnd);        }    }}

有經驗的面試官又來了，題目難度需要升下級，??~

題目： 接上題，面試官會繼續要求改造此函數使其能夠保證原先輸入數組的奇數內部順序以及偶數內部順序，即如果輸入為{2，1，3，6，4，7，8，5}，則輸出應為{1，3，7，5，2，6，4，8}，奇數之間的相互順序和偶數之間的相互順序不得被改變。

解題思路

要想保證原數組內元素的順序，可使用O(n)的temp數組空間按順序緩存偶數，奇數依次放到原數組前面，最後將temp中偶數取出放在原數組後面。

圖 2.1 藉助O(n)的temp數組緩存偶數，進而保證原數組順序。

註：

變數解釋：st為即將插入的奇數在原數組中的索引，evenCount為緩存的偶數個數。

（1）初始化和原數組相同長度的數組temp，指針p1指向首個元素，st=eventCount=0。 （2）將p1指向的偶數

2

放入在temp中，evenCount自加1。 （3）由於p1指針向右移動一位指向的是奇數

1

，所以將p1指向的值賦值給Array[st]，此時還st=0，賦值完成後st自加1。 （8）依次邏輯，直到循環結束時，已完成原數組中奇數元素按順序插入到了頭部，偶數按順序緩存在了temp數組中，即圖中狀態。

上圖展示了偶數按順序緩存到temp數組中，奇數按順序放到原數組前面。

最後將temp數組中的偶數依次按序放在原數組後面，這個過程較簡單，就沒體現到圖中，具體請看下面代碼實現。

測試用例

同上一題。這裡就省略了。

編碼

Java代碼：

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) {                 

// 將奇數依次放在原數組前面

                 nums[st] = nums[i];             }             st++;         }     }     

if

 (evenCount > 

0

) {         

for

 (

int

 i = st; i < nums.length; i++) {             nums[i] = temp[i - st];         }     }     

return

 nums;}

C++代碼：

void v2_1_solution(

int

* nums,unsigned 

int

 

len

){     

if

 (!nums || 

len

 <= 

1

) {         

return

;     }     

int

 st = 

0

;     

int

 evenCount = 

0

;     

// 申請的內存空間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) {                 

// 將奇數依次放在原數組前面

                 nums[st] = nums[i];             }            st++;         }     }     

// 將temp中偶數取出放在原數組後面

     

if

 (evenCount > 

0

) {         

for

 (

int

 i = st; i < 

len

; i++) {             nums[i] = temp[i - st];         }     } }

學習心得&解題套路

細心的讀者可能發現了，文中解題過程大致是這樣的：分析思路->測試用例->編碼->調試並通過測試。你可能會問怎樣才能很好的掌握演算法編程呢？我的建議是：有事沒事刷道題吧，勤加練習，終成大神。哈哈，請輕拍。

關於解題思路

（詳見劍指offer）

• 畫圖讓抽象問題形象化

• 舉例讓抽象問題具體化

• 分解讓複雜問題簡單化

各種數據結構及演算法書籍： 大話數據結構、劍指offer、演算法導論等等。在線編程：LeetCode、牛客網、七月在線菜鳥練手推薦：C++在線工具

總結

現在去大公司面試，都會有演算法題，所以不是你想不想掌握它，而是公司會通過它把一部分人淘汰掉，說的可能有點嚇人，但現實就是這樣操作的。文中所有代碼均編譯運行並通過測試用例檢查，由於篇幅限制，代碼沒有貼全，完整的可運行代碼請點擊鏈接獲取： https://github.com/yangjiantao/DSAA。 由於作者水平有限，文中錯誤之處在所難免，敬請讀者指正。

— — — END — — —

推薦閱讀

青春少女萌萌的愛情故事

給大家推薦個開源項目

那些年面試求職中踩過的坑

推薦閱讀：