leetcode18-27

自己解法，空间复杂度高 自己思路写出来就好了，第一遍先不追求最完美。况且有时候最完美也不易读

class Solution:
    def setZeroes(self, matrix: List[List[int]]) -> None:
        """
        Do not return anything, modify matrix in-place instead.
        """
        zeroes =[]
        m = len(matrix)
        n = len(matrix[0])
        for i in range(m):
            for j in range(n):
                if matrix[i][j] == 0:
                    zeroes.append([i, j])
        for num in zeroes:
            i, j = num[0], num[1]
            for k in range(n):
                matrix[i][k] = 0
            for k in range(m):
                matrix[k][j] = 0

                    
        

class Solution:
    def spiralOrder(self, matrix):
        m, n = len(matrix), len(matrix[0])
        upper_bound, lower_bound = 0, m - 1
        left_bound, right_bound = 0, n - 1
        res = []
        # res.size() == m * n 则遍历完整个数组
        while len(res) < m * n:
            if upper_bound <= lower_bound:
                # 在顶部从左向右遍历
                for j in range(left_bound, right_bound + 1):
                    res.append(matrix[upper_bound][j])
                # 上边界下移
                upper_bound += 1

            if left_bound <= right_bound:
                # 在右侧从上向下遍历
                for i in range(upper_bound, lower_bound + 1):
                    res.append(matrix[i][right_bound])
                # 右边界左移
                right_bound -= 1

            if upper_bound <= lower_bound:
                # 在底部从右向左遍历
                for j in range(right_bound, left_bound - 1, -1):
                    res.append(matrix[lower_bound][j])
                # 下边界上移
                lower_bound -= 1

            if left_bound <= right_bound:
                # 在左侧从下向上遍历
                for i in range(lower_bound, upper_bound - 1, -1):
                    res.append(matrix[i][left_bound])
                # 左边界右移
                left_bound += 1
        return res

遍历顺序是 顺时针，画图求解

我们可以先将 n x n 矩阵 matrix 按照左上到右下的对角线进行镜像对称：

然后再对矩阵的每一行进行反转：

class Solution:
    def rotate(self, matrix: List[List[int]]) -> None:
        """
        Do not return anything, modify matrix in-place instead.
        """
        n = len(matrix)
        for i in range(n):
            for j in range(i, n):
                matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
        
        for row in matrix:
            self.reverse(row)
    def reverse(self, row):
        i, j = 0, len(row) - 1
        while i < j:
            row[i], row[j] = row[j], row[i]
            i += 1
            j -= 1

我们可以发散一下，如何将矩阵逆时针旋转 90 度呢？

思路是类似的，只要通过另一条对角线镜像对称矩阵，然后再反转每一行，就得到了逆时针旋转矩阵的结果：

由于矩阵是排序的，可以使用一种类似“削减搜索空间”的方法。这种策略选择从矩阵的右上角开始搜索。这样做的好处是：

• 从右上角开始

  ：这个元素是该行的最大值，同时是该列的最小值。

  • 如果该元素等于 target，直接返回 True。
  • 如果该元素小于 target，说明 target 只能出现在下一行，因此 i += 1 。
  • 如果该元素大于 target，说明 target 只能出现在该列的左边，因此 j -= 1 。

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        m = len(matrix)
        n = len(matrix[0])

        i, j = 0, n - 1
        while i < m and j >= 0 : #确保搜索范围，不然while一直下去，都超过矩阵了
            if matrix[i][j] == target:
                return True 
            if matrix[i][j] < target:
                i += 1
            else:
                j -= 1
        return False 
        

找公共结点， 强行制造长度相等，遍历相同节点。

while p1 != p2: 也就是这个引用指向的内存地址不同，就是不同结点， 不同结点的定义就是内存空间中不同，只要结点不同，就指向下一个结点

节点的内存地址不同：

• 每个链表节点在内存中的地址是唯一的。当你创建新的链表节点时，系统会在内存中分配一个新的位置，因此每个节点的地址都会不同。
• 节点地址的不同是因为每个节点在内存中有独立的存储位置，即使它们存储的数据类型相同，它们的内存地址也会不同。

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> Optional[ListNode]:
        p1, p2 = headA, headB 
        while p1 != p2:
            p1 = p1.next if p1 else headB
            p2 = p2.next if p2 else headA 
        return p1 
        

迭代解法，利用pre, cur, nxt 三个指针，每次反转一个

class Solution:
    # 反转以 head 为起点的单链表
    def reverseList(self, head: ListNode) -> ListNode:
        if head is None or head.next is None:
            return head
        # 由于单链表的结构，至少要用三个指针才能完成迭代反转
        # cur 是当前遍历的节点，pre 是 cur 的前驱结点，nxt 是 cur 的后继结点
        pre, cur, nxt = None, head, head.next
        while cur is not None:
            # 逐个结点反转
            cur.next = pre
            # 更新指针位置
            pre = cur
            cur = nxt
            if nxt is not None:
                nxt = nxt.next
        # 返回反转后的头结点
        return pre

