pc蛋蛋游戏体验网站建设,下载安装百度一下,网页版微信怎么登陆,做仿网站的书82.删除排序链表中的重复元素II 定义单个指针 cur#xff0c;指向虚拟头节点。如果 cur.next cur.next.next#xff0c;说明 cur 后面的两个节点重复#xff0c;例如 节点2 后面存在 2个节点3。我们令 节点2 - 节点4#xff0c;实现删除两个节点3的操作。 class Solut…82.删除排序链表中的重复元素II 定义单个指针 cur指向虚拟头节点。如果 cur.next cur.next.next说明 cur 后面的两个节点重复例如 节点2 后面存在 2个节点3。我们令 节点2 - 节点4实现删除两个节点3的操作。 class Solution:def deleteDuplicates(self, head: Optional[ListNode]) - Optional[ListNode]:dummyhead ListNode(val 0, next head)cur dummyheadwhile cur.next and cur.next.next:if cur.next.val cur.next.next.val:repeat_val cur.next.val# 跳过某段重复while cur.next and cur.next.val repeat_val:cur.next cur.next.nextelse:cur cur.nextreturn dummyhead.next
240.搜索二维矩阵II 利用矩阵的递增性质从左下角元素开始搜索同列元素都小于此元素同行元素都大于此元素。因此和 target 比较后我们可以立即排除一行或者一列的元素。如下图从右上角开始同理这是由于这两处的元素大小处在所在行和列的所有元素中间可以利用二分思想缩减搜索规模。而左上和右下角的元素处在所在行和列的所有元素的两端。 class Solution:def searchMatrix(self, matrix: List[List[int]], target: int) - bool:# 起始点定在矩阵左下角i, j len(matrix) - 1, 0while i 0 and j len(matrix[0]) - 1:if matrix[i][j] target:i - 1elif matrix[i][j] target:j 1else:return Truereturn False
冒泡排序 遍历数组每次交换相邻两个元素一次遍历后最大的数将会被移至末尾。针对所有的元素重复以上的步骤除了最后一个。持续每次对越来越少的元素重复上面的步骤直到没有任何一对数字需要比较。时间复杂度为 O(n^2) def bubble_sort(arr):n len(arr)# 遍历所有数组元素for i in range(n):for j in range(0, n-i-1):# 遍历数组从0到n-i-1# 交换如果元素大于下一个元素if arr[j] arr[j1]:arr[j], arr[j1] arr[j1], arr[j]return arr
快速排序 选择基准值从数组中选择一个元素作为基准值。选择方法有多种如选择第一个元素、最后一个元素、中间元素等。 分区操作重新排列数组使得所有小于基准值的元素都排在基准前面而所有大于基准值的元素都排在基准的后面相等的数可以到任一边。在这个分区退出之后该基准就处于数组的中间位置。 递归排序递归地将小于基准值的子数组和大于基准值的子数组排序。 时间复杂度为O(n log n) def quick_sort(arr):# 分区函数根据pivot基准值将数组分为两部分def partition(left, right):pivot arr[left] # 选择左边界的元素作为pivotwhile left right:# 从右向左扫描找到第一个小于pivot的元素移动到左边while left right and arr[right] pivot:right - 1arr[left] arr[right]# 从左向右扫描找到第一个大于pivot的元素移动到右边while left right and arr[left] pivot:left 1arr[right] arr[left]# 循环结束left和right相遇这是pivot的正确位置将pivot放回arr[left] pivotreturn left # 返回pivot的位置# 递归排序的辅助函数def quick_sort_recursive(left, right):if left right: # 至少包含两个元素的区间才需要排序pi partition(left, right) # 对当前区间进行分区得到pivot的位置quick_sort_recursive(left, pi - 1) # 递归排序pivot左侧的子数组quick_sort_recursive(pi 1, right) # 递归排序pivot右侧的子数组quick_sort_recursive(0, len(arr) - 1) # 对整个数组进行快速排序return arr # 返回排序后的数组538.把二叉搜索树转换为累加树 累加树Greater Sum Tree常见于二叉搜索树Binary Search Tree的变体。在累加树中每个节点的值被修改为原始二叉搜索树中所有大于或等于该节点值的节点值之和。 举例 有以下BST 反向中序遍历右中左 我们遍历的顺序是9 - 8 - 5 - 4 - 3 - 2。遍历时我们累计已经访问过的节点值的和并将这个累积和赋给当前节点。 访问节点 9当前累积和 9更新节点 9 的值为 9。访问节点 8当前累积和 9 8 17更新节点 8 的值为 17。访问节点 5当前累积和 17 5 22更新节点 5 的值为 22。访问节点 4当前累积和 22 4 26更新节点 4 的值为 26。访问节点 3当前累积和 26 3 29更新节点 3 的值为 29。访问节点 2当前累积和 29 2 31更新节点 2 的值为 31。 class Solution:def convertBST(self, root: Optional[TreeNode]) - Optional[TreeNode]:self.sum 0def dfs(node):# 递归终止条件if not node:return# 反向中序右 - 中 - 左# 右dfs(node.right)# 中self.sum node.valnode.val self.sum # 更新节点值# 左dfs(node.left)dfs(root)return root
1743.从相邻元素对还原数组 数组元素各不相同有以下观察 每个元素除了首尾元素都会有两个相邻元素前一个和后一个。数组的首元素 只有一个相邻元素即它后面的元素。数组的尾元素 同样只有一个相邻元素即它前面的元素。 因此在从 adjacentPairs 构建的 adj_map 中大多数键代表 nums 中的元素都会有两个条目在其对应的列表中这两个条目分别表示它的前一个和后一个相邻元素。例外的是 nums 的首尾元素它们在 adj_map 中的列表长度将是 1因为它们各自只有一个相邻元素。 举例说明 考虑数组 nums [1, 2, 3, 4]其相邻元素对可能包括 [1, 2][2, 3][3, 4] 在通过这些对构建 adj_map 后其内容将是 1 - [2]2 - [1, 3]3 - [2, 4]4 - [3] 由于顺序不限我们随意选择其中一个长度为 1 的键作为起点然后根据相邻关系依次添加元素到结果数组中直到所有元素都被添加。 class Solution:def restoreArray(self, adjacentPairs: List[List[int]]) - List[int]:n len(adjacentPairs) 1# 构建关系哈希表adj_map defaultdict(list)for u, v in adjacentPairs:adj_map[u].append(v)adj_map[v].append(u)# 找到 nums 的起始元素for key, val in adj_map.items():if len(val) 1:start keybreak# 构建 numsnums []nums.append(start)nums.append(adj_map[start][0])while len(nums) n:cur_val nums[-1]pre_val nums[-2]for next_val in adj_map[cur_val]:# cur_val键对应的值包含cur_val的前一个和后一个元素# 对于cur_val的后一个元素的确定我们需要避免重复选择cur_val的前一个元素pre_valif next_val ! pre_val:nums.append(next_val)else:continuereturn nums
