算法急救LeetCode62题-python版（1）/ 数组、链表

常考题型的迅速回顾，用于没时间刷力扣的

一：数组

1：704.二分查找

题目描述： 给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

示例1：
输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4
示例2：
输入: nums = [-1,0,3,5,9,12], target = 2
输出: -1
解释: 2 不存在 nums 中因此返回 -1

提示：

你可以假设 nums 中的所有元素是不重复的。
n 将在 [1, 10000]之间。
nums 的每个元素都将在 [-9999, 9999]之间。

思路： 这道题目的前提是数组为有序数组，同时题目还强调数组中无重复元素，因为一旦有重复元素，使用二分查找法返回的元素下标可能不是唯一的，这些都是使用二分法的前提条件，当大家看到题目描述满足如上条件的时候，可要想一想是不是可以用二分法了。
写二分法，区间的定义一般为两种，左闭右闭即[left, right]，或者左闭右开即[left, right)

代码：

时间复杂度：O(log n)
空间复杂度：O(1)

版本一）左闭右闭区间
class Solution:def search(self, nums: List[int], target: int) -> int:left, right = 0, len(nums) - 1  # 定义target在左闭右闭的区间里，[left, right]while left <= right:middle = left + (right - left) // 2if nums[middle] > target:right = middle - 1  # target在左区间，所以[left, middle - 1]elif nums[middle] < target:left = middle + 1  # target在右区间，所以[middle + 1, right]else:return middle  # 数组中找到目标值，直接返回下标return -1  # 未找到目标值

# （版本二）左闭右开区间
class Solution:def search(self, nums: List[int], target: int) -> int:left, right = 0, len(nums)  # 定义target在左闭右开的区间里，即：[left, right)while left < right:  # 因为left == right的时候，在[left, right)是无效的空间，所以使用 <middle = left + (right - left) // 2if nums[middle] > target:right = middle  # target 在左区间，在[left, middle)中elif nums[middle] < target:left = middle + 1  # target 在右区间，在[middle + 1, right)中else:return middle  # 数组中找到目标值，直接返回下标return -1  # 未找到目标值

2：59.螺旋矩阵II

题目描述： 给定一个正整数 n，生成一个包含 1 到 n^2 所有元素，且元素按顺时针顺序螺旋排列的正方形矩阵。

示例1：
输入: 3
输出: [ [ 1, 2, 3 ], [ 8, 9, 4 ], [ 7, 6, 5 ] ]

思路：
这道题目可以说在面试中出现频率较高的题目，本题并不涉及到什么算法，就是模拟过程，但却十分考察对代码的掌控能力。
求解本题要坚持循环不变量原则。模拟顺时针画矩阵的过程:

填充上行从左到右
填充右列从上到下
填充下行从右到左
填充左列从下到上
由外向内一圈一圈这么画下去。

代码：

时间复杂度 O(n^2): 模拟遍历二维矩阵的时间
空间复杂度 O(1)

class Solution:def generateMatrix(self, n: int) -> List[List[int]]:nums = [[0] * n for _ in range(n)]startx, starty = 0, 0               # 起始点loop, mid = n // 2, n // 2          # 迭代次数、n为奇数时，矩阵的中心点count = 1                           # 计数for offset in range(1, loop + 1) :      # 每循环一层偏移量加1，偏移量从1开始for i in range(starty, n - offset) :    # 从左至右，左闭右开nums[startx][i] = countcount += 1for i in range(startx, n - offset) :    # 从上至下nums[i][n - offset] = countcount += 1for i in range(n - offset, starty, -1) : # 从右至左nums[n - offset][i] = countcount += 1for i in range(n - offset, startx, -1) : # 从下至上nums[i][starty] = countcount += 1                startx += 1         # 更新起始点starty += 1if n % 2 != 0 :			# n为奇数时，填充中心点nums[mid][mid] = count return nums

链表

1：203.移除链表元素

题目描述： 删除链表中等于给定值 val 的所有节点。

