[数据结构与算法]代码随想训练营（两个月）

Day1 数组：二分搜索 + 移除元素

Leetcode 704 二分查找

第一次知道还要考虑区间，但是感觉双闭的区间和代码更对称，更好理解一些。就是while有没有等号的区别。

重点：left，right和mid的更新

• mid：只有left <= right的时候更新，是最简单的，每次循环都会更新，left == right的时候就是要结束的时候了。
• left和right：因为while的条件包含=，所以是双闭区间，在当前循环中，已经比较过nums[mid]和target了，下次循环就不需要再考虑mid本身了。所以要向前或者向后缩小范围。

考虑到left，right两个整数相加得到的整数可能会溢出，所以采用mid = left + (right - left) // 2这种写法。

# 左闭右闭
class Solution:
    def search(self, nums: List[int], target: int) -> int:
        left, right = 0, len(nums)-1
        while left <= right:
            mid = left + (right - left) // 2
            if nums[mid] < target:
                left = mid + 1
            elif nums[mid] > target:
                right = mid - 1
            else:
                return mid
        return -1

Leetcode 27 移除元素

看到“原地”，就知道只能在原数组操作了，一开始只想到快慢指针的思路，但是相向双指针也可以。

本质：双指针交换元素

• 同向双指针（快慢双指针）：可以理解为在遍历两个数组，fast在遍历旧数组（因为跑得快，遍历完整个数组了，slow只跑了一段），slow遍历的是旧数组。因fast相当于是探路的，所以要对fast的值进行判定（if语句），然后根据结果，告诉slow少走一些弯路。
• 相向双指针（对向）：一个遇到val停下，一个没有遇到val就停下，然后交换。

#快慢指针
class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        slow, fast = 0, 0
        while fast < len(nums):
            # if相当于更新slow，新数组的一个操作，fast理解为遍历旧数组
            # fast不管怎么都要遍历，而slow只有更新了之后才会向前（遍历）
            if nums[fast] != val:
                nums[slow] = nums[fast]
                slow += 1
                fast += 1
            fast += 1
        return slow

# 相向双指针
class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        if nums is None or len(nums) == 0:
            return 0
        left, right = 0, len(nums)-1
        while left < right:
            # 这造成left只有遇到val才会跳出循环
            # right只有不是val的时候才会跳出
            # 刚好可以互换
            while nums[left] != val and left < right:
                left += 1
            while nums[right] == val and left < right:
                right -= 1
            nums[left], nums[right] = nums[right], nums[left]
        # 在中间边界存在一个问题：left == right情况
        if nums[left] == val:
            return left    
        else:
            return left + 1

感觉这种解法没有快慢指针那么优雅，所以还是放弃了，还要额外对left==right情况进行判定。

Day2 数组：有序数组平方 + 长度最小子数组 + 螺旋矩阵生成

Leetcode 977 有序数组的平方

一看到题目，就想着用双指针，只不过一开始有点被昨天的题目影响了，想在原数组进行操作，结果没操作出来。看了一眼答案，发现新定义了一个数组result来返回结果，只要在旧数组往中间遍历就行了。这样就简单多了。

不过一开始还是没注意，把平方写在条件判断外，导致多次平方。

class Solution:
    def sortedSquares(self, nums: List[int]) -> List[int]:
        n = len(nums)
        left, right = 0, n-1
        result = [-1] * n
        k = n - 1
        while left <= right:
            if nums[left]**2 > nums[right]**2:
                result[k] = nums[left]**2
                left += 1
                k -= 1
            else:
                result[k] = nums[right]**2
                right -= 1
                k -= 1
        return result

Leetcode 209 长度最小的子数组

滑动窗口可解，也是快慢指针，要有一个total来记录窗口内的元素之和，还要有一个index来记录窗口索引长度。

这么看这次要更新的有4个参数：slow，fast，total，index

• slow：total > target时更新
• fast：跟着while循环更新
• total：slow更新之前要减去nums[slow]
• index：total > target，要对当前的索引差与之前的最小值比较更新

可以看出来，基本都和total的变化相关，所以while内部，对total的值进行判定。

做题的时候，忘记考虑（输入数组为空）和（输入数字的全部数都小于target）的这两种情况了。

class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        slow, fast = 0, 0
        total, index =0, len(nums)+1
        while fast < len(nums):
            total += nums[fast]
            while total >= target:
                index = min(index, fast-slow+1) # 为啥+1？
                total -= nums[slow]
                slow += 1
            fast += 1
        return 0 if index == len(nums)+1 else index

