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

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

作者：Guff_9hys | 2024-08-10 16:07:29

赞

踩

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

1 二分查找

704. 二分查找

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

    1. //左闭右开
    2. int search(vector<int>& nums, int target) {
    3.         int left = 0;
    4.         int right = nums.size();
    5.  
    6.         while(left < right)   //left =  right 是没有意义的
    7.         {
    8.             int mid =  left+ ((right -left)>>1)  ; // >> 优先级 
    9.             if(nums[mid] > target)
    10.             {
    11.                 right = mid;
    12.             } else if(nums[mid] < target)
    13.             {
    14.                 left = mid+1;
    15.             }else{
    16.                 return mid;
    17.             }
    18.         }
    19.         return -1;
    20. }
    21. //左闭右闭
    22.  int search(vector<int>& nums, int target) {
    23.         int left = 0;
    24.         int right = nums.size()-1;
    25.  
    26.         while(left <= right)
    27.         {
    28.             int mid =  left+ ((right -left)>>1)  ; // >> 优先级 
    29.             if(nums[mid] > target)
    30.             {
    31.                 right = mid-1;
    32.             } else if(nums[mid] < target)
    33.             {
    34.                 left = mid+1;
    35.             }else{
    36.                 return mid;
    37.             }
    38.         }
    39.         return -1;
    40. }

35. 搜索插入位置

  • 给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

    请必须使用时间复杂度为 O(log n) 的算法。

    1. int searchInsert(vector<int>& nums, int target) {
    2.          int left = 0;
    3.          int right = nums.size();
    4.  ​
    5.          while(left< right)
    6.          {
    7.              int mid = left + ((right - left) >> 1);
    8.              if(nums[mid] > target)
    9.              {
    10.                  right = mid;
    11.              }else if(nums[mid] < target)
    12.              {
    13.                  left = mid +1;
    14.              }else{
    15.                  return mid;
    16.              }
    17.          }
    18.          return right ;
    19.      }

  • 当 left = right 时，left 就是要插入的位置

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

  • 给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。

    如果数组中不存在目标值 target，返回 [-1, -1]。

    你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。

  • 示例 1：

     输入：nums = [5,7,7,8,8,10], target = 8
 输出：[3,4]

    示例 2：

     输入：nums = [5,7,7,8,8,10], target = 6
 输出：[-1,-1]

    示例 3：

     输入：nums = [], target = 0
 输出：[-1,-1]
    1. vector<int> searchRange(vector<int>& nums, int target) {
    2.        int left = 0,right = nums.size();
    3.        int mid = 0;
    4.        while(left < right)  
    5.        {
    6.            mid = left+ ((right - left)>>1);
    7.            if( nums[mid] >  target )
    8.            {
    9.                right = mid;
    10.            }else if(nums[mid] < target)
    11.            {
    12.                left = mid +1;
    13.            }else{
    14.                break;
    15.            }
    16.        }
    17.        if(left == right) return {-1,-1};
    18.        left = mid;
    19.        right = mid;
    20.        while(left-1 >= 0 && nums[left-1] == target)
    21.        {
    22.            left --;
    23.        }
    24.         while(right+1 < nums.size() && nums[right+1] == target)
    25.        {
    26.            right ++;
    27.        }
    28.        return {left,right};
    29.  ​
    30.      }

  • 先找到target， 再往两边扩展

