1.兩數之和

題目描述：給定一個整數數組 nums 和一個目標值 target，請你在該數組中找出和爲目標值的那兩整數，並返回他們的數組下標。你可以假設每種輸入只會對應一個答案。但是，數組中同一個元素不能使用兩遍。

示例：給定 nums = [2, 7, 11, 15], target = 9。因爲 nums[0] + nums[1] = 2 + 7 = 9，所以返回 [0, 1]。

這道題的總體上思路是num[i]一定位於數組中，所以只要找出target-num[i]在數組中的位置即可。

第一種方法是遍歷數組，但每一次循環都會利用切片將i之前的元素轉化成一個新的數組，這樣做是爲了應對數組中出現類似於[2,3,3,5]相鄰數字相等的狀況。如果找到了符合的值就賦給j，由於j總是位於i之前，所以返回[j,i]。

def twoSum(nums, target):
    j = -1
    for i in range(1,len(nums)):
        new_nums = nums[:i]
        if target-nums[i] in new_nums:
            j = new_nums.index(target-nums[i])
            break
    if j>=0:
        return [j,i]

第二種方法是利用哈希表，首先初始化一個空字典，遍歷數組，如果target-num[i]在字典中，就返回該值的索引和i；如果未出現在字典中，就將該值作爲key，該索引作爲value傳入字典中，等下次循環再判斷。

def twoSum(nums, target):
    dict_ = {}
    for i in range(len(nums)):
        if target-nums[i] in dict_:
            return [dict_[target-nums[i]],i]
        else:
            dict_[nums[i]] = i

• 方法一用時548ms，內存消耗14.8MB
• 方法二用時68ms，內存消耗14.9MB

7.整數反轉

題目描述：題目描述給出一個 32 位的有符號整數，你需要將這個整數中每位上的數字進行反轉。

示例：輸入: 123輸出: 32、輸入: -123輸出: -321、輸入: 120輸出: 21

注意：假設我們的環境只能存儲得下 32 位的有符號整數，則其數值範圍爲 [−231,  231 − 1]。請根據這個假設，如果反轉後整數溢出那麼就返回 0。

第一種方法是利用字符串，首先對字符串反轉，這一步可以利用切片或者內置函數reverse。如果輸入數字$x\geq0$，直接將反轉後的字符串轉爲整型賦值給num；如果$x<0$，需要先在字符串前加上"-"再轉爲整型賦值給num。若num處於範圍之內直接返回，否則返回0。

def reverse(x):
    str1 = str(abs(x))
    str2 = str1[::-1]
    if x>=0:
        num = int(str2)
    else:
        str3 = '-'+str2
        num = int(str3)
    if num < (-2) ** 31 or num > 2 ** 31 - 1:
        return 0
    else:
        return num

第二種方法是利用數學方法，利用整數除以10取餘可以得到該整數的最後一位、整數地板除可以去除該整數的最後一位兩個性質相結合就可以得到反轉後的數字，之後的判斷與上述方法同理。

def reverse(x):
    temp = abs(x)
    i = len(str(temp))
    num = 0
    while i>0:
        num = num * 10 + temp % 10
        temp = temp // 10
        i -= 1
    if x<0:
        num = -num
    if num<(-2)**31 or num>2**31-1:
        return 0
    else:
        return num

• 方法一用時52ms，內存消耗13.7MB
• 方法二用時52ms，內存消耗13.4MB

13. 羅馬數字轉整數

示例：輸入: "III"輸出: 3、輸入: "IV"輸出: 4、輸入: "MCMXCIV"輸出: 1994(解釋: M = 1000, CM = 900, XC = 90, IV = 4)。

第一種方法是利用字典(哈希表)暴力破解，將所有可能出現的組合按照羅馬數字作爲key、阿拉伯數字作爲value的格式存入字典中，對於輸入的字符串，如果一個字符對應值小於其右邊的值，那麼這個組合必定是IV、IX、XL、XC、CD、CM其中一個。