Leetcode 59 螺旋数组II

记得前段时间写过这道题，但是现在也忘了（拍脑门）

但是有思路，应该是要模拟，要考虑边界问题，就像704二分查找的第二种解法，应该是左闭右开的沿着边走；

• python里range()就是一个完美的左闭右开范围。
• 声明一个n*n的数组
• left和right，还有top和bottom相等的时候，已经是到中心点了，循环就要结束了。

class Solution:
    def generateMatrix(self, n: int) -> List[List[int]]:
        left, right = 0, n-1
        top, bottom = 0, n-1
        res = [[0] * n for _ in range(n)] # 初始化数组
        num = 1 
        while left <= right and top <=bottom:
            for column in range(left, right+1):
                res[top][column] = num
                num += 1
            for row in range(top+1, bottom+1):
                res[row][right] = num
                num += 1
            if left < right and top < bottom:
                for column in range(right-1, left, -1):
                    res[bottom][column] = num
                    num += 1
                for row in range(bottom, top, -1):
                    res[row][left] = num
                    num += 1
            left, right, top, bottom = left+1, right-1, top+1, bottom-1
        return res

周末要整理一下怎么初始化数组。

Day3 链表：移除链表元素 + 设计链表 + 链表翻转

Leetcode 203 移除链表元素

和Day1 27题的移除元素（数组）差不多，不过这个是在链表上进行操作。

重点：虚拟头结点，因为链表的遍历是一次性的，到了结尾，如果没有设置备份和虚拟头结点的话，要返回处理过后的链表很麻烦。

class Solution:
   def removeElements(self, head: Optional[ListNode], val: int) -> Optional[ListNode]:
       dummy = ListNode(0, head)  # 新建一个虚拟头结点，方便返回
       cur = dummy
       while cur.next:
           if cur.next.val == val:
               cur.next = cur.next.next
           else:
               cur = cur.next
       return dummy.next

Leetcode 707 设计链表

设计链表的实现。您可以选择使用单链表或双链表。单链表中的节点应该具有两个属性：val 和 next。val 是当前节点的值，next 是指向下一个节点的指针/引用。如果要使用双向链表，则还需要一个属性 prev 以指示链表中的上一个节点。假设链表中的所有节点都是 0-index 的。
在链表类中实现这些功能：
get(index)：获取链表中第 index 个节点的值。如果索引无效，则返回-1。
addAtHead(val)：在链表的第一个元素之前添加一个值为 val 的节点。插入后，新节点将成为链表的第一个节点。
addAtTail(val)：将值为 val 的节点追加到链表的最后一个元素。
addAtIndex(index,val)：在链表中的第index 个节点之前添加值为 val 的节点。如果 index 等于链表的长度，则该节点将附加到链表的末尾。如果 index大于链表长度，则不会插入节点。如果index小于0，则在头部插入节点。
deleteAtIndex(index)：如果索引 index有效，则删除链表中的第 index 个节点。

这题得把题目放这，说实话，之前一看到这种题，我都是直接跳过了，因为太麻烦了（现在也非常抗拒），要写一个比较完整的的类了。为了让自己印象深刻一点，还是写详细一些这次。

这个类有3个属性，val，next，index和5个函数：

• get(index)：根据索引获取val
• addAtHead(val)：头部加入节点，之前链表的index也要跟着变化
• addAtTail(val)：尾部加入节点，
• addAtIndex(index,val)：根据索引值index，在中间插入节点
• deleteAtIndex(index)：删除某个索引的节点

就是说设计链表其实包含和插入链表和删除节点两个题了。

需要两个类，一个是节点Node类，另一个是链表MyLinkList类，它们的属性有：

• class Node：节点的值val，节点指向的下一个节点next
• class MyLinkList：链表的虚拟头_head，链表的长度_length

class Node:
    def __init__(self, val):
        self.val = val
        self.next = None

class MyLinkedList:
    def __init__(self):
        self._head = Node(0)
        self._length = 0
    
    def get(self, index: int) -> int:
    def addAtHead(self, val: int) -> None:
    def addAtTail(self, val: int) -> None:
    def addAtIndex(self, index: int, val: int) -> None:
    def deleteAtIndex(self, index: int) -> None:

