算法七

hahg大约 36 分钟

算法七

四十九、石子游戏

力扣链接：https://leetcode.cn/problems/stone-game-vi/

Alice 和 Bob 轮流玩一个游戏，Alice 先手。
一堆石子里总共有 n 个石子，轮到某个玩家时，他可以移出一个石子并得到这个石子的价值。Alice 和 Bob 对石子价值有 不一样的的评判标准 。双方都知道对方的评判标准。
给你两个长度为 n 的整数数组 aliceValues 和 bobValues 。aliceValues[i] 和 bobValues[i] 分别表示 Alice 和 Bob 认为第 i 个石子的价值。
所有石子都被取完后，得分较高的人为胜者。如果两个玩家得分相同，那么为平局。两位玩家都会采用 最优策略 进行游戏。
请你推断游戏的结果，用如下的方式表示：
如果 Alice 赢，返回 1 。如果 Bob 赢，返回 -1 。如果游戏平局，返回 0 。
示例 1：
输入：aliceValues = [1,3], bobValues = [2,1]
输出：1
解释：
如果 Alice 拿石子 1 （下标从 0开始），那么 Alice 可以得到 3 分。
Bob 只能选择石子 0 ，得到 2 分。
Alice 获胜。
示例 2：
输入：aliceValues = [1,2], bobValues = [3,1]
输出：0
解释：
Alice 拿石子 0 ， Bob 拿石子 1 ，他们得分都为 1 分。
打平。
提示：
n == aliceValues.length == bobValues.length
1 <= n <= 105
1 <= aliceValues[i], bobValues[i] <= 100

（1）贪心算法

当拿了一个石子的时候，拿石子的人既 获取到的石子的价值 又让对面 失去了这个石子的价值

所以选择石子优先选择： 获取到的石子的价值 加上 失去了这个石子的价值 最大。

但实际自己获取到只有自己认为的价值。

class Solution {
  public int stoneGameVI(int[] aliceValues, int[] bobValues) {
    
    int n = aliceValues.length;
    // 存放总和数组
    int[][] sum = new int[n][2];

    // 计算两个数组对应格的和
    for (int i = 0; i < n; i++) {
      sum[i][0] = aliceValues[i] + bobValues[i];
      sum[i][1] = i;
    }
    
    // 对数组进行排序
    Arrays.sort(sum, new Comparator<int[]>() {
      @Override
      public int compare(int[] o1, int[] o2) {
        if (o1[0] == o2[0]) return 0;
        return o1[0] > o2[0] ? -1 : 1;
      }
    });

    int sumA = 0;
    int sumB = 0;
    // 分别统计两个玩家的分数
    for (int i = 0; i < n; i++) {
      int index = sum[i][1];
      if (i % 2 == 0){
        sumA += aliceValues[index];
      } else {
        sumB += bobValues[index];
      }
    }
    
    // 根据结果分别输出不同结果
    if (sumA == sumB) {
      return 0;
    }
    return sumA > sumB ? 1 : -1;
  }
}

public class Solution {
  public int networkDelayTime(int[][] times, int n, int k) {
    int[][] graph = new int[n][n];    //邻接矩阵初始化图
    for (int i = 0; i < n; i++) {
      Arrays.fill(graph[i], Integer.MAX_VALUE / 2);   //因为可能点与点之间无连接，因此初始化为无穷大。此处为避免33行计算溢出，>>2
    }
    for (int i = 0; i < times.length; i++) {         //根据题目给的信息times，对graph初始化。
      int source = times[i][0] - 1;
      int target = times[i][1] - 1;
      graph[source][target] = times[i][2];
    }
    boolean[] visited = new boolean[n];             //初始值为false,若访问，则为true。
    int[] dist = new int[n];                        //距离表。
    Arrays.fill(dist, Integer.MAX_VALUE / 2);   //初始化距离表为无穷。
    dist[k - 1] = 0;             //初始化起始点K-K的距离为0
    //dijkstra
    for (int j = 0; j < n; j++) {  //一次加入一个节点到路径中
      int cur = -1;
      for (int i = 0; i < n; i++){  //找出距离表中最小的节点 收录进来 即锁死该点，以后就不用了
        if (!visited[i] && (cur == -1 || dist[i] < dist[cur])) {   //！vidsited[i]即锁死的不用
          cur = i;
        }
      }

      visited[cur] = true;   //锁死上述找到的距离表中最小的节点。

      for (int i = 0; i < n; i++) {    //更新锁死节点与其相邻节点的dist.
        dist[i] = Math.min(dist[i], dist[cur] + graph[cur][i]);
      }
    }

    int result = 0;                      //题目要求，若dist中有未到达的节点，return-1；
    for (int i = 0; i < n; i++) {
      if (dist[i] == Integer.MAX_VALUE / 2) {
        return -1;
      }
      result = Math.max(result, dist[i]);
    }
    return result;
  }
}

原题链接：https://mp.weixin.qq.com/s?__biz=MzU4NDE3MTEyMA==&mid=2247485658&idx=1&sn=f298abe76d9cc058805b6a18d2523db6&chksm=fd9ca3c5caeb2ad31f6faefd800471b339d21cf54988e123fc507ff07b1447ae31337d826b0e&cur_album_id=1715134171561410565&scene=189#wechat_redirect

这是 LeetCode 上的**「416. 分割等和子集」**，难度为 Medium。
给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
注意:
每个数组中的元素不会超过 100
数组的大小不会超过 200
示例 1:
输入: [1, 5, 11, 5]
输出: true
解释: 数组可以分割成 [1, 5, 5] 和 [11].
示例 2:
输入: [1, 2, 3, 5]
输出: false
解释: 数组不能分割成两个元素和相等的子集.
提示：
1 <= nums.length <= 200
1 <= nums[i] <= 100

（1）分析

通常「背包问题」相关的题，都是在考察我们的「建模」能力，也就是将问题转换为「背包问题」的能力。

由于本题是问我们能否将一个数组分成两个「等和」子集。

问题等效于**「能否从数组中挑选若干个元素，使得元素总和等于所有元素总和的一半」**。

这道题如果抽象成「背包问题」的话，应该是：

我们背包容量为 $target = sum / 2$ ，每个数组元素的「价值」与「成本」都是其数值大小，求我们能否装满背包。

（2）转换为背包问题

然后就可以转换成背包问题

由于每个数字（数组元素）只能被选一次，而且每个数字选择与否对应了**「价值」和「成本」**，求解的问题也与「最大价值」相关。

可以使用「01 背包」的模型来做。

当我们确定一个问题可以转化为「01 背包」之后，就可以直接套用「01 背包」的状态定义进行求解了。

我们直接套用「01 背包」的状态定义：

