前言
本系列涧至，希望使用Python通關(guān)LeetCode腹躁，暫時(shí)開(kāi)始做簡(jiǎn)單題。
初次刷LeetCode目的是為了提高自己的算法能力南蓬，我的解法在時(shí)間復(fù)雜度上肯定不是最優(yōu)的纺非，忘各位指導(dǎo)哑了。
另外，LeetCode早已推出了中文官網(wǎng)https://leetcode-cn.com烧颖，希望各位親自嘗試這些題目弱左。
21. 合并兩個(gè)有序鏈表
將兩個(gè)有序鏈表合并為一個(gè)新的有序鏈表并返回。新鏈表是通過(guò)拼接給定的兩個(gè)鏈表的所有節(jié)點(diǎn)組成的炕淮。
示例：
輸入：1->2->4, 1->3->4
輸出：1->1->2->3->4->4
思路：我看到有些人并沒(méi)有仔細(xì)看題目科贬，而以為首先要使用Python實(shí)現(xiàn)一個(gè)鏈表才能做這道題，其實(shí)仔細(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已為我們定義好了鏈表這個(gè)數(shù)據(jù)結(jié)構(gòu)榜掌。
鏈表是一種遞歸的數(shù)據(jù)結(jié)構(gòu)，它或者為空（null）乘综，或者是指向一個(gè)結(jié)點(diǎn)（node）的引用憎账，該節(jié)點(diǎn)還有一個(gè)元素和一個(gè)指向另一條鏈表的引用。
清楚了鏈表的定義卡辰，就很簡(jiǎn)單了只需要依次比較l1和l2所指向的數(shù)字胞皱，大的數(shù)字進(jìn)入新的鏈表，以此類推九妈。其實(shí)搞清楚了鏈表這個(gè)數(shù)據(jù)結(jié)構(gòu)就很容易解決了這個(gè)問(wèn)題反砌。
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ù)項(xiàng)
給定一個(gè)排序數(shù)組，你需要在原地刪除重復(fù)出現(xiàn)的元素萌朱，使得每個(gè)元素只出現(xiàn)一次宴树，返回移除后數(shù)組的新長(zhǎng)度。
不要使用額外的數(shù)組空間晶疼，你必須在原地修改輸入數(shù)組并在使用 O(1) 額外空間的條件下完成酒贬。
示例 1：
給定數(shù)組 nums = [1,1,2],
函數(shù)應(yīng)該返回新的長(zhǎng)度 2, 并且原數(shù)組 nums 的前兩個(gè)元素被修改為 1, 2。
你不需要考慮數(shù)組中超出新長(zhǎng)度后面的元素翠霍。
示例 2：
給定 nums = [0,0,1,1,1,2,2,3,3,4],
函數(shù)應(yīng)該返回新的長(zhǎng)度 5, 并且原數(shù)組 nums 的前五個(gè)元素被修改為 0, 1, 2, 3, 4锭吨。
你不需要考慮數(shù)組中超出新長(zhǎng)度后面的元素。
思路：本題的關(guān)鍵就是原地算法寒匙，不能使用額外的數(shù)組零如，只能在原數(shù)組中進(jìn)行操作。我的思路很簡(jiǎn)單锄弱，就是將所有重復(fù)的數(shù)字移動(dòng)到數(shù)組的末尾考蕾，在循環(huán)對(duì)比過(guò)后，移除末尾重復(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. 移除元素
給定一個(gè)數(shù)組 nums 和一個(gè)值 val，你需要原地移除所有數(shù)值等于 val 的元素狈谊，返回移除后數(shù)組的新長(zhǎng)度。
不要使用額外的數(shù)組空間，你必須在原地修改輸入數(shù)組并在使用 O(1) 額外空間的條件下完成河劝。
元素的順序可以改變壁榕。你不需要考慮數(shù)組中超出新長(zhǎng)度后面的元素。
示例 1:
給定 nums = [3,2,2,3], val = 3,
函數(shù)應(yīng)該返回新的長(zhǎng)度 2, 并且 nums 中的前兩個(gè)元素均為 2赎瞎。
你不需要考慮數(shù)組中超出新長(zhǎng)度后面的元素牌里。
思路：本題的思路與上一題完全一致，只需要將與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. 實(shí)現(xiàn)strStr()
實(shí)現(xiàn) strStr() 函數(shù)。
給定一個(gè) haystack 字符串和一個(gè) needle 字符串敞临，在 haystack 字符串中找出 needle 字符串出現(xiàn)的第一個(gè)位置 (從0開(kāi)始)态辛。如果不存在，則返回 -1挺尿。
示例 1:
輸入: haystack = "hello", needle = "ll"
輸出: 2
示例 2:
輸入: haystack = "aaaaa", needle = "bba"
輸出: -1
思路：這道題的目的是字符串B在字母串A中出現(xiàn)的第一個(gè)索引值奏黑。最直觀的方法依然是使用循環(huán)比較的辦法，但是這次我們不需要完全循環(huán)完一整個(gè)字符串编矾，當(dāng)字符串A剩余的字符數(shù)小于字符串B時(shí)熟史，就沒(méi)有必要進(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. 搜索插入位置
給定一個(gè)排序數(shù)組和一個(gè)目標(biāo)值窄俏，在數(shù)組中找到目標(biāo)值蹂匹，并返回其索引。如果目標(biāo)值不存在于數(shù)組中凹蜈，返回它將會(huì)被按順序插入的位置怒详。
你可以假設(shè)數(shù)組中無(wú)重復(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
思路：本題就非常直觀了踪区，若這個(gè)數(shù)字不在原數(shù)組中就插入這個(gè)數(shù)組中昆烁。之后只要查找到這個(gè)數(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. 最大子序和
給定一個(gè)整數(shù)數(shù)組 nums 缎岗，找到一個(gè)具有最大和的連續(xù)子數(shù)組（子數(shù)組最少包含一個(gè)元素）静尼，返回其最大和。
示例:
輸入: [-2,1,-3,4,-1,2,1,-5,4],
輸出: 6
解釋: 連續(xù)子數(shù)組 [4,-1,2,1] 的和最大传泊，為 6鼠渺。
思路：這道題很簡(jiǎn)單，我們循環(huán)數(shù)組進(jìn)行求和眷细，前兩位元素的和與前三位的和作比較拦盹，總是保存最大的值。當(dāng)循環(huán)到的元素出現(xiàn)負(fù)值時(shí)溪椎，理所應(yīng)當(dāng)?shù)募右粋€(gè)負(fù)數(shù)普舆，和肯定是變小的恬口，所以這串子數(shù)組的末尾元素一定不會(huì)是負(fù)數(shù)（數(shù)組長(zhǎng)度為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. 最后一個(gè)單詞的長(zhǎng)度
給定一個(gè)僅包含大小寫字母和空格 ' ' 的字符串沼侣，返回其最后一個(gè)單詞的長(zhǎng)度祖能。
如果不存在最后一個(gè)單詞，請(qǐng)返回 0 蛾洛。
說(shuō)明：一個(gè)單詞是指由字母組成养铸，但不包含任何空格的字符串。
示例:
輸入: "Hello World"
輸出: 5
思路：這道題用Python難道不算作弊么轧膘？钞螟？首先使用split()方法，將字符串分割為一個(gè)list谎碍，再返回最后一個(gè)長(zhǎng)度不為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.加一
給定一個(gè)由整數(shù)組成的非空數(shù)組所表示的非負(fù)整數(shù)鳞滨，在該數(shù)的基礎(chǔ)上加一。
最高位數(shù)字存放在數(shù)組的首位椿浓， 數(shù)組中每個(gè)元素只存儲(chǔ)一個(gè)數(shù)字太援。
你可以假設(shè)除了整數(shù) 0 之外，這個(gè)整數(shù)不會(huì)以零開(kāi)頭扳碍。
示例 1:
輸入: [1,2,3]
輸出: [1,2,4]
解釋: 輸入數(shù)組表示數(shù)字 123提岔。
示例 2:
輸入: [4,3,2,1]
輸出: [4,3,2,2]
解釋: 輸入數(shù)組表示數(shù)字 4321。
思路：這道題有一個(gè)很傻瓜的思路笋敞，就是把這個(gè)list轉(zhuǎn)換成一個(gè)整數(shù)碱蒙，然后對(duì)這個(gè)數(shù)字進(jìn)行加一，最后再分割為一個(gè)list夯巷。這個(gè)方法雖然直觀易懂赛惩，但是時(shí)間復(fù)雜度較高。我還沒(méi)有理解其他的方法趁餐，所以暫時(shí)展現(xiàn)這個(gè)比較直觀的方法喷兼。
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
