持续更新ing…
本博客记录自己开始刷leetcode的记录，包含刷过的题目，遇到的挫折，以及找到的解决办法，希望能给其他人一些参考。
[TOC]

数组

1.两数之和（E）

暴力解法

第一道题目,也是leetcode之旅的第一题，上来直接两个for循环

class Solution:
    def twoSum(self, nums, target):
        for i in range(len(nums)):
            for j in range(i+1,len(nums)):
                num = nums[i] + nums[j]
                if num == target:
                    return [i, j]

暴力解法，第一个循环遍历一遍数组的下标，第二个循环从下一个位置往后再遍历一次
时间复杂度为$O(N^2)$,空间复杂度为$O(1)$

哈希表

不会做，看的官解

class Solution:
    def twoSum(self, nums, target):
        hash_table = dict()
        for i,num in enumerate(nums):
            if target - num in hash_table:
                return hash_table[target-num],i
            hash_table[num] = i

hash_table创造一个空字典，储存数组中每个元素和他的索引
enumerate(nums)同时返回元素的索引和值
使用哈希表的好处在于，遍历一次，查找的时候时间复杂度为$O(N)$,但空间复杂度稍微高了一点，也为$O(N)$

26. 删除有序数组中的重复项

第一次做的时候没做出来,只过了一个test。。。。

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        count = 0
        for i in range(len(nums) - 2):
            if nums[i+1] == nums[i]:
                count += 1
                nums.pop(i+1)

然后看了官解，要用双指针,一边遍历一边查找相同元素

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        if not nums:
            return
        slow,fast = 0,1
        while fast < len(nums):
            if nums[fast] != nums[slow]:
                slow +=1
                nums[slow] = nums[fast]
            fast += 1
        return slow + 1

27.移除元素

暴力

第一次做出来的这个解实际上并不高效,44ms,和16.93MB的内存分布,思路是这样的：

新建一个数组val_index，储存通过遍历检测到nums中和val值一样的索引值
再使用一个循环，对储存索引值的数组进行遍历，从而得到需要删除的索引值

在循环中，加入一个循环从后往前遍历nums，删除对应位置的元素

class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        length = len(nums)
        val_index = []
        for i in range(length):
            if(nums[i] == val):
                val_index.append(i)
        for i in reversed(val_index):
            for delete in  range(i, length - 1):
                nums[delete] = nums[delete + 1]
            length -= 1
        return length

优化了一点，36ms,17MB,减少了对索引值的储存

class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        length = len(nums)
        val_index = []
        for i in range(length-1,-1,-1):
            if(nums[i] == val):
                for delete in range(i,length-1):
                    nums[delete] = nums[delete + 1]
                length -= 1
        return length

双指针

网上参考别人的双指针方法，36ms，16.9MB在尝试的过程当中发现一件事情，用for循环比用while循环的时间占用更多

class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        a = 0
        b = 0
        while a < len(nums):
            if nums[a] != val:
                nums[b] = nums[a]
                b += 1
            a += 1
        return b

35.搜索插入位置

刚做这道题时，还不太会二分查找，看到时间复杂度需要使用$O(\log(n))$时，以为又是双指针,后来尝试了下发现没必要，直接暴力解出来,但其实这样的时间复杂度是$O(n)$,不符合题目要求

暴力

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        for i in range(len(nums)):
            if nums[i] >= target:
                return i
        return len(nums)

二分查找

之后学习了二分查找以后，写出来了第一个二分查找的代码，比较简单，结果也证明了没有考虑很多的东西，60ms,17.5MB

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        i,j = 0,len(nums) - 1
        while i<=j:
            m = (i+j) // 2
            if target < nums[m]:
                j = m - 1
            elif target > nums[m]:
                i = m + 1
            else:
                return m
        return i

为了优化代码，查了题解，发现自己二分查找只是学习了大概，还有很多细节没有学到：

二分查找学习的第一步需要确定区间的左右开闭情况
固定数组长度：例如左闭右开就是[0,len(nums)]
循环退出条件：while left < right:,由于区间是右开，因此不能有=
中间值的写法：m = left + (right - left) // 2,防止数太大溢出
中间值和目标值的比较：常规比较方法，后期忘记了可以再复习下

之后，参考孤柒「一起学计算机」的题解代码：

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        left, right = 0, len(nums) #采用左闭右开区间[left,right)
        while left < right: # 右开所以不能有=,区间不存在
            mid = left + (right - left)//2 # 防止溢出, //表示整除
            if nums[mid] < target: # 中点小于目标值,在右侧,可以得到相等位置
                left = mid + 1 # 左闭,所以要+1
            else:
                right = mid # 右开,真正右端点为mid-1
        return left # 此算法结束时保证left = right,返回谁都一样

66.加一

之前解过一次，思路简单，不要以10作为判断条件，而是9，是9直接变0，不是9加1然后直接返回，注意，如果digits = [9],那么前面加个1就好了

class Solution:
    def plusOne(self, digits: List[int]) -> List[int]:
        for i in range(len(digits) - 1,-1,-1):
            if digits[i] == 9:
                digits[i] = 0
                if digits[0] == 0:
                    return [1] + digits
            else:
                digits[i] += 1
                return digits

链表

21.合并两个有序链表

做的第一道链表题，不会做，看的官解，需要用递归的方法

递归

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
class Solution:
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        if list1 is None:
            return list2
        elif list2 is None:
            return list1
        elif list1.val < list2.val:
            list1.next = self.mergeTwoLists(list1.next,list2)
            return list1
        else:
            list2.next = self.mergeTwoLists(list1,list2.next)
            return list2

言于舟

LeetCode刷题记录(python)

数组