f[i][j] 代表考虑前 i 个数值，其选择数字总和不超过 j 的最大价值。

当有了「状态定义」之后，结合我们的「最后一步分析法」，每个数字都有「选」和「不选」两种选择。

因此不难得出状态转移方程：

f[i - 1, j] ：不选该数字
f[i - 1][j - nums[i]] + nums[j] ：选了该数字

f[i][j] = max( f[i - 1, j], f[i - 1][j - nums[i]] + nums[j] )

优化：

如果全部和除以 2 为奇数时，等和子集的目标和必然不能凑成。
- 根据题目已知，能分割子集的式子： $f[0] + f[1] + ... + f[n-2] = f[n-1]$ （假设数组已经升序排序），可以推出 $\sum_{n=0}^{n-1} {f[n]} = f[0] + f[1] + ... + f[n-2] + f[n-1] = 2f[n-1]$ ，左右边全部除以 2， $\frac{\sum_{n=0}^{n-1} {f[n]}}{2} = f[0] + f[1] + ... + f[n-2] + f[n-1]$
一维下标为 n，代表在该下标之前取到的数。例如下标为 2，代表可以取到 0，1，2 三个物品
二维下标为价值数量，代表小于该数值的情况下的最大价值。例如二维下标为 4，代表不超过价值 4 的情况下的最大价值，最大价值是 4，且是最后一格，则返回证明可以凑成。

class Solution {
  public boolean canPartition(int[] nums) {
    int n = nums.length;

    //「等和子集」的和必然是总和的一半
    int sum = 0;
    for (int i : nums) sum += i;
    int target = sum / 2;

    // 对应了总和为奇数的情况，注定不能被分为两个「等和子集」
    if (target * 2 != sum) return false;

    int[][] f = new int[n][target + 1];
    // 先处理考虑第 1 件物品的情况
    for (int j = 0; j <= target; j++) {
      f[0][j] = j >= nums[0] ? nums[0] : 0;
    }

    // 再处理考虑其余物品的情况
    for (int i = 1; i < n; i++) {
      int t = nums[i];
      // 遍历价值
      for (int j = 0; j <= target; j++) {
        // 不选第 i 件物品
        int no = f[i - 1][j];
        // 选第 i 件物品
        int yes = j >= t ? f[i - 1][j - t] + t : 0;
        f[i][j] = Math.max(no, yes);
      }
    }
    // 如果最大价值等于 target，说明可以拆分成两个「等和子集」
    return f[n - 1][target] == target;
  }
}

时间复杂度： $target$ 为数组总和的一半， $n$ 为数组元素个数。或者看两层循环的长度。共有 $target * n$ 个状态需要被转移，复杂度为 $O(target * n)$
空间复杂度： $O(target * n)$

（3）优化空间

之前也说过动态规划优化空间。

