devbox
Guff_9hys
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

代码随想录算法训练营第一天|LeetCode 704、二分查找 LeetCode 27、移除元素_leetcode 点和矩阵二分查找

作者：Guff_9hys | 2024-08-10 16:20:21

赞

踩

leetcode 点和矩阵二分查找

目录

知识前置

LeetCode 704.二分查找

LeetCode 27.移除元素

LeetCode 35.搜索插入位置

LeetCode 26.删除有序数组的重复项

LeetCode 34.在排序数组中查找元素的第一个和最后一个位置

LeetCode 69.x的平方根

LeetCode 367.有效的完全平方数

LeetCode 283.移动零

知识前置

定义：

        数组是存储在连续空间且元素类型相同的集合。

特点：

        1.数组的下标是从0开始的。

        2.在数组当中，要查找或者修改数据，只需要知道你所要的数据的索引即可；但是当你进行删除或者增加的操作的时候，你不仅需要知道你所需要的索引还得进行挪动空间的操作，此时数组就会显得不那么便利。

        3.在数组中当中，要删除或者添加数据，通常都需要挪动空间的操作。在进行删除操作中，如果需要删除的元素在数组末尾则不需要挪动空间；在进行添加操作中，如果需要添加的元素在数组最后一个元素后则也不需要挪动空间。除了以上两种情况外，通常都需要进行挪动空间的操作，挪动空间的操作则以覆盖的形式来表现。

目标：

        1.熟悉二分查找的逻辑，以及不同区间的写法。

        2.熟悉在数组中删除元素其实就是进行覆盖操作。

        3.多联系，孰能生巧。

LeetCode 704.二分查找

文档讲解：代码随想录

视频讲解：手把手带你撕出正确的二分法 | 二分查找法 | 二分搜索法 | LeetCode：704. 二分查找_哔哩哔哩_bilibili

力扣题目：LeetCode 704.二分查找

题目获取的信息：

第一：有序且为升序,元素不重复的数组

第二：在数组中找到对应target的值

第三：有则返回对应target的下标，无则返回-1

思路：

1.使用二分查找的前提有两个：1是有序的数组，2是数组元素不重复，题目都符合要求。

2.在二分查找过程中，不断进行折半处理。而在折半处理的过程中，数组的范围是在不断缩减的，所以会联想到要用循环体。在这个过程中，影响着3个变量，这3个变量来控制数组范围，也即是left（左边界），right（右边界），middle（中间下标）。

3.定义left = 0；right = nums.length - 1; middle = left  + (right - left) / 2;

4.那么循环体的条件该如何定义呢？如果是左闭右开区间，此时右区间要更改为nums的长度。假设一开始的nums[middle]>target,因为nums为升序数组，所以可以得知target是在[left, middle]这个区间的。相应的我们要对判断条件中的right值来进行修改，right = middle。为什么不是right = middle - 1呢?因为我们是左闭右开区间，在循环判断条件中，并没有帮我们判断右区间，所以我们要在循环体内的判断进行相应的修改；同理，要是左闭右闭区间，此时右区间要更改为nums的长度-1。假设一开始的nums[target]>target,因为nums为升序数组，所以可以得知target是在[left, middle)这个区间的。因为循环判断条件中以及帮我们判断了右区间，所以在循环体内的判断条件可以中，right = middle - 1;

所以综上所述代码如下（左闭右闭）：

  1. class Solution {
  2.     public int search(int[] nums, int target) {
  3.  
  4.         //定义数组左边界下标值left
  5.         int left = 0;
  6.         //定义数组右边界下标值right
  7.         int right = nums.length - 1;
  8.         //定义数组中间下标值middle
  9.         int middle = 0;
  10.  
  11.         //1.二分查找的前提是有序数组
  12.         //2.以中间下标为寻找对象，不断缩减范围
  13.         while(left <= right){
  14.  
  15.             middle = left + (right - left) / 2;
  16.  
  17.             if(nums[middle] > target){
  18.                 right = middle - 1;
  19.             }else if(nums[middle] < target){
  20.                 left = middle + 1;
  21.             }else{
  22.                 return middle;
  23.             }
  24.  
  25.         }
  26.  
  27.         return -1;
  28.     }
  29. }

代码如下（左闭右开）:

  1. class Solution {
  2.     public int search(int[] nums, int target) {
  3.  
  4.         int left = 0;
  5.         int right = nums.length;
  6.  
  7.         while(left < right){
  8.  
  9.             int middle = left + (right - left) / 2;
  10.  
  11.             if(nums[middle ] < target){
  12.                 left = middle + 1;
  13.             }else if(nums[middle] > target){
  14.                 right = middle;
  15.             }else{
  16.                 return middle;
  17.             }
  18.  
  19.         }
  20.  
  21.         return -1;
  22.     }
  23. }

总结：使用二分查找的时候，前提是数组中的元素是有序的；其次就是数组中的元素是不重复的；最后就是要保持区间不变性的原则，就是你要确定区间的范围是左闭右闭，还是左闭右开区间，两种不同的思想对于代码的编写还是会不一样的。 

LeetCode 27.移除元素

文档讲解：代码随想录

