LeetCode【刷题日记】：数组篇（1）含原理讲解

前言：经过前面对java语言的学习，大体的了解了java语言的基础内容和技术栈，而算法这篇，主要是培养我们的编程思维，让我们能在实际问题中运用编程思维解决问题，同时算法也是找工作，找实习面试中重要的一环，尤其是LeetCode，已经快成为算法的标准题库了，我们多刷肯定是有帮助的。

1.二分查找

题目原型：LeetCode 704

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

我的观点：这道题看着简单，实则也有很多容易让人犯迷糊的地方 ，让我们来详细的讲解一下这题。

首先，什么是二分查找，简单的说，就像是一个猜数字游戏，1-100，我们每次猜的数字都是范围的一半，这样就能根据结果排除一半的范围（大了，或者小了），从而更新我们查找的范围，提高了查找的效率。

题解一：（左闭右闭）

class Solution {
    public int search(int[] nums, int target) {
   
        int left=0;
        int right=nums.length-1;
        while(left<=right){
        int mid=left+((right-left)>>1);
        if(target==nums[mid]){
            return mid;
        }
        else if(target<nums[mid]){
            right=mid-1;
        }else{
            left=mid+1;
        }


        }

        return-1;

    }
}

分析一下：

我们先定义两个值，用来表示要查询的范围，最核心的就是while语句中的条件了，这里我们写的是 闭区间【】，意味着两边都能取到，那这个条件影响我们后面的什么呢？

最直接的影响就是我们后面更新区间的时候能不能取等号的问题，或者是加一，减一的问题

当两边都取闭区间时，我们拿target目标值和中间值进行比较，如果目标值小于中间值，那么我们就取中间值的左半部分区间，更新原来区间的right的值，由于都是闭区间，我们要把值更新成mid-1，，因为是闭区间，我们能取到mid，但是前提是目标值已经小于mid了

同理，如果是目标值大于mid，我们就更新原来区间的left，更新成mid+1，原理一样。

题解二：（左闭右开）

class Solution {
    public int search(int[] nums, int target) {
        int left = 0, right = nums.length;
        while (left < right) {
            int mid = left + ((right - left) >> 1);
            if (nums[mid] == target) {
                return mid;
            }
            else if (nums[mid] < target) {
                left = mid + 1;
            }
            else { // nums[mid] > target
                right = mid;
            }
        }
        // 未找到目标值
        return -1;
    }
}

分析一下：

前面的部分都相同，关于while里的条件是不一样的，是不带等号=的，因为是左闭右开，带等号这个区间是不合法的，但是这里的条件变化了，肯定会影响到后面的区间更新

我们来具体讲解，当target目标值小于mid时，我们取原来区间的左半部分，把right更新成mid，为什么不是mid-1，因为右边本来就是开区间，取不到

当target值大于mid时，我们取原来区间的右半部分，把left更新为mid+1，为什么是这样，是因为我们左边是闭区间，可以取到mid。

一句话总结：二分查找的两种写法本质是一样的，区别在于区间定义决定了边界如何更新——闭区间可以取到边界，开区间取不到，所以要相应调整更新逻辑。

2.移除元素

题目背景：LeetCode 27

给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。 不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并原地修改输入数组。 元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。 示例 1: 给定 nums = [3,2,2,3], val = 3, 函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。 你不需要考虑数组中超出新长度后面的元素。 示例 2: 给定 nums = [0,1,2,2,3,0,4,2], val = 2, 函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。 你不需要考虑数组中超出新长度后面的元素。

我的观点：这题题目简单，思想挺重要，引入了双指针的概念思想

题解一：暴力拆解

class Solution {
    public int removeElement(int[] nums, int val) {
	// 暴力法
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            if (nums[i] == val) {
                for (int j = i + 1; j < n; j++) {
                    nums[j - 1] = nums[j];
                }
                i--;
                n--;
            }
        }
        return n;
    }
}

分析一下：逻辑非常简单，简单的两个for循环，时间复杂度：O(n^2)

题解二：双指针法

什么是双指针？简单的说，就是两个人协同干活，减少循环次数，底层就是把两次for循环变成一次for循环

class Solution {
    public int removeElement(int[] nums, int val) {
        // 快慢指针
        int slowIndex = 0;
        for (int fastIndex = 0; fastIndex < nums.length; fastIndex++) {
            if (nums[fastIndex] != val) {
                nums[slowIndex] = nums[fastIndex];
                slowIndex++;
            }
        }
        return slowIndex;
    }
}

分析一下：这里的快慢指针是同一起点的，还有双向的，但原理都是一样的，我们把这个步骤形容成整理书架，书架的垃圾是需要删除（覆盖的）元素

具体的实现步骤：

书：[0, 1, 2, 2, 3, 0, 4, 2] 要扔：2 第1本：fast=0，书是0（要留） [0, 1, 2, 2, 3, 0, 4, 2] ↑ slow=0 侦察兵：0是好书！ 搬运工：放到slow位置（0）→ [0, ...] slow前进到1 ✓ 第2本：fast=1，书是1（要留） [0, 1, 2, 2, 3, 0, 4, 2] ↑ slow=1 侦察兵：1是好书！ 搬运工：放到slow位置（1）→ [0, 1, ...] slow前进到2 ✓ 第3本：fast=2，书是2（要扔） [0, 1, 2, 2, 3, 0, 4, 2] ↑ slow=2 侦察兵：2是垃圾！ 搬运工：不动，slow还是2（空位留着） [0, 1, 2, 2, ...] ← 垃圾还在 第4本：fast=3，书是2（要扔） [0, 1, 2, 2, 3, 0, 4, 2] ↑ slow=2 侦察兵：又是垃圾！ 搬运工：不动，slow还是2 第5本：fast=4，书是3（要留） [0, 1, 2, 2, 3, 0, 4, 2] ↑ slow=2 侦察兵：3是好书！ 搬运工：放到slow位置（2）→ [0, 1, 3, 2, 3, 0, 4, 2] 把原来的垃圾2覆盖了！ slow前进到3 ✓ 第6本：fast=5，书是0（要留） [0, 1, 3, 2, 3, 0, 4, 2] ↑ slow=3 侦察兵：0是好书！ 搬运工：放到slow位置（3）→ [0, 1, 3, 0, 3, 0, 4, 2] 把原来的垃圾2覆盖了！ slow前进到4 ✓ 第7本：fast=6，书是4（要留） [0, 1, 3, 0, 3, 0, 4, 2] ↑ slow=4 侦察兵：4是好书！ 搬运工：放到slow位置（4）→ [0, 1, 3, 0, 4, 0, 4, 2] 把原来的3覆盖了！ slow前进到5 ✓ 第8本：fast=7，书是2（要扔） [0, 1, 3, 0, 4, 0, 4, 2] ↑ slow=5 侦察兵：垃圾！ 搬运工：不动 检查完毕

结语：如果对你有帮助，请点赞，关注，收藏，你的支持就是我最大的鼓励！