69. x 的平方根

  • 给你一个非负整数 x ，计算并返回 x 的 算术平方根 。

    由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。

    注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。

  • 示例 1：

     输入：x = 4
 输出：2

    示例 2：

     输入：x = 8
 输出：2
 解释：8 的算术平方根是 2.82842..., 由于返回类型是整数，小数部分将被舍去。
    1. int mySqrt(int x) {
    2.          if(x == 0) return 0;
    3.          if(x<=3) return 1;
    4.          if(x<=8) return 2;
    5.  ​
    6.          long long  left = 3,right = x/2;
    7.  ​
    8.          while( left < right )
    9.          {
    10.              long long  mid = left + ((right - left)>>1);
    11.  ​
    12.              if(mid * mid < x)  // mid < x / mid;
    13.              {
    14.                  left = mid +1;
    15.              }else if( mid * mid > x ){
    16.                  right = mid ;
    17.              }else{
    18.                  return mid;
    19.              }
    20.          }
    21.          return left-1;  //此时left = right ，但是right 无意义 // right是向上取整
    22.      }
    23.  
    24.   int mySqrt(int x) {
    25.          if(x == 0) return 0;
    26.          if(x<=3) return 1;
    27.          if(x<=8) return 2;
    28.  ​
    29.          long long  left = 3,right = x/2;
    30.          while( left <= right ) 
    31.          {
    32.            long long   mid = left + ((right - left)>>1);
    33.  ​
    34.              if(mid * mid < x)
    35.              {
    36.                  left = mid + 1;
    37.              }else if( mid * mid > x ){
    38.                  right = mid-1 ;
    39.              }else{
    40.                  return mid;
    41.              }
    42.          }
    43.          return right; // 带等号的时候，退出时left > right 
    44.      }

  • 牛顿迭代 : 快速求解函数零点的方法。

    • 用 C 表示待求出平方根的那个整数 ,C 的平方根就是函数 y= x^2 - C 的零点

      1. int mySqrt(int x) {
      2.          if(x == 0) return 0;
      3.        
      4.          double  C = x,x0= x;
      5.          while(true)
      6.          {
      7.              double xi = 0.5*(x0 + C /x0);  //切线与x轴交点
      8.              if(fabs(x0 - xi) < 1e-7)
      9.              {
      10.                  break;
      11.              }
      12.              x0 = xi;
      13.          }        
      14.          return int(x0);
      15.      }

2 双指针

27. 移除元素

  • 给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。

    不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。

    元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

  • 示例 1：

     输入：nums = [3,2,2,3], val = 3
 输出：2, nums = [2,2]
 解释：函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。你不需要考虑数组中超出新长度后面的元素。例如，函数返回的新长度为 2 ，而 nums = [2,2,3,3] 或 nums = [2,2,0,0]，也会被视作正确答案。

    示例 2：

     输入：nums = [0,1,2,2,3,0,4,2], val = 2
 输出：5, nums = [0,1,3,0,4]
 解释：函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。注意这五个元素可为任意顺序。你不需要考虑数组中超出新长度后面的元素。
    1. int removeElement(vector<int>& nums, int val) {
    2.          int i = 0,j =0;
    3.          while(j < nums.size())
    4.          {
    5.              if(nums[j] != val)
    6.              {
    7.                  nums[i] = nums[j];
    8.                  i++;
    9.              }
    10.              j++;
    11.          }
    12.          return i;
    13.      }

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

  • 给你一个 非严格递增排列 的数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。然后返回 nums 中唯一元素的个数。

  • 示例 1：

     输入：nums = [1,1,2]
 输出：2, nums = [1,2,_]
 解释：函数应该返回新的长度 2 ，并且原数组 nums 的前两个元素被修改为 1, 2 。不需要考虑数组中超出新长度后面的元素。

    示例 2：

     输入：nums = [0,0,1,1,1,2,2,3,3,4]
 输出：5, nums = [0,1,2,3,4]
 解释：函数应该返回新的长度 5 ， 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4 。不需要考虑数组中超出新长度后面的元素。
    1. int removeDuplicates(vector<int>& nums) {
    2.          if(nums.size() == 1) return 1;
    3.          int i = 1,j = 1;
    4.  ​
    5.          while(j < nums.size())
    6.          {
    7.              if( nums[j] != nums[i-1] )
    8.              {
    9.                  nums[i] = nums[j];
    10.                  i++;
    11.              }
    12.              j++;
    13.          }
    14.          return i;
    15.      }

  • 只将第一次出现的数保存下来

