今天的题都是数组和链表相关的，看来之前做的效果不错，感觉都有思路，自己也基本都能敲出来。

238. 除了自身以外数组的乘积

给你一个整数数组 nums，返回 数组 answer ，其中 answer[i] 等于 nums 中除了 nums[i] 之外其余各元素的乘积 。

题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在  32 位 整数范围内。

请 不要使用除法，且在 O(n) 时间复杂度内完成此题。

示例 1:

输入: nums = [1,2,3,4]
输出: [24,12,8,6]

示例 2:

输入: nums = [-1,1,0,-3,3]
输出: [0,0,9,0,0]

思路：说实话，不知道这个题为什么是中等题，感觉像简单题。直接前缀积和后缀积，然后再乘

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        # 前缀积，后缀积
        pre = [1] * len(nums)
        suf = [1] * len(nums)
        res = [0] * len(nums)
        print(pre)
        for i in range(len(nums)):
            if i > 0:
                pre[i] = pre[i - 1] * nums[i - 1]
        for i in range(len(nums) - 1,-1, -1):
            if i < len(nums) - 1:
                suf[i] = suf[i + 1] * nums[i + 1]
        for i in range(len(nums)):
            res[i] = pre[i] * suf[i]
        return res

        

41.缺失的第一个正数

给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。

请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。

示例 1：

输入：nums = [1,2,0]
输出：3
解释：范围 [1,2] 中的数字都在数组中

思路：这个题想用最优解，感觉比较难。没有思路，直接看的答案。正解：将元素和数组的下标联系起来，如果当前元素是当前下标 + 1，那就说明当前位置是对的元素；如果不是，那就需要交换当前元素和当前元素为下标的对应元素，其中如果当前元素为下标，这个下标是不符合数组边界的话，那就不做处理，意思就是没有合适的元素与之交换。其中还有需要注意的就是影子问题，也就是要交换的元素和当前元素相等的话，那就是不用交换了，要不然会陷入死循环。 最后元素 ！= 下标 + 1的就是没有出现的最小整数。还要注意本来就是正确元素的，需要返回最后一个最大值 + 1。

其中还需要注意先用target暂存一下 当前元素。要不然后续交换的时候会失效。

class Solution:
    def firstMissingPositive(self, nums: List[int]) -> int:
        # 数组下标为i的对应数字为i+1，不是的话，就交换。
        for i in range(len(nums)):
            while 0 <= nums[i] - 1 < len(nums) and nums[i] != nums[nums[i] - 1]:
                
                target = nums[i]
                tmp = nums[i]
                nums[i] = nums[target - 1]
                nums[target - 1] = tmp
                    
                
        for i in range(len(nums)):
            if nums[i] != i + 1:
                return i + 1
        return len(nums) + 1

        

73.矩阵置零

给定一个 m x n 的矩阵，如果一个元素为 0 ，则将其所在行和列的所有元素都设为 0 。请使用 原地 算法。

示例 1：

输入：matrix = [[1,1,1],[1,0,1],[1,1,1]]
输出：[[1,0,1],[0,0,0],[1,0,1]]

