OJ刷题总结4——二分

许久尚未更新，我没摆烂，准备保研这段时间着实是有点小忙。。复现论文/oj/408。。

34

给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。

如果数组中不存在目标值 target，返回 [-1, -1]。

你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。

两次二分：

  1. 找target的开始位置，也就是说，左边部分=target，返回r即可
  2. 找target的结束为止，也就是说，左边部分<=target，右边部分>target，返回l即可
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        if (nums.empty())   return {-1, -1};
        int l = -1, r = nums.size();
        vector<int> ans;
        while (l + 1 != r) {
            int mid = l + (r - l) / 2;
            if (nums[mid] >= target)    r = mid;
            else l = mid;
        }
        if (r == nums.size())   return {-1, -1};
        else if(nums[r] == target)   ans.push_back(r);
        else return {-1, -1};
        l = -1, r = nums.size();
        while (l + 1 != r) {
            int mid = l + (r - l) / 2;
            if (nums[mid] < target + 1) l = mid;
            else r = mid;
        }
        ans.push_back(l);
        return ans;
    }
};

2529

给你一个按 非递减顺序 排列的数组 nums ，返回正整数数目和负整数数目中的最大值。

  • 换句话讲，如果 nums 中正整数的数目是 pos ，而负整数的数目是 neg ，返回 pos 和 neg二者中的最大值。

注意：0 既不是正整数也不是负整数。

一个朴素的做法是遍历一遍，统计一下结果。这样的时间复杂度是O(n)

然而，由于题目给的条件是非递减，因此，我们要抓住这个关键点。可以二分，找到0的位置，然后再进行比较，时间复杂度O(logn)

二分的模版，我用的是这里的，强推！不需要背什么边界条件

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int maximumCount(vector<int>& nums) {
        int left = -1, right = nums.size();
        while(left + 1 != right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] < 0) left = mid;
            else right = mid;
        }
        int less0 = 0, more0 = 0;
        less0 = left + 1;
        left = -1, right = nums.size(); 
        while(left + 1 != right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] > 0) right = mid;
            else left = mid;
        }
        more0 = nums.size() - right;
        return max(less0, more0);
    }
};

2300

给你两个正整数数组 spells 和 potions ，长度分别为 n 和 m ，其中 spells[i] 表示第 i 个咒语的能量强度，potions[j] 表示第 j 瓶药水的能量强度。

同时给你一个整数 success 。一个咒语和药水的能量强度 相乘 如果 大于等于 success ，那么它们视为一对 成功 的组合。

请你返回一个长度为 n 的整数数组 pairs，其中 pairs[i] 是能跟第 i 个咒语成功组合的 药水 数目。

每对去二分，时间复杂度O(nlgm)/O(mlgn)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    vector<int> successfulPairs(vector<int>& spells, vector<int>& potions, long long success) {
        vector<int> ans;
        sort(potions.begin(), potions.end());
        for (int i = 0; i < spells.size(); i ++) {
            long long target = 0;
            if (success % spells[i] == 0) target = success / spells[i];
            else target = success / spells[i] + 1;
            int left = -1, right = potions.size();
            while(left + 1 != right) {
                int mid = left + (right - left) / 2;
                if (potions[mid] >= target) right = mid;
                else left = mid;
            }
            ans.push_back(potions.size() - right);
        }
        return ans;
    }
};

2563

给你一个下标从 0 开始、长度为 n 的整数数组 nums ，和两个整数 lower 和 upper ，返回 公平数对的数目 。

如果 (i, j) 数对满足以下情况，则认为它是一个 公平数对 ：

  • 0 <= i < j < n，且
  • lower <= nums[i] + nums[j] <= upper

