704 二分查找
- 文章链接
- 什么是二分查找？
将一组有序数据分成两半，找出目标值所在的那一半，将其再次分成两半，如此往复，每一次拆分都会减小数据范围，最终找到目标值。
- 代码
class Solution { public: int search(vector<int>& nums, int target) { int left = 0; int right = nums.size() - 1; int res = -1; while(left <=right){ int middle = left + (right - left )/2; if(nums[middle] < target ){ left = middle + 1; }else if(nums[middle] > target){ right = middle - 1; }else{ res = middle; break; } } return res; } };
- 思路
因为之前已经刷过几次，因为不是科班所以第一次见这类题的时候几乎蒙圈，看了随想录的讲解才有的解题思路。我的理解就是一半一半的拆。但是需要注意的是二分法的区间。左闭右开和左闭右闭两者对应的middle赋值方法是不一样的。防止混淆我一直用左闭右闭。
- 感受
第三次刷这个题了，第一次艰难，第二次有些卡顿，第三次秒杀。加油。
27. 移除元素
- 文章链接
- 看到题目时的想法
没有什么头绪，练暴力解也要想半天
- 看完解题思路后的想法
先看的暴力解，一目了然，不用看视频讲解。看了1分钟左右，马上开始暴力解。
然后看的单向双指针，也是一目了然，看完后很快就写出来了。（不是抄答案，理解思路独立coding）
相向双指针：看了代码还是不理解，自己在草稿上画了一下就理解了，讲的还是非常通透的。
- 难点
不看文章一点不会，看了文章一点就通。难点主要是双向双指针的方法。
- 代码
暴力解
class Solution { public: //暴力解 int removeElement(vector<int>& nums, int val) { int size = nums.size(); for(int i = 0 ;i < size ;++i){ if(nums[i] == val){ for(int j = i ;j < size - 1;++j){ nums[j] = nums[ j +1]; } size --; i--; } } return size; } };
单向双指针
class Solution { public: //单向双指针 int removeElement(vector<int>& nums, int val) { int slow_index = 0; for(int fastindex = 0;fastindex < nums.size() ;++fastindex){ if(val != nums[fastindex]){ nums[slow_index++ ] = nums[fastindex]; } } return slow_index; } };
相向双指针
class Solution { public: //相向双指针，左侧指针移动到val前一个index，把右侧不等于val的值放入val所在位置，右侧索引减一，如此往复直到结束 int removeElement(vector<int>& nums, int val) { int left = 0; int right = nums.size() - 1; while(left <= right){ //寻找val所在的索引，目的为了存放后面不等于val的值 while(left<=right && val != nums[left]){ left++; } //找到一个val， right-1；该位置的值没必要放入left位置。 while(left<=right && val ==nums[right]){ right--; } //将后面不等于val的值移入val所在位置，同时right-1 if(left<right){ nums[left++] = nums[right --]; } } return left; } };
收获
日拱一卒，通透理解了二分查找和双指针方法
