代码随想录算法训练营Day1
704二分查找
算法思路
其实算法本身没有什么难度,但是学习了卡哥的题解后对二分思路更加清晰了,分两种写法真的可以帮助理清思路,弄明白为什么有这个等号或没有这个等号,为什么减一还是不减一。(全文middle采用下取整)
其实只要把握住一点,最后是否要减一就取决于target能否被新区间盖住,对于左闭右闭来说,既然已经判断过vec[middle]==target这个条件,那么right取middle已经不可能是目标值了,自然是要减一;对于左闭右开来说,middle-1很可能就是目标值,如果取成开区间还减一的话,那么很可能导致搜索遗漏,把握住让target不逃出区间这个原则我们就很容易把握各种区间的写法了。
先来一个左闭右闭的写法
class Solution {
public:
int search(vector<int>& nums, int target) {
int left,middle,right;
left=0;
right=nums.size()-1;
while (left<=right)
{
middle=left (right-left)/2;
if (nums[middle]==target)
{
return middle;
}
else{
if (nums[middle]<target)
{
left=middle 1;
}
else{
right=middle-1;
}
}
}
return -1;
}
};
这个是左闭右开(注意初始搜索区间,别让最后一个被开区间删了)
class Solution {
public:
int search(vector<int>& nums, int target) {
int left,middle,right;
left=0;
right=nums.size();
while (left<right)
{
middle=left (right-left)/2;
if (nums[middle]==target)
{
return middle;
}
else{
if (nums[middle]<target)
{
left=middle 1;
}
else{
right=middle;
}
}
}
return -1;
}
};
27移除元素
常规的暴力法就不写了……双指针法是今天的学习重点,实现过程遇见了很多问题,也都在这里写一写
快慢指针的思路就是用一个快指针遍历整个数组,来寻找和val不等的元素,而慢指针作为一个存储容器等待快指针的数据返还。这个题目思路非常简单,但是由于我对题中数据范围没有看清,用了nums.size()-1从而频繁报错……不过因为是cpp初学者,vector的几个基本操作也不熟悉,就把今天学会的几个基本函数也写在小结里吧。
上代码
class Solution {
public:
int removeElement(vector<int>& nums, int val) {
int slowindex,i;
slowindex=0;
for (i=0;i<nums.size();i )
{
if (nums[i]!=val)
{
nums[slowindex]=nums[i];
slowindex ;
}
}
return slowindex;
}
};
小结
第一天的题目比较简单,但是还是学到了不少东西,比如vector的几个基本操作,第二题我也试过使用vector.erase进行删除,但是时间上明显不如双指针法。vector.push_back();vector.pop_back();vector.size();vector.erase(index);还有学习了class solution这类写法的好处,可以将函数进行归类,不会全部变成全局函数,在大型项目中容易出现重名之类的现象。今天的收获大概就是这些~
这篇好文章是转载于:学新通技术网
- 版权申明: 本站部分内容来自互联网,仅供学习及演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系,请提供相关证据及您的身份证明,我们将在收到邮件后48小时内删除。
- 本站站名: 学新通技术网
- 本文地址: /boutique/detail/tanhgekcai
-
photoshop保存的图片太大微信发不了怎么办
PHP中文网 06-15 -
Android 11 保存文件到外部存储,并分享文件
Luke 10-12 -
《学习通》视频自动暂停处理方法
HelloWorld317 07-05 -
word里面弄一个表格后上面的标题会跑到下面怎么办
PHP中文网 06-20 -
photoshop扩展功能面板显示灰色怎么办
PHP中文网 06-14 -
微信公众号没有声音提示怎么办
PHP中文网 03-31 -
excel下划线不显示怎么办
PHP中文网 06-23 -
怎样阻止微信小程序自动打开
PHP中文网 06-13 -
excel打印预览压线压字怎么办
PHP中文网 06-22 -
TikTok加速器哪个好免费的TK加速器推荐
TK小达人 10-01