【Double Week】No.22

C_01 两个数组间的距离值

Given two integer arrays arr1 and arr2, and the integer d, return the distance value between the two arrays.

The distance value is defined as the number of elements arr1[i] such that there is not any element arr2[j] where |arr1[i]-arr2[j]| <= d.

方法一：枚举

* 一定要细心：返回的是符合条件的 arr1 中的元素个数。

public int findTheDistanceValue(int[] arr1, int[] arr2, int d) {
  int count = 0;
  boolean flag = true;
  for (int i = 0; i < arr1.length; i++) {
    int t = 0;
    for (int j = 0; j < arr2.length; j++) {
      if (Math.abs(arr1[i]-arr2[j]) > d) {
        t++;
      }
    }
    if (t == arr2.length)
      count++;
  }
  return count;
}

复杂度分析

• 时间复杂度：$O(n × m)$O(n×m)，
• 空间复杂度：$O()$O()，

---

B_02 安排电影院座位

如上图所示，电影院的观影厅中有 n 行座位，行编号从 1 到 n ，且每一行内总共有 10 个座位，列编号从 1 到 10 。

给你数组 reservedSeats ，包含所有已经被预约了的座位。比如说，researvedSeats[i]=[3,8] ，它表示第 3 行第 8 个座位被预约了。

请你返回 最多能安排多少个 4 人家庭 。4 人家庭要占据 同一行内连续 的 4 个座位。隔着过道的座位（比方说 [3,3] 和 [3,4]）不是连续的座位，但是如果你可以将 4 人家庭拆成过道两边各坐 2 人，这样子是允许的。

输入：n = 3, reservedSeats = [[1,2],[1,3],[1,8],[2,6],[3,1],[3,10]]
输出：4
解释：上图所示是最优的安排方案，总共可以安排 4 个家庭。蓝色的叉表示被预约的座位，橙色的连续座位表示一个 4 人家庭。

方法一：贪心

思路

• 求在 n 行，每行只有 10 个座位的影院中最多能安排 4 人连续座位的个数，每一行最多安排 2 个，最多能安排 2n 个连续座位，每一行能坐下 4 人家庭的位置只有 3 种情况，分别是：
  • 2-5 的位置没有预约。
  • 4-7 的位置没有预约。
  • 6-9 的位置没有预约。

这样一来，感觉清晰多了，其实我们只要从每一行中计算出被预约的座位在哪即可，比如：初始状态我们默认位置没有被占据，即 unable = 2：

先检查两侧：

• 2~5 位置如果有预约，unable--
• 6~9 如果有预约，unable--

后检查中间：

• 如果 unable > 0，这表示有满足的条件的 4 人家庭座位。
• 如果 unable = 0，则需要对 4~7 的位置进行一次特判。为什么？
  • 被预约的位置可能处于 2~3 或 8~9，但这些位置不影响安排 4~7 的 4 人连续家庭。

算法

• map 存储位置全部行的预约信息，其中 key 为行数，val 为一行中的预约信息。
  • computeIfAbsent 是 java8 的新语法。
• 按照上面分析的思路对 map 中的每一行，即检查 map 中每一个 set。

public int maxNumberOfFamilies(int n, int[][] rss) {
    int total = 2 * n;
    if (rss.length == 0 || rss == null)
        return total;
    Map<Integer, Set<Integer>> map = new HashMap<>();
    for (int[] rs : rss) {
        Set<Integer> set = map.computeIfAbsent(rs[0], k -> new HashSet<>());
        set.add(rs[1]);
    }
    for (Map.Entry<Integer, Set<Integer>> pair : map.entrySet()) {
        Set<Integer> set = pair.getValue();
        int enable = 2;

        for (int i = 2; i <= 5; i++) {
            if (set.contains(i)) {
                enable--;
                break;
            }
        }
        for (int i = 6; i <= 9; i++) {
            if (set.contains(i)) {
                enable--;
                break;
            }
        }
        if (enable == 0) {
            for (int i = 4; i <= 7; i++) {
                enable = 1;     //假设还有一个位置
                if (set.contains(i)) {
                    enable--;
                    break;
                }
            }
        }
        if (enable == 0)
            total -= 2;
        if (enable == 1)
            total -= 1;
    }
    return total;
}

