• 数据结构与算法------数组

    一.二分查找

    704. 二分查找

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

    示例 :

    1. 输入: nums = [-1,0,3,5,9,12], target = 9     
    2. 输出: 4       
    3. 解释: 9 出现在 nums 中并且下标为 4    
    4.  
    5. 输入: nums = [-1,0,3,5,9,12], target = 2     
    6. 输出: -1        
    7. 解释: 2 不存在 nums 中因此返回 -1

    思路：二分查找最容易混淆的就是边界的选择，我总结了两种，二分查找满足的条件一般是给定一个有序数组而且是不重复，有两种写法，第一种是左闭右闭，第二种是左闭右开。

    左闭右闭写法：

    假设[left,right]则要配合如下条件：

    1.while(left<=right)

    2.if(nums[mid]>right) right=mid-1

    左闭右开写法:

    假设[left,right)则要配合如下条件:

    1.while(left<right)

    2.if(nums[mid)>right right=mid

    题解代码：

    左闭右闭

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

    左闭右开

    1. class Solution{
    2.      public int search(int[] nums, int target) {
    3.         int n=nums.length;
    4.         int left=0;
    5.         int right=n-1;
    6.         while(left<right){//和第一种的区别
    7.             int mid=left+(right-left)/2;
    8.             if(nums[mid]==target){
    9.                 return mid;
    10.             }else if(nums[mid]>right){
    11.                 right=mid;//和第一种的区别
    12.             }else if(nums[mid]<left){
    13.                 left=mid+1;
    14.             }
    15.         }
    16.         return -1;
    17.      }
    18. }

    与二分查找相似的题目有：

    35. 搜索插入位置

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

    69. x 的平方根 

    367. 有效的完全平方数

    =========================================================================

    搜索插入位置

    2.给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。请必须使用时间复杂度为 O(log n) 的算法。

    示例：

    1. 输入: [1,3,5,6], 5
    2. 输出: 2
    3. 示例 2:
    4.  
    5. 输入: [1,3,5,6], 2
    6. 输出: 1
    7. 示例 3:
    8.  
    9. 输入: [1,3,5,6], 7
    10. 输出: 4
    11. 示例 4:
    12.  
    13. 输入: [1,3,5,6], 0
    14. 输出: 0

    思路：这题和二分查找类似，只需要把二分查找的"框架"写上再修改一些细节，这里的细节指的是返回值，是left还是right还是right+1还是left+1,这个可以采用带入值得出结论，没有更好的办法要么就是多写代码多分析。这里返回的值是right+1.

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

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

    思路：这题比之前的有些难度，可以说是综合了二者，我们知道二分查找就是找边界值，但是一般是找一个，而这题的新颖之处在于找左右两个边界，同理我们可以利用最基本的二分查找来找左右边界，一个找左边界，一个找右边界，最后通过左右两边界相减判断是否存在数组内，如果存在则返回边界，否则返回[-1,-1]。

    1. class Solution {
    2. 	public int[] searchRange(int[] nums, int target) {
    3.         int left=getLeft(nums,target);//左边界
    4.         int right=getRight(nums,target);//右边界
    5.         if(left==-2 || right==-2) return new int[]{-1,-1};//插入的值在nums左或右
    6.         if(right-left>1) return new int[]{left+1,right-1};        
    7.         return new int[]{-1,-1};
    8.     }
    9.     public int getLeft(int[] nums,int target){//寻找左边界
    10.         int n=nums.length;
    11.         int left=0;
    12.         int right=n-1;
    13.         int leftBorder=-2;
    14.         while(left<=right){
    15.             int mid=left+(right-left)/2;
    16.             if(nums[mid]>=target){
    17.                 right=mid-1;
    18.                 leftBorder=right;
    19.             }else{
    20.                 left=mid+1;
    21.             }
    22.         }
    23.         return leftBorder;
    24.     } 
    25.     public int getRight(int[] nums,int target){//寻找右边界
    26.         int n=nums.length;
    27.         int left=0;
    28.         int right=n-1;
    29.         int rightBorder=-2;
    30.         while(left<=right){
    31.             int mid=left+(right-left)/2;
    32.             if(nums[mid]>target){
    33.                 right=mid-1;
    34.             }else{
    35.                 left=mid+1;
    36.                 rightBorder=left;
    37.             }
    38.         }
    39.         return rightBorder;
    40.     }
    41. }

    69. x 的平方根 

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

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

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

    1. 示例 1：
    2.  
    3. 输入：x = 4
    4. 输出：2
    5. 示例 2：
    6.  
    7. 输入：x = 8
    8. 输出：2
    9. 解释：8 的算术平方根是 2.82842..., 由于返回类型是整数，小数部分将被舍去。
    10.

    思路：这题一眼看过去好像没什么头绪，这怎么和二分查找有关？不是要左右边界才能考虑嘛？其实可以把边界写成[0,x]，这样只需要判断mid*mid和x的关系即可。

    1. class Solution{
    2.      public int mySqrt(int x){
    3.          int left=0;
    4.          int right=x;
    5.          int ans=0;
    6.          while(left<=right){
    7.              int mid=left+(right-left)/2;
    8.              if((long)mid*mid==x){
    9.                  return mid;
    10.              }else if((long)mid*mid>x){
    11.                  right=mid-1;
    12.              }else if((long)mid*mid<x){
    13.                  ans=mid;
    14.                  left=mid+1;
    15.              }
    16.         }
    17.         return ans;
    18.     }
    19. }

    367. 有效的完全平方数

    给定一个 正整数 num ，编写一个函数，如果 num 是一个完全平方数，则返回 true ，否则返回 false 。

    进阶：不要 使用任何内置的库函数，如  sqrt 。

    1. 示例 1：
    2.  
    3. 输入：num = 16
    4. 输出：true
    5. 示例 2：
    6.  
    7. 输入：num = 14
    8. 输出：false

    思路：和上面一题几乎一样，这题只需要判断返回true或者false，也是使用二分查找即可,需要注意的是为了防止溢出需要转化为long类型。

    1. class Solution {
    2.     public boolean isPerfectSquare(int num) {
    3.         int left=0;
    4.         int right=num;
    5.        
    6.         
    7.          while(left<=right){
    8.             int mid=left+(right-left)/2;
    9.             
    10.            if((long)mid*mid>num){
    11.                 right=mid-1;
    12.             }else if((long)mid*mid<num){
    13.                 left=mid+1;
    14.             }else if((long)mid*mid==num){
    15.                 return true;
    16.             }
    17.         }
    18.         return false;
    19.     }
    20. }

    二.双指针

    209. 长度最小的子数组

    给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中满足其和 ≥ s 的长度最小的子数组。如果不存在符合条件的子数组，返回 0。

    1. 输入: [2,3,1,2,4,3], s = 7
    2. 输出: 2
    3. 解释: 子数组 [4,3] 是该条件下的长度最小的子数组。

    思路：这题考虑用滑动窗口，本质就是双指针，滑动窗口的题需要解决以下问题：1.缩小左右边界 2.窗口内的值的变化 

    1. class Solution{
    2.     public int minSubArrayLen(int target, int[] nums){
    3.         int slow=0;//滑动窗口左边界
    4.         int sum=0;
    5.         int res=Integer.MAX_VALUE;
    6.         for(int fast=0;fast<nums.length;fast++){//滑动窗口右边界
    7.             sum+=nums[fast];
    8.             while(sum>=target){//当窗口内的值大于等于target时需要将左边界缩小
    9.                 res=Math.min(res,fast-slow+1);//先记录此时窗口的长度
    10.                 sum-=nums[slow];//因为窗口左边界缩小所以里面的值也要相应的减去左边界的值
    11.                 slow++;//移动左边界
    12.             }
    13.         }
    14.         return res==Integer.MAX_VALUE?0:res;//如果target不能满足返回0
    15.     }
    16. }

    904. 水果成篮

    你正在探访一家农场，农场从左到右种植了一排果树。这些树用一个整数数组 fruits 表示，其中 fruits[i] 是第 i 棵树上的水果 种类 。

    你想要尽可能多地收集水果。然而，农场的主人设定了一些严格的规矩，你必须按照要求采摘水果：

    你只有 两个 篮子，并且每个篮子只能装 单一类型 的水果。每个篮子能够装的水果总量没有限制。
    你可以选择任意一棵树开始采摘，你必须从 每棵 树（包括开始采摘的树）上 恰好摘一个水果 。采摘的水果应当符合篮子中的水果类型。每采摘一次，你将会向右移动到下一棵树，并继续采摘。
    一旦你走到某棵树前，但水果不符合篮子的水果类型，那么就必须停止采摘。
    给你一个整数数组 fruits ，返回你可以收集的水果的 最大 数目。

    1. 示例 1：
    2.  
    3. 输入：fruits = [1,2,1]
    4. 输出：3
    5. 解释：可以采摘全部 3 棵树。
    6. 示例 2：
    7.  
    8. 输入：fruits = [0,1,2,2]
    9. 输出：3
    10. 解释：可以采摘 [1,2,2] 这三棵树。
    11. 如果从第一棵树开始采摘，则只能采摘 [0,1] 这两棵树。
    12. 示例 3：
    13.  
    14. 输入：fruits = [1,2,3,2,2]
    15. 输出：4
    16. 解释：可以采摘 [2,3,2,2] 这四棵树。
    17. 如果从第一棵树开始采摘，则只能采摘 [1,2] 这两棵树。
    18. 示例 4：
    19.  
    20. 输入：fruits = [3,3,3,1,2,1,1,2,3,3,4]
    21. 输出：5
    22. 解释：可以采摘 [1,2,1,1,2] 这五棵树。
    23.  
    24. 来源：力扣（LeetCode）
    25. 链接：https://leetcode.cn/problems/fruit-into-baskets
    26. 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
    1. class Solution {
    2.     public int totalFruit(int[] fruits) {
    3.         int slow=0;//左边界
    4.         Map<Integer,Integer> map=new HashMap<>();//使用map计数
    5.         int res=0;
    6.         for(int fast=0;fast<fruits.length;fast++){//有边界
    7.             map.put(fruits[fast],map.getOrDefault(fruits[fast],0)+1);//将右边界的值添加
    8.             while(map.size()>2){ //不满足条件 即容量大于2            
    9.                     
    10.                 if(map.get(fruits[slow])==1){
    11.                     map.remove(fruits[slow]);//如果size为1 则删除
    12.                     slow++;
    13.                 }else{
    14.                     map.put(fruits[slow],map.get(fruits[slow])-1);//如果size不为1 说明不只一个重复 只需要计数减一
    15.                     slow++;//移动左边界
    16.                 }
    17.                 
    18.             }
    19.             res=Math.max(res,fast-slow+1);//比较
    20.         }
    21.         return res;
    22.     }
    23. }

    59. 螺旋矩阵 II

    给你一个正整数 n ，生成一个包含 1 到 n2 所有元素，且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix 。

    示例 1：

    1. 输入：n = 3
    2. 输出：[[1,2,3],[8,9,4],[7,6,5]]
    3. 示例 2：
    4.  
    5. 输入：n = 1
    6. 输出：[[1]]

     思路：解题的核心思路是按照右、下、左、上的顺序遍历数组，并使用四个变量圈定未遍历元素的边界：

    随着螺旋遍历，相应的边界会收缩，直到螺旋遍历完整个数组： 

    1. class Solution {
    2.     public int[][] generateMatrix(int n) {
    3.         int upper=0;
    4.         int right=n-1;
    5.         int lower=n-1;
    6.         int left=0;
    7.         int[][] matrix=new int[n][n];
    8.         int num=1;
    9.         while(num<=n*n){
    10.                 //上边界
    11.                 if(upper<=lower){
    12.                     for(int i=left;i<=right;i++){
    13.                         matrix[upper][i]=num++;
    14.                     }
    15.                     upper++;//上边界向下移动
    16.                 }
    17.  
    18.                 //右边界
    19.                 if(left<=right){
    20.                     for(int j=upper;j<=lower;j++){
    21.                         matrix[j][right]=num++;
    22.                     }
    23.                     right--;//右边界向左移动
    24.                 }
    25.  
    26.                 //下边界
    27.                 if(upper<=lower){
    28.                     for(int i=right;i>=left;i--){
    29.                         matrix[lower][i]=num++;
    30.                     }
    31.                     lower--;//下边界向上移动
    32.                 }
    33.  
    34.                 //左边界
    35.                 if(left<=right){
    36.                     for(int j=lower;j>=upper;j--){
    37.                         matrix[j][left]=num++;
    38.                     }
    39.                     left++;//左边界向有移动
    40.                 }
    41.         }
    42.         
    43.         return matrix;
    44.     }
    45. }

    参考：二维数组的花式遍历技巧 :: labuladong的算法小抄

    小总结：总体来说数组类的题目分为两类：第一个是一维数组，第二个是二维数组。对于一维数组最常用的方法就是二分查找法，二分查找法有一定的框架，然后根据题目要求修改细节；还有一个方法就是用双指针，其中包括快慢指针，滑动窗口，一般而言都是让两个指针slow=0，fast=0；还有就是slow=0，fast=nums.length-1具体看题目要求。第二类是二维数组，二维数组的操作主要是观察行和列之间的关系，包括一些变换，对角线对称，旋转等。 

  • 相关阅读:
    慢SQL优化
    pytorch深度学习入门
    16-SpringBoot 整合Druid数据源
    CentOS8安装MySQL
    webGL编程指南 第三章 矩阵旋转三角形rotatedTriangle_Matrix
    vue3 + axios 中断取消接口请求
    前端Vue入门-day08-vant组件库
    部署LVS-DR群集
    DolphinDB & 浙商银行 | 第二期现场培训圆满结束
    https协议
  • 原文地址：https://blog.csdn.net/weixin_46345400/article/details/125550737