示例1：
输入：head = [1,2,6,3,4,5,6], val = 6 输出：[1,2,3,4,5]
示例2：
输入：head = [], val = 1 输出：[]
示例3：
输入：head = [7,7,7,7], val = 7 输出：[]

思路：
链表操作的两种方式：

直接使用原来的链表来进行删除操作。
移除头结点和移除其他节点的操作是不一样的，因为链表的其他节点都是通过前一个节点来移除当前节点，而头结点没有前一个节点。
所以头结点如何移除呢，其实只要将头结点向后移动一位就可以，这样就从链表中移除了一个头结点。
设置一个虚拟头结点在进行删除操作。
置一个虚拟头结点，这样原链表的所有节点就都可以按照统一的方式进行移除。
return 头结点的时候，return dummyNode->next; 这才是新的头结点

代码：

时间复杂度: O(n)
空间复杂度: O(1)

（版本一）虚拟头节点法
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:def removeElements(self, head: Optional[ListNode], val: int) -> Optional[ListNode]:# 创建虚拟头部节点以简化删除过程dummy_head = ListNode(next = head)# 遍历列表并删除值为val的节点current = dummy_headwhile current.next:if current.next.val == val:current.next = current.next.nextelse:current = current.nextreturn dummy_head.next

2：707.设计链表

题目描述： 在链表类中实现这些功能：

get(index)：获取链表中第 index 个节点的值。如果索引无效，则返回-1。
addAtHead(val)：在链表的第一个元素之前添加一个值为 val 的节点。插入后，新节点将成为链表的第一个节点。
addAtTail(val)：将值为 val 的节点追加到链表的最后一个元素。
addAtIndex(index,val)：在链表中的第 index 个节点之前添加值为 val 的节点。如果 index 等于链表的长度，则该节点将附加到链表的末尾。如果 index 大于链表长度，则不会插入节点。如果index小于0，则在头部插入节点。
deleteAtIndex(index)：如果索引 index 有效，则删除链表中的第 index 个节点。
示例1：
MyLinkedList linkedList =newMyLinkedList();
linkedList.addAtHead(1);
linkedList.addAtTail(3);
linkedList.addAtIndex(1,2); //链表变为1->2->3
linkedList.get(1); //返回2
linkedList.deleteAtIndex(1); //现在链表是1->3
linkedList.get(1); //返回3

思路：
这道题目设计链表的五个接口：

获取链表第index个节点的数值
在链表的最前面插入一个节点
在链表的最后面插入一个节点
在链表第index个节点前面插入一个节点
删除链表的第index个节点

可以说这五个接口，已经覆盖了链表的常见操作，是练习链表操作非常好的一道题目

代码：

时间复杂度: 涉及 index 的相关操作为 O(index), 其余为 O(1)
空间复杂度: O(n)

（版本一）单链表法
class ListNode:def __init__(self, val=0, next=None):self.val = valself.next = nextclass MyLinkedList:def __init__(self):self.dummy_head = ListNode()self.size = 0def get(self, index: int) -> int:if index < 0 or index >= self.size:return -1current = self.dummy_head.nextfor i in range(index):current = current.nextreturn current.valdef addAtHead(self, val: int) -> None:self.dummy_head.next = ListNode(val, self.dummy_head.next)self.size += 1def addAtTail(self, val: int) -> None:current = self.dummy_headwhile current.next:current = current.nextcurrent.next = ListNode(val)self.size += 1def addAtIndex(self, index: int, val: int) -> None:if index < 0 or index > self.size:returncurrent = self.dummy_headfor i in range(index):current = current.nextcurrent.next = ListNode(val, current.next)self.size += 1def deleteAtIndex(self, index: int) -> None:if index < 0 or index >= self.size:returncurrent = self.dummy_headfor i in range(index):current = current.nextcurrent.next = current.next.nextself.size -= 1# Your MyLinkedList object will be instantiated and called as such:
# obj = MyLinkedList()
# param_1 = obj.get(index)
# obj.addAtHead(val)
# obj.addAtTail(val)
# obj.addAtIndex(index,val)
# obj.deleteAtIndex(index)

