704 二分查找

思路

之前写过
这次复习巩固

代码

class Solution {
public:int search(vector<int>& nums, int target) {//左闭右闭int left = 0;int right = nums.size() - 1;while (left <= right){int mid = left + ((right - left) / 2);if (target < nums[mid]) {right = mid - 1;}else if (target > nums[mid]) {left = mid + 1;}else if (target == nums[mid]) {return mid;}}return -1;}
};

总结

1. 这次能很快写出来整体逻辑，之后要多复习思路，采用的是左闭右闭的写法。
2. 这次发现记忆薄弱的地方是 mid的计算方法，总是记不住，这次一开始也没记住
   mid的计算方法是：
   mid = left + ((right - left) / 2);

27 移除元素

思路

首先肯定能暴力解，O（n^2）

双指针法

• 有很多能使用双指针法的题目，4/5整理一下

一个快指针，一个慢指针
快指针用来寻找新数组（不含目标元素的数组）的元素
慢指针用来指向更新新数组下表的位置
所以快指针是用来遍历旧数组，跳过val值的元素，慢指针在遇到val的时候会变得比快指针慢(相差的位置是==val值的元素个数)
所以总体代码的思路是：
快指针用for循环遍历，里面的if判断条件是快指针指向的值不等于val，此时完成新值覆盖，同时慢指针向后移，更新新数组的长度，而当快指针指向的值等于val时，没有具体操作，这样代表着这一步循环里，新数组的长度没有新增（慢指针没后移），快指针继续向后遍历，寻找可以放入旧数组的元素。
虽然这里说的是新旧数组，实际上不需要额外的空间，是在同一块存储空间上完成的

代码

class Solution {
public:int removeElement(vector<int>& nums, int val) {int slowptr;int fastptr;slowptr = 0;fastptr = 0;for(; fastptr < nums.size(); fastptr ++) {if (nums[fastptr] != val ) {nums[slowptr++] = nums[fastptr];}}return slowptr;}
};

总结

1. 这题之前也写了，但是不太熟练，记入记忆曲线，常练常记
2. 主要是之前没有彻底理解快慢指针各自操作的含义

钢筋切割