复杂度分析

• 时间复杂度：$O(n × 10)$O(n×10)，
• 空间复杂度：$O(n × 10)$O(n×10)，

---

B_03 将整数按权重排序

我们将整数 x 的 权重 定义为按照下述规则将 x 变成 1 所需要的步数：

• 如果 x 是偶数，那么 x = x / 2
• 如果 x 是奇数，那么 x = 3 * x + 1

比方说，x=3 的权重为 7 。因为 3 需要 7 步变成 1 （3 --> 10 --> 5 --> 16 --> 8 --> 4 --> 2 --> 1）。

给你三个整数 lo， hi 和 k 。你的任务是将区间 [lo, hi] 之间的整数按照它们的权重 升序排序 ，如果大于等于 2 个整数有 相同 的权重，那么按照数字自身的数值 升序排序 。

请你返回区间 [lo, hi] 之间的整数按权重排序后的第 k 个数。

注意，题目保证对于任意整数 x （lo <= x <= hi） ，它变成 1 所需要的步数是一个 32 位有符号整数。

输入：lo = 12, hi = 15, k = 2
输出：13
解释：12 的权重为 9（12 --> 6 --> 3 --> 10 --> 5 --> 16 --> 8 --> 4 --> 2 --> 1）
13 的权重为 9
14 的权重为 17
15 的权重为 17
区间内的数按权重排序以后的结果为 [12,13,14,15] 。对于 k = 2 ，答案是第二个整数也就是 13 。
注意，12 和 13 有相同的权重，所以我们按照它们本身升序排序。14 和 15 同理。

方法一：排序 | 堆

按照规则排序即可。

public int getKth(int lo, int hi, int k) {
  PriorityQueue<Integer> pQ = new PriorityQueue<>(new Comparator<Integer>() {
    @Override
    public int compare(Integer o1, Integer o2) {
      int step1 = needStep(o1);
      int step2 = needStep(o2);
      if (step1 == step2) {
        return o1 - o2;
      }
      return step1 - step2;
    }
  });

  for (int i = lo; i <= hi; i++) {
    pQ.add(i);
  }
  for (int i = 0; i < k-1; i++) {
    pQ.poll();
  }
  return pQ.peek();
}

/**
 * 如果 x 是偶数，那么 x = x / 2
 * 如果 x 是奇数，那么 x = 3 * x + 1
 */
private int needStep(int x) {
  int step = 0;
  while (x != 1) {
    if ((x & 1) == 0)
      x >>>= 1;
    else
      x = 3 * x + 1;
    step++;
  }
  return step;
}

复杂度分析

• 时间复杂度：$O(nlogn)$O(nlogn)，
• 空间复杂度：$O(n)$O(n)，

---

A_04 3n 块披萨（不会做）

给你一个披萨，它由 3n 块不同大小的部分组成，现在你和你的朋友们需要按照如下规则来分披萨：

你挑选 任意 一块披萨。

• Alice 将会挑选你所选择的披萨逆时针方向的下一块披萨。
• Bob 将会挑选你所选择的披萨顺时针方向的下一块披萨。
• 重复上述过程直到没有披萨剩下。

每一块披萨的大小按顺时针方向由循环数组 slices 表示。

请你返回你可以获得的披萨大小总和的最大值。

输入：slices = [1,2,3,4,5,6]
输出：10
解释：选择大小为 4 的披萨，Alice 和 Bob 分别挑选大小为 3 和 5 的披萨。
然后你选择大小为 6 的披萨，Alice 和 Bob 分别挑选大小为 2 和 1 的披萨。
你获得的披萨总大小为 4 + 6 = 10 。

方法一：

听说是 dp 来的，而且是打家劫舍升级版，有空瞧瞧。

复杂度分析

• 时间复杂度：$O()$O()，
• 空间复杂度：$O()$O()，

---