每次往前指一个数， 走到最后，cur 和nxt 都是None

1、一旦出现类似 nxt.next 这种操作，就要条件反射地想到，先判断 nxt 是否为 null，否则容易出现空指针异常。！！！

2、注意循环的终止条件。你要知道循环终止时，各个指针的位置，这样才能保返回正确的答案。如果你觉得有点复杂想不清楚，那就动手画一个最简单的场景跑一下算法，比如这道题就可以画一个只有两个节点的单链表 1->2，然后就能确定循环终止后各个指针的位置了。

利用分解问题的思路，递归的方法 这就是「分解问题」的思路，通过递归函数的定义，把原问题分解成若干规模更小、结构相同的子问题，最后通过子问题的答案组装原问题的解。

reverseList 函数定义是这样的：

输入一个节点 head，将「以 head 为起点」的链表反转，并返回反转之后的头结点。

不要跳进递归（你的脑袋能压几个栈呀？），而是要根据刚才的函数定义，来弄清楚这段代码会产生什么结果： 不要进入递归，弄明白函数的定义。

class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:#反转链表函数的定义是，翻转
    #输入一个节点 head，将「以 head 为起点」的链表反转，并返回反转之后的头结点。 
        if head is None or head.next is None:
            return head #base case 
        last = self.reverseList(head.next) 
        #再把断的衔接起来
        head.next.next = head 
        head.next = None
        return last 

转换为数组来写，

class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if head is None or head.next is None:
            return head 
        nums = []
        while head:
            nums.append(head.val)
            head = head.next 
        traverse = nums[::-1]
        head = ListNode(traverse[0])
        current = head 
        for value in traverse[1:]:
            current.next = ListNode(value)
            current = current.next 
        return head 

在处理链表题目时，有时可以将问题转换为数组来解决，但是否能够通过取决于具体问题的性质和要求。将链表转换为数组的方法通常涉及以下几个步骤：

数组法，数组nb

class Solution:
    def isPalindrome(self, head: Optional[ListNode]) -> bool:
        nums = []
        while head:
            nums.append(head.val)
            head = head.next 
        i, j = 0, len(nums) - 1
        while i < j:
            if nums[i] == nums[j]:
                i += 1
                j -= 1
                continue 
            else:
                return False
        return True

普通方法算了，不掌握了

快慢指针是一种高效且常见的链表操作技巧，适用于解决链表中涉及查找中点、检测环、回文判断等问题。掌握快慢指针技巧可以帮助你在处理链表问题时避免多次遍历链表，从而提高代码效率

判断链表是否包含环属于经典问题了，解决方案也是用快慢指针：

每当慢指针 slow 前进一步，快指针 fast 就前进两步。

如果 fast 最终能正常走到链表末尾，说明链表中没有环；如果 fast 走着走着竟然和 slow 相遇了，那肯定是 fast 在链表中转圈了，说明链表中含有环。

class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        slow, fast = head, head 
        while fast is not None and fast.next is not None:
            slow = slow.next 
            fast = fast.next.next 
            if slow == fast:
                return True 
        return False 

几何关系，相遇点并不一定就是环的起来， 不过可以假设相遇点距离环起点为 m, 再利用一个走的距离时k 一个是 2k

任意移动一个到起始到，下次再相遇的时候就是环的起点了！！

class Solution:
    def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
        slow, fast = head, head 
        while fast is not None and fast.next is not None:
            slow = slow.next 
            fast = fast.next.next 
            if slow == fast:
                break 
        if fast is None or fast.next is None:
            return None #出来时fast,或者fast下一个是空，那么没有环存在
        slow = head 
        while slow != fast:
            fast = fast.next 
            slow = slow.next 
        return slow #最后肯定会相遇的，如果有环的话
        

使用虚拟头结点的情况：创造新链表时候 我这里总结下：当你需要创造一条新链表的时候，可以使用虚拟头结点简化边界情况的处理。

比如说，让你把两条有序链表合并成一条新的有序链表，是不是要创造一条新链表？再比你想把一条链表分解成两条链表，是不是也在创造新链表？这些情况都可以使用虚拟头结点简化边界情况的处理。

虚拟头结点（dummy node） 是链表问题中非常常用的技巧，它可以简化代码逻辑，尤其在处理链表的头结点操作时，避免大量特殊情况的处理。使用虚拟头结点的场景主要集中在需要频繁插入、删除、合并链表的场景中。下面总结一下使用虚拟头结点的原因和常见的应用场景。