前言

本系列，希望使用Python通關(guān)LeetCode，暫時開始做簡單題。
初次刷LeetCode目的是為了提高自己的算法能力，我的解法在時間復(fù)雜度上肯定不是最優(yōu)的，忘各位指導(dǎo)。
另外，LeetCode早已推出了中文官網(wǎng)https://leetcode-cn.com，希望各位親自嘗試這些題目。

21. 合并兩個有序鏈表

將兩個有序鏈表合并為一個新的有序鏈表并返回。新鏈表是通過拼接給定的兩個鏈表的所有節(jié)點組成的。

示例：
輸入：1->2->4, 1->3->4
輸出：1->1->2->3->4->4

思路：我看到有些人并沒有仔細(xì)看題目，而以為首先要使用Python實現(xiàn)一個鏈表才能做這道題，其實仔細(xì)觀察題目中的代碼輸入?yún)^(qū)域可以看到。

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

這里L(fēng)eetCode已為我們定義好了鏈表這個數(shù)據(jù)結(jié)構(gòu)。

鏈表是一種遞歸的數(shù)據(jù)結(jié)構(gòu)，它或者為空（null），或者是指向一個結(jié)點（node）的引用，該節(jié)點還有一個元素和一個指向另一條鏈表的引用。

清楚了鏈表的定義，就很簡單了只需要依次比較l1和l2所指向的數(shù)字，大的數(shù)字進(jìn)入新的鏈表，以此類推。其實搞清楚了鏈表這個數(shù)據(jù)結(jié)構(gòu)就很容易解決了這個問題。

class Solution:
    def mergeTwoLists(self, l1, l2):
        """
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """
        if l1 is None:
            return l2
        if l2 is None:
            return l1

        head = ListNode(0)
        current = head

        while l1 is not None and l2 is not None:
            if l1.val < l2.val:
                current.next = l1
                l1 = l1.next
            else:
                current.next = l2
                l2 = l2.next
            current = current.next

        if l1 is None:
            current.next=l2
        elif l2 is None:
            current.next=l1
        return head.next
        

26. 刪除排序數(shù)組中的重復(fù)項

給定一個排序數(shù)組，你需要在原地刪除重復(fù)出現(xiàn)的元素，使得每個元素只出現(xiàn)一次，返回移除后數(shù)組的新長度。

不要使用額外的數(shù)組空間，你必須在原地修改輸入數(shù)組并在使用 O(1) 額外空間的條件下完成。

示例 1：
給定數(shù)組 nums = [1,1,2],
函數(shù)應(yīng)該返回新的長度 2, 并且原數(shù)組 nums 的前兩個元素被修改為 1, 2。
你不需要考慮數(shù)組中超出新長度后面的元素。

示例 2：
給定 nums = [0,0,1,1,1,2,2,3,3,4],
函數(shù)應(yīng)該返回新的長度 5, 并且原數(shù)組 nums 的前五個元素被修改為 0, 1, 2, 3, 4。
你不需要考慮數(shù)組中超出新長度后面的元素。

思路：本題的關(guān)鍵就是原地算法，不能使用額外的數(shù)組，只能在原數(shù)組中進(jìn)行操作。我的思路很簡單，就是將所有重復(fù)的數(shù)字移動到數(shù)組的末尾，在循環(huán)對比過后，移除末尾重復(fù)的部分，這樣就完成了。

