研究一下算法题里面数组常见的一些题出法和思路

参考链接:
代码随想录 (programmercarl.com)

双指针

删除元素

对应题目：27. 移除元素 - 力扣（Leetcode）

  • 快指针 !=目标值 快慢同步运动
  • 快指针 =目标值 出现步幅差
    双指针实现
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    public int removeElement(int[] nums, int val) {
    	// 快慢指针
    	int slowIndex = 0;
    	// 快指针遍历
    	for (int fastIndex = 0; fastIndex < nums.length; fastIndex++) {
    		//慢指针同步运动
    		if (nums[fastIndex] != val) {
    			nums[slowIndex
    			
    			
    			
    			] = nums[fastIndex];
    			slowIndex++;
    		}
    	}
    	return slowIndex;
    }

有序数组平方

对应题目：977. 有序数组的平方 - 力扣（Leetcode）

  • 因为有序所以最大值出现在左右两端
  • 放入新结果集的时候只需要比较端点值大小
    双指针移动
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    public int[] sortedSquares(int[] nums) {
    	int right = nums.length - 1;
    	int left = 0;
    	int[] result = new int[nums.length];
    	int index = result.length - 1;
    	while (left <= right) {
    		if (nums[left] * nums[left] > nums[right] * nums[right]) {
    			// 正数的相对位置是不变的， 需要调整的是负数平方后的相对位置
    			result[index--] = nums[left] * nums[left];
    			++left;
    		} else {
    			result[index--] = nums[right] * nums[right];
    			--right;
    		}
    	}
    	return result;
    }

二分法

二分法是数组常用的方法，思路是逐渐减少范围，获得需要的值。
必要条件是：

  1. 数组为有序数组（确定范围的手段）
  2. 数组中无重复元素（确定下标的唯一性)
二分法的难点

重点在区间划分

“大家写二分法经常写乱，主要是因为对区间的定义没有想清楚，区间的定义就是不变量。要在二分查找的过程中，保持不变量，就是在while寻找中每一次边界的处理都要坚持根据区间的定义来操作，这就是循环不变量规则。”

写二分法，区间的定义一般为两种，左闭右闭即[left, right]，或者左闭右开即[left, right)。
二分法不断二分的循环驱动力是

1
while(left < right)

或者

1
while(left <= right)

双闭区间边界交换
个人认为二分法的 区间划分 问题过程在它的边界交换过程上，即在判定 mid 标志对应的数组位置值 大于或者小于 目标值的过程，修改新一次的范围的过程，需要对 mid 和 或者是 left 或者是 right 进行交换。这事涉及到边界交换。
核心点在：新的子区间相对于原有区间的范围（以mid）为界

  • 左闭右闭
    • 左右都闭，都能取到，为保证完全遍历，选用while(left <= right)
    • 区间形式能覆盖到右侧边界，所以已经对比过nums[mid],此时范围应该不包括nums[mid]
      • 选用 left = mid + 1 和 right = mid - 1
  • 左闭右开
    • 左闭右开，只有左的部分能取到，为保证完全遍历，不能让l，r重合，选用``while(left < right)````
    • 区间形式不能覆盖到右侧边界，此时范围应该可包括nums[mid]
      • 选用 left = mid + 1 和 right = mid

Leetcode:

  1. 704. 二分查找 - 力扣（Leetcode）
  2. 剑指 Offer 53 - I. 在排序数组中查找数字 I - 力扣（Leetcode）(二分查找 + 确定范围)
  3. 剑指 Offer II 072. 求平方根 - 力扣（Leetcode）

滑动窗口

滑动窗口

  • 不断的调节子序列的起始位置和终止位置，从而得出我们要想的结果
    滑动窗口操作
    在本题中实现滑动窗口，主要确定如下三点：
  • 窗口内是什么？
  • 如何移动窗口的起始位置？
  • 如何移动窗口的结束位置？
    滑动窗口关键
    对应题目209. Minimum Size Subarray Sum - 力扣（Leetcode）
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    public int minSubArrayLen(int s, int[] nums) {
    	int left = 0;
    	int sum = 0;
    	int result = Integer.MAX_VALUE;
    	
    	for (int right = 0; right < nums.length; right++) {
    		//每次添加right位置
    		sum += nums[right];
    		//如果满足最低限制开始判定，是个循环
    		while (sum >= s) {
    			//result是子序列长度
    			result = Math.min(result, right - left + 1);
    			// 循环每次都会做到维持sum大于s下的最极限left位置
    			sum -= nums[left++];
    		}
    	}
    	return result == Integer.MAX_VALUE ? 0 : result;
    }

    特定的算法

    开平方
    底层的算法实现，可行的实现思路有:
  1. 基于二分法的实现方式
    • 思路简单,基础的二分法即可
    • 没有绝对准确值，精度由acc控制，可理解为左右都开区间
    • 优化：可以对0,1特殊取值，然后右侧high优化到 num>>1
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      public static double Sqrt(int num){
          //使用二分法进行检测
          double low = 0, high = num, accury = 1e-5;
          double middle = (low + high) / 2;
          while (Math.abs(middle * middle - num) > accury){
               if(middle * middle > num){
                   high = middle;
               }else {
                   low = middle;
               }
               middle = (low + high) / 2;
          }
          return middle;
       }

  2. 牛顿迭代
    • 底层原理是泰勒级数,实现简单思路难
    • 牛顿迭代公式来源
      1
      2
      3
      4
      5
      6
      7
      8
          public int mySqrt(int x) {
              if (x < 0)  return 0;
              double err = 1e-2;      //精度不要太高，否则较大数运算时间过长  
              double t = x;             //t is a number we just guess
              while (Math.abs(x - t*t) > err)
                  t = (x/t + t) / 2.0;
              return (int)t;
          }

      参考链接：(18条消息) 牛顿法开平方_来离的博客-CSDN博客