前言
本系列，希望使用Python通关LeetCode，暂时开始做简单题。
初次刷LeetCode目的是为了提高自己的算法能力，我的解法在时间复杂度上肯定不是最优的，忘各位指导。
另外，LeetCode早已推出了中文官网https://leetcode-cn.com，希望各位亲自尝试这些题目。
21. 合并两个有序链表
将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例：
输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4
思路：我看到有些人并没有仔细看题目，而以为首先要使用Python实现一个链表才能做这道题，其实仔细观察题目中的代码输入区域可以看到。
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
这里LeetCode已为我们定义好了链表这个数据结构。
链表是一种递归的数据结构，它或者为空（null），或者是指向一个结点（node）的引用，该节点还有一个元素和一个指向另一条链表的引用。
清楚了链表的定义，就很简单了只需要依次比较l1和l2所指向的数字，大的数字进入新的链表，以此类推。其实搞清楚了链表这个数据结构就很容易解决了这个问题。
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. 删除排序数组中的重复项
给定一个排序数组，你需要在原地删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。
不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。
示例 1：
给定数组 nums = [1,1,2],
函数应该返回新的长度 2, 并且原数组 nums 的前两个元素被修改为 1, 2。
你不需要考虑数组中超出新长度后面的元素。
示例 2：
给定 nums = [0,0,1,1,1,2,2,3,3,4],
函数应该返回新的长度 5, 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4。
你不需要考虑数组中超出新长度后面的元素。
思路：本题的关键就是原地算法，不能使用额外的数组，只能在原数组中进行操作。我的思路很简单，就是将所有重复的数字移动到数组的末尾，在循环对比过后，移除末尾重复的部分，这样就完成了。
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. 移除元素
给定一个数组 nums 和一个值 val，你需要原地移除所有数值等于 val 的元素，返回移除后数组的新长度。
不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。
元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
示例 1:
给定 nums = [3,2,2,3], val = 3,
函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。
你不需要考虑数组中超出新长度后面的元素。
思路：本题的思路与上一题完全一致，只需要将与val相等的元素移到末尾，在处理完移除重复部分即可。
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. 实现strStr()
实现 strStr() 函数。
给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在，则返回 -1。
示例 1:
输入: haystack = "hello", needle = "ll"
输出: 2
示例 2:
输入: haystack = "aaaaa", needle = "bba"
输出: -1
思路：这道题的目的是字符串B在字母串A中出现的第一个索引值。最直观的方法依然是使用循环比较的办法，但是这次我们不需要完全循环完一整个字符串，当字符串A剩余的字符数小于字符串B时，就没有必要进行循环了。
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. 搜索插入位置
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
你可以假设数组中无重复元素。
示例 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
思路：本题就非常直观了，若这个数字不在原数组中就插入这个数组中。之后只要查找到这个数字在数组中的索引即可。
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. 最大子序和
给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
示例:
输入: [-2,1,-3,4,-1,2,1,-5,4],
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
思路：这道题很简单，我们循环数组进行求和，前两位元素的和与前三位的和作比较，总是保存最大的值。当循环到的元素出现负值时，理所应当的加一个负数，和肯定是变小的，所以这串子数组的末尾元素一定不会是负数（数组长度为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.加一
给定一个由整数组成的非空数组所表示的非负整数，在该数的基础上加一。
最高位数字存放在数组的首位， 数组中每个元素只存储一个数字。
你可以假设除了整数 0 之外，这个整数不会以零开头。
示例 1:
输入: [1,2,3]
输出: [1,2,4]
解释: 输入数组表示数字 123。
示例 2:
输入: [4,3,2,1]
输出: [4,3,2,2]
解释: 输入数组表示数字 4321。
思路：这道题有一个很傻瓜的思路，就是把这个list转换成一个整数，然后对这个数字进行加一，最后再分割为一个list。这个方法虽然直观易懂，但是时间复杂度较高。我还没有理解其他的方法，所以暂时展现这个比较直观的方法。
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