每对去二分，时间复杂度O(nlgn)

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
class Solution {
public:
    long long countFairPairs(vector<int>& nums, int lower, int upper) {
        long long ans = 0;
        sort(nums.begin(), nums.end());
        int n = nums.size();
        for (int i = 0; i < n; i ++) {
            int left = -1, right = n;
            int temp_lower = lower - nums[i];
            int temp_upper = upper - nums[i];
            int nearupper = 0, nearlower = 0;
            // r 表示第一个 >= lower
            while(left + 1 != right) {
                int mid = left + (right - left) / 2;
                if (nums[mid] >= temp_lower) right = mid;
                else left = mid;
            }
            if (right == n) continue;
            else nearlower = right;
            left = -1, right = n;
            while(left + 1 != right) {
                int mid = left + (right - left) / 2;
                if (nums[mid] <= temp_upper) left = mid;
                else right = mid;
            }
            if (left == -1) continue;
            else nearupper = left;
            if (i >= nearlower && i <= nearupper) ans += nearupper - nearlower;
            else ans += nearupper - nearlower + 1;
        }
        return ans / 2;
    }
};

275

给你一个整数数组 citations ，其中 citations[i] 表示研究者的第 i 篇论文被引用的次数，citations 已经按照 升序排列 。计算并返回该研究者的 h 指数。

h 指数的定义：h 代表“高引用次数”（high citations），一名科研人员的 h 指数是指他（她）的 （n 篇论文中）至少 有 h 篇论文分别被引用了至少 h 次。

请你设计并实现对数时间复杂度的算法解决此问题。

这题最开始，emmmm有点难理解，哥们没发过论文wwww

我们可以这样看待这个问题：可以把citations从高到低排序，如果citations[i] >= i + 1，说明h指数至少为i + 1，那么可以继续往下看；否则没i，往前看

也是个二分的问题，我们要找的左半边是满足 citations[i] >= i + 1，右半边是 citations[i] < i + 1。因此返回L。

在这里，我忽然感悟，二分的本质不是单调性，而是在寻求一个临界点，来分开左右两边。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int hIndex(vector<int>& citations) {
        int n = citations.size();
        int left = -1, right = n;

        reverse(citations.begin(), citations.end());

        while (left + 1 != right) {
            int mid = left + (right - left) / 2;
            if (citations[mid] >= mid + 1) left = mid;
            else right = mid;
        }
        return left + 1;
    }
};

当然了，用reverse肯定就慢了

可以，反着写，只是有点反人类了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int hIndex(vector<int>& citations) {
        int n = citations.size();
        int left = -1, right = n;

        while (left + 1 != right) {
            int mid = left + (right - left) / 2;
            if (citations[mid] >= n - mid) right = mid;
            else left = mid;
        }

        return n - right;
    }
};

875

珂珂喜欢吃香蕉。这里有 n 堆香蕉，第 i 堆中有 piles[i] 根香蕉。警卫已经离开了，将在 h 小时后回来。

珂珂可以决定她吃香蕉的速度 k （单位：根/小时）。每个小时，她将会选择一堆香蕉，从中吃掉 k 根。如果这堆香蕉少于 k 根，她将吃掉这堆的所有香蕉，然后这一小时内不会再吃更多的香蕉。

珂珂喜欢慢慢吃，但仍然想在警卫回来前吃掉所有的香蕉。

返回她可以在 h 小时内吃掉所有香蕉的最小速度 k（k 为整数）。

二分答案

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
class Solution {
public:
    bool check(vector<int>& piles, long long mid, int h) {
        long long sum = 0;
        for (int i = 0; i < piles.size(); i ++) {
            if (piles[i] % mid == 0) sum += piles[i] / mid;
            else sum += piles[i] / mid + 1;
        }
        return sum <= h;
    }
    int minEatingSpeed(vector<int>& piles, int h) {
        long long sum = 0;
        int n = piles.size();
        for (int i = 0; i < n; i ++) {
            sum += piles[i];
        }
        long long left = 0, right = sum + 1;
        while(left + 1 != right) {
            long long mid = left + (right - left) / 2;
            if (check(piles, mid, h)) right = mid;
            else left = mid;
        }
        return right;
    }   
};

2187

给你一个数组 time ，其中 time[i] 表示第 i 辆公交车完成 一趟**旅途** 所需要花费的时间。

每辆公交车可以 连续 完成多趟旅途，也就是说，一辆公交车当前旅途完成后，可以 立马开始 下一趟旅途。每辆公交车 独立 运行，也就是说可以同时有多辆公交车在运行且互不影响。

