LC704. 二分查找
二分法编码时的难点，在于对数组边界问题的处理上。处理该问题的思想有两种，这两者的区别是基于数学里区间的概念去解释的。
对于区间，[1,1]的取值是合理的，而[1,1)是不合理的。
-
左闭右闭写法：
因为[1,1]是合理的，所以left是可以等于right的，而且在更新索引下标index时，对于左边界或右边界的更新，是不能包含上一轮比较中已经被包含的数据的。
////左闭右闭思想
int size = nums.size() - 1;
right = size;
while (left <= right)
{
index = (left + right) >> 1;
if (target == nums[index])
{
return index;
}
else if (nums[index] > target)
{
right = index - 1;
}
else
{
left = index + 1;
}
}
-
左闭右开写法：
////左闭右开思想
int size = nums.size();
right = size;
while (left < right)
{
index = (left + right) >> 1;
if (target == nums[index])
{
return index;
}
else if (nums[index] > target)
{
right = index - 1;
}
else
{
left = index + 1;
}
}
LC27. 删除元素
想到了用双指针，但自己想问题太过复杂了，而且复杂的写法会导致很多特殊的情况没有考虑到，自感觉还是刷题比较少，继续加油。
注意点：
-
left第一次匹配val后，后面的非val值都要向左边移动。为了实现这点，在if (nums[left] != val)这个判断下，总是有nums[left] = nums[right]赋值。即使可能在还未匹配val之前有做无用赋值的工作，但保证了代码的通用性。
-
开始使用 while (left < size)或者 while (right < size)做最外层的循环判断都不正确，前者可能会导致right向右移动越界，后者会导致left还没索引完vector全部元素，right就已经到达右边界了，从而可能导致val_count偏小的情况。最好的方法就是对数组索引做边界判断处理。
int removeElement(vector<int>& nums, int val)
{
int left = 0, right = 0;
int val_count = 0;
int size = nums.size();
while (right < size)
{
if (nums[right] == val)
{
val_count++;
}
if (nums[left] != val)
{
nums[left++] = nums[right++];
}
else
{
while (nums[right] == val)
{
right++;
if (right >= size) //超过边界的考虑
{
right = size - 1;
break;
}
if (nums[right] == val)
{
val_count++;
}
}
nums[left++] = nums[right++];
}
}
return size - val_count;
}
开始自己的写法还是有一些情况没有考虑到的，如下图所示：
但粗略写法的同时自己还是有所思考：
思考：凡是涉及到双指针的问题，都要考虑全两者的边界问题。尤其是与数组或者有界区域相关的内存下，做边界判断处理是最有效的方法。
官方双指针的思想是让双指针从两头各自出发，但这种解法下，我弄不太明白循环条件while (left < right)和while (left <= right)的差异以及其对返回值是return left或者是return left+1的影响
int removeElement(vector<int>& nums, int val) {
int left = 0, right = nums.size();
while (left < right) {
if (nums[left] == val) {
nums[left] = nums[right - 1];
right--;
} else {
left++;
}
}
return left;
}
最后参考Carl的快慢指针思想，自己再写一次：
//// 快指针用于获取新数组中的元素
//// 慢指针获取新数组中需要更新的位置
int removeElement(vector<int>& nums, int val)
{
int slow = 0, fast = 0;
int size = nums.size();
for (fast = 0; fast < size; fast++)
{
if (nums[fast] != val)
{
nums[slow] = nums[fast];
slow++;
}
}
return slow;
}