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

给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target  ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

判断条件是 value = target
因为数组是升序，其实每种查找方法应该相差不大？
不过题目都标了二分查找了emmm 

class Solution {
    public int search(int[] nums, int target) {
        // 左闭右闭的情况 左闭右开就暂时不想了，心累orz
        // target和区间边界判断，肯定不在直接退出
        if (target < nums[0] || target > nums[nums.length - 1]) {
            return -1;
        }
        //边界
        int left = 0, right = nums.length - 1;
        // 停止条件：target和某一边界重合 
        // 闭区间是可以取到边界的所以是<=不是<
        while (left <= right) {
            //中间值 
            int mid = left + ((right - left) / 2);
            if (nums[mid] == target){
                return mid;
            }
            // 大于mid 落在右边 更新left    
            // 因为一开始考虑的是闭区间，所以要保证循环时即使改变范围也还是闭区间 所以有mid+1 和mid-1
            else if (nums[mid] < target){
                left = mid + 1;
            }
            // 小于mid 落在左边 更新right      
            else if (nums[mid] > target){
                right = mid - 1;
            }  
        }
        return -1;

    }
}

给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。
不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。
元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

 O(1) 额外空间并 原地 修改输入数组==>意思是只有一个多余的空位可以考虑？
做了二分题目后第一反应是：用sort先排序，再二分查找，但是这题没说元素不重复... 
卒

class Solution {
    public int removeElement(int[] nums, int val) {
        // 快慢指针 慢指针
        int slowIndex = 0;
        // 快指针 寻找新数组所需的元素
        for (int fastIndex = 0; fastIndex < nums.length; fastIndex++) {
        // 这一步真的...去掉=target的 其实就是留下≠target的，
        // 如有target，slow留在原地，fast向前走，用不是target的后面的值来覆盖掉前面的target
            if (nums[fastIndex] != val) {
                nums[slowIndex] = nums[fastIndex];
                slowIndex++;
            }
        }
        return slowIndex;
    }
}

其实参加训练营之前有练过一点点（从数组到字符串），但是这东西真的几天不复习就很难再想起来
而且口述思路看似简单，实际上写代码时才发现有很多细节是需要考虑的，之前面试写代码的时候发现数组的初始化都没法直接正确地写出来，基础还是不太牢，略痛苦
最近真的好多事啊，不过因为经历了这么多深刻明白一切只能靠自己，只有好好坚持下来才能达成自己的目的...

需要记忆的点：
    （704）
    1、有序、无重复数组用二分查找
    2、首先判断target和区间边界
    3、保证一开始是双闭区间的话，循环中改变边界也要是双闭区间，前后的两个区间不能重复包含某个边界值
    （27）
    1、首先把快慢指针法这种方法刻进DNA(到底怎么样才能想出这样的办法能不能给我看看你们的脑子
    2、快指针用来 向前移动找值
    3、慢指针用来 留在原地等覆盖
    4、一起向前的时候，就意味着值是满足需求的，留着；不一起向前，就是要覆盖 
    

本栏目推荐文章
• 2024/1/13 算法笔记
• 代码随想录 day18 找树左下角的值 路径总和 从中序与后序遍历序列构造二叉树
• Openharmony 跑 CV 算法
• .NET中的加密算法总结(自定义加密Helper类续)
• 算法练习题
• 算法学习Day26组合总和、分割回文串
• （坚持每天写算法）基础算法复习与学习part1基础算法1-7——高精度减法（处理t=1和t>1代码的写法，t为操作次数）
• 【SPFA】最短路的一种算法
• [代码随想录] 第四天
• darknet-yolov4训练自己的模型记录

随想录 训练营 随想 算法 元素最大值 训练营 随想 元素 随想录 训练营 随想 算法 算法 随想录 训练营 随想 算法 随想录 训练营 序列 算法 随想录 训练营 数组 训练营 随想 元素 代码 训练营 随想 元素 温度 算法 随想录 训练营 总和 子集 算法 随想录 训练营 算法 解数 随想录 训练营