首先是根据索引获得值val

    def get(self, index: int) -> int: 
        if index < 0 or index >= self._length: # 根据index取值，需要遍历
            return -1
        
        post = self._head
        for _ in range(index + 1): # 需要考虑虚拟头结点
            post = post.next
        return post.val

接下来的三个成员函数实际上是一个功能，只要实现了addAtIndex就可以简单实现另外两个，增加和删除链表都要注意长度的变化。

   def addAtIndex(self, index: int, val: int) -> None:
        if index < 0: index = 0 # 前面条件判断
        elif index > self._length: return None 
        
        self._length += 1
        insert = Node(val)

        pre, post = None, self._head  # 前一个节点和后一个节点（index）
        for _ in range(index + 1):
            pre, post = post, post.next # 相当于在遍历两个链表， pre从self._head.next开始遍历
        else:
            pre.next, insert.next = insert, post

	def addAtHead(self, val: int) -> None:
        self.addAtIndex(0, val)

    def addAtTail(self, val: int) -> None:
        self.addAtIndex(self._length, val)

这里我不小心将self._length的增加操作放在范围判断之前了，导致出错。

    def deleteAtIndex(self, index: int) -> None:
       
        if index < 0 or index >= self._length: return None
        self._length -= 1
        
        pre, post = None, self._head
        for _ in range(index+1):  # 需要考虑虚拟头结点
            pre, post = post, post.next
        else:
            pre.next = post.next

Leetcode 206 链表翻转

感觉做完上一题设计链表，确实对链表的遍历理解加深了。pre和post有种快慢链表的味道，只不过他们一直相差1，同时对它们俩进行遍历。

pre就相当于虚拟头结点dummy了，最后可以直接返回。

感觉就是每次的操作，只是将后一个节点的next先保存，然后指向前一个节点pre ，然后更新两个节点。

重点：要将

class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        pre, post = None, head  
        while post:
            temp, post.next = post.next, pre  # 只将后一个节点的next先保存，然后指向前一个节点pre 
            pre, post = post, temp  # 都向后移动一位
        return pre  # 因为pre在head的前一个节点，所以相当于虚拟头结点了，这题因为翻转了，可以这么返回

Day4 链表 两两交换节点 + 删除倒数第n个节点 + 链表相交

Leetcode 24 两两交换链表中的节点

感觉画图会更好理解一点，其实根据原理和链表翻转类型，可以视为进阶题目。

class Solution:
    def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
        cur = dummy = ListNode(0, head)
        while cur.next and cur.next.next:
            node_1, node_2 = cur.next, cur.next.next
            node_1.next, node_2.next, cur.next = node_2.next, node_1, node_2   # 从后往前更新
            cur = node_1  # 更新cur
        return dummy.next 

重点：是逆着箭头的走向进行更新。

Leetcode 19 删除链表的倒数第n个节点

之前刷过一次，使用了两次扫描，第一次得到链表的长度，第二次进行删除，删除操作和设计链表的删除功能差不多。

# 两次扫描
class Solution:
    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
        def getLength(head:ListNode)->int:
            length = 0
            while head:
                length += 1
                head = head.next
            return length
        cur = dummy = ListNode(0, head)  # dummy是虚拟头结点
        size = getLength(head)
        for i in range(1, size - n + 1):
            cur = cur.next
        cur.next = cur.next.next
        return dummy.next

这次试试单次扫描的方法，确实没想到，使用快慢指针，先让fast移动n步，然后fast和slow同时移动，fast到结尾了，就删除slow的节点。
出错点：将dummy.next用来初始化slow和fast了，感觉对边界还是不是很熟悉

class Solution:
    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
        dummy = ListNode(0,head)
        slow = fast = dummy
        while n:  # 删除倒数第n个
            n -= 1 
            fast = fast.next
        
        while fast.next:
            slow, fast =slow.next, fast.next
        else:
            slow.next = slow.next.next
            return dummy.next

面试题 02.07. 链表相交

一开始确实没想到，感觉更像数学题目：

• 遍历两次，求长度差，然后一个先走，一个后走，类似快慢指针
• 这个方法太巧妙了，类似直接走headA和headB的总长度，如果有交点的话，第二段的最后肯定是相同。

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
        if not headA or not headB:
            return None
        cura, curb = headA, headB
        while cura != curb:
            cura = cura.next if cura else headB
            curb = curb.next if curb else headA
        return cura

Leetcode 142 环形链表