704. 二分查找
https://leetcode.com/problems/binary-search/
由于之前跟着Carl哥学了一阵二叉树，二叉树涉及到很多递归方面的知识。所以我下意识的就带入了递归的想法去做这道题。这道题写的也不是很轻松，在终止条件（也就是左闭右闭还是左闭右开）上面做了很多尝试。
这是我自己写的递归方式的二分查找。
class Solution {
public:
int res = -1;
void bs(vector<int>& nums, int start, int end, int target){
int mid_index = (start+end)/2;
if(start > end){
res = -1;
}
else{
if(nums[mid_index] < target){
bs(nums,mid_index+1,end,target);
}
else if(nums[mid_index] > target){
bs(nums,start,mid_index-1,target);
}
else{
res = mid_index;
}
}
}
int search(vector<int>& nums, int target) {
if((nums.size() == 1) && (nums[0] != target))
return -1;
bs(nums, 0, nums.size(), target);
return res;
}
};
这是看了讲解之后写的左闭右开的方法。
class Solution {
public:
int search(vector<int>& nums, int target) {
int left = 0;
int right = nums.size();
int mid = nums.size()/2;
while(left < right){
mid = (left + right)/2;
if(nums[mid] > target){
right = mid;
}
else if(nums[mid] < target){
left = mid+1;
}
else{
return mid;
}
}
return -1;
}
};
27.移除元素
https://leetcode.com/problems/remove-element/
我首先想到的办法是调用erase直接删除数值等于val的元素。
class Solution {
public:
int removeElement(vector<int>& nums, int val) {
for (auto i = nums.begin(); i != nums.end();++i) {
if (*i == val) {
nums.erase(i);
i--;
}
}
return nums.size();
}
};
看到Carl在笔记里提示说使用双指针，我的第一反应是创建两个int指针跟踪，但看了给的答案，其实并没有那么复杂，用两个int来表示index就可以。快的指针一直从头走到尾，慢的指针只在 快指针所在的值不等于val的时候再在原本的数组上写下快指针当前的数值就可以。我照着写了一遍：
class Solution {
public:
int removeElement(vector<int>& nums, int val) {
int p1 = 0;
for(int p2=0; p2<nums.size(); p2++){
if(nums[p2] != val){
nums[p1] = nums[p2];
p1++;
}
}
return p1;
}
};