3：206.反转链表

题目描述： 反转一个单链表。

示例1：
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL

思路：
如果再定义一个新的链表，实现链表元素的反转，其实这是对内存空间的浪费。其实只需要改变链表的next指针的指向，直接将链表反转，而不用重新定义一个新的链表。

首先定义一个cur指针，指向头结点，再定义一个pre指针，初始化为null。
然后就要开始反转了，首先要把 cur->next 节点用tmp指针保存一下，也就是保存一下这个节点。为什么要保存一下这个节点呢，因为接下来要改变 cur->next 的指向了，将cur->next 指向pre ，此时已经反转了第一个节点了。
接下来，就是循环走如下代码逻辑了，继续移动pre和cur指针。
最后，cur 指针已经指向了null，循环结束，链表也反转完毕了。此时我们return pre指针就可以了，pre指针就指向了新的头结点。

代码：

时间复杂度: O(n)
空间复杂度: O(1)

（版本一）双指针法
# 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: ListNode) -> ListNode:cur = head   pre = Nonewhile cur:temp = cur.next # 保存一下 cur的下一个节点，因为接下来要改变cur->nextcur.next = pre #反转#更新pre、cur指针pre = curcur = tempreturn pre

（版本二）递归法
# 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: ListNode) -> ListNode:return self.reverse(head, None)def reverse(self, cur: ListNode, pre: ListNode) -> ListNode:if cur == None:return pretemp = cur.nextcur.next = prereturn self.reverse(temp, cur)

4：142.环形链表II

题目描述： 给定一个链表，返回链表开始入环的第一个节点。如果链表无环，则返回 null。

为了表示给定链表中的环，使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。

说明：不允许修改给定的链表。

示例1：
输入:head=[3,2,0,-4]，pos =1
输出:tail connects to node index 1
解释:链表中有一个环，其尾部连接到第二个节点。
示例2：
输入:head=[1,2]，pos =0
输出:tail connects to node index 0
解释:链表中有一个环，其尾部连接到第一个节点。

思路：
这道题目，不仅考察对链表的操作，而且还需要一些数学运算。
主要考察两知识点：

判断链表是否环
可以使用快慢指针法，分别定义 fast 和 slow 指针，从头结点出发，fast指针每次移动两个节点，slow指针每次移动一个节点，如果 fast 和 slow指针在途中相遇，说明这个链表有环。
为什么fast 走两个节点，slow走一个节点，有环的话，一定会在环内相遇呢，而不是永远的错开呢
如果有环，如何找到这个环的入口
假设从头结点到环形入口节点的节点数为x。环形入口节点到 fast指针与slow指针相遇节点节点数为y。从相遇节点再到环形入口节点节点数为 z。
那么相遇时： slow指针走过的节点数为: x + y， fast指针走过的节点数：x + y + n (y + z)，n为fast指针在环内走了n圈才遇到slow指针，（y+z）为一圈内节点的个数A。
因为fast指针是一步走两个节点，slow指针一步走一个节点，所以 fast指针走过的节点数 = slow指针走过的节点数 * 2。

代码：

时间复杂度: O(n)，快慢指针相遇前，指针走的次数小于链表长度，快慢指针相遇后，两个index指针走的次数也小于链表长度，总体为走的次数小于 2n
空间复杂度: O(1)

（版本一）快慢指针法
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = Noneclass Solution:def detectCycle(self, head: ListNode) -> ListNode:slow = headfast = headwhile fast and fast.next:slow = slow.nextfast = fast.next.next# If there is a cycle, the slow and fast pointers will eventually meetif slow == fast:# Move one of the pointers back to the start of the listslow = headwhile slow != fast:slow = slow.nextfast = fast.nextreturn slow# If there is no cycle, return Nonereturn None

（版本二）集合法
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = Noneclass Solution:def detectCycle(self, head: ListNode) -> ListNode:visited = set()while head:if head in visited:return headvisited.add(head)head = head.nextreturn None

来源于代码随想录的小记，官网上有详细的解析，需要的小伙伴可以去官网看哟~