class Solution:
    def removeDuplicates(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        i = 0
        for j in range(1, len(nums)):
            if nums[j] != nums[i]:
                i += 1
                nums[i] = nums[j]
        del nums[i+1:len(nums)]
            
        return len(nums)
        

27. 移除元素

給定一個數(shù)組 nums 和一個值 val，你需要原地移除所有數(shù)值等于 val 的元素，返回移除后數(shù)組的新長度。
不要使用額外的數(shù)組空間，你必須在原地修改輸入數(shù)組并在使用 O(1) 額外空間的條件下完成。
元素的順序可以改變。你不需要考慮數(shù)組中超出新長度后面的元素。

示例 1:
給定 nums = [3,2,2,3], val = 3,
函數(shù)應(yīng)該返回新的長度 2, 并且 nums 中的前兩個元素均為 2。
你不需要考慮數(shù)組中超出新長度后面的元素。

思路：本題的思路與上一題完全一致，只需要將與val相等的元素移到末尾，在處理完移除重復(fù)部分即可。

class Solution:
    def removeElement(self, nums, val):
        """
        :type nums: List[int]
        :type val: int
        :rtype: int
        """
        i = 0
        for j in range(len(nums)):
            if nums[j] == val:
                nums[j], nums[i]= nums[i], nums[j]
                i += 1
        del nums[:i]
        return len(nums)

28. 實現(xiàn)strStr()

實現(xiàn) strStr() 函數(shù)。
給定一個 haystack 字符串和一個 needle 字符串，在 haystack 字符串中找出 needle 字符串出現(xiàn)的第一個位置 (從0開始)。如果不存在，則返回 -1。

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

思路：這道題的目的是字符串B在字母串A中出現(xiàn)的第一個索引值。最直觀的方法依然是使用循環(huán)比較的辦法，但是這次我們不需要完全循環(huán)完一整個字符串，當(dāng)字符串A剩余的字符數(shù)小于字符串B時，就沒有必要進(jìn)行循環(huán)了。

class Solution:
    def strStr(self, haystack, needle):
        """
        :type haystack: str
        :type needle: str
        :rtype: int
        """

        len1 = len(haystack)
        len2 = len(needle)

        for i in range(len1-len2+1):
            if haystack[i:i+len2] == needle:
                return i
        return -1
        

35. 搜索插入位置

給定一個排序數(shù)組和一個目標(biāo)值，在數(shù)組中找到目標(biāo)值，并返回其索引。如果目標(biāo)值不存在于數(shù)組中，返回它將會被按順序插入的位置。

你可以假設(shè)數(shù)組中無重復(fù)元素。

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

思路：本題就非常直觀了，若這個數(shù)字不在原數(shù)組中就插入這個數(shù)組中。之后只要查找到這個數(shù)字在數(shù)組中的索引即可。

class Solution:
    def searchInsert(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        if target not in nums:
            nums.append(target)
        nums = sorted(nums)

        for i in range(len(nums)):
            if nums[i] == target:
                return i
        

53. 最大子序和

給定一個整數(shù)數(shù)組 nums ，找到一個具有最大和的連續(xù)子數(shù)組（子數(shù)組最少包含一個元素），返回其最大和。

示例:
輸入: [-2,1,-3,4,-1,2,1,-5,4],
輸出: 6
解釋: 連續(xù)子數(shù)組 [4,-1,2,1] 的和最大，為 6。

思路：這道題很簡單，我們循環(huán)數(shù)組進(jìn)行求和，前兩位元素的和與前三位的和作比較，總是保存最大的值。當(dāng)循環(huán)到的元素出現(xiàn)負(fù)值時，理所應(yīng)當(dāng)?shù)募右粋€負(fù)數(shù)，和肯定是變小的，所以這串子數(shù)組的末尾元素一定不會是負(fù)數(shù)（數(shù)組長度為1除外）。

class Solution:
    def maxSubArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if not nums:
            return 0
        current = nums[0]
        m = current
        for i in range(1, len(nums)):
            if current < 0:
                current = 0
            current += nums[i]
            m = max(current, m)
        return m

58. 最后一個單詞的長度

給定一個僅包含大小寫字母和空格 ' ' 的字符串，返回其最后一個單詞的長度。
如果不存在最后一個單詞，請返回 0 。

說明：一個單詞是指由字母組成，但不包含任何空格的字符串。

示例:
輸入: "Hello World"
輸出: 5

思路：這道題用Python難道不算作弊么？？首先使用split()方法，將字符串分割為一個list，再返回最后一個長度不為0的元素就可以了啊.....

class Solution:
    def lengthOfLastWord(self, s):
        """
        :type s: str
        :rtype: int
        """
        if len(s) == 0:
            return 0
        
        s_list = s.split(' ')

        for word in s_list[::-1]:
            if len(word) > 0:
                return len(word)
        return 0

66.加一

給定一個由整數(shù)組成的非空數(shù)組所表示的非負(fù)整數(shù)，在該數(shù)的基礎(chǔ)上加一。
最高位數(shù)字存放在數(shù)組的首位， 數(shù)組中每個元素只存儲一個數(shù)字。
你可以假設(shè)除了整數(shù) 0 之外，這個整數(shù)不會以零開頭。

示例 1:
輸入: [1,2,3]
輸出: [1,2,4]
解釋: 輸入數(shù)組表示數(shù)字 123。
示例 2:
輸入: [4,3,2,1]
輸出: [4,3,2,2]
解釋: 輸入數(shù)組表示數(shù)字 4321。

思路：這道題有一個很傻瓜的思路，就是把這個list轉(zhuǎn)換成一個整數(shù)，然后對這個數(shù)字進(jìn)行加一，最后再分割為一個list。這個方法雖然直觀易懂，但是時間復(fù)雜度較高。我還沒有理解其他的方法，所以暫時展現(xiàn)這個比較直觀的方法。

class Solution:
    def plusOne(self, digits):
        """
        :type digits: List[int]
        :rtype: List[int]
        """
        num = int(''.join([str(x) for x in digits])) + 1
        num = [int(x) for x in str(num)]
        return num