代码随想录算法第一天|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. 逻辑思考能力问题，写题解时思维不流畅。