2560.打家劫舍IV

链接：2560.打家劫舍IV
难度：Medium
标签：数组、二分查找
简介：给你一个下标从 0 开始的字符串数组 words 以及一个二维整数数组 queries 。返回一个整数数组，其中数组的第 i 个元素对应第 i 个查询的答案。

题解 1 - cpp

• 编辑时间：2023-02-05
• 执行用时：136ms
• 内存消耗：55.6MB
• 编程语言：cpp
• 解法介绍：结果二分+dp。

class Solution {
public:
    long long minCost(vector<int>& basket1, vector<int>& basket2) {
        unordered_map<int, int> m;
        for (auto &v : basket1) m[v]++;
        for (auto &v : basket2) m[v]--;
        vector<int> list;
        int nmin = 0x3f3f3f3f;
        for (auto &item : m) {
            if (item.second % 2 != 0) return -1;
            nmin = min(nmin, item.first);
            for (int i = 0; i < abs(item.second) / 2; i++) list.push_back(item.first);
        }
        sort(list.begin(), list.end());
        long long ans = 0;
        for (int i = 0; i < list.size() / 2; i++) ans += min(list[i], nmin * 2);
        return ans;
    }
};

题解 2 - python

• 编辑时间：2023-02-05
• 执行用时：740ms
• 内存消耗：22.9MB
• 编程语言：python
• 解法介绍：同上。

class Solution:
    def minCapability(self, nums: List[int], k: int) -> int:
        def bs(target):
            prev1, prev2 = 0, 0
            for num in nums:
                if num <= target:
                    prev1, prev2 = prev2, max(prev1 + 1, prev2)
                else:
                    prev1 = prev2
            return prev2
        l, r = 1, max(nums)
        while l < r:
            m = (l + r) // 2
            if bs(m) >= k: r = m
            else: l = m + 1
        return l

题解 3 - rust

• 编辑时间：2023-02-05
• 执行用时：16ms
• 内存消耗：4MB
• 编程语言：rust
• 解法介绍：同上。

impl Solution {
    pub fn min_capability(nums: Vec<i32>, k: i32) -> i32 {
        let (mut l, mut r) = (1, 1);
        for num in nums.iter() {
            r = r.max(*num);
        }
        let bs = move |target| {
            let (mut prev1, mut prev2) = (0, 0);
            for num in nums.iter() {
                if *num <= target {
                    let tmp = prev2;
                    prev2 = prev2.max(prev1 + 1);
                    prev1 = tmp;
                } else {
                    prev1 = prev2;
                }
            }
            prev2
        };
        while l < r {
            let m = (l + r) / 2;
            if bs(m) >= k {
                r = m;
            } else {
                l = m + 1
            }
        }
        l
    }
}

题解 4 - python

• 编辑时间：2023-09-19
• 执行用时：520ms
• 内存消耗：27.9MB
• 编程语言：python
• 解法介绍：同上。

class Solution:
    def minCapability(self, nums: List[int], k: int) -> int:
        n = len(nums)
        def check(target: int) -> bool:
            cnt = 0
            prev = -1
            for i in range(n):
                if nums[i] <= target and (prev == -1 or prev + 1 != i):
                    prev = i
                    cnt += 1
            return cnt >= k
        l, r = min(nums), max(nums)
        while l < r:
            m = (l + r) // 2
            if check(m):
                r = m
            else:
                l = m + 1
        return l