刷题日记 Day 1 : Leetcode 704 二分查找以及 Leetcode 27 移除元素

分手后的思念是犯贱 2024-03-25 14:54 57阅读 0赞

#### 刷题日记 Day1 ####

*  一 . Leetcode 704 : 二分查找
 *   *  扩展 - Leetcode 35 : 搜索插入位置
     *  扩展 - Leetcode 34 : 在排序数组中查找元素的第一个和最后一个位置
 *  二 . LeetCode 27 : 移除元素

> 本篇文章 , 是在代码随想录 60 天编程挑战的基础上进行的题目讲解  
> 参与链接在此 : [https://programmercarl.com/other/xunlianying.html][https_programmercarl.com_other_xunlianying.html]

> 大家好 , 这个专栏 , 给大家带来的是 60 天刷题强训 . 最令大家头疼的事就是刷题了 , 题目又臭又长又抽象 , 有的题读都读不懂 , 更别说做了 . 所以 , 这个专栏想要帮助大家摆脱困境 , 横扫饥饿 , 做回自己 . 让大家掌握最常见的面试题 , 面对陌生的题目也不至于无从下手 .  
> 也希望大家监督 , 60 天从 0 到 1 , 咱们一起做大佬 ~  
> ![image.png][]  
> 专栏链接 : [https://blog.csdn.net/m0\_53117341/category\_12247938.html?spm=1001.2014.3001.5482][https_blog.csdn.net_m0_53117341_category_12247938.html_spm_1001.2014.3001.5482]

## 一 . Leetcode 704 : 二分查找 ##

题目链接 :  
[704. 二分查找][704.]

实现版本 1 :  
二分查找的本质 , 就是在一个有序数组中找到指定的值  
我们给大家举个栗子 :  
![image.png][image.png 1]  
所以二分法的代码就是下面这个样子

class Solution {
        
        public int search(int[] nums, int target) {
        
            // 1. 参数判断
            if(nums == null) {
        
                return -1;
            }
    
            // 2. 确定左右边界
            int left = 0;
            int right = nums.length - 1;
    
            // 3. 进行二分查找 
            // 循环条件:left 不能跑到 right 右边
            while(left <= right) {
        
                // 3.1 求中间结点
                int mid = left + ((right - left) >> 1);// 防止越界做的优化
                if(nums[mid] < target) {
         // 如果中间节点的值比目标值小,那就在中间结点右边找
                    left = mid + 1;
                } else if (nums[mid] > target) {
         // 如果中间节点的值比目标值大,那就在中间结点左边找
                    right = mid - 1;
                } else {
         // 找到就直接返回
                    return mid;
                }
            }
    
            // 没找到的话返回 -1 即可
            return -1;
        }
    }

那有的同学也见过其他版本的二分法 , 那是怎么回事呢 ?  
我们还是推荐上面这个二分法的代码 , 但是另一个版本的二分也给大家讲一下  
首先 , 另一个版本的二分的右边界是 arr.length  
我们直接画图给大家讲解  
![image.png][image.png 2]  
代码也贴在这里了

class Solution {
        
        public int search(int[] nums, int target) {
        
            // 1. 参数判断
            if(nums == null) {
        
                return -1;
            }
    
            // 2. 确定左右边界
            int left = 0;
            int right = nums.length;
    
            // 3. 进行二分查找 
            // 循环条件:left 不能跑到 right 右边
            while(left < right) {
        
                // 3.1 求中间结点
                int mid = left + ((right - left) >> 1);// 防止越界做的优化
                if(nums[mid] < target) {
         // 如果中间节点的值比目标值小,那就在中间结点右边找
                    left = mid + 1;
                } else if (nums[mid] > target) {
         // 如果中间节点的值比目标值大,那就在中间结点左边找
                    right = mid;
                } else {
         // 找到就直接返回
                    return mid;
                }
            }
    
            // 没找到的话返回 -1 即可
            return -1;
        }
    }

这道二分查找的题我们就 so easy 的完成了  
![image.png][image.png 3]

### 扩展 - Leetcode 35 : 搜索插入位置 ###

题目链接 : [35. 搜索插入位置][35.]  
这道题实际上就是在二分查找的基础上增加了一丢丢内容  
这道题的意思就是给出一个值 , 如果数组中有这个值 , 返回他的下标 . 没有这个值的话 , 我应该插入到哪里  
也非常简单 , 我们直接看图  
![image.png][image.png 4]  
代码也给大家贴到这里了

class Solution {
        
        public int searchInsert(int[] arr, int target) {
        
            // 1. 定义左右下标
            int left = 0;
            int right = arr.length - 1;
    
            // 2. 开始二分查找元素
            // 找到就返回
            while(left <= right) {
        
                int mid = left + ((right - left) >> 1);
                if(arr[mid] < target) {
        
                    left = mid + 1;
                } else if (arr[mid] > target) {
        
                    right = mid - 1;
                } else {
        
                    return mid;
                }
            }
    
            // 3. 此时没找到的话就应该返回它将会被按顺序插入的位置
            // 二分查找完成之后,left所在的位置就是他将被按顺序插入的位置
            return left;
        }
    }

### 扩展 - Leetcode 34 : 在排序数组中查找元素的第一个和最后一个位置 ###

题目链接 : [34. 在排序数组中查找元素的第一个和最后一个位置][34.]  
大家可以自行完成 , 后续我也会把这道题的解题思路以及代码更新

## 二 . LeetCode 27 : 移除元素 ##

题目链接 : [27. 移除元素][27.]  
移除元素这道题 , 有两种解法  
一种必然是暴力了 , 另一种我们可以通过双指针的思想来解决  
我们先看暴力方法  
既然是移除元素 , 我们首先得找到要移除的元素 , 那就外层循环遍历一遍数组 , 找到要移除的元素  
在循环中我们判定一下当前的值是不是我们要删除的元素 , 如果是的话就需要将后面所有的元素依次向前覆盖  
但是其中还有一些小坑 , 我们可以举个栗子看看 :  
![image.png][image.png 5]  
那基本思路非常简单 , 大家可以直接看代码

class Solution {
        
        public int removeElement(int[] arr, int val) {
        
            // 1. 参数判断
            if(arr == null) {
        
                return -1;
            } 
    
            // 2. 先将数组长度提取出来,最后好直接返回
            int length = arr.length;
    
            // 3. 循环遍历数组
            // 注意:这里需要将循环条件写成 <length,因为数组不断删除元素,长度是不断变化的
            for(int i = 0;i < length;i++) {
        
                // 当该元素和要删除的值相等,那就让后面所有元素依次向前覆盖
                if(arr[i] == val) {
        
                    // 再定义一个循环,将后面的元素依次向前覆盖
                    for(int j = i + 1;j < arr.length;j++) {
        
                        arr[j - 1] = arr[j];
                    }
                    // 注意:i需要进行--
                    // 比如:[0,1,2,2,3,0,4,2] 删 2
                    // 当有连续两个2的时候,i不往前回退,会少删除一个2
                    i--;
                    // 删除元素,长度也要减1
                    length--;
                }
            }
            // 最后返回我们定义的长度即可
            return length;
        }
    }

但是这道题 , 重头戏是双指针算法  
我们来给大家讲解一下什么叫双指针  
**双指针法（快慢指针法）在数组和链表的操作中是非常常见的，很多考察数组、链表、字符串等操作的面试题，都使用双指针法**  
在本道题中 , 我们定义两个指针 fast、slow  
fast 指针的作用就是遍历数组元素 , 找到跟要删除的值不相等的元素 , 将他放到数组中  
slow 指针的作用就是作为数组的下标 , 接收来自 fast 传过来的元素  
直接上图  
![image.png][image.png 6]  
代码也在这里

class Solution {
        
        public int removeElement(int[] arr, int val) {
        
            
            // 1. 定义快慢指针
            int fast = 0;// 快指针相当于出门挣钱的
            int slow = 0;// 慢指针就相当于在家看孩子的
            
            // 2. 让快指针依次往后遍历,遇到不是val的就放到slow身上
            for(;fast < arr.length;fast++) {
        
                // 如果 fast 的值不是要删除的,那就把它送给 slow
                if(arr[fast] != val) {
        
                    // slow记得也要往后移动
                    arr[slow++] = arr[fast];
                }
            } 
    
            // 3. 最后返回 slow 下标,此时 slow 下标就是新数组的长度
            return slow;
        }
    }

这样的话 , Leetcode 刷题数又 +1 了~  
![image.png][image.png 7]

--------------------

到这里 , 我们第一天的任务就完成了~  
如果对你有帮助的话 , 请一键三连嗷~  
![image.png][image.png 8]

[https_programmercarl.com_other_xunlianying.html]: https://programmercarl.com/other/xunlianying.html
[image.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/d68f8004e416490488bd392986fb222a.png
[https_blog.csdn.net_m0_53117341_category_12247938.html_spm_1001.2014.3001.5482]: https://blog.csdn.net/m0_53117341/category_12247938.html?spm=1001.2014.3001.5482
[704.]: https://leetcode.cn/problems/binary-search/
[image.png 1]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/6a661de94dc645158fda7ca15f4d4d03.png
[image.png 2]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/0dd20298555f4e5a9fbb99d7aecb9e83.png
[image.png 3]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/7fc718c7ba914fd795d998210b79c90f.png
[35.]: https://leetcode.cn/problems/search-insert-position/
[image.png 4]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/4e4b9b34c6a548aa82c1a5b5a7ce61d7.png
[34.]: https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/
[27.]: https://leetcode.cn/problems/remove-element/
[image.png 5]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/9fa35c4796c94f1da6912923163defeb.png
[image.png 6]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/f3cc5a1d1d92474984c201e09e4d1d9b.png
[image.png 7]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/37ccf57975aa4bb3afa3842204bbfd60.png
[image.png 8]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/6351807d5b7d4736b658ecdf0cd6b3b3.png