6/27 每日一題 (in-place反轉列表)

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

You must do this by modifying the input array in-place with O(1) extra memory.

 

Example 1:

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

Example 2:

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

 

Constraints:

• 1 <= s.length <= 105
• s[i] is a printable ascii character.

法一

class Solution:

    def reverseString(self, s: List[str]) -> None:

        """

        Do not return anything, modify s in-place instead.

        """

        c=0

        while c < len(s)//2 : #使用指針 同時改變首相末項

            s[c], s[-1-c] = s[-1-c] , s[c] #右側運算優於左側

            #s = ["h","e","l","l","o"]為例

            #這段程式碼,c=0時, 會先記錄右側的s[-1]='o' , s[0]='h'

            #紀錄完成後在進一步指派給s[0]=s[-1] , s[-1]=s[0]

            c += 1 #指針移動

法二

如果單純的使用a=s 將s指向的物件也給a指向

他實際上就只是指向同一個物件的兩個名稱,所以修改s時, a也會同時被修改,

因為他們指向同一個記憶體位置

所以如果希望保留原始物件s的內容, 不讓a被修改,就需要使用 a=s.copy() 創建a的副本

這樣a就是一個新的列表,與s無關連

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

法三

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