代码随想录算法训练营第一天 | 704.二分查找 27. 移除元素 977.有序数组的平方

理论知识study

首先数组是一个连续存储的数据结构，对于二维数组而言，在c++中通常连续排列，但在Java中并不是这样，如果想要验证会发现结果给不出一个实际的地址，而是虚拟的。

数组里的元素只能覆盖不能删除。

c语言中的array和c++里的vector<int>本质上是一样的，都是连续存储的。

数组存储的元素要是相同的数据类型。

704. 二分查找

 题目链接：704. 二分查找 - 力扣（LeetCode）

视频讲解：手把手带你撕出正确的二分法 | 二分查找法 | 二分搜索法 | LeetCode：704. 二分查找_哔哩哔哩_bilibili

二分这种类型的题目已经很熟悉了，但是可能在实际操作过程中存在可能的失误

代码随想录记录的方法让我可以更好地完成二分题目，减少错误率

思路就是：先确定好不变量：左闭右开，左闭右闭 两种区间规则 

根据这两种不同的规则，可以写出不同的代码：

1. 左闭右开：
 

class Solution {
public:int search(vector<int>& nums, int target) {int left=0,right=nums.size();//左闭右开，右边不计入，所以选sizewhile(left<right){//左闭右开，left=right不存在int mid=left+((right-left)>>1);if(nums[mid]>target){right=mid;}else if(nums[mid]<target){left=mid+1;}else{return mid;}}return -1;}
};

2. 左闭右闭

class Solution {
public:int search(vector<int>& nums, int target) {int left=0,right=nums.size()-1;//左闭右闭，右边计入，所以选size-1while(left<=right){//左闭右闭，left=right存在int mid=left+((right-left)>>1);if(nums[mid]>target){right=mid-1;}else if(nums[mid]<target){left=mid+1;}else{return mid;}}return -1;}
};

27. 移除元素

 题目链接：27. 移除元素 - 力扣（LeetCode）

视频讲解：

数组中移除元素并不容易！ | LeetCode：27. 移除元素_哔哩哔哩_bilibili

这个题刚开始有些懵，除了暴力解法外，双指针解法也是个不错的选择，但始终无法完全通过。

学习之后通过反思总结发现了自己的错误。

1. 暴力解法：

class Solution {
public:int removeElement(vector<int>& nums, int val) {int size=nums.size();for(int i=0;i<size;i++){if(nums[i]==val){for(int j=i+1;j<size;j++){nums[j-1]=nums[j];}i--;//由于上面已经移动过数组，所以当前位置仍需要判断是否等于val，所以需要i--size--;//这个也减小了}}return size;}
};

2. 双指针解法：

• 快指针：寻找新数组的元素 ，新数组就是不含有目标元素的数组
• 慢指针：指向更新 新数组下标的位置

class Solution {
public:int removeElement(vector<int>& nums, int val) {//双指针法//快指针：寻找新数组的元素 ，新数组就是不含有目标元素的数组//慢指针：指向更新 新数组下标的位置int j=0;for(int i=0;i<nums.size();i++){if(nums[i]!=val){nums[j++]=nums[i];}}return j;}
};

977.有序数组的平方

 题目链接：977. 有序数组的平方 - 力扣（LeetCode）

视频讲解：

双指针法经典题目 | LeetCode：977.有序数组的平方_哔哩哔哩_bilibili

解法：

class Solution {
public:vector<int> sortedSquares(vector<int>& nums) {vector<int> r(nums.size(), 0);//创建数组并初始化int l=nums.size()-1;//双指针，一个是指向开始，一个指向末尾，始终满足指向开始的小于等于指向末尾的for(int i=0,j=l;i<=j;){//这个i<=j至关重要if(nums[i]*nums[i]>nums[j]*nums[j]){r[l--]=nums[i]*nums[i];//这个l大的确认了，下一个就是l--i++;//被选中，往右移}else{r[l--]=nums[j]*nums[j];j--;}}return r;}
};