思路：这个题，说实话一开始没有什么思路。可能早上脑子不太清楚。它的基本逻辑是用记事本，也就是遍历数组之后，记录下来哪一行和列有0，然后遍历一遍去置0。这样的话，空间复杂度是O(M+N)。然后O(1）的空间复杂度，那就是只能在原数组上修改。思路就是用原数组第一行和第1列表示当前行和列是否需要置0，这样的话就需要先把第一行和第一列本身的情况，先存储下来，直接用两个变量就可以了。然后从第2行和第2列开始变量，进行置零操作，最后在处理第一行和第一列。

class Solution:
    def setZeroes(self, matrix: List[List[int]]) -> None:
        """
        Do not return anything, modify matrix in-place instead.
        """
        # 用额外的记事本来记录当前行和列是否有0，有的话，标记一下。但是不让额外o(n)的空间，那就把该行和该列的情况保存到第一行和第一列。
        # 需要先维护第一行和第一列原本的情况
        # 从第2行和第2列开始，有0的话，记录到第1行的对应列，和对应行的第1列
        # 从第2行和第2列开始，先看该行的第1列，和该列的第1行，有标记，当前就变成0
        # 最后看第1行和第1列，有标记，就把第1行和第1列变成0
        row0_flag = -1
        col0_flag = -1
        m = len(matrix)
        n = len(matrix[0])
        for j in range(n):
            if matrix[0][j] == 0:
                row0_flag = 0
        for i in range(m):
            if matrix[i][0] == 0:
                col0_flag = 0
        for i in range(1,m):
            for j in range(1,n):
                if matrix[i][j] == 0:
                    matrix[i][0] = 0
                    matrix[0][j] = 0
        for i in range(1,m):
            for j in range(1,n):
                if matrix[i][0] == 0:
                    matrix[i][j] = 0
                if matrix[0][j] == 0:
                    matrix[i][j] = 0
        if row0_flag == 0:
            for j in range(n):
                matrix[0][j] = 0
        if col0_flag == 0:
            for i in range(m):
                matrix[i][0] = 0

        


        

54.螺旋矩阵

给你一个 m 行 n 列的矩阵 matrix ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素。

示例 1：

输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出：[1,2,3,6,9,8,7,4,5]

思路：这个题是自己写出来的，就是一个模拟的过程，因为之前记得有loop来待变第几圈的问题，所以就OK

class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        # 四个方向，分别写一下，用loop判断当前是第几圈，loop最后的值需要确定
        loop = 0
        m = len(matrix)
        n = len(matrix[0])
        minn = min(m,n)
        ans = []
        i = 0
        j = 0
        vis = [([0] * n) for _ in range(m)]
        while loop <= minn // 2:
            for j in range(loop,n - loop):
                if vis[i][j] == 0:
                    ans.append(matrix[i][j])
                    vis[i][j] = 1
            # j -= 1
            for i in range(loop + 1,m - loop):
                if vis[i][j] == 0:
                    ans.append(matrix[i][j])
                    vis[i][j] = 1
                
            # i -= 1
            for j in range(n - loop - 1 - 1,loop - 1, -1):
                if vis[i][j] == 0:
                    ans.append(matrix[i][j])
                    vis[i][j] = 1
                
            for i in range(m - loop - 1 - 1,loop ,-1):
                if vis[i][j] == 0:
                    ans.append(matrix[i][j])
                    vis[i][j] = 1
                
            loop += 1
        return ans

        

48.旋转图像

给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。

你必须在 原地 旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像。

示例 1：

输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出：[[7,4,1],[8,5,2],[9,6,3]]

思路：这个题也是自己写出来的，就是先对角线翻转，在以中间竖线为轴，进行轴对称翻转

class Solution:
    def rotate(self, matrix: List[List[int]]) -> None:
        """
        Do not return anything, modify matrix in-place instead.
        """
        # 先对称翻转  
        # 在对角线翻转
        m = len(matrix)
        n = len(matrix[0])
        for i in range(m):
            for j in range(i + 1):
                tmp = matrix[i][j]
                matrix[i][j] = matrix[j][i]
                matrix[j][i] = tmp
        for i in range(m):
            for j in range(n//2):
                tmp = matrix[i][j]
                matrix[i][j] = matrix[i][n - j - 1]
                matrix[i][n - j - 1] = tmp
        
        
        

240.搜索二维矩阵II

编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：

• 每行的元素从左到右升序排列。
• 每列的元素从上到下升序排列。

示例 1：

输入：matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 5
输出：true

思路：如果用遍历的话，非常简单，但是题目中说的升序 就没什么用了。然后我就看了答案。答案意思是将这个矩阵逆时针旋转45°，然后可以看出来每个节点的左侧都是小于该节点的，右侧都是大于该节点的。类似于二叉树。然后可以从矩阵的左下角那个位置开始搜索，如果target > nums[m-1][0] 那就说明target在右侧，直接 j++ ; 小于的话就是在上面，那就是 i--。等于的话，就是找到了。

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        # 利用行递增和列递增的特点
        # 将图逆时针旋转45°，可以看到，类似二叉树，左叉小于该值，右差大于该值。把矩阵中左下角当作根节点，从这里开始遍历
        m = len(matrix)
        n = len(matrix[0])
        i = m - 1
        j = 0
        while 0 <= i < m and 0 <= j < n:
            if matrix[i][j] < target:
                j += 1
            elif matrix[i][j] > target:
                i -= 1
            else:
                return True
        return False


        

160.相交链表

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。

图示两个链表在节点 c1 开始相交：

题目数据 保证 整个链式结构中不存在环。

注意，函数返回结果后，链表必须 保持其原始结构 。

思路：这个题我没有什么很好的办法，就是笨方法，先遍历两个链表，得到各自的长度，然后根据长度来判断让哪个链表的指针先走。 要注意python返回的是None

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> Optional[ListNode]:
        # 从后向前，这感觉遍历不了啊，链表本身就是向前指的吧，除非双链表？？
        # 目前想到的就是统计 a b 的链表长度，从一样长的地方开始遍历，如果指针一样那就是 相交节点
        cnta = 0
        cntb = 0
        tmpa = headA
        tmpb = headB
        while tmpa:
            tmpa = tmpa.next
            cnta += 1
        while tmpb:
            tmpb = tmpb.next
            cntb += 1
        if cnta < cntb :
            for i in range(cntb - cnta):
                headB = headB.next
        if cnta > cntb:
            for i in range(cnta - cntb):
                headA = headA.next
        Len = min(cnta,cntb)
        for i in range(Len):
            if headA == headB:
                return headA
            headA = headA.next
            headB = headB.next
        return None

206.反转链表

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

示例 1：

输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]

思路：这个题就是有感觉，但是没把代码整明白，直到是直接修改.next就可以，然后看了答案，希望记住。需要pre来代表当前节点的前驱，cur就是当前节点，tmp用来保存当前节点的下一个节点，要不然修改.next之后，后面的就丢失了，所以需要保存。巧妙点在于，更新pre = cur cur = tmp就可以了，这样就可以不混淆的进行修改。

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        # 需要pre表示前驱节点，cur表示当前节点，tmp表示当前节点的下一个节点，用来暂存
        pre = None 
        cur = head 
        while cur:
            tmp = cur.next 
            cur.next = pre 
            pre = cur 
            cur = tmp 
        return pre
        
        

234.回文链表

给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。

示例 1：

输入：head = [1,2,2,1]
输出：true

思路：我一开始的想法就是把链表中的val 保存到数组中，然后判断数组是否是回文的，但是感觉有额外的空间。答案的想法是：

1、用快慢指针，快指针每次走2步，慢指针每次走1步，这样快指针到最后的时候，慢指针就走到了中间。

2、将后半段反转，利用上一题的思路，这样反转是在原地进行反转的。没有额外的空间。

3、反转之后直接比较前半段和反转之后的val是否一致。

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def isPalindrome(self, head: Optional[ListNode]) -> bool:
        # fast指针每次走2步，slow指针每次走1步，当fast=None 或者fast.next时候，slow就走到了中间，slow位置就是后半段的开头节点
        fast = head 
        slow = head 
        while fast and fast.next :
            slow = slow.next 
            fast = fast.next.next 
        pre = None
        cur = slow 
        while cur:
            tmp = cur.next 
            cur.next = pre 
            pre = cur 
            cur = tmp 
        # print(pre)
        # print(head)
        while pre:
            if pre.val != head.val :
                # print(pre.val)
                # print(head.val)
                return False
            pre = pre.next
            head = head.next
        return True
        

141.环形链表

给你一个链表的头节点 head ，判断链表中是否有环。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。

如果链表中存在环 ，则返回 true 。 否则，返回 false 。

思路：这个题也是自己做出来的，就是快慢指针

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        # 快慢指针
        fast = head 
        slow = head 
        while fast and fast.next:
            fast = fast.next.next 
            slow = slow.next 
            if fast == slow:
                return True
        return False
        

142.环形指针II

这个相比于上一个题，就是要把环形的入口点索引返回。

思路： 这个题有印象，就是一个公式转换。大体就是，当相遇的时候，从相遇节点和头开始，分别两个指针，速度一致，再次相遇就是环形的入口点。

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
        # 数学题中那个相约问题，咋做？？记不清楚了，反正是相遇之后，有什么关系
        # 相遇之后，假设从头到入环口的距离为a，从入环口到相遇地点为b,从相遇到入环口为c，这些都是距离。然后快指针的距离是慢指针距离的2倍，因为时间相同，速度是2倍。所以 a + b = a + n*(b + c) + b,简化公式后就是a = (n - 1)*(b + c) + c
        # 也就是说从开头到入环口的距离和从相遇点到入环口的距离是相等的，所以用两个同速度指针，再次相遇就是入环口
        fast = head 
        slow = head 
        flag = 0
        while fast and fast.next:
            fast = fast.next.next 
            slow = slow.next 
            if fast == slow:
                flag = 1
                break
        if flag == 0:
            return None 
        pre = head 
        while pre != slow:
            pre = pre.next 
            slow = slow.next 
        return pre

        

21.合并两个有序链表

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 

示例 1：

输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]

思路：不要在原本的headA和headB操作。需要引入哨兵节点，然后分别遍历俩链表，谁小，移动谁。最后谁还有剩余直接接在后面

# Definition for singly-linked list.
# 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]:
        # 两个指针分别遍历两个链表，谁小，谁移动
        # 需要一个新链表，不知道有没有空间复杂度更小的方法？？？
        # 不用新链表的话，就是需要一个哨兵节点
        dummy = ListNode(-1) #这个是创建哨兵节点的方法
        res = dummy
        while list1 and list2:
            if list1.val <= list2.val:
                dummy.next = list1 
                list1 = list1.next 
            else:
                dummy.next = list2 
                list2 = list2.next 
            dummy = dummy.next
        if list1:
            dummy.next = list1
            
        if list2:
            dummy.next = list2
           
        return res.next