【算法训练营day1】LeetCode704. 二分查找 LeetCode27. 移除元素
LeetCode704. 二分查找
题目链接：704. 二分查找
初次尝试
看到题目标题是二分查找，所以尝试使用二分查找的思想，代码思路是一直循环二分，直到两个指针相等，再判定所指元素是否等于target，这样对于任何输入都需要二分至尽头才能得出结论，果不其然提交后超时。
class Solution {
public:
int search(vector<int>& nums, int target) {
int low = 0, up = nums.size() - 1;
while (true) {
if (target <= nums[(low+up)/2]) {
up = (low + up) / 2;
}
else {
low = (low + up) / 2 + 1;
}
if (low == up) {
return target == nums[low] ? low : -1;
}
}
}
};
看完代码随想录后的想法
意识到了不需要对于任何输入都二分到尽头，可以在二分的过程中判断target是否与二分的中间点相等，如果相等就可以直接返回中间点的下标（当然这是在数组元素都不重复的前提下）。这是符合逻辑的，毕竟如果在二分判定的过程中已经找到了和target相等元素的下标，何必继续二分到尽头呢？直接返回不就完事了！
关于题解中讲到的循环不变量，也就是左闭右闭等的问题，我感觉对我个人不是难点，在初次尝试中就有类似的思考过程，感觉对于边界开闭的留意已经是一种习惯了，故在此不再赘述。
class Solution {
public:
int search(vector<int>& nums, int target) {
int low = 0, up = nums.size() - 1;
// 左闭右闭
while (low <= up) {
int mid = (low + up) / 2;
if (target < nums[mid]) up = mid - 1;
else if (target > nums[mid]) low = mid + 1;
else return mid;
}
return -1;
}
};
LeetCode27. 移除元素
题目链接：27. 移除元素
初次尝试
思路是使用暴力解法，直接两个for循环，外层遍历数组，内层寻找等于val的元素并更新数组。
class Solution {
public:
int removeElement(vector<int>& nums, int val) {
int numslen = nums.size();
for (int i = 0; i < numslen; i++) {
if (nums[i] == val) {
for (int j = i + 1; j < numslen; j++) {
nums[j-1] = nums[j];
}
numslen--;
i--;
}
}
return numslen;
}
};
然后想到当有连续多个等于val的元素时，每个都要更新一次实在是平添时间复杂度，于是修改了一下，当遇到连续多个等于val的元素时，判定一下有几个，然后一次性更新数组，看似优化了，其实换汤不换药，仍然是嵌套着的for循环，没有大的优化。
class Solution {
public:
int removeElement(vector<int>& nums, int val) {
int numslen = nums.size();
for (int i = 0; i < numslen; i++) {
int k = 0;
for (int j = i; j < numslen; j++) {
if (nums[j] == val) k++;
else break;
}
if (k > 0) {
for (int j = i + k; j < numslen; j++) {
nums[j-k] = nums[j];
}
numslen -= k;
}
}
return numslen;
}
};
看完代码随想录后的想法
双指针真是yyds！其实看到题解视频的开头我就突然明白怎么用双指针了，定义一个慢指针和一个快指针，快指针负责遍历整个数组，找出可以留下来的元素，每找到一个就把它告诉慢指针，慢指针只需要听令，把可以留下来的元素放到现在的坑里，然后+1跳到下一个坑即可。之所以有快慢指针之分是因为每次for循环，快指针都会+1，而慢指针看情况+1（当快指针指向可以留下来的元素的时候），所以慢指针一定不快于快指针。
class Solution {
public:
int removeElement(vector<int>& nums, int val) {
int numslen = nums.size();
int slow = 0;
for (int fast = 0; fast < numslen; fast++) {
if (nums[fast] != val) {
nums[slow++] = nums[fast];
}
}
return slow;
}
};
今日的小想法
对于刷题初期的我，感觉看到题目首先想到的还是如何暴力解出来，然后再进行优化，而题解往往有一些另辟蹊径的解法，所以多积累解题技巧是现阶段的主要任务。今日用时：约4h
标签：二分,val,LeetCode704,int,nums,day1,移除,numslen,指针 From： https://www.cnblogs.com/BarcelonaTong/p/16784235.html