Leetcode 刷题笔记——分治

Posted on In Symbols count in article: 3.8k Reading time ≈ 3 mins.
  • 分而治之：基于递归，将一个复杂的问题分解成两个或更多相似的子问题，直到子问题足够简单可以直接解决，最后将子问题的解合并得到原问题的解。
  • 先自顶向下分解，后自底向上合并。
  • 重叠子问题可以通过记忆化进行优化。

169. 多数元素

给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。

将数组一分为二，分别找出左右两段子区间的众数。如果二者相同，显然整段的众数也是该数；如果不相同，则需要遍历整个区间统计二者出现的次数哪个更多。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
    public int majorityElement(int[] nums) {
        return _majorityElement(nums, 0, nums.length - 1);
    }

    private int _majorityElement(int[] nums, int lo, int hi) {
        if (lo == hi) return nums[lo];

        int mid = lo + ((hi - lo) >> 1);
        int leftMaj = _majorityElement(nums, lo, mid);
        int rightMaj = _majorityElement(nums, mid + 1, hi);
        if (leftMaj == rightMaj) return leftMaj;

        int leftCnt = count(nums, leftMaj, lo, hi);
        int rightCnt = count(nums, rightMaj, lo, hi);
        return leftCnt > rightCnt ? leftMaj : rightMaj;
    }

    private int count(int[] nums, int key, int lo, int hi) {
        int cnt = 0;
        for (int i = lo; i <= hi; i++) {
            if (nums[i] == key) cnt++;
        }
        return cnt;
    }
}

932. 漂亮数组

对于某些固定的 N，如果数组 A 是整数 1, 2, ..., N 组成的排列，使得：

对于每个 i < j，都不存在 k 满足 i < k < j 使得 A[k] * 2 = A[i] + A[j]。

那么数组 A 是漂亮数组。

给定 N，返回任意漂亮数组 A（保证存在一个）。

首先给出一个重要的性质：如果某个数组 \([a_1,a_2,\cdots,a_n]\) 是漂亮的，那么对这个数组进行仿射变换，得到的新数组 \([ka_1+b,ka_2+b,\cdots,ka_n+b]\) 也是漂亮的（其中 \(k\neq0\) ）。证明略。

我们将数组分为 left 和 right 两部分，只要能保证左右两段分别是漂亮数组，且不存在 \(A[k]*2=A[i]+A[j]\)（其中 \(A[i],A[j]\) 分别属于 left 和 right），那么整个数组就是一个漂亮数组。我们发现等式右边是个偶数，那么只需要让 left 中都是奇数，right 中都是偶数，就可以满足条件。

因此，我们先求解减小了一半规模的子问题，然后将已经成为漂亮数组的左右两部分分别映射为奇数和偶数，从而得到整个漂亮数组。注意使用记忆化避免相同子问题的重复计算。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    HashMap<Integer, int[]> memo = new HashMap<>();

    public int[] beautifulArray(int N) {
        if (N == 1) return new int[]{1};
        if (memo.containsKey(N)) return memo.get(N);

        int[] arr = new int[N];
        int[] left = beautifulArray((N + 1) / 2);
        int[] right = beautifulArray(N / 2);
        int i = 0;
        for (int e : left) arr[i++] = 2 * e - 1;
        for (int e : right) arr[i++] = 2 * e;
        memo.put(N, arr);
        return arr;
    }
}

218. 天际线问题

城市的天际线是从远处观看该城市中所有建筑物形成的轮廓的外部轮廓。现在，假设您获得了城市风光照片（图A）上显示的所有建筑物的位置和高度，请编写一个程序以输出由这些建筑物形成的天际线（图B）。

每个建筑物的几何信息用三元组 [Li，Ri，Hi] 表示，其中 Li 和 Ri 分别是第 i 座建筑物左右边缘的 x 坐标，Hi 是其高度。可以保证 0 ≤ Li, Ri ≤ INT_MAX, 0 < Hi ≤ INT_MAX 和 Ri - Li > 0。您可以假设所有建筑物都是在绝对平坦且高度为 0 的表面上的完美矩形。

输出是以 [ [x1,y1], [x2, y2], [x3, y3], ... ] 格式的“关键点”（图B中的红点）的列表，它们唯一地定义了天际线。关键点是水平线段的左端点。请注意，最右侧建筑物的最后一个关键点仅用于标记天际线的终点，并始终为零高度。此外，任何两个相邻建筑物之间的地面都应被视为天际线轮廓的一部分。

由于输入是按 Li 升序排序的，我们可以递归地将建筑物按 Li 分为两部分，分别求出左右两段独立的天际线，然后设法将其合并成一条。当划分到只有一座建筑物的时候，返回 [[Li, Hi], [Ri, 0]] 即可。

合并的过程类似于归并排序，我们用两个指针分别指向左右两段当前的点，将 x 坐标更小的先加入结果列表。而对于 y 坐标，还应考虑另一段中最后一个进入结果列表的点的高度，取其与自身高度之间的最大值。此外，在加入结果列表之前，要先与列表最后一个点的高度作比较，如果高度相同，则说明在一条水平线上，应舍弃后一个点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
class Solution {	// 这题用C++写能简洁很多，用Java写太反人类了
public:
    vector<vector<int>> getSkyline(vector<vector<int>> &buildings) {
        if (buildings.size() == 0) return {};
        return getSubSkyline(buildings, 0, buildings.size() - 1);
    }

    vector<vector<int>> getSubSkyline(vector<vector<int>> &buildings, int lo, int hi) {
        if (lo == hi) {
            return {{buildings[lo][0], buildings[lo][2]}, 
                    {buildings[lo][1], 0}};
        }

        int mid = lo + ((hi - lo) >> 1);
        vector<vector<int>> left = getSubSkyline(buildings, lo, mid);
        vector<vector<int>> right = getSubSkyline(buildings, mid + 1, hi);

        int lh_prev = 0, rh_prev = 0;
        int i = 0, j = 0;
        vector<int> temp;
        vector<vector<int>> res;
        while (i < left.size() && j < right.size()) {
            if (left[i][0] < right[j][0]) {
                temp = {left[i][0], max(left[i][1], rh_prev)};
                lh_prev = left[i++][1];
            } else if (left[i][0] > right[j][0]) {
                temp = {right[j][0], max(right[j][1], lh_prev)};
                rh_prev = right[j++][1];
            } else {
                temp = {left[i][0], max(left[i][1], right[j][1])};
                lh_prev = left[i++][1];
                rh_prev = right[j++][1];
            }
            if (res.size() == 0 || res[res.size()-1][1] != temp[1]) {
                res.push_back(temp);
            }
        }
        while (i < left.size()) res.push_back(left[i++]);
        while (j < right.size()) res.push_back(right[j++]);
        return res;
    }
};