leetcode

反轉字符串

編寫一個函數，其作用是將輸入的字符串反轉過來。輸入字符串以字符數組 s 的形式給出。

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

示例 1：

輸入：s = [“h”,“e”,“l”,“l”,“o”]
輸出：[“o”,“l”,“l”,“e”,“h”]
示例 2：

輸入：s = [“H”,“a”,“n”,“n”,“a”,“h”]
輸出：[“h”,“a”,“n”,“n”,“a”,“H”]

提示：

1 <= s.length <= 105
s[i] 都是 ASCII 碼表中的可打印字符

作者：力扣 (LeetCode)
鏈接：https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/xnhbqj/
來源：力扣（LeetCode）
著作權歸作者所有。商業轉載請聯系作者獲得授權，非商業轉載請注明出處。

Solution1

python列表的reverse方法。

class Solution:
def reverseString(self, s: List[str]) -> None:
""" Do not return anything, modify s in-place instead. """
s.reverse()
return s

Solution2

• python列表的切片。步長為-1即逆序。
  將逆序列表賦值給切片，返回原列表s。
• 注意：切片是淺拷貝。s[:]和s內存地址不同，但指向同一個子對象。
  將逆序列表返回給切片s[:]，即s的值變為逆序的列表，結果返回s，符合題目要求“不要給另外的數組分配額外的空間，你必須原地修改輸入數組”。
• 深拷貝淺拷貝
  https://www.runoob.com/w3cnote/python-understanding-dict-copy-shallow-or-deep.html

class Solution:
def reverseString(self, s: List[str]) -> None:
""" Do not return anything, modify s in-place instead. """
s[:] = s[::-1]
return s

Solution1、Solution2就是跟大家開個玩笑。接著往下看

Solution3

定義循環次數loop等於列表長度除以2取整。交換頭尾元素。

class Solution:
def reverseString(self, s: List[str]) -> None:
""" Do not return anything, modify s in-place instead. """
loop = int(len(s)/2)
for i in range(loop):
s[i],s[len(s)-1-i] = s[len(s)-1-i],s[i]
return s

Solution4

雙指針。
定義left指針、right指針，分別存儲頭尾的index。
當左指針小於右指針，結束循環。

class Solution:
def reverseString(self, s: List[str]) -> None:
""" Do not return anything, modify s in-place instead. """
left = 0
right = len(s) - 1
while left < right:
s[left],s[right] = s[right],s[left]
left += 1
right -= 1
return s