第 1 个方式是滚动数组，只存放两行数据，当前行和上一行，每次覆盖将下一行的值覆盖到上一行的位置
第 2 个方式优化成一维数组，利用每次取数据的方向。因为每次取数据的是一个方向，覆盖已经取数据的位置就行。
- 但循环是向右遍历从 0 到 target - 1 ，而取数的方向是往左取的——f[i - 1][j - t] ，j - t 代表了是取左边的数，而之前左边的数被新数据覆盖，取不到旧数据。
- 所以循环需要换个方向，从右往左循环 for (int j = target; j >= 0; j--) {

全部代码如下：

class Solution {
  public boolean canPartition(int[] nums) {
    int n = nums.length;

    int sum = 0;
    for (int i : nums) sum += i;
    int target = sum / 2;

    if (target * 2 != sum) return false;

    // 将「物品维度」取消
    int[] f = new int[target + 1];
    for (int i = 0; i < n; i++) {
      int t = nums[i];
      // 将「容量维度」改成从大到小遍历
      for (int j = target; j >= 0; j--) {
        // 不选第 i 件物品
        int no = f[j];
        // 选第 i 件物品
        int yes = j >= t ? f[j-t] + t : 0;
        f[j] = Math.max(no, yes);
      }
    }
    // 如果最大价值等于 target，说明可以拆分成两个「等和子集」
    return f[target] == target;
  }
}

五十一、数据流中的第 K 大元素

原题链接：https://mp.weixin.qq.com/s?__biz=MzU4NDE3MTEyMA==&mid=2247485689&idx=1&sn=a0f92c80f91049d5ca5b0101274b14a6&chksm=fd9ca3e6caeb2af02b761d529eb833ab020694001c9ed7b0cd224dfdf615cb302ae8c28d6738&cur_album_id=1715134171561410565&scene=189#wechat_redirect

这是 LeetCode 上的**「703. 数据流中的第 K 大元素」**，难度为 「Easy」。
设计一个找到数据流中第 k 大元素的类（class）。
注意是排序后的第 k 大元素，不是第 k 个不同的元素。
请实现 KthLargest 类：
KthLargest(int k, int[] nums) 使用整数 k 和整数流 nums 初始化对象。
int add(int val) 将 val 插入数据流 nums 后，返回当前数据流中第 k 大的元素。
示例：
输入：
["KthLargest", "add", "add", "add", "add", "add"]
[[3, [4, 5, 8, 2]], [3], [5], [10], [9], [4]]
输出：
[null, 4, 5, 5, 8, 8]
解释：
KthLargest kthLargest = new KthLargest(3, [4, 5, 8, 2]);
kthLargest.add(3); // return 4
kthLargest.add(5); // return 5
kthLargest.add(10); // return 5
kthLargest.add(9); // return 8
kthLargest.add(4); // return 8
提示：
1 <= k <= 10⁴
0 <= nums.length <= 10⁴
-10⁴ <= nums[i] <= 10⁴
-10⁴ <= val <= 10⁴
最多调用 add 方法 10⁴ 次
题目数据保证，在查找第 k 大元素时，数组中至少有 k 个元素

（1）冒泡排序

初始化时，不排序，只有在添加的时候再排序。
使用列表：因为扩展数组的长度较容易

class KthLargest {

  List<Integer> data = new ArrayList();

  int k;

  public KthLargest(int k, int[] nums) {
    this.k = k;
		// 不排序依次添加到列表
    for (int i : nums) {
      data.add(i);
    }
  }

  public int add(int val) {
    // 添加新的数字
    data.add(val);
    
    // 进行冒泡排序（降序）
    int n = data.size(); 
    for (int i = 0; i < k; i++) {
      // 找到最大值
      int maxIndex = findMax(i, n - 1);
      // 将最大值与当前位置的数字交换
      swapNum(i, maxIndex);
    }
    return data.get(k - 1);
  }

  public void swapNum(int a, int b) {
    int temp = data.get(a);
    data.set(a, data.get(b));
    data.set(b, temp);
  }

  // 在start和end下标之间找最大值
  public int findMax(int start, int end) {
    int max = Integer.MIN_VALUE / 2;
    int maxIndex = start;
    for (int i = start; i <= end; i++) {
      int tempNum = data.get(i);
      if (tempNum > max) {
        max = tempNum;
        maxIndex = i;
      }
    }
    return maxIndex;
  }
}

时间复杂度： $O(n * k)$
空间复杂度： $O(k)$
当 $n、k$ 都很大时，就会超时。如果使用 Java 自带的排序进行排序，不会超时，但花费的时间依然很多

（2）移动数字

其实 没有必要在每次添加数字后进行排序，因为第 1 次添加的时候已经排过一次序。后面添加的时候只需要找到新数字的位置，然后再将其余的数字往后移动。

import java.util.Collections;
class KthLargest {

  int[] data;

  int length;

  int k;

  public KthLargest(int k, int[] nums) {
    this.k = k;
    this.data = nums;
    this.length = data.length;
		// 对数组进行排序（升序）
    Arrays.sort(data);
  }

  public int add(int val) {
    // 新建一个临时数组
    int[] tempArray = new int[++length];

    // 如果最开始的空的，不适合移动数字算法
    if (length == 1) {
      tempArray[0] = val;
      data = tempArray;
      return val;
    }
    
    int i = length - 1;
    for (; i > 0; i--) {
      if (val < data[i - 1]) {	// 如果新数比当前数字小，直接将数字往后移
        tempArray[i] = data[i - 1];
      } else {	// 如果新数大于等于当前数字，结束循环
        // 将新的数字放入空格中
        tempArray[i] = val;
        // 剩余的数字一一对应放入
        for (int j = 0; j < i; j++) {
          tempArray[j] = data[j];
        }
        break;
      }
    }
    
    // 如果将所有的数字全部移了一遍，
    // 则新数组里的第1格是空的，需要额外处理
    if (i == 0) {
      tempArray[0] = val;
    }
    // 更新对面的里数组
    data = tempArray;
    return data[length - k];
  }
}

时间复杂度：
- 排序： $O(nlogn)$
- 调用 1 次 add() 方法：最差 $O(n)$ ，最好 $O(1)$
- 所以最差情况，n 个数字添加，每次都要移动全部数字， $O(n^2)$
空间复杂度： $O(n)$

（3）小根堆

小根堆：会自动排序的容器，最顶部是容器中的最小值。
只存放 k 个数：因为我们使用到前面 k 个数，只有添加的数符合某些规则时，才会调整这 k 个数
- 添加的数 <= 根顶元素：因为堆里面是 数组里前 k 大的值，如果添加的数小于或者等于第 k 大的值，则添加的数是第 k + x 大的数，我们永远不会使用到
- 添加的数 > 根顶元素：一定会导致堆变化，而根顶的元素 一定会被排除在前面 k 个数 ，所以直接
- 小根堆的使用场景：只在乎存的数值，不在乎在数组里的位置。在【四十八、跳跃游戏】中，虽然也是找滑动窗口的最大值，但是移除元素的时候是根据在数组的下标.

class KthLargest {
  int k;
  PriorityQueue<Integer> queue;
  
  public KthLargest(int _k, int[] _nums) {
    k = _k;
    // 新建小根堆
    queue = new PriorityQueue<>(k, Integer::compare);
    int n = _nums.length;
    // 前 k 个数直接放入小根堆里
    for (int i = 0; i < k && i < n; i++) queue.add(_nums[i]);
    // 其他的数，调用add()方法来添加，以维持小根堆的长度
    for (int i = k; i < n; i++) add(_nums[i]);
  }
  
  public int add(int val) {
    // 如果小根堆是空，则无法取出根顶元素
    int t = !queue.isEmpty() ? queue.peek() : Integer.MIN_VALUE;
    // 只有两种场景才要操作
    // 1. 堆的长度没有够 k
    // 2. 堆满的时候，新数大于根顶
    if (val > t || queue.size() < k) {
      // 当堆满的时候才需要去除元素
      if (queue.size() >= k) {
        queue.poll();
      }
      // 因为无论是第1点还是第2点，都需要添加元素
      // 所以相同的操作提取出来
      queue.add(val);
    }
    return queue.peek();
  }
}

时间复杂度：最坏情况下，n 个元素入堆，都触发堆调整。调整一次堆排序就需要时间 $O(logk)$ ，所以总复杂度为 $O(nlogk)$
空间复杂度： $O(logk)$

五十二、分割等和子集2

原题链接：https://mp.weixin.qq.com/s?__biz=MzU4NDE3MTEyMA==&mid=2247485727&idx=1&sn=2cfb1a43bdb4f47cf4457c58f809deb8&chksm=fd9ca200caeb2b16e7c70ffe673886ba3577b3c084ec204a532cf4a5e0d46dc1b51b34970ba2&cur_album_id=1715134171561410565&scene=189#wechat_redirect

这是 LeetCode 上的**「416. 分割等和子集」**，难度为 Medium。
给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
注意:
每个数组中的元素不会超过 100
数组的大小不会超过 200
示例 1:
输入: [1, 5, 11, 5]
输出: true
解释: 数组可以分割成 [1, 5, 5] 和 [11].
示例 2:
输入: [1, 2, 3, 5]
输出: false
解释: 数组不能分割成两个元素和相等的子集.
提示：
1 <= nums.length <= 200
1 <= nums[i] <= 100

（1）分析

在【分割等和子集1】中，我们是间接得出结果。

间接：先求出不超过某个值的最大值，再判断是否和某个值相等。

这次要改正使用，要直接得出结果

直接：直接知道是否可以凑出指定数字。

（2）实现

现在需要改变 状态定义 和 转移方程。

状态定义：
- f[i - 1][j] 代表不选当前数字，是否恰好可以凑出；
- f[i - 1][j - nums[i]] 代表选了当前数字，是否恰好可以凑出
转移方程：
- 二维数组中存放的是 布尔值。
- 第 1 行会遇到初始化问题，因为每个行都依靠上一行的数据。所以需要在第 1 行添加 不考虑任何物品 的情况。
- 最终的转移方程是 $f[i][j] = f[i-1][j] \vee f[i][j-nums[i]]$
- $i$ 的取值范围 $0 \sim n$ ； $j$ 的取值范围 $0 \sim target$

最后的数组为这样：假设有 [1, 2, 3]

	0	1	2	3
0	T	F	F	F
1	T	T	F	F
2	T	T
3	T

因为第 1 行不放任何东西，所以只有背包容量为 0 时，才恰好装满
其他行就是看上面和当前行的前面某列

class Solution {
  public boolean canPartition(int[] nums) {
    int n = nums.length;

    //「等和子集」的和必然是总和的一半
    int sum = 0;
    for (int i : nums) sum += i;
    int target = sum / 2;

    // 对应了总和为奇数的情况，注定不能被分为两个「等和子集」
    if (target * 2 != sum) return false;

    // f[i][j] 代表考虑前 i 件物品，能否凑出价值「恰好」为 j 的方案
    // 横坐标：0 ~ n，长度为 n + 1
    // 纵坐标：0 ~ target,长度为 target + 1
    boolean[][] f = new boolean[n + 1][target + 1];
    f[0][0] = true;
    
    // i的范围是0 ~ n，但第1行已初始化，循环的范围是1 ~ n
    for (int i = 1; i <= n; i++) {
      // 取 nums[] 的数 i 需要减 1，因为 nums 下标范围是 0 ~ n-1
      int t = nums[i - 1];
      for (int j = 0; j <= target; j++) {
        // 不选该物品
        boolean no = f[i - 1][j];
        // 选该物品
        boolean yes = j >= t ? f[i - 1][j - t] : false;
        f[i][j] = no | yes;
      }
    }
    return f[n][target];
  }
}

时间复杂度： $target$ 为数组总和的一半， $n$ 为数组元素个数。或者看两层循环的长度。共有 $target * n$ 个状态需要被转移，复杂度为 $O(target * n)$
空间复杂度： $O(target * n)$

五十三、被围绕的区域

力扣链接：https://leetcode.cn/problems/surrounded-regions/

这是 LeetCode 上的**「130. 被围绕的区域」**，难度为 Medium。
给你一个 m x n 的矩阵 board ，由若干字符 'X' 和 'O' ，找到所有被 'X' 围绕的区域，并将这些区域里所有的 'O' 用 'X' 填充。
示例 1：
输入：
board = [
  ["X", "X", "X", "X"],
  ["X", "O", "O", "X"],
  ["X", "X", "O", "X"],
  ["X", "O", "X", "X"]
]
  
输出：[
  ["X", "X", "X", "X"],
  ["X", "X", "X", "X"],
  ["X", "X", "X", "X"],
  ["X", "O", "X", "X"]
]
提示：
m == board.length
n == board[i].length
1 <= m, n <= 200
board[i][j] 为 'X' 或 'O'

（1）普通思维

使用普通的人脑思维，这道题就是从一个 “ O ” 出发，然后找到其他 “ O ”，然后再看这些 “ O ” 中有没有到达边界。

这种思维有两个需要记录的地方：

记录 之前访问过的位置，在下次循环的时候可以跳过。因为访问过的位置，不会再改变了
记录 当前趟 所遍历过的位置，用于将当前趟的所有格变成 “ X ”。

下面代码就是模仿人脑思维：

首先遍历每一个没有访问过的 “ O ” ，第 27 ~ 43 行 board[i][j] == 'O' && flag[i][j] != '-'
将这格标记已访问过，并记录到临时列表 memory 中。然后通过这个 “ O ”，找出与其相邻的 “ O ”，
重复第 2 步，直到 周围被 “ X ” 包围 或者 到达边界，第 48 ~ 72 行。如果在遍历过程中，到达边界，则将 ifWrap 置为 false ，因为只要到达边界，当前趟就处于不被包围状态。
退出递归后，判断 ifWrap 变量，如果为 true ，则将当前趟的所有格变为 “ X ”

class Solution {

  // 记录标记每格的访问情况
  char[][] flag;
  // 成员变量，便于递归调用
  char[][] data;
	// 记录当前趟已访问过的坐标
  List<int[]> memory = new ArrayList<>();

  boolean ifWrap;

  int[][] direction = {
    // 上      下       左      右
    {-1, 0}, {1, 0}, {0, -1}, {0, 1}
  };


  public void solve(char[][] board) {

    data = board;
    int m = board.length;
    int n = board[0].length;
    flag = new char[m][n];
    // 复制成一模一样的数组
    copyArray(flag, board);

    for (int i = 1; i < m - 1; i++) {
      for (int j = 1; j < n - 1; j++) {
        // 如果当前格是“O”并且没访问过，则进行递归
        if (board[i][j] == 'O' && flag[i][j] != '-') {
          // 重置标志然后进行递归
          ifWrap = true;
          findIfWrap(i, j);
          // 如果发现当前趟是被包围的则将当前趟变为“X”
          // 否则清除列表
          if (ifWrap == true) {	
            changeItemToX();
          } else {
            memory.clear();
          }
        }
      }
    }
  }

  // 作用：找出当前坐标是否被包围
  // 参数：m - 当前行；n - 当前列
  public void findIfWrap(int m, int n) {
    // 如果到达边界则说明没被包围
    if (m == data.length - 1 || n == data[0].length - 1 || m == 0 || n == 0) {
        ifWrap = false;
        return;
    }
    
    // 将当前坐标记录在列表中
    memory.add(new int[] {m, n});
    // 记录当前格已被访问
    flag[m][n] = '-';
    
    // 遍历四个方向
    for (int i = 0; i < direction.length; i++) {
      int[] item = direction[i];
      // 记录下一个到的格子的坐标
      int nm = m + item[0];
      int nn = n + item[1];
      // 如果当前格是“O”并且没有被访问，则进行递归
      if (data[nm][nn] == 'O' && flag[nm][nn] != '-') {
       	// 深度遍历
        findIfWrap(nm, nn);
      }
    }
  }

  // 改变
  public void changeItemToX() {
    for (int i = 0; i < memory.size(); i++) {
      int m = memory.get(i)[0];
      int n = memory.get(i)[1];

      data[m][n] = 'X';
    }

    memory.clear();
  }
  
  public void copyArray(char[][] t, char[][] s){
    for (int i = 0; i < t.length; i++) {
      for (int j = 0; j < t[0].length; j++) {
        t[i][j] = s[i][j];
      }
    }
  }
}

时间复杂度：因为每个格都遍历过一遍，所以时间复杂度为 $O(m*n)$
空间复杂度：两个 $m*n$ 的数组，和最大空间可以到达 $m*n$ 的列表， $O(3*m*n)$ ，忽略常数则为 $O(m*n)$
主要耗时：
- 改变被包围 “ O ” 的值（将指定的 “ O ” 变为 “ X ”）：先记录当前趟所到达的位置，然后再遍历所记录的位置，将其全部变成 “ X ”。如果当前趟到达过的位置很多，几乎是全部位置，则遍历两次就会很花时间，最后一个用例就是这种情况。

（2）规律解法

换种思维，之前是 从里面找是否到达边界，现在可以试下 从边界到达里面。

如果通过边界遍历完后，没有遍历到的 “ O ” ，就需要变为 “ X ”。

这个解法就巧妙地解决了第（1）点的耗时。
- 遍历两次不需要改变的 “ O ”
- 遍历一次需要改变的 “ O ”
- 因为最后一个用例需要改变的 “ O ”较多，所以在力扣上这个解法比较省时

代码思路：

将通过边界的遍历到的位置变为 “ - ”
将剩余的 “ O ”，变为 “ X ”
将 “ - ” 变为 “ O ”

class Solution {
  int m;
  int n;
  char[][] data;
  int[][] direction = {
    // 上      下       左      右
    {-1, 0}, {1, 0}, {0, -1}, {0, 1}
  };

  public void solve(char[][] board) {
    m = board.length;
    n = board[0].length;
    data = board;

		// 遍历第 1 行和最后 1 行
    for (int i = 0; i < n; i++) {
      dfs(0, i);
      dfs(m - 1, i);
    }

    // 遍历第 1 列和最后 1 列
    for (int i = 0; i < m; i++) {
      dfs(i, 0);
      dfs(i, n - 1);
    }

    // 将 "O" 变为 "X"，将 "-" 变为 "O"
    for (int i = 0; i < m; i++) {
      for (int j = 0; j < n; j++) {
        if (board[i][j] == 'O')
          board[i][j] = 'X';
        if (board[i][j] == '-')
          board[i][j] = 'O';
      }
    }
  }

  private void dfs(int a, int b) {
    // 如果当前遍历过，不为 "O"，并且到达边界之外，
    // 则退出当层递归
    if(a < 0 || b < 0|| a >= m || b >= n || data[a][b] != 'O')
      return;

    // 将当前位置置为 ”-“
    data[a][b] = '-';

    // 遍历当前格的四个方向
    for (int i = 0; i < direction.length; i++) {
      int na = direction[i][0] + a;
      int nb = direction[i][1] + b;
      dfs(na, nb);
    }
  }
}

时间复杂度：因为变化值需要遍历数组的全部元素，所以复杂度为 $O(m*n)$
空间复杂度： $O(m*n)$

五十四、第K个语法符号

原题链接：https://leetcode.cn/problems/k-th-symbol-in-grammar/

这是 LeetCode 上的**「779. 第K个语法符号」**，难度为 Medium。
我们构建了一个包含 n 行( 索引从 1 开始 )的表。首先在第一行我们写上一个 0。接下来的每一行，将前一行中的0替换为01，1替换为10。
例如，对于 n = 3 ，第 1 行是 0 ，第 2 行是 01 ，第3行是 0110 。
给定行数 n 和序数 k，返回第 n 行中第 k 个字符。（ k 从索引 1 开始）
示例 1:
输入: n = 1, k = 1
输出: 0
解释: 第一行：0
示例 2:
输入: n = 2, k = 1
输出: 0
解释:
第一行: 0
第二行: 01
提示:
1 <= n <= 30
1 <= k <= 2n - 1

（1）普通解法

从题目可以找到规律，下一行的前半部分是当前的行。这个特性就可以知道 每个数字不会随着行数改变的。

现在题目就变换成了，求第 x 行的第 k 个字符，第 x 行的数量是最接近 k 的位置的，不必求出第 n 行的全部数字。

举个例子，假设现在求出第 20 行的第 3 个数，我们不必就第 20 行的数字全部求出来，只需要求到第 3 行就行。

下面为部分通过代码，思路没错，就是后面的案例。不通过原因，需要的数字太多，例如案例 30 262466395 ，就需要 268435456 个位数，取第 262466395 位，而就算是 long 类型，也只能 64 位。

class Solution {
  public int kthGrammar(int n, int k) {
    // 计算出需要多少个数字
    int count = (int) Math.pow(2, n - 1);

    // 总的循环次数
    while (count / 2 > k) {
      count /= 2;
    }

    // 存放最终结果
    int res = 0;
		// 记录当前有多少个数字
    int i = 1;
    
    // 只要当前数字个数少于需要的数字，就继续循环计算每一行的数字
    while (i < count) {
			// 将当前数字的后一半取出来
      int second = cutHalf(res, i);
			// 将后一半的数字进行扩展
      int newSecond = extendBit(second);
      // 当前数字个数翻倍
      i *= 2;
      // 将原数组进行位扩展，扩展多自己的一倍
      res = res << (i / 2);
      // 然后更新后一半的数字
      res += newSecond;
    }

		// 取出指定位置的数字
    return res >> (count - k) & 1;
  }

  // 作用：扩展参数里的每一个数组
  int extendBit(int source) {
    // 如果参数是0，则直接扩展完成的01
    if (source == 0) {
      return 1;
    }
    
    // 扩展完成的最终结果
    int res = 0;
    // 记录每位需要移动到的位置
    int moveBit = 0;
    while (source > 0) {
      // 取最后一位
      int bit = source & 1;

      if (bit == 1) {	// 如果是1，则左移一位，变为 10
        bit = bit << 1;
      } else {	// 如果是0，则加1，变为 01
        bit += 1;
      }
      // 将结果移位到对应位置，然后存到res里
      res += bit << moveBit;
      // 更新移动到的位置
      moveBit += 2;
      // 将最后一位去掉
      source = source >> 1;
    }
    return res;
  }

  // 作用：将参数切一半
  // 返回：参数的后半部分
  int cutHalf(int source, int length) {

    // 将参数右移一半再左移一半，就能将后半部分清零
    int first = source >> (length / 2) << (length / 2);
		// 参数减取高位，就能得到低位
    int second = source - first;

    return second;
  }
}

（2）规律解法

从上面可知，不论多少行，每一位的数字都是一成不变的。例如第 1 行的第 1 个数字和第 30 行的第 1 个数字是一致的。

我们就需要找到其中的规律，这个数字的位置和最终得出的数字有没有规律。

看到 0 1 交替出现，会有点奇偶校验的感觉

举个例子：易知见几个数为 0110 1001

索引为x -> 数值
  0    ->  0   0000[0个1]
  1    ->  1   0001[1个1]
  2    ->  1   0010[1个1]
  3    ->  0   0011[2个1]
  4    ->  1   0100[1个1]
  5    ->  0   0101[2个1]
  6    ->  0   0110[2个1]
  7    ->  1   0111[3个1]

从 1 的个数可以发现规律，当 0、2 个 1 时，数值就是 0；当 1、3 个 1 时，数值就是 1

换句话来说，就是将当前索引转换成二进制， 这个二进制里的 1 的个数为偶数，数值就是 0；奇数的话，数值就是 1

一句话来说就是 偶校验 （原本的二进制数 + 数值的 1 的个数是偶数）

class Solution {
  public int kthGrammar(int n, int k) {
    // 将第x位，转化为索引为x
    k--;
    // 用于累计1个个数
    int total = 0;
    
    // 循环取出每一个位的数
    while (k > 0) {
      // 取出最后1位
      int bit = k & 1;
      // 如果当前是1，则累计加1
      if (bit == 1) {
        total++;
      }
      // 更新最后一位
      k = k >> 1;
    }
    
    if (total % 2 == 0) { // 如果是偶数就返回0
      return 0;
    } else {	// 如果是奇数就返回1
      return 1;
    }
  }
}

（3）位置解法

根据第（1）点，下一行的前半部分是当前的行，所以我们就需要找到后半部分与前半部分的规律

0            
01           		  -> 0        的相反是 1    
01 10             -> 01       的相反是 10  
0110 1001         -> 0110     的相反是 1001 
01101001 10010110 -> 01101001 的相反是 10010110

可以得知前部分取反就是后半部分。但从第（1）点可知，我们不可能将所有的数字求出来，然后再取出指定位置的数字。所以需要二分法来不断反转。

用第 5 行举一个例子：

现在要求出第 13 个数字的值，从上面一个个数可知，第13个数是 0

先求出当前行的数字的个数 —— 2⁴ = 16
根据需要求数字的位置定位到是 前半部分 还是 后半部分
13 > 16/2 = 8 所以在后半部分
然后在 前半部分的对应位置/上一行的对应位置 取反
而 前部分的对应位置/上一行的对应位置 也可以分为两部分，然后回到第 1 步

（第 4 步也可以使用一个全局变量记录在后半部分的位置，然后在退出递归的时候直接计算记录的奇偶性）

这个就可以使用递归来计算

五十五、合并两个有序链表

原文链接：https://mp.weixin.qq.com/s?__biz=MzU4NDE3MTEyMA==&mid=2247485797&idx=1&sn=1ff86bf0657d94697cdece55767f75ba&chksm=fd9ca27acaeb2b6cf3ae56cde513b218e1bbb4d8adba5e3eb79be0a5bb8f54d7135077a52b98&cur_album_id=1715134171561410565&scene=189#wechat_redirect

这是 LeetCode 上的**「21. 合并两个有序链表」**，难度为 「Easy」。
将两个升序链表合并为一个新的**「升序」**链表并返回。
新链表是通过拼接给定的两个链表的所有节点组成的。
示例 1：
输入：
l1 = [1, 2, 4]
l2 = [1, 3, 4]
输出：[1, 1, 2 ,3, 4, 4]
提示：
两个链表的节点数目范围是 [0, 50]
-100 <= Node.val <= 100
l1 和 l2 均按「非递减顺序」排列
链表定义：
// Definition for singly-linked list.
public class ListNode {
  int val;
  ListNode next;
  ListNode() {}
  ListNode(int val) { this.val = val; }
  ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}

（1）核心解法

我们使用双指针解法。

做有关链表的题目，有个常用技巧：添加一个虚拟头结点（哨兵），可以简化边界情况的判断。

边界情况的判断主要在于三个方面

其中一个链表为空
第一个和第二个链表都为空

如果不考虑边界情况的核心代码如下：

循环的退出的条件是两个链表其中一个为空
循环里所作的事是
- 1、找出数字大的节点
- 2、将结果链表指向数字大的节点
- 3、数字大的节点向后移动一个

while(list1 != null && list2 != null) {
  if (list1.val >= list2.val) {
    temp.next = list2;
    temp = temp.next;
    list2 = list2.next;
  } else {
    temp.next = list1;
    temp = temp.next;
    list1 = list1.next;
  }
}

退出循环有两种可能：
- 其中一个指针指向为空 -> 将为空的指针指向不为空的指针
- 两个链表都为空 -> 不做任何事

if(list1 == null) {
  temp.next = list2;
} else {
  temp.next = list1;
}

（2）双指针解法（哨兵技巧）

如果不添加一个虚拟头结点（哨兵），看要怎么来写代码：

判断两个链表哪个为空
结果链表指向其中不为空的链表
不为空链表的头指针移动到下一格

ListNode temp = null;
if (list1 == null && list2 != null) {	// 当list1为空
	temp = new ListNode(list2.val);
  list2 = list.next;
} else if (list2 == null && list1 != null) {	// 当list2为空
  temp = new ListNode(list2.val);
  list2 = list.next;
}
// ...

return temp;

如果添加了虚拟头结点，就代码就很简单了。

头指针不动
新建一个临时指针，最开始指向头结点，然后往后移动添加结点
最后返回头指针的下一个结点

// 新建一个虚拟头结点，因为用不到其值，其值可以随意
ListNode head = new ListNode();

// 新建一个临时结点
ListNode temp = head;

// ...

// 返回虚拟头结点的下一个结点
return head.next;

五十六、两两交换链表中的节点

原文链接：https://mp.weixin.qq.com/s?__biz=MzU4NDE3MTEyMA==&mid=2247485831&idx=1&sn=9881e540c2c329d211dfb12308a9ce86&chksm=fd9ca298caeb2b8e5120e16462e4b4722cedecdd122d97cf049a2f5f32a0254ca461c660d678&cur_album_id=1715134171561410565&scene=189#wechat_redirect

这是 LeetCode 上的**「24. 两两交换链表中的节点」**，难度为 Medium。
给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。
你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
示例 1：
输入：
head = [1,2,3,4]
输出：
result = [2,1,4,3]
提示：
链表中节点的数目在范围 [0, 100] 内
0 <= Node.val <= 100

（1）递归解法

因为是重复做一样的事，可以使用循环或者递归，这里先使用递归

核心算法：交换两个结点，具体步骤如下：

现在指针 head 指向的是这两个结点的 前面一个结点
假设这两个结点的第一个结点为 before，第二个结点为 after
先 head 指向 after，这步将 after 结点从第二个结点变为了第一个结点，before 结点这时变为后半部分的头结点
然后将 before 结点指向 after 的下一个结点，不再指向 after 结点，防止 after 的下一个结点丢失
最后将 after 指向 before ，这步与 after 的下一个结点断开，与 before 和原来相反连接

最后代码如下：这里也使用了虚拟头结点，这样在第 1 个递归的时候也符合普遍情况（有前结点），这样可以不用特殊处理

void swap(ListNode head) {
  ListNode before = head.next;
  if (before != null && before.next != null) {
    // 取出after结点
    ListNode after = before.next;
    
    // 先 head 指向 after
    head.next = after;
    
    // 将 before 结点指向 after 的下一个结点
    before.next = after.next;
    
    // 最后将 after 指向 before
    after.next = before;

    // 现在before变为第2个结点
    // 传入方法继续递归
    swap(before);
  }
}

上面代码处理了一些边界情况，例如两个结点其中有一个为空，或者两个都为空，判断顺序如下：

两个为空，只需要判断 before 是否为空
如果其中一个为空，那一定是 after 为空，只需要判断 after 是否为空
注意一定先判断 before 为空，如果为空则 before.next 就会报错，如第 2 行。after 的初始化一定要写在 if 里面，如第 4 行

  ListNode before = head.next;
  if (before != null && before.next != null) {
    // 取出after结点
    ListNode after = before.next;

（2）迭代解法（哨兵技巧）

所有的递归都能转化为迭代：将递归退出的条件变为迭代（循环）退出的条件

public ListNode swapPairs(ListNode head) {
  ListNode empty = new ListNode();

  empty.next = head;

  ListNode temp = empty;

  while (temp.next!= null && temp.next.next != null) {
    ListNode before = temp.next;
    // 取出after结点
    ListNode after = temp.next.next;

    // 先 head 指向 after
    temp.next = after;

    // 将 before 结点指向 after 的下一个结点
    before.next = after.next;

    // 最后将 after 指向 before
    after.next = before;

    temp = before;
  }

  return empty.next;
}

五十七、搜索旋转排序数组

原文链接：https://mp.weixin.qq.com/s?__biz=MzU4NDE3MTEyMA==&mid=2247486020&idx=2&sn=9ada4b6e7eccecddbd8faa18f14c4eeb&chksm=fd9ca15bcaeb284d727905c174624e32b39b196e2337a2bfc791b22fcce35eb543b552031530&cur_album_id=1715134171561410565&scene=189#wechat_redirect

原题链接：https://leetcode.cn/problems/search-in-rotated-sorted-array/

这是 LeetCode 上的**「33. 搜索旋转排序数组」**，难度为 Medium。
升序排列的整数数组 nums 在预先未知的某个点上进行了旋转
例如， [0,1,2,4,5,6,7] 经旋转后可能变为 [4,5,6,7,0,1,2] 。
请你在数组中搜索 target ，如果数组中存在这个目标值，则返回它的索引，否则返回 -1 。
示例 1：
输入：nums = [4, 5, 6, 7, 0, 1, 2], target = 0
输出：4
示例 2：
输入：nums = [4, 5, 6, 7, 0, 1, 2], target = 3
输出：-1
提示：
1 <= nums.length <= 5000
- <= nums[i] <=
nums 中的每个值都独一无二
nums 肯定会在某个点上旋转
- <= target <=
进阶：你可以设计一个时间复杂度为的解决方案吗？

（1）二分解法

朴素解法很简单，直接遍历数组每一个值就可以。现在使用二分解法来解决

使用二分法找出旋转点。

小技巧：

/ 2 运算可以使用 >>1 来代替
根据题目可以知道，旋转点是左侧，需要注意 mid 的取值和判断的联动关系。
- 例如当只有两个元素时，mid 取得是左边那个数，然后在下面判断需要改变 r 或者 l。根据旋转点在左侧，并且无重复值，可知若只剩两个数，左边的数一定是旋转点，所以需要改变 r ，如代码所示 —— r = mid - 1;

int l = 0;
int r = nums.length - 1;
while (l < r) {
  int mid = (r + l + 1) >> 1;  // mid = (r + l + 1) / 2 【>>1】
  if (nums[mid] >= nums[0]) { // = 的情况是当只有一个元素的时候
    l = mid;
  } else {
    r = mid - 1;    // 不可以改变为 r = mid;
  }
}

判断目标数在左侧还是右侧。

// 2. 判断是否目标数在旋转点的左边和右边
// 此时 l 和 r 都代表旋转点，改变 l 或 r，构造出一个只升序的数列
if (nums[0] > target) { // 代表目标数在旋转点右边
  r = nums.length - 1;
  l = l + 1;  // 旋转点的特殊性，所以不能包括在右边
} else {
  l = 0;  // 旋转点的特殊性，可以包括在左边
}

使用二分法找出目标数

// 在这里找到最接近目标数的位置
while (l < r) {
  int mid = (r + l) / 2;
  if (nums[mid] >= target) {
    r = mid;
  } else {
    l = mid + 1;    // 这里不包括等于中间数的话，就一定要移动
  }
}

return nums[r] == target ? l : -1;

虽然使用了两次二分法，其时间复杂度是 $O(2logn)$ ，但省略常数时间复杂度依然是 $O(logn)$

全部代码如下：

public int search(int[] nums, int target) {
        if (nums.length == 1) return nums[0] == target ? 0 : -1;
        // 1. 找出旋转点
        int l = 0;
        int r = nums.length - 1;
        
        while (l < r) {
            int mid = (r + l + 1) >> 1;  // TODO mid = (r + l + 1) / 2 【>>1】
            if (nums[mid] >= nums[0]) { // = 的情况是当只有一个元素的时候
                l = mid;
            } else {
                r = mid - 1;    // TODO 是否可以改变为 r = mid;
            }
        }

        // 2. 判断是否目标数在旋转点的左边和右边
        // 此时 l 和 r 都代表旋转点，改变 l 或 r，构造出一个只升序的数列
        if (nums[0] > target) { // 代表目标数在旋转点右边
            r = nums.length - 1;
            l = l + 1;  // 旋转点的特殊性，所以不能包括在右边
        } else {
            l = 0;  // 旋转点的特殊性，可以包括在左边
        }

        // 在这里找到最接近目标数的位置
        while (l < r) {
            int mid = (r + l) / 2;
            if (nums[mid] >= target) {
                r = mid;
            } else {
                l = mid + 1;    // 这里不包括等于中间数的话，就一定要移动
            }
        }

        return nums[r] == target ? l : -1;
    }

下面的折现图，可以模拟这种情况

一个折线图案例

const getMacNum = (macAddress) => {
    let resultArray = new Set()

    const lowerCase = macAddress.toLocaleLowerCase()

    const patt1 =
      /(?=([0-9a-f]{2}:[0-9a-f]{2}:[0-9a-f]{2}:[0-9a-f]{2}:[0-9a-f]{2}:[0-9a-f]{2}))/g

    const res1 = [...lowerCase.matchAll(patt1)]

    res1.forEach((item) => {
      let matchStr = item[1]
      resultArray.add(matchStr)
    })

    const patt2 =
      /(?=([0-9a-f]{2}-[0-9a-f]{2}-[0-9a-f]{2}-[0-9a-f]{2}-[0-9a-f]{2}-[0-9a-f]{2}))/g

    const res2 = [...lowerCase.matchAll(patt2)]

    res2.forEach((item) => {
      let matchStr = item[1]
      resultArray.add(matchStr)
    })

    return resultArray.size
  }

  console.log(getMacNum('0a-0a-0a-0a-0a-0a-0A-0b'))

// 1. 保证用户不会多次申请
// 2. 传入的时间绝对正确

// 难点：
// 1. 占用高等级通道，但收的是低等级的费用
// 2. 通道降级

let system = [[], [], []]

let cost = []
/**
 * @description: 初始化系统
 * @param {*} channeks 表示视频类型为i的初始可用通道个数
 * @param {*} charge 表示视频类型为i的单位时间费用
 * @return {*}
 */
const VideoService = function (channeks, charge) {
  system[0] = Array(channeks[0]).fill({})
  system[1] = Array(channeks[1]).fill({})
  system[2] = Array(channeks[2]).fill({})

  cost = charge
}

/**
 * @description: 在某个时刻，某个用户是否可以成功申请使用某个类型的视频服务
 * @param {*} time 某个时刻
 * @param {*} userId 用户Id
 * @param {*} videoType 视频类型
 * @return {*} 返回true为申请成功，返回false为申请失败
 */
const allocateChannel = function (time, userId, videoType) {
  // 在
  let origin = videoType
  while (videoType < 3) {
    let index = system[videoType].findIndex(
      (item) => JSON.stringify(item) === '{}'
    )
    if (index !== -1) {
      system[videoType][index] = { time, userId, videoType: origin }
      return true
    }
    videoType++
  }
  return false
}

/**
 * @description: 在某个时刻，某个用户申请停止在使用的视频服务
 * @param {*} time 某个时刻
 * @param {*} userId 用户Id
 * @return {*} 该次的服务的费用，否则返回-1
 */
const freeChannel = function (time, userId) {
  for (let i = 0; i < system.length; i++) {
    const channel = system[i]
    for (let j = 0; j < channel.length; j++) {
      const obj = channel[j]
      if (obj.userId === userId) {
        let allCost = (time - obj.time) * cost[obj.videoType]
        system[i][j] = {}
        moveChannelObj()
        return allCost
      }
    }
  }
  return -1
}

const moveChannelObj = function () {
  // 移动的话先从超清移动到标清，然后超清移动高清，最后从高清移动到标清
  // 先找到标清里是否为空
  let standardEmptyIndex = system[0].findIndex(
    (item) => JSON.stringify(item) === '{}'
  )

  let highEmptyIndex = system[1].findIndex(
    (item) => JSON.stringify(item) === '{}'
  )

  // 标清有空的，所以移动的终点为标清
  if (standardEmptyIndex !== -1) {
    // 先判断移动的起点是否为超清
    let ultra = system[2]
    for (let index = 0; index < ultra.length; index++) {
      const element = ultra[index]
      // 如果当前的视频类型符合规则，则=往下移
      if (element.videoType === 0) {
        system[0][standardEmptyIndex] = element
        system[2][index] = {}
        return
      }
    }

    // 先判断移动的起点是否为高清
    let high = system[1]
    for (let index = 0; index < high.length; index++) {
      const element = high[index]
      // 如果当前的视频类型符合规则，则=往下移
      if (element.videoType === 0) {
        system[0][standardEmptyIndex] = element
        system[1][index] = {}
        return
      }
    }
  } else if (highEmptyIndex !== -1) {
    // 先判断移动的起点是否为超清
    let ultra = system[2]
    for (let index = 0; index < ultra.length; index++) {
      const element = ultra[index]
      // 如果当前的视频类型符合规则，则=往下移
      if (element.videoType === 1) {
        system[1][highEmptyIndex] = element
        system[2][index] = {}
        return
      }
    }
  }
}

/**
 * @description: 查询某个用户所占用通道的视频类型
 * @param {*} userId 用户Id
 * @return {*} 返回占用通过的视频类型，不存在用户或者服务则返回-1
 */
const queryChannel = function (userId) {
  for (let i = 0; i < system.length; i++) {
    const channel = system[i]
    for (let j = 0; j < channel.length; j++) {
      const obj = channel[j]
      if (obj.userId === userId) {
        return obj.videoType
      }
    }
  }
  return -1
}

// VideoService([8, 1, 1], [10, 15, 30])

// console.log(allocateChannel(3, 107, 1))
// console.log(allocateChannel(3, 108, 1))
// console.log(allocateChannel(5, 110, 1))
// console.log(queryChannel(108))
// console.log(freeChannel(13, 107))
// console.log(system)
VideoService([1, 1, 2], [5, 10, 20])

console.log(allocateChannel(1, 100, 0))
console.log(allocateChannel(1, 101, 0))
console.log(allocateChannel(2, 102, 0))
console.log(allocateChannel(4, 103, 0))
console.log(freeChannel(6, 100))
console.log(queryChannel(102))
console.log(freeChannel(7, 103))
console.log(allocateChannel(7, 104, 1))
console.log(freeChannel(8, 102))
console.log(queryChannel(104))
console.log(system)

const temp = function (sectorSize, opArray) {
  let system = []

  system.push(opArray[0])

  // 合并
  for (let i = 1; i < opArray.length; i++) {
    const opElement = opArray[i]
    const opStart = opElement[0]
    const opEnd = opElement[1]
    let flag = true
    for (let j = 0; j < system.length; j++) {
      const sysElement = system[j]
      let sysStart = sysElement[0]
      let sysEnd = sysElement[1]
      if (opStart <= sysEnd) {
        system[j][0] = Math.min(opStart, sysStart)
        system[j][1] = Math.max(opEnd, sysEnd)
        flag = false
        break
      } 
    }

    if (flag) {
      system.push([opStart, opEnd])
    }


  }

  let zoneResult = []
  // 拆分
  for (let index = 0; index < system.length; index++) {
    const element = system[index]
    const sysStart = element[0]
    const sysEnd = element[1]
    let nextStart = sysStart
    let nextEnd = Math.pow(Math.ceil(Math.sqrt(sysStart)), 2) - 1

    if (nextEnd === 0) {
      nextEnd = sectorSize - 1 
    }
    // 找到最近的平方值

    if (nextEnd > sysEnd) {
      zoneResult.push([sysStart, sysEnd])
      continue
    }

    while (nextEnd < sysEnd) {
      zoneResult.push([nextStart, nextEnd])
      nextStart = nextEnd + 1
      nextEnd += sectorSize
    }

    zoneResult.push([nextStart, sysEnd])
  }
}

temp(32, [[0, 30],[10,33],[130,150],[151,158],[60,100],[130,150],[20,50]])