高端交互式网站建设,不懂编程如何做网站,vs网站开发,有哪些网站或者公司招募做视频的目录 0 引言1 二分查找1.1 我的解题1.2 修改后1.3 总结 2 移除元素2.1 暴力求解2.2 双指针法#xff08;快慢指针#xff09; #x1f64b;♂️ 作者#xff1a;海码007#x1f4dc; 专栏#xff1a;算法专栏#x1f4a5; 标题#xff1a;代码随想录算法训练营第一天… 目录 0 引言1 二分查找1.1 我的解题1.2 修改后1.3 总结 2 移除元素2.1 暴力求解2.2 双指针法快慢指针 ♂️ 作者海码007 专栏算法专栏 标题代码随想录算法训练营第一天 | 704.二分查找、27.移除元素❣️ 寄语书到用时方恨少事非经过不知难 0 引言
1 二分查找 文档讲解https://programmercarl.com/0704.%E4%BA%8C%E5%88%86%E6%9F%A5%E6%89%BE.html 视频讲解https://www.bilibili.com/video/BV1fA4y1o715/ 做题状态有思路但是不清晰对于循环的判断条件还有区间的变换存在疑惑这些就是二分法的易错点 1.1 我的解题 class Solution {
public:int search(vectorint nums, int target) {int left, right, middle;left 0;right nums.size() - 1;if (right left){if (target nums[left]){return left;}else{return -1;}}while (right ! left 1){middle (right - left) / 2 left;cout middle middle endl;if (target nums[middle]){return middle;}else if (target nums[middle]){left middle;}else{right middle;}}if (target nums[left]){return left;}else if (target nums[right]){return right;}else{return -1;}}
};分析没有标准答案简洁原因是我的 left 和 right 赋值思路不对相差1。我是判断完大小后直接将 left 和 right 直接赋值 middle 。其实这样不对因为 middle 的值已经判断过了不需要再将这个索引值包含在 [left, right]区间中。
1.2 修改后
所以需要将代码进行如下修改这样可以省去很多其他条件的判断。
class Solution {
public:int search(vectorint nums, int target) {int left, right, middle;left 0;right nums.size() - 1;while (right left){middle (right - left) / 2 left;cout middle middle endl;if (target nums[middle]){return middle;}else if (target nums[middle]){left middle 1;}else{right middle - 1;}}return -1;}
};1.3 总结
看到顺序排列的数组就可以联想到二分法
二分法易错点
while循环条件 while(left right)while(left right) left和right的赋值 left middle1; right middle -1;left middle1; right middle;
其实while和left、right的赋值是对应的
使用while(left right)循环时left middle1; right middle -1;使用while(left right)循环时left middle1; right middle;
因为当 left middle1; right middle -1; left和right都把已经判断过的 middle 索引给排除在区间之外了所以循环遍历的条件需要包括 left和right 也就是 左闭右闭 区间。 当 left middle1; right middle; 可以发现right没有把已经判断过的 middle 索引给排除在区间之外所以循环条件不需要包括 right 的索引 也就是 左闭右开 区间。 使用左闭右闭 区间时最后left和right的结果是什么当 left等于right的时候此时middle也等于left和right还会再执行一次循环当nums[middle] target 时 right middle1; 也就是说right又往右移动了一位。当nums[middle] target 时right保持原位置不变。 这个特性可以帮助 35.搜索插入位置 这道题理解。
2 移除元素 文档讲解https://www.programmercarl.com/ 视频讲解https://www.bilibili.com/video/BV12A4y1Z7LP/?vd_sourced499e7f3a8e68e2b173b1c6f068b2147 做题状态暴力求解没太大难度快慢指针有需要理解的地方 2.1 暴力求解
一开始用暴力求解输出答案不对代码如下。我的的输出结果总是不能把最后一位元素给移除后面发现遍历时没有遍历到最后一个元素。i arraySize - 1 判断条件没写好应该是 i arraySize 或者 i arraySize - 1 。这个易错点以后要注意 class Solution {
public:int removeElement(vectorint nums, int val) {int arraySize nums.size();for (int i 0; i arraySize - 1; i){cout i i endl;if (nums[i] val){for (int j i; j arraySize - 1; j){nums[j] nums[j 1];}--arraySize;--i;}}return arraySize;}
};2.2 双指针法快慢指针
快指针遍历元素值 慢指针存储新数组的元素值
思路 遇到等于目标元素的值就跳过遇到不等于目标元素的值就进行赋值。借助两个索引值fastIndex和slowIndex实现fastIndex遇到目标元素就跳过此时slowIndex不动因为目标元素不需要存储。然后遇到不等于目标元素的值就进行赋值。此时是fastIndex在前面探路然后slowIndex将fastIndex探路得到的结果进行保存。
因为数组的存放是顺序的所以只有在遇到不等于目标元素的值时slowIndex才会增加一然后将非目标值保存下来。
fastIndex从头遍历到尾所以直接用fastIndex作为遍历元素条件为 fastIndex nums.size() 即可。然后当 fastIndex 所指元素不等于目标元素值时此时将 fastIndex 的值赋值给slowIndex 处。并且slowIndex加一。由此可知 nums 数组中有多少个不等于目标值的元素个数就是slowIndex。
class Solution {
public:int removeElement(vectorint nums, int val) {int fastIndex;int slowIndex 0;for ( fastIndex 0; fastIndex nums.size(); fastIndex){if (nums[fastIndex] ! val){nums[slowIndex] nums[fastIndex];slowIndex;}}return slowIndex;}
};
