Time：2019/4/18
Title: Reverse String
Difficulty: Easy
Author: 小鹿

題目：Reverse String(反轉(zhuǎn)字符串)

Write a function that reverses a string. The input string is given as an array of characters char[].

Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.

You may assume all the characters consist of printable ascii characters.

編寫一個(gè)函數(shù)，其作用是將輸入的字符串反轉(zhuǎn)過來。輸入字符串以字符數(shù)組 char[] 的形式給出。

不要給另外的數(shù)組分配額外的空間，你必須原地修改輸入數(shù)組、使用 O(1) 的額外空間解決這一問題。

你可以假設(shè)數(shù)組中的所有字符都是 ASCII 碼表中的可打印字符。

Example 1:

Input: ["h","e","l","l","o"]
Output: ["o","l","l","e","h"]

Example 2:

Input: ["H","a","n","n","a","h"]
Output: ["h","a","n","n","a","H"]

Slove:

▉ 問題分析

1）反轉(zhuǎn)字符串，第一想到的就是將字符窗倒序存儲到數(shù)組中，可以先輸出，然后再 for 循環(huán)加入到數(shù)組中。題目中要求需要原地修改輸入數(shù)組，那么我們再想一個(gè)辦法。

2）數(shù)組中的操作，需要原地修改數(shù)組，第一想到的就是用到指針，為什么能想到用指針呢？當(dāng)你做這種數(shù)組的也好還是鏈表的也好，做多了之后，下意識的給出解決方法然后去看看可不可行。

▉ 算法思路

通過以上分析，得出兩種方法：

• 字符串反轉(zhuǎn)法
• 雙指針法

字符串反轉(zhuǎn)法：

1）字符串反轉(zhuǎn)法很簡單了，按照我們正常的思路走就可以了，首先輸出數(shù)組中的字符拼接成字符串。

2）然后從字符串尾部開始遍歷，正向輸入數(shù)組。

雙指針法：

1）定義兩個(gè)指針，分別指向字符串頭部和尾部。

2）兩個(gè)指針指向的值進(jìn)行交換。

3）注意終止條件。

• 如果為偶數(shù)，當(dāng)頭指針 - 1 等于尾指針時(shí)，反轉(zhuǎn)完畢。
• 如果為奇數(shù)，當(dāng)兩個(gè)指針相等時(shí)，反轉(zhuǎn)完畢。

▉ 測試用例

1）空字符串。

2）偶數(shù)個(gè)數(shù)的字符串。

3）奇數(shù)個(gè)數(shù)的字符串。

4）長度為 1 的字符串。

▉ 雙指針法

var reverseString = function(s) {
    //判斷輸入的字符串是否為空
   if(s.length ==0) return s;
    //定義兩個(gè)指針
    let low = 0;
    let high = s.length - 1;
    // 循環(huán)反轉(zhuǎn)字符
    while(true){
        // 分為奇數(shù)/偶數(shù)兩種可能
        if(low === high || high + 1 === low) break;
        let temp = s[low];
        s[low] = s[high];
        s[high] = temp;
        low++;
        high--;
    }
    // 返回反轉(zhuǎn)好的字符串
    return s;
};

▉ 字符串反轉(zhuǎn)法

var reverseString = function(s) {
    //判斷輸入的字符串是否為空
    if(s.length ==0) return s;
    let str = "";
    // 輸出字符串
    for(let i in s){
        str = str+`${s[i]}`;
    }
    // 反轉(zhuǎn)字符串輸入
    for(let i = s.length - 1,j = 0;i >= 0;i--,j++){
        s[j] = str.charAt(i);
    }
    //返回反轉(zhuǎn)好的字符串
    return s;
};

▉ 性能分析

字符串反轉(zhuǎn)法

• 時(shí)間復(fù)雜度：O（n）。遍歷整個(gè)數(shù)組，時(shí)間復(fù)雜度為 O（n）。
• 空間復(fù)雜度：O（n）。輸出數(shù)組需要額外的存儲空間，如果用數(shù)組存儲，需要開辟大小為 n 大小的內(nèi)存空間。如果需要數(shù)組輸出拼接字符串，空間復(fù)雜度為 O(1) 了。

雙指針法：

• 時(shí)間復(fù)雜度：O（n）。需要遍歷 n/2 的數(shù)據(jù)，時(shí)間復(fù)雜度為 O(n)。
• 空間復(fù)雜度：O（n）。只需常量級別的內(nèi)存空間，空間復(fù)雜度為O（1）。

▉ 考查內(nèi)容

1）對字符串的基本操作。

2）數(shù)組的基本操作。