844. 比较含退格的字符串

  • 给定 s 和 t 两个字符串，当它们分别被输入到空白的文本编辑器后，如果两者相等，返回 true 。# 代表退格字符。

    注意：如果对空文本输入退格字符，文本继续为空。

  • 示例 1：

     输入：s = "ab#c", t = "ad#c"
 输出：true
 解释：s 和 t 都会变成 "ac"。

    示例 2：

     输入：s = "ab##", t = "c#d#"
 输出：true
 解释：s 和 t 都会变成 ""。

    示例 3：

     输入：s = "a#c", t = "b"
 输出：false
 解释：s 会变成 "c"，但 t 仍然是 "b"。
    1. bool backspaceCompare(string s, string t) {
    2.          int i = 0,j =0;
    3.          int sNum ,tNum ;
    4.          while(j < s.size())
    5.          {
    6.              if(s[j] != '#')
    7.              {
    8.                  s[i] = s[j];
    9.                  i++;
    10.              }else if(i > 0){
    11.                  i--;
    12.              }
    13.              j++;
    14.          }
    15.          sNum = i;
    16.          i = 0,j = 0;
    17.          while(j < t.size())
    18.          {
    19.              if(t[j] != '#')
    20.              {
    21.                  t[i] = t[j];
    22.                  i++;
    23.              }else if(i > 0){
    24.                  i--;
    25.              }
    26.              j++;
    27.          }
    28.          tNum = i;
    29.          if(sNum != tNum) return false;
    30.          i = 0;
    31.          while(i< sNum)
    32.          {
    33.              if(s[i] != t[i])
    34.                  return false; 
    35.             i++; 
    36.          }
    37.          return true;
    38.      }

  • 仿照前面两个题的思路，从左往右双指针遍历

  • 匹配消除还可以用栈的思路

977. 有序数组的平方

  • 给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序

  • 示例 1：

     输入：nums = [-4,-1,0,3,10]
 输出：[0,1,9,16,100]
 解释：平方后，数组变为 [16,1,0,9,100]
 排序后，数组变为 [0,1,9,16,100]

    示例 2：

     输入：nums = [-7,-3,2,3,11]
 输出：[4,9,9,49,121]
    1. //中间往两边取，费时费力
    2.  ​
    3.  vector<int> sortedSquares(vector<int>& nums) {
    4.          vector<int>result;
    5.          int zeroIndex = 0;
    6.          int left ,right;
    7.          if(nums[0] >= 0 )
    8.          {
    9.                      for(int i =0;i< nums.size();i++)
    10.                      {
    11.                          result.push_back(nums[i]*nums[i]);
    12.                      } 
    13.                      return result;
    14.          }else if( nums[nums.size()-1] <= 0 ){
    15.                      for(int i =nums.size()-1;i>=0;i--)
    16.                      {
    17.                      result.push_back(nums[i]*nums[i]);
    18.                      }
    19.                      return result;
    20.          }
    21.  ​
    22.          for(int i =0;i< nums.size();i++)
    23.          {
    24.              if(nums[i]< 0 &&nums[i+1]>=0  )
    25.              {
    26.                  left = i,right = i+1;
    27.              }
    28.          }
    29.  ​
    30.          while(left >= 0 && right<= nums.size()-1)
    31.          {
    32.              if( fabs(nums[left]) > fabs(nums[right]) )
    33.              {
    34.                  result.push_back(nums[right]*nums[right]);
    35.                  right++;
    36.              }else{
    37.                   result.push_back(nums[left]*nums[left]);
    38.                  left--;
    39.              }
    40.          }
    41.          while(left>=0)
    42.          {
    43.               result.push_back(nums[left]*nums[left]);
    44.                  left--;
    45.          }
    46.          while(right <= nums.size()-1)
    47.          {
    48.               result.push_back(nums[right]*nums[right]);
    49.                  right++;
    50.          }
    51.          return result;
    52.  ​
    53.  ​
    54.      }

  •  
    1. vector<int> sortedSquares(vector<int>& nums) {
    2.          vector<int>result(nums.size(),0);
    3.          int i = 0,j = nums.size()-1;
    4.          int num = nums.size()-1;
    5.          while(i<=j)
    6.          {
    7.              if(fabs(nums[i]) < fabs(nums[j]))
    8.              {
    9.                  result[num] = nums[j] * nums[j];
    10.                  j--;
    11.              }else{
    12.                  result[num] = nums[i] * nums[i];
    13.                  i++;
    14.              }
    15.              num--;
    16.          }
    17.          return result;
    18.      }

  • 两边往中间遍历，不用判断0在哪

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

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

  

闽ICP备14008679号