邵阳网站建设的话术,永嘉网站建设工作室,wordpress只启用cdn,2023年企业所得税最新政策系列综述#xff1a; #x1f49e;目的#xff1a;本系列是个人整理为了秋招算法的#xff0c;整理期间苛求每个知识点#xff0c;平衡理解简易度与深入程度。 #x1f970;来源#xff1a;材料主要源于代码随想录进行的#xff0c;每个算法代码参考leetcode高赞回答和… 系列综述 目的本系列是个人整理为了秋招算法的整理期间苛求每个知识点平衡理解简易度与深入程度。 来源材料主要源于代码随想录进行的每个算法代码参考leetcode高赞回答和其他平台热门博客其中也可能含有一些的个人思考。 结语如果有帮到你的地方就点个赞和关注一下呗谢谢 数据结构基础知识总结篇 文章目录二分查找基本二分法搜索插入位置在排序数组中查找元素的第一个和最后一个位置快慢指针移除元素有序数组的平方滑动窗口移除元素参考博客点此到文末惊喜↩︎ 二分查找
基本二分法
二分法前提有序无重复的数组 数组有序一次比较即可确定需要查找的那一半效率高的关键数组中无重复元素一旦有重复元素使用二分查找法返回的元素下标可能不是唯一查找对象为数组数组可以进随机存取 边界处理方式 左闭右闭 [left, right]基本算法可以定位后再寻找相同元素区域的左右边界左闭右开 [left, right)可以在存在相同元素时定位到相同元素区域的 左右边界 leetcode题目704. 二分查找 // *****************前闭后闭的基本二分查找可以代替下一种*******************
int search(vectorint nums, int target) {
// 0. 健壮性检查if(nums.size() 0) return -1;
// 1. 定义边界指针指向遍历数组区域的边界位置int left 0;int right nums.size() - 1; // 定义target在左闭右闭的区间里
// 2. 基本算法步骤的循环 while (left right) { // 前闭后闭用// - 定义int mid left ((right - left)2);// 防止溢出 等同于(left right)/2// 目标值在左区间if (target nums[mid]) {right mid - 1; // 目标值在右区间} else if (target nums[mid]) {left mid 1; // 找到目标值即相等时} else {return mid; // 数组中找到目标值直接返回下标}}
// 3. 添加进行左右边界的定位操作// ...return -1;// 未找到目标值
}mid L ((R - L)1) 防溢出如果L 和 R太大直接相加就有溢出的可能移位等价于除法算法但是效率高 使用前闭后闭的二分区域查找可以在查找target位置后再进行相同元素相连区域的定位操作。 搜索插入位置
该题与二分查找类似但是最后返回的是插入的位置所以没找到时应该返回的是最后比较的位置的后一个leetcode题目35. 搜索插入位置 class Solution {
public:int searchInsert(vectorint nums, int target) {int left 0;int right nums.size()-1;while (left right){int mid left ((right-left) 2);if(target nums[mid]){right mid - 1;}else if(target nums[mid]){left mid 1;}else{return mid;}}return left;// left为相等值未找到时应插入的位置}
};在排序数组中查找元素的第一个和最后一个位置
该题与二分查找类似但是最后应该对于相邻相同元素的起始和末尾进行遍历判断leetcode题目35. 搜索插入位置 vectorint searchRange(vectorint nums, int target) {vectorint res(2,-1);// 初始化两个值为-1的元素if(nums.size() 0) return res; // 基本二分法int left 0;int right nums.size()-1;int mid;while(left right){mid left ((right -left) 2);if(target nums[mid]){right mid - 1;}else if(target nums[mid]){left mid 1;}else{break;// 保留mid}}// 寻找相似相邻区间的左右边界int l mid;int r mid;if(nums[mid] ! target){return res;}else{while (l 0){if(nums[l] nums[l-1]){l--;}elsebreak;}while (r nums.size()-1){if(nums[r] nums[r1]){r;}elsebreak;}}cout res[0] endl;res[0]l;res[1]r;return res;}快慢指针
移除元素
快慢指针 快指针fast用于条件判断慢指针slow用于位置保存 leetcode题目27. 移除元素 给你一个数组 nums 和一个值 val你需要 原地 移除所有数值等于 val 的元素并返回移除后数组的新长度。 不要使用额外的数组空间你必须仅使用 O(1) 额外空间并原地修改输入数组。 元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。 示例 1: 给定 nums [3,2,2,3], val 3, 函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。 你不需要考虑数组中超出新长度后面的元素。 示例 2: 给定 nums [0,1,2,2,3,0,4,2], val 2, 函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 你不需要考虑数组中超出新长度后面的元素。 int removeElement(vectorint nums, int val) {// 快慢指针int slow 0;int fast slow;while(fast nums.size()){if(nums[fast] val){// 如果元素值为val快指针选择下一个fast;}else{// 如果找到非val元素将该元素赋值给nums[slow]nums[slow] nums[fast];slow;fast;}}return slow;
}有序数组的平方
循环不变量循环中的变量的逻辑 初始化 迭代前循环不变量为真保持 迭代中前后状态的转移仍然能保证循环不变量为真终止 迭代后循环不变量可以提供有用结果 逆向思维充分利用不变的逻辑进行程序的简化。如下题中的从后向前和从两边向中间的遍历方式。leetcode题目977. 有序数组的平方 vectorint sortedSquares(vectorint nums) {// 用双指针指向两端从两端向中间进行逼近int left 0;int right nums.size()-1;// 从后向前将每次比较较大的填入新的数组中vectorint res(nums);int index right;while (left right) {if (nums[left] * nums[left] nums[right] * nums[right]) {res[index--] nums[left] * nums[left];left;} else {res[index--] nums[right] * nums[right];--right;}}return res;
} 滑动窗口
移除元素 滑动窗口不断的调节子序列的起始位置和终止位置从而得出我们要想的结果 滑动窗口基本框架 void slidwindow(vectorint nums)
{// 1. 窗口区间为[left, right)int left 0;int right 0;// 2. 直到到达窗口右边界while(right nums.size()){// - 扩大右边界并更新窗口状态...right;// - 窗口到达什么状态需要收缩while(需要收缩){// - 缩小左边界并更新窗口状态...left;}}
}leetcode题目209. 长度最小的子数组 int minSubArrayLen(int target, vectorint nums) {int left 0;int right 0; int res INT_MAX;int len 0;int windows_sum 0;while(right nums.size())//窗口区间为[left, right){windows_sum nums[right];//更新窗口状态right;while(windows_sum target)//收缩窗口{len right - left;res min(res, len);windows_sum - nums[left];//更新窗口状态left;}}return res INT_MAX? 0:res;
}少年我观你骨骼清奇颖悟绝伦必成人中龙凤。 不如点赞·收藏·关注一波 点此跳转到首行↩︎
参考博客 leetcode二分查找 代码随想录 二分查找算法详解 待定引用 待定引用 待定引用 待定引用 待定引用