那麼就可以利用切片在字符串中截取兩位，在字典中查詢這個組合的對應值，並且下標也需後移兩位；否則只需在字典中查詢該字符對應值，下標後移一位即可。

def romanToInt(self, s: str) -> int:
    dict_ = {"I": 1, "IV":4,"V": 5,"IX":9, "X": 10, "XL":40,"L": 50,
             "XC":90,"C": 100,"CD":400,"D": 500, "CM":900,"M": 1000}
    sum = 0
    i = 0
    while i< len(s) - 1:
        if dict_[s[i]] < dict_[s[i + 1]]:
            sum += dict_[s[i:i + 2]]
            i += 2
        else:
            sum += dict_[s[i]]
            i += 1
    if i >= len(s):
        return sum
    else:
        return sum + dict_[s[-1]]

最後爲什麼又會增加一個判斷呢？是因爲i的範圍是(0,len(s)-1)，所以最後需要查詢的可能是一個組合，也可能是單個字符，需要區分這兩種可能性。

第二種方法也是利用哈希表，這種方法也是遍歷整個字符串，如果一個字符小於它右邊的字符，那麼在和的基礎上減去這個字符對應值，比如IV不就是-1+5=4嘛；否則就直接在和的基礎上加上該字符對應值即可，由於每次只判斷一個字符，所以也無需對結果進行上面的區分。

def romanToInt(self, s: str) -> int:
    dict_ = {"I":1,"V":5,"X":10,"L":50,"C":100,"D":500,"M":1000}
    sum = 0
    for i in range(len(s)-1):
        if dict_[s[i]]<dict_[s[i+1]]:
            sum -= dict_[s[i]]
        else:
            sum += dict_[s[i]]
    return sum + dict_[s[-1]]

• 方法一用時76ms，內存消耗13.6MB
• 方法二用時64ms，內存消耗13.7MB

14. 最長公共前綴

題目描述：編寫一個函數來查找字符串數組中的最長公共前綴。如果不存在公共前綴，返回空字符串 ""。

示例：輸入: ["flower","flow","flight"]輸出: "fl"、輸入: ["dog","racecar","car"]輸出: ""。

前綴是指字符串最後一個字符之前所有字符

第一種方法是利用兩層循環嵌套，因爲公共前綴的長度一定是小於等於數組中最短字符長度的，所以第一層循環用來切分字符串，利用第一個字符串str0與其餘字符串做比較，如果str0更長，則其切分後的長度需要與其相比較的字符串相等。

第二層循環是在str0長度範圍內，依次比較str0和其他字符串每個對應位置上的字符是否相等，如果不相等則更新str0並利用break退出該層循環，再比較下一個字符串。

def longestCommonPrefix(strs):
    if len(strs) == 0:
        return ""
    str0 = strs[0]
    for i in strs:
        if len(str0) > len(i):
            str0 = str0[:len(i)]
        for j in range(len(str0)):
            if str0[j] != i[j]:
                str0 = str0[:j]
                break
    return str0

第二種方法利用了zip和set兩個方法相結合，下面結合程序一些斷點運行截圖進行講解。

def longestCommonPrefix(strs):
    words = list(zip(*strs))
    str_ = ''
    for i in words:
        word = list(set(i))
        if len(word) == 1:
            str_ += word[0]
        else:
            break
    return str_

可以看到zip(*strs)會將每個字符串相應位置上的字符存入一個元組中，元祖的個數就是輸入中字符串最小長度。然後遍歷words這個列表，對每個元祖利用set方法去重，如果去重後得到新列表的長度爲1，那麼證明這個字符是三者共有的，就可以將其加入到定義的空字符串str_中；否則就跳出循環返回字符串str_。

• 方法一用時48ms，內存消耗13.6MB
• 方法二用時36ms，內存消耗13.7MB

20.有效的括號

