526互联

代码随想录算法第一天704

发布时间 2023-09-07 09:12:51作者: 烫烫烫汤圆

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

学习（复习）数组理论基础：

​ (https://programmercarl.com/数组理论基础.html)

​ 新了解到Java中数组地址不是连续的。

704.二分查找

题目

题目链接：https://leetcode.cn/problems/binary-search/

文章讲解：https://programmercarl.com/0704.%E4%BA%8C%E5%88%86%E6%9F%A5%E6%89%BE.html

视频讲解：https://www.bilibili.com/video/BV1fA4y1o715

解题

  • 第一想法：

    • 实现整个二分查找的流程。
    • 可以用递归和普通循环，注意确定查找范围时的比较条件。

  • 第二想法:

    • 二分法前提是元素有序不重复。
    • 把分区的方式想简单了。
    • 具体实现时分区方式决定了是否要将边界元素包含到新查找范围中。

  • 错误代码及纠正

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

      }
      return -1;
    }
};

​

27.移除元素

题目

题目链接：https://leetcode.cn/problems/remove-element/

文章讲解：https://programmercarl.com/0027.%E7%A7%BB%E9%99%A4%E5%85%83%E7%B4%A0.html

视频讲解：https://www.bilibili.com/video/BV12A4y1Z7LP

解题

  • 第一想法:

    • 暴力解法：遍历若nums[i]与val值相同，则把后面的数字一次前进一位，若不同则把记录数组长度变量自增一并继续向后遍历直到数组结束。

    • 没有想到怎么使用双指针。

      • 问题：1.整体思想无误,没有注意遍历指针在一个元素被移除后应该保持不动的细节.

        ​ 2.错误的将遍历指针的逻辑关系放在判别元素是否相同的分支中。

        ​ 3.代码实现是记录数目错误。

  • 第二想法：

    • 双指针：快指针获取新数组需要的元素，慢指针获取新数组需要更新的位置。基于此知道，注意循环结束条件，一遍AC。

  • 错误代码及纠正：

    错误：
class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int len=0;
        for(int i=0;i<nums.size();i++)
        {
            if(nums[i]==val)
            {
                for(int j=i;j<nums.size();j++)
                {
                    nums[j]=nums[j+1];

                }
            }
                i--;
                len++;
        }
        return len;

    }
};
正确：
    class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int len=nums.size();
        for(int i=0;i<nums.size();i++)
        {
            if(nums[i]==val)
            {
                for(int j=i;j<nums.size()-1;j++)
                {
                    nums[j]=nums[j+1];

                }
                i--;
                len--;
            }
             
        }
        return len;
    }
};

  • 双指针代码：

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

    }
};

今日收获（2.5h）

​ 复习二分查找和双指针，暴露两个问题

	1. 代码能力低，表现在循环条件控制不熟练，逻辑分支分辨有问题
	1. 逻辑思考能力问题，写题解时思维不流畅。