704.二分查找
思路
最开始了解的二分查找法，竟只是闭区间的一种，没想到还有这么多说法
讨论其根本数学逻辑，是落在集合中，若为闭区间查找left/right=mid±1是核心思想，必须把查找过的全部剔除，不然查找过的数据仍然在集合中可能出错，就一定会出错；若为开区间，什么是开区间？落在算法中可以设置左、右虚节点代表（全是花活），此时left/right=mid核心思想。
开区间和闭区间的区别本质还体现在终止条件中，一想便知。
谨记二分法使用的严格条件：有序、不重复
闭区间图解：
开区间图解：
题解
class Solution {
public:
int search(vector<int>& nums, int target)
{//最常用的版本闭区间
// int left = 0,right = nums.size()-1;
// while(left <= right)
// {
// int mid = left+(right-left)/2;
// if(nums[mid]>target){right = mid-1;}
// else if(nums[mid]<target){left = mid+1;}
// else return mid;
// }
// return -1;
//学习的左闭右开版本--有区间的概念，虚节点
// int left = 0,right = nums.size();
// while(left<right)
// {
// int mid = left+(right-left)/2;
// if(nums[mid]>target){right = mid;}
// else if(nums[mid]<target){left = mid+1;}
// else return mid;
// }
// return -1;
//全部开区间
int left = -1,right = nums.size();
while(left+1<right)
{
int mid = left+(right-left)/2;
if(nums[mid]>target){right = mid;}
else if(nums[mid]<target){left = mid;}
else return mid;
}
return -1;
}
};
27.移除元素
思路
最开始的思路：两个for循环，把有用的元素放到前面，无用的放到后面，虽然能解决问题，但不像正规军队。
暴力解法：题目最本质的要求是？是移除数组中的元素，而显而易见数组中的元素无法删除，只能整体移动覆盖且size-1，解法由此得来。
双指针（数组复用）解法：fast负责不断向后寻找需要数据并赋值给slow位置，slow不断向前构成新数组
题解
class Solution {
public:
int removeElement(vector<int>& nums, int val)
{//我的方法
// int number = 0;
// for(int i = 0;i<nums.size();i++)
// {
// if(nums[i] == val)
// {
// for(int j = nums.size()-1;j>=0;j--)
// {
// if(nums[j]!=val)
// {
// nums[i] = nums[j];
// nums[j] = val;
// number++;
// break;
// }
// if(i==j)
// {
// return number;
// }
// }
// }
// else number++;
// }
// return number;
//暴力覆盖法
// int number = nums.size();
// for(int i = 0;i<number;i++)
// {
// if(nums[i] == val)
// {
// for(int j = i+1;j<number;j++)
// {
// nums[j-1] = nums[j];
// }
// i--;
// number--;
// }
// }
// return number;
//双指针，新数组法
int fast = 0, slow = 0;
for(fast = 0;fast<nums.size();fast++)
{
if(nums[fast]!=val)
{
nums[slow] = nums[fast];
slow++;
}
}
return slow;
}
};
977.有序数组的平方
题目链接：977.有序数组的平方
文档讲解：代码随想录
状态：瞟了眼思路轻松解决
思路
最开始的思路：全部平方，再排个序，美滋滋啊，但是不懂排序这个题目就失去了意义。
双指针法：本题的双指针和上一个题性质明显不同，对于有序序列，平方大小一定是两边大中间小，双指针由此得来。
图解：
题解
class Solution {
public:
vector<int> sortedSquares(vector<int>& nums)
{//暴力思想
// for(int i = 0;i<nums.size();i++)
// {
// nums[i] *= nums[i];
// }
// sort(nums.begin(),nums.end());
// return nums;
//双指针法
int k = nums.size()-1;
vector<int> result(nums.size(),0);
for(int i = 0, j = nums.size()-1;i<=j;)
{
if(nums[i]*nums[i]>=nums[j]*nums[j]){result[k--] = nums[i]*nums[i];i++;}
else {result[k--] = nums[j]*nums[j];j--;}
}
return result;
}
};