视频讲解：数组中移除元素并不容易！ | LeetCode：27. 移除元素_哔哩哔哩_bilibili

题目：LeetCode 27.移除元素

思路：看到题目要原地修改的时候，会想到双指针的解法。但实际操作下来，会发现还是会用回原来的暴力解法，而没有想到用快慢指针的操作。

暴力解法思路：定义两个循环体，第一个循环体遍历整个数组，第二个循环体则用来更新数组。

代码如下（暴力解法）： 

  1. class Solution{
  2.     
  3.     public int removeElement(int[] nums, int val){
  4.         
  5.         int length = nums.length;
  6.  
  7.         for(int oneIndex = 0; oneIndex < nums.length; oneIndex++){
  8.             
  9.             if(nums[oneIndex] == val){    
  10.  
  11.                 for(int twoIndex = oneIndex + 1; twoIndex < nums.length; twoIndex++){
  12.                     
  13.                     nums[twoIndex - 1] = nums[twoIndex];
  14.                     
  15.                 }
  16.  
  17.                 oneIndex--;
  18.                 length--;
  19.             }
  20.         }
  21.  
  22.         return length;
  23.     }
  24. }

快慢指针的思路：首先在for循环中定义一个快指针fastIndex，fastIndex就是用来遍历整个数组。其次，思考慢指针在快指针遍历的数组的过程中，如何慢下来，也就是思考判断条件。

代码如下（快慢指针解法）：

  1. class Solution {
  2.     public int removeElement(int[] nums, int val) {
  3.  
  4.         int slowIndex = 0;
  5.  
  6.         for(int fastIndex = 0; fastIndex < nums.length; fastIndex++){
  7.             
  8.             if(nums[fastIndex] != val){
  9.                 nums[slowIndex] = nums[fastIndex];
  10.                 slowIndex++;
  11.             }
  12.                 
  13.         }
  14.  
  15.         return slowIndex;
  16.     }
  17. }

总结：数组中进行删除操作的本质就是进行数组元素覆盖的操作，然后返回删除后的数组长度。那么，在进行覆盖操作的时候，有两种不同的解法。一是进行暴力解法，第一遍循环进行查找目标元素，第二遍循环把目标元素往后的元素进行向前覆盖的操作，即从目标元素的后一个元素开始，进行向前覆盖的操作 。进行两次循环之后，回退一个第一遍循环所需要索引的位置，这个操作是用来进行删除重复元素的操作；二是进行双指针的解法，定义两个指针，fast指针以及slow指针。fast指针作为循环的变量，slow指针作为符合条件时进行覆盖的位置，通俗来讲就是，fast指针用来寻找符合条件的元素，当找到符合条件的元素的时候，把元素填进slow的位置当中。

  

LeetCode 35.搜索插入位置

文章讲解：代码随想录

力扣题目：LeetCode 35.搜索插入位置 

思路：

1.用二分查找的方法找到适合的位置，找到就返回下标

2.当target值不在数组范围内的时候，同样用二分查找找到最接近target值的下标位置，此时你需要找一个相对位置，像left下标或者right下标又或者middle下标，这个就看各人编码习惯。

3.假设我用的是right下标，那么因为这个是有序且为递增数组，没有重复元素。如果target比该数组最小的值还要小，那么在二分查找最后一次循环当中，就要移动right的下标，那么此时right的下标一定为-1，显然插入的位置一定为数组的开头即下标为0的位置，也就是right+1的位置；如果target比该数组的最大的位置还要大，那么在二分查找最后一次循环当中，就要移动left下标，那么此时left下标为数组的长度加一，显然插入的位置一定为数组的长度末尾的位置，即right+1的位置；如果target的位置在数组中间，那么对于二分查找最后一次循环当中，无非就是大一个位置或小一个位置，target值大，那么移动left的位置，此时right+1的位置就是插入的位置。target值小，那么移动right的位置，此时也是right+1的位置就是插入的位置。

代码如下（Java）：

  1. class Solution {
  2.     public int searchInsert(int[] nums, int target) {
  3.  
  4.         int left = 0;
  5.         int right = nums.length - 1;
  6.         int middle = 0;
  7.  
  8.         while(left <= right){
  9.  
  10.             middle = left + (right - left) / 2;
  11.  
  12.             if(target < nums[middle]){
  13.                 right = middle - 1;
  14.             }else if(target > nums[middle]){
  15.                 left = middle + 1;
  16.             }else{
  17.                 return middle;
  18.             }
  19.  
  20.         }
  21.  
  22.         if(target < nums[middle]){
  23.             return middle;
  24.         }else{
  25.             return middle + 1;
  26.         }
  27.     }
  28. }