给你一个整数 totalTrips ，表示所有公交车 总共 需要完成的旅途数目。请你返回完成 至少 totalTrips 趟旅途需要花费的 最少 时间。

二分答案

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:
    bool check(vector<int>& time, long long mid, int totalTrips) {
        int sum = 0;
        for (int i = 0; i < time.size(); i ++) {
            if ((mid / time[i])) {
                sum += mid / time[i];
                if (sum >= totalTrips) return true;
            }
            else break;
        }
        return false;
    }

    long long minimumTime(vector<int>& time, int totalTrips) {
        sort(time.begin(), time.end());
        long long left = time[0] - 1;
        long long right = (long long) time[0] * totalTrips + 1;
        while(left + 1 != right) {
            long long mid = left + (right - left) / 2;
            if (check(time, mid, totalTrips)) right = mid;
            else left = mid;
        }
        return right;
    }
};

2439

给你一个下标从 0 开始的数组 nums ，它含有 n 个非负整数。

每一步操作中，你需要：

  • 选择一个满足 1 <= i < n 的整数 i ，且 nums[i] > 0 。
  • 将 nums[i] 减 1 。
  • 将 nums[i - 1] 加 1 。

你可以对数组执行 任意 次上述操作，请你返回可以得到的 nums 数组中 最大值 最小 为多少。

看到最大值最小化/最小值最大化，就是二分答案！！！！！

二分答案，检查这个答案是否可以

问题是，怎么个检查

现在，假设我们已经二分出一个mid了，检查这个mid是否满足呢？

可以从数组的最后一个开始，看它是否超了mid，超了就减，剩下的让前一个承受，有点像算术的减法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    bool check(vector<int>& nums, int mid) {
        long long extra = 0;
        for (int i = nums.size() - 1; i > 0; i --) {
            if (nums[i] + extra > mid) {
                extra = (long long)nums[i] + extra - mid;
            }
            else extra = 0;
        }
        return nums[0] + extra <= mid;
    }
    int minimizeArrayValue(vector<int>& nums) {
        int left = -1, right = ranges::max(nums) + 1;
        while (left + 1 != right) {
            int mid = left + (right - left) / 2;
            if (check(nums, mid)) right = mid;
            else left = mid;
        }
        return right;
    }
};

2517

给你一个正整数数组 price ，其中 price[i] 表示第 i 类糖果的价格，另给你一个正整数 k 。

商店组合 k 类 不同 糖果打包成礼盒出售。礼盒的 甜蜜度 是礼盒中任意两种糖果 价格 绝对差的最小值。

返回礼盒的 最大 甜蜜度。

同样，看到最大值最小化/最小值最大化，就是二分答案！！！！！

题目着实有点难读懂

我们要求甜蜜度

甜蜜度越小，越能选k类；越大，越难选k类

这就是单调性，二分，找临界点！

[1, 2, 5, 8, 13, 21]

假设说 ans = 7

先选1，选完1之后，下一个要>= 1 + 7，因此选8；选完8之后，下一个要>= 8 + 7，因此选21

所以可以选出k个出来，k<=3

假设说 ans = 9

先选1，选完1之后，下一个要>= 1 + 9，因此选13；选完13之后，下一个要22，寄了

所以，当甜蜜度=9时，最多可以有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
class Solution {
public:
    // 给定 price 和 任意两者的差 mid，求出最多的k
    int check(vector<int>& price, int mid) {
        int ans = 1, pre = price[0];
        for (int p : price) {
            if (p >= pre + mid) {
                ans ++;
                pre = p;
            }
        }
        return ans;
    }
    int maximumTastiness(vector<int>& price, int k) {
        sort(price.begin(), price.end());
        int n = price.size();
        int left = 0, right = (price[n - 1] - price[0]) / (k - 1) + 1;
        while (left + 1 != right) {
            int mid = left + (right - left) / 2;
            if (check(price, mid) >= k) left = mid;
            else right = mid;
        }
        return left;
    }
};

上界的解释，简单来说，就是price的平均值。因为这是一种理想的情况，当k=price.size()时，就是这个情况。正常来说间隔有大有小，会被小的限制。