代码随想录一刷记录Day1—— leetcode704. 二分查找 leetcode27. 移除元素 leetcode977.有序数组的平方
前言
之前就有刷代码随想录，但奈何总是三天打鱼两天晒网，而且刷的也很囫囵吞枣，于是乎决定参加代码随想录训练营，准备精刷一遍，希望自己能坚持下去，结营后自己的算法水平能更上一个level，冲ing！
leetcode704. 二分查找
题目链接leetcode704. 二分查找
思路
题目中明确说明给定的数组是有序数组且无重复元素，此时可以想到使用二分查找。
这也是使用二分查找的前提，因为有重复元素的话使用二分查找返回的下标不唯一。
使用二分查找时，要注意边界的界定，保持循环不变量原则，即在while循环中每一次边界的处理都要根据区间的定义来写，例如本题中while(left <= right) 和 while(left < right)在处理 更新右区间的位置完全是两码事
此外还要注意在代码中获取中间值下标，要写成middle = left + (right - left)/2; 以 防止溢出，作用等同于(left + right)/2
代码
//针对左闭右闭区间classSolution{public:intsearch(vector<int>&nums,inttarget){intleft=0;intright=nums.size()-1;while(left<=right){intmiddle=left+(right-left)/2;// 防止溢出 等同于(left + right)/2if(target>nums[middle]){left=middle+1;}elseif(target<nums[middle]){right=middle-1;}else{returnmiddle;}}return-1;}};//针对左闭右开区间classSolution{public:intsearch(vector<int>&nums,inttarget){intleft=0;intright=nums.size();while(left<right){intmiddle=left+(right-left)/2;// 防止溢出 等同于(left + right)/2if(target>nums[middle]){left=middle+1;}elseif(target<nums[middle]){right=middle;}else{returnmiddle;}}return-1;}};leetcode27. 移除元素
题目链接leetcode27. 移除元素
思路
本题一种是暴力法，一种是经典的双指针法（快慢指针）。
快慢指针核心是要搞清快慢指针分别代表的含义！
快指针：寻找新数组的元素 （删除目标元素后）
慢指针：指向更新（新数组下标的位置），所以本题代码中慢指针的值就是最终要的返回值
注意：使用暴力法在删除某元素后，对该元素后面的元素整体前移时，数组访问不要越界。
我第一次写成了如下，导致了越界访问错误（当 j 循环到最后一个有效索引（即 len-1）时，nums[j+1] 变成了 nums[len]，这已经超出了向量的末尾）
if(nums[i]==val){for(intj=i;j<len;j++){//如果下面不变的话可以写成 j < len -1nums[j]=nums[j+1];}}代码
//方法一：暴力法classSolution{public:intremoveElement(vector<int>&nums,intval){intsize=nums.size();for(inti=0;i<size;i++){if(nums[i]==val){for(intj=i+1;j<size;j++){nums[j-1]=nums[j];}i--;// 因为下标i以后的数值都向前移动了一位，所以i也向前移动一位size--;// 此时数组的大小-1}}returnsize;}};//方法二：快慢指针法classSolution{public:intremoveElement(vector<int>&nums,intval){intlen=nums.size();intslow=0;for(intfast=0;fast<len;fast++){if(nums[fast]!=val){nums[slow++]=nums[fast];}}returnslow;}};leetcode977.有序数组的平方
题目链接leetcode977.有序数组的平方
思路
其实这道题能想到数组内元素平方后最大值一定位于数组左右最两侧，就好解了，使用双指针法。
代码
classSolution{public:vector<int>sortedSquares(vector<int>&nums){intlen=nums.size()-1;vector<int>result(nums.size(),0);for(inti=0,j=nums.size()-1;i<=j;){if(nums[i]*nums[i]>nums[j]*nums[j]){result[len--]=nums[i]*nums[i];i++;}else{result[len--]=nums[j]*nums[j];j--;}}returnresult;}};