題目描述：給定一個只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判斷字符串是否有效。有效字符串需滿足：左括號必須用相同類型的右括號閉合；左括號必須以正確的順序閉合。注意空字符串可被認爲是有效字符串。

示例：輸入: "()[]{}"輸出: true、輸入: "(]"輸出: false、輸入: "([)]"輸出: false、輸入: "{[]}"輸出: true。

第一種方法利用了內置方法replace，根據示例可以看到每組括號都需要左右括號對應才能消除，只要字符串中含有可以消除的括號，就可以將其替換成空字符串，利用循環無腦替換，最後字符串如果爲空就返回True，反之則返回False。

def isValid(s):
    if len(s)%2 != 0:
        return False
    while '()' in s or '[]' in s or '{}'in s:
        s = s.replace('()','').replace('[]','').replace('{}','')
    return s==''

第二種方法利用棧的思想，首先按照右括號爲key，左括號爲value的格式傳入字典中，然後遍歷整個字符串，如果是左括號就存入棧中，然後如果是右括號則比較其對應的左括號是否與棧頂位置的左括號相同，相同的話從棧中移除，不同的話就將其存入棧中，循環過後的棧如果和最初的棧相同返回True，反之則返回False。

這裏需要注意的是在新定義棧時，需要向其中加入一個元素，防止在比較的時候列表下標溢出的現象發生。

def isValid(s):
    if s == '':
        return True
    dict = {')':'(',']':'[','}':'{'}
    stack = [0]
    for i in s:
        if i in ['(','[','{']:
            stack.append(i)
        elif dict[i] == stack[-1]:
            stack.pop()
        else:
            stack.append(i)
    return stack == [0]

• 方法一用時56ms，內存消耗13.7MB
• 方法二用時44ms，內存消耗13.7MB

26. 刪除排序數組中的重複項

題目描述：給定一個排序數組，你需要在 原地 刪除重複出現的元素，使得每個元素只出現一次，返回移除後數組的新長度。不要使用額外的數組空間，你必須在 原地 修改輸入數組 並在使用 O(1) 額外空間的條件下完成。

示例：給定 nums = [0,0,1,1,1,2,2,3,3,4],函數應該返回新的長度5，並且原數組 nums 的前五個元素被修改爲 0, 1, 2, 3, 4，不需要考慮數組中超出新長度後面的元素。

在編寫程序的時候一定要注意題目中兩個關鍵的要求，一個是不要使用額外的空間，所以這裏不能定義新的數組；另一個是不需要考慮數組中超出新長度後面的元素，在需要滿足示例中的要求的基礎上可以選擇刪除、覆蓋、交換多種方式。

第一種方法利用雙指針，分別初始化爲0和1，遍歷輸入數組，如果兩個指針對應元素值相等，則移除後面指針對應元素；否則就將兩個指針分別加一，繼續排查數組中剩下的元素。

def removeDuplicates(nums):
    market1,market2 = 0, 1
    while market2<len(nums):
        if nums[market1]==nums[market2]:
            nums.pop(market2)
        else:
            market1 += 1
            market2 += 1
    return len(nums)

第二種方法是將數組自後向前遍歷，如果從前向後遍歷的話，每當刪除一個元素時，它後面所有元素的下標都會變，而且也容易有下溢出的情況。而自後向前很好的解決了這個問題，因爲輸入數組總是有序數組嘛，所以值相等的永遠相鄰，只需要比較兩個相鄰元素是否相等，若相等則刪去後面的元素。

def removeDuplicates(nums):
    for i in range(len(nums)-1,0,-1):
        if nums[i] == nums[i-1]:
            nums.pop(i)
    return len(nums)

這裏在介紹一下第三種方法(官方解法)，這種方法也是利用雙指針，但它體現的是覆蓋而不是是刪除，首先定義第一個指針i=0，然後利用第二個指針j遍歷數組，如果j與i對應元素值不相等，則將j的值賦給i+1，隨之指針i也後移一位，這樣i+1就是新數組的長度，並且每個元素都不重複。

