【算法训练营day1】LeetCode704. 二分查找 LeetCode27. 移除元素LeetCode704. 二分查找【【算法训练营day1】LeetCode704. 二分查找 LeetCode27. 移除元素】题目链接：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;}};
经验总结扩展阅读
- CAN随机度测试
- AVX图像算法优化系列二: 使用AVX2指令集加速查表算法。
- 盒装豆腐放冰箱能放几天
- 感情熬到尽头就分开的星座
- 哪些星座女假分手常常变真分手
- 冰美式和冰拿铁的区别
- 黑芝麻煮粥可以直接放进煮吗
- 木姜子的食用方法
- 青岛啤酒节白天开吗
- 在爱人面前会变得蠢蠢的星座