代码随想录算法训练营第一天| LeetCode:704. 二分查找、27. 移除元素

题目链接：LeetCode 704 二分查找

c++代码

class Solution {
public:
    int search(vector<int>& nums, int target) {
         int l = 0; 
         int r = nums.size()-1;
         while (l<r) {
            int middle = (l+r)/2;
            if (nums[middle]>=target) r=middle;
            else l = middle + 1;
         }
         if (nums[l]==target) return l;
         else return -1; 
    }
};

1. 二分查找步骤（伪代码）

   • 写出left和right，让元素在这个范围中

   • while(left<right)

   • middle ：left+right>>1或left+right+1>>1

   • if(check()) 缩小范围（这个check能显现出二段性，且筛选出答案） left=middle或right=midlle

   • else left=middle+1或right=middle-1;

   重点：一右加一不变，二左减一变大

   理解：

   • 一代表求满足条件的第一个值，二代表求满足条件的最后一个值

   • 右代表r=middle,左代表l=middle

   • 加一代表 l=middle+1,减一代表r=middle-1;

   • 不变代表求middle时不加1，变大代表求middle时加1

什么时候用二分：有序能让答案分出二段性//题目中需要寻找值

题目链接：LeetCode 27 移除元素

暴力做法

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 < nums.size(); j++) nums[j-1] = nums[j];
                size--;
                i--;
            }
        }
        return size;
    }
};

官方解释

• 数组只能进行移动的增删，删除只能进行覆盖
• 覆盖后的长度不变，因为后面的值还是一样的

nums.size()--;

• 覆盖了，当前的i还有可能是那个数

i--；

双指针做法

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

双指针法（快慢指针法）： 通过一个快指针和慢指针在一个for循环下完成两个for循环的工作

• 快指针：新数组所需要的元素，寻找新数组的元素 ，新数组就是不含有目标元素的数组、
• 慢指针：新数组更新的位置，每次快指针找到新元素，都更新这个元素

只要明白两个指针的含义，双指针不难