def removeDuplicates(nums) int:
    i = 0
    for j in range(len(nums)):
        if nums[j]!=nums[i]:
            nums[i+1] = nums[j]
            i += 1
    return i+1

• 方法一用時72ms，內存消耗14.8MB
• 方法二用時56ms，內存消耗14.7MB
• 方法三用時44ms，內存消耗14.7MB

28. 實現 strStr()

題目描述：給定一個 haystack 字符串和一個 needle 字符串，在 haystack 字符串中找出 needle 字符串出現的第一個位置 (從0開始)。如果不存在，則返回-1。

示例：輸入: haystack = "hello", needle = "ll"輸出: 2、輸入: haystack = "aaaaa", needle = "bba"輸出: -1。

第一種方法就是暴力破解，問題是在haystack中找到needle出現的第一個位置，這個位置一定是在0到len(haystack)-len(needle)+1之間，因爲剩下的字符串也要匹配嘛。在haystack中利用切片方法搜尋與needle相同的字符串，找到返回第一個位置對應下標，反之返回-1。

def strStr(haystack,needle):
    m,n = len(haystack),len(needle)
    for i in range(0,m-n+1):
        if needle == haystack[i:i+n]:
            return i
    return -1

第二種方法是利用雙指針方法，利用兩個指針遍歷兩個數組，比較對應位置字符是否相同，相同的話兩個指針分別加一。不相同的話，如果needle數組中的指針移動過了，則需要將其重置，haystack數組指針則回到二者匹配開始的下一位重新匹配；如果needle數組中的指針未移動，只需將haystack數組指針後移一位即可。

例如haystack="ababd",needle="abd"，二個數組下標爲3時，即a和d不匹配，那麼haystack數組的指針要指向第一個b的位置，而needle數組的指針則指向a。

def strStr(haystack,needle):
    m,n = len(haystack),len(needle)
    mar1,mar2=0,0
    while mar1<m and mar2<n:
        if haystack[mar1] == needle[mar2]:
            mar1 += 1
            mar2 += 1
        else:
            if mar2>0:
                mar1 = mar1-mar2+1 #回到匹配的下一位
                mar2 = 0
            else:
                mar1 += 1
    return mar1-n if mar2==n else -1

• 方法一用時28ms，內存消耗14.8MB
• 方法二用時60ms，內存消耗14.7MB

35. 搜索插入位置

題目描述：給定一個排序數組和一個目標值，在數組中找到目標值，並返回其索引。如果目標值不存在於數組中，返回它將會被按順序插入的位置。你可以假設數組中無重複元素。

示例：輸入: [1,3,5,6], 5輸出: 2、輸入: [1,3,5,6], 2、輸出: 1、輸入: [1,3,5,6], 7輸出: 4。

第一種方法利用單層循環查找，因爲輸入數組是排序數組，所以只需要找到數組中第一個大於等於target元素的下標即可，如果等於那麼該位置就是target在數組中的位置，如果是大於那麼該位置正好是target需要插入的位置；若沒有符合條件的元素，則證明target最大，需要插入至列表最後。

def searchInsert(nums,target):
    mar = 0
    while mar<len(nums):
        if nums[mar] >= target:
            return mar
        mar += 1
    return len(nums)

第二種方法是二分查找法，首先初始化一個左指針left和右指針right，並在二者之間找到處於中間位置的下標mid。如果該位置元素小於target，下次查找位於mid+1與right之間的元素；如果該位置元素大於target，則下次查找位於left與mid-1之間的元素；如果兩者相等(target在數組中)，則直接返回mid，反之返回左指針left。

def searchInsert(nums,target):
    left = 0
    right = len(nums) - 1
    while (left <= right):
        mid = (right + left) // 2
        if nums[mid] < target:
            left = mid + 1
        elif nums[mid] > target:
            right = mid - 1
        else:
            return mid
    return left

• 方法一用時44ms，內存消耗14.1MB
• 方法二用時36ms，內存消耗14.4MB