外链网站 风险,网站设计要点 优帮云,台州网站推广排名,如何在百度搜到自己的网站查找
一、二分查找
二分查找是一种高效的查找算法#xff0c;适用于在已排序的数组或列表中查找特定元素。它通过将搜索范围逐步减半来快速定位目标元素。理解二分查找的“不变量”和选择左开右闭区间的方式是掌握这个算法的关键。
二分查找关键点
不变量
在二分查找中适用于在已排序的数组或列表中查找特定元素。它通过将搜索范围逐步减半来快速定位目标元素。理解二分查找的“不变量”和选择左开右闭区间的方式是掌握这个算法的关键。
二分查找关键点
不变量
在二分查找中不变量是指在每一步迭代中保持不变的条件。对于二分查找来说不变量通常是目标值在当前搜索范围内在每次迭代中目标值始终位于 left 和 right 指针之间。如在查找一个值 target并且当前的搜索范围是 arr[left]- arr[right]那么我们可以保证如果 arr[left]≤target≤arr[right]则 target 一定在这个范围内。
区间定义
二分查找时区间的左右端取开区间还是闭区间在绝大多数时候都可以二分查找中的左闭右开和左闭右闭的本质区别主要体现在搜索范围的定义和边界处理上。这种选择会影响算法的实现细节、边界条件的处理以及最终的查找结果。
二分查找实现
1左闭右闭区间 [left, right]
定义left 和 right 都是闭合的表示搜索范围包括 left 和 right。当 left 等于 right 时搜索范围仍然包含 right。在计算中间值时使用 mid left (right - left) / 2。但是这种都是闭区间可能会导致重复元素的处理变得复杂特别是在查找第一个或最后一个出现的元素时。
int binarySearchClosed(const std::vectorint arr, int target) {int left 0;int right arr.size() - 1;while (left right) {int mid left (right - left) / 2;if (arr[mid] target) {return mid; // 找到目标值} else if (arr[mid] target) {left mid 1; // 在右半部分继续查找} else {right mid - 1; // 在左半部分继续查找}}return -1; // 未找到目标值
}2左闭右开区间 [left, right)
left 是闭合的right 是开合的表示搜索范围包括 left但不包括 right。当 left 等于 right 时搜索范围不包含 right因此 right 的值是 arr.size()。并且在更新 right 时使用 right mid。优点避免了中间元素重复的情况特别适合查找插入位置。逻辑上更容易处理边界条件特别是在处理空数组或查找插入位置时。但是没有左闭右闭直观。
int binarySearchOpen(const std::vectorint arr, int target) {int left 0;int right arr.size(); // 注意这里是 arr.size()while (left right) { // 注意这里是 left rightint mid left (right - left) / 2;if (arr[mid] target) {return mid; // 找到目标值} else if (arr[mid] target) {left mid 1; // 在右半部分继续查找} else {right mid; // 在左半部分继续查找}}return -1; // 未找到目标值
}二分区间查找
34. 在排序数组中查找元素的第一个和最后一个位置 - 力扣LeetCode
给你一个按照非递减顺序排列的整数数组 nums和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。如果数组中不存在目标值 target返回 [-1, -1]。你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。
class Solution {// lower_bound 返回最小的满足 nums[i] target的下标 i// 如果数组为空或者所有数都 target则返回nums.size()int lower_bound(vectorint nums, int target) {int left 0, right (int) nums.size() - 1; // 闭区间while (left right) {// 循环不变量nums[left-1] target nums[right1] targetint mid left (right - left) / 2;if (nums[mid] target) {right mid - 1; } else {left mid 1; }}// 循环结束后 left right1// 此时 nums[left-1] target 而 nums[left] nums[right1] target// 所以 left 就是第一个 target 的元素下标return left;}
public:vectorint searchRange(vectorint nums, int target) {int start lower_bound(nums, target);if (start nums.size() || nums[start] ! target) {return {-1, -1}; // nums 中没有 target}// 如果 start 存在那么 end 必定存在int end lower_bound(nums, target 1) - 1;return {start, end};}
}; 二、深度搜索
沿分支尽可能深入到达叶子节点后回溯继续探索其他分支。
113. 路径总和 II - 力扣LeetCode
class Solution:def pathSum(self, root: Optional[TreeNode], targetSum: int) - List[List[int]]:def dfs(node, path, current_sum):if not node:returncurrent_sum node.valpath.append(node.val)if not node.left and not node.right and current_sum targetSum:result.append(list(path))dfs(node.left, path, current_sum)dfs(node.right, path, current_sum)path.pop() # 回溯result []dfs(root, [], 0)return result
三、广度搜索
按层级逐层遍历先处理离根节点最近的节点可以使用队列FIFO存储待访问节点。
102. 二叉树的层序遍历 - 力扣LeetCode
BFS层次遍历
class Solution:def levelOrder(self, root: Optional[TreeNode]) - List[List[int]]:if root is None:return []ans[]qdeque([root])while q:vals[]for _ in range(len(q)):nodeq.popleft()vals.append(node.val)if node.left: q.append(node.left)if node.right:q.append(node.right)ans.append(vals)return ans
200. 岛屿数量 - 力扣LeetCode
BFS
def numIslands(grid):if not grid:return 0rows, cols len(grid), len(grid[0])count 0from collections import dequefor i in range(rows):for j in range(cols):if grid[i][j] 1:queue deque([(i, j)])grid[i][j] 0 # 标记为已访问while queue:x, y queue.popleft()for dx, dy in [(-1,0), (1,0), (0,-1), (0,1)]:nx, ny x dx, y dyif 0 nx rows and 0 ny cols and grid[nx][ny] 1:queue.append((nx, ny))grid[nx][ny] 0count 1return count
DFS
def numIslands(grid):def dfs(x, y):if 0 x rows and 0 y cols and grid[x][y] 1:grid[x][y] 0dfs(x1, y)dfs(x-1, y)dfs(x, y1)dfs(x, y-1)rows len(grid)if rows 0:return 0cols len(grid[0])count 0for i in range(rows):for j in range(cols):if grid[i][j] 1:dfs(i, j)count 1return count
排序
排序算法总结-CSDN博客
数组中第K大元素
215. 数组中的第K个最大元素 - 力扣LeetCode
给定整数数组 nums 和整数 k请返回数组中第 k 个最大的元素。请注意你需要找的是数组排序后的第 k 个最大的元素而不是第 k 个不同的元素。你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。
要在时间复杂度为O(n) 的情况下找到数组中第k个最大的元素可以使用快速选择Quickselect算法。这个算法的思想与快速排序相似但它只关注找到第k 个最大的元素而不是对整个数组进行排序。排序后return nums[nums.size() - k]; O(nlogn)
选择基准元素从数组中随机选择一个基准元素。快排一趟确定一个元素的位置 分区操作将数组分为两部分左侧是小于基准的元素右侧是大于基准的元素。 判断基准位置如果基准元素的位置正好是n−k因为我们需要找到第k 个最大的元素那么这个元素就是我们要找的元素。如果基准元素的位置大于n−k则第k 个最大的元素在左侧部分。 如果基准元素的位置小于n−k则第k 个最大的元素在右侧部分。
class Solution {
public:int quickselect(vectorint nums, int l, int r, int k) {if (l r)return nums[k];int partition nums[l], i l - 1, j r 1;while (i j) {do i; while (nums[i] partition);do j--; while (nums[j] partition);if (i j)swap(nums[i], nums[j]);}if (k j)return quickselect(nums, l, j, k);else return quickselect(nums, j 1, r, k);}int findKthLargest(vectorint nums, int k) {int n nums.size();return quickselect(nums, 0, n - 1, n - k);}
};
