Leetcode 344：Reverse String 反轉(zhuǎn)字符串（python、java）

Ajian 發(fā)布于2019-07-31 11:24 / 713人閱讀

摘要：反轉(zhuǎn)字符串公眾號愛寫編寫一個(gè)函數(shù)，其作用是將輸入的字符串反轉(zhuǎn)過來。輸入字符串以字符數(shù)組的形式給出。解題思路第一個(gè)字符與最后一個(gè)交換位置，繼而第二個(gè)與倒數(shù)第二個(gè)交換位置，一直交換到到中位數(shù)結(jié)束。持續(xù)交換它們所指向的元素，直到這兩個(gè)指針相遇。

Leetcode 344：Reverse String 反轉(zhuǎn)字符串

公眾號：愛寫bug
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"]

解題思路：

? 第一個(gè)字符與最后一個(gè)交換位置，繼而第二個(gè)與倒數(shù)第二個(gè)交換位置，一直交換到到中位數(shù) 結(jié)束。

代碼：

Java：

class Solution {
    public void reverseString(char[] s) {
        char temp;
        for(int i=0,j=s.length-1;i
Python3：
class Solution:
    def reverseString(self, s: List[str]) -> None:
        """
        Do not return anything, modify s in-place instead.
        """
        i = 0
        j = len(s) - 1
        while (i < j):
            s[i], s[j] = s[j], s[i]#交換賦值
            i+=1
            j-=1
其實(shí)py3有很多好玩的操作，比如這道題可以這樣：s=list(reversed(s)) 因?yàn)?reversed() 函數(shù)返回的是一個(gè)迭代器，所以要用 list() 函數(shù)才行。但是速度不快。
如果是字符串反轉(zhuǎn)而不是數(shù)組還可以這樣 s=s[::-1] （字符串切片：string[start:stop:step]）
總結(jié)：
這道題應(yīng)當(dāng)解釋雙指針問題最常引用的題目了，其思想是將第一個(gè)元素與末尾進(jìn)行交換，再向前移動(dòng)到下一個(gè)元素，并不斷地交換，直到它到達(dá)中間位置。
我們可以同時(shí)使用兩個(gè)指針來完成迭代：一個(gè)從第一個(gè)元素開始，另一個(gè)從最后一個(gè)元素開始。持續(xù)交換它們所指向的元素，直到這兩個(gè)指針相遇。
摘自Leetcode：
總之，使用雙指針技巧的典型場景之一是你想要
從兩端向中間迭代數(shù)組。
這時(shí)你可以使用雙指針技巧：
一個(gè)指針從始端開始，而另一個(gè)指針從末端開始。