代码如下（Java）：二分查找

  1. class Solution {
  2.     public int searchInsert(int[] nums, int target) {
  3.  
  4.         int left = 0;
  5.         int right = nums.length - 1;
  6.  
  7.         while(left <= right){
  8.  
  9.             int middle = left + (right - left) / 2;
  10.  
  11.             if(nums[middle] < target){
  12.                 left = middle + 1;
  13.             }else if(nums[middle] > target){
  14.                 right = middle - 1;
  15.             }else{
  16.                 return middle;
  17.             }
  18.  
  19.         }
  20.  
  21.         return left;    
  22.     }
  23. }

 代码如下（Java）：二分查找

  1. class Solution {
  2.     public int searchInsert(int[] nums, int target) {
  3.  
  4.         int left = 0;
  5.         int right = nums.length - 1;
  6.  
  7.         while(left <= right){
  8.  
  9.             int middle = left + (right - left) / 2;
  10.  
  11.             if(nums[middle] < target){
  12.                 left = middle + 1;
  13.             }else if(nums[middle] > target){
  14.                 right = middle - 1;
  15.             }else{
  16.                 return middle;
  17.             }
  18.  
  19.         }
  20.  
  21.         return right + 1;    
  22.     }
  23. }

总结：当你遇到数组有序且不重复的时候，可以考虑一下二分查找。这道题的思路就是搜索位置，然后返回相应插入的位置即可。 

LeetCode 26.删除有序数组的重复项

力扣题目：LeetCode 26.删除有序数组的重复项

思路：

1.数组中删除元素的操作通常是使用覆盖或者新建数组的方式，本题目要求原地删除，所以选择覆盖的方式。

2.那么选择覆盖的方式，自然就会想到用多指针的方式来进行覆盖

3.使用fast指针初始化为1，slow指针初始化为0，fast指针随着循环的次数自然增加。那么当fast指针所指向的元素和slow指针指向的元素不同的时候，slow指针才往前加一，且fast指针所指向的值需要赋给slow+1的位置。

如下图所示：

代码如下（Java）：

  1. class Solution {
  2.     public int removeDuplicates(int[] nums) {
  3.  
  4.         int slow = 0;
  5.  
  6.         for(int fast = 1; fast < nums.length; fast++){
  7.  
  8.             if(nums[fast] != nums[slow]){
  9.                 nums[slow+1] = nums[fast];
  10.                 slow++; 
  11.             }
  12.  
  13.         }
  14.  
  15.         return slow + 1;
  16.     }
  17. }

总结：在数组中进行删除操作的时候需要进行两个动作，一个动作就是进行查找，一个动作就是进行覆盖，这样就可以尝试使用双指针的操作，看看题目的要求，先整理以下思路，在进行编码。

LeetCode 34.在排序数组中查找元素的第一个和最后一个位置

力扣题目： LeetCode 34.在排序数组中查找元素的第一个和最后一个位置

思路：

1.用两个for循环，一个for循环顺序找出target的开始位置，一个for循环倒序用来找出target的结束位置 。

代码如下（Java）：暴力解法

  1. class Solution {
  2.     public int[] searchRange(int[] nums, int target) {
  3.  
  4.         int[] result = new int[]{-1,-1};
  5.  
  6.         for(int start = 0; start < nums.length; start++){
  7.             if(nums[start] == target){
  8.                 result[0] = start;
  9.                 break;
  10.             }
  11.         }
  12.  
  13.         for(int end = nums.length - 1; end > -1; end--){
  14.             if(nums[end] == target){
  15.                 result[1] = end;
  16.                 break;
  17.             }
  18.         }
  19.  
  20.         return result;
  21.     }
  22. }

LeetCode 69.x的平方根

力扣题目：LeetCode 69.x的平方根

代码如下（Java）：

  1. class Solution {
  2.     public int mySqrt(int x) {
  3.  
  4.         int left = 0;
  5.         int right = x;
  6.         int res = 0;
  7.  
  8.         while(left <= right){
  9.  
  10.             int middle = left + (right - left) / 2;
  11.  
  12.             if((long)middle * middle <= x){
  13.                 
  14.                 res = middle;
  15.                 left = middle + 1;
  16.  
  17.             }else{
  18.  
  19.                 right = middle - 1;
  20.  
  21.             }
  22.  
  23.         }   
  24.  
  25.         return res;     
  26.     }
  27. }

LeetCode 367.有效的完全平方数

力扣题目：LeetCode 367.有效的完全平方数

代码如下（Java）：

  1. class Solution {
  2.     public boolean isPerfectSquare(int num) {
  3.  
  4.         long x = 1;
  5.         long square = 1;
  6.  
  7.         while(square <= num){
  8.  
  9.             if(square == num)   return true;
  10.             ++x;
  11.             square = x * x;
  12.  
  13.         }
  14.  
  15.         return false;
  16.     }
  17. }

LeetCode 283.移动零

力扣题目：LeetCode 283.移动零

代码如下（java）：

  1. class Solution {
  2.     public void moveZeroes(int[] nums) {
  3.  
  4.         for(int slow = 0, fast = 1; fast < nums.length; fast++){
  5.  
  6.             if(nums[slow] != 0){
  7.                 slow++;
  8.             }
  9.  
  10.             if(nums[slow] == 0 && nums[fast] != 0){
  11.                 int temp = nums[fast];
  12.                 nums[fast] = nums[slow];
  13.                 nums[slow] = temp;
  14.                 slow++;
  15.             }
  16.  
  17.         }
  18.     }
  19.  
  20. }

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/Guff_9hys/article/detail/959299
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号