Skip to content

Latest commit

 

History

History
302 lines (246 loc) · 7.84 KB

README.md

File metadata and controls

302 lines (246 loc) · 7.84 KB
Raw
comments difficulty edit_url tags
true
中等
贪心
字符串
排序

3119. 最大数量的可修复坑洼 🔒

English Version

题目描述

给定一个字符串 road，只包含字符 "x" 和 "."，其中每个 "x" 代表一个坑洼，每个 "." 代表一个平滑的道路，以及一个整数 budget。

在一次修复操作中，您可以以 n + 1 的价格修复 n 个连续坑洼。

返回可以修复的坑洼的 最大 数量，以便所有修复的价格总和 不会超过 给定的预算 budget。

示例 1:

输入: road = "..", budget = 5

输出: 0

解释:

没有坑洼需要修复。

示例 2:

输入: road = "..xxxxx", budget = 4

输出: 3

解释:

我们修复了前三个坑洼（它们是连续的）。任务所需的预算为 3 + 1 = 4。

示例 3:

输入: road = "x.x.xxx...x", budget = 14

输出: 6

解释:

我们可以修复所有的坑洼。总花费为 (1 + 1) + (1 + 1) + (3 + 1) + (1 + 1) = 10 在我们的预算 14 之内。

 

提示：

  • 1 <= road.length <= 105
  • 1 <= budget <= 105 + 1
  • road 只包含字符 '.' 和 'x'。

解法

方法一：计数 + 贪心

我们首先统计出每个连续的坑洼的数量，记录在数组 $cnt$ 中，即 $cnt[k]$ 表示有 $cnt[k]$ 个长度为 $k$ 的连续坑洼。

由于我们要尽可能多地修补坑洼，而对于长度为 $k$ 的连续坑洼，我们需要花费 $k + 1$ 的代价，应该优先修补长度较长的坑洼，这样可以使得代价最小。

因此，我们从最长的坑洼开始修补，对于长度为 $k$ 的坑洼，我们最多可以修补的个数为 $t = \min(\text{budget} / (k + 1), \text{cnt}[k])$，我们将修补的个数乘以长度 $k$ 加到答案中，然后更新剩余的预算。对于长度为 $k$ 的其余 $cnt[k] - t$ 个坑洼，我们将它们合并到长度为 $k - 1$ 的坑洼中。继续这个过程，直到遍历完所有的坑洼。

时间复杂度 $O(n)$，空间复杂度 $O(n)$。其中 $n$ 为字符串 $road$ 的长度。

Python3

class Solution:
    def maxPotholes(self, road: str, budget: int) -> int:
        road += "."
        n = len(road)
        cnt = [0] * n
        k = 0
        for c in road:
            if c == "x":
                k += 1
            elif k:
                cnt[k] += 1
                k = 0
        ans = 0
        for k in range(n - 1, 0, -1):
            if cnt[k] == 0:
                continue
            t = min(budget // (k + 1), cnt[k])
            ans += t * k
            budget -= t * (k + 1)
            if budget == 0:
                break
            cnt[k - 1] += cnt[k] - t
        return ans

Java

class Solution {
    public int maxPotholes(String road, int budget) {
        road += ".";
        int n = road.length();
        int[] cnt = new int[n];
        int k = 0;
        for (char c : road.toCharArray()) {
            if (c == 'x') {
                ++k;
            } else if (k > 0) {
                ++cnt[k];
                k = 0;
            }
        }
        int ans = 0;
        for (k = n - 1; k > 0 && budget > 0; --k) {
            int t = Math.min(budget / (k + 1), cnt[k]);
            ans += t * k;
            budget -= t * (k + 1);
            cnt[k - 1] += cnt[k] - t;
        }
        return ans;
    }
}

C++

class Solution {
public:
    int maxPotholes(string road, int budget) {
        road.push_back('.');
        int n = road.size();
        vector<int> cnt(n);
        int k = 0;
        for (char& c : road) {
            if (c == 'x') {
                ++k;
            } else if (k) {
                ++cnt[k];
                k = 0;
            }
        }
        int ans = 0;
        for (k = n - 1; k && budget; --k) {
            int t = min(budget / (k + 1), cnt[k]);
            ans += t * k;
            budget -= t * (k + 1);
            cnt[k - 1] += cnt[k] - t;
        }
        return ans;
    }
};

Go

func maxPotholes(road string, budget int) (ans int) {
	road += "."
	n := len(road)
	cnt := make([]int, n)
	k := 0
	for _, c := range road {
		if c == 'x' {
			k++
		} else if k > 0 {
			cnt[k]++
			k = 0
		}
	}
	for k = n - 1; k > 0 && budget > 0; k-- {
		t := min(budget/(k+1), cnt[k])
		ans += t * k
		budget -= t * (k + 1)
		cnt[k-1] += cnt[k] - t
	}
	return
}

TypeScript

function maxPotholes(road: string, budget: number): number {
    road += '.';
    const n = road.length;
    const cnt: number[] = Array(n).fill(0);
    let k = 0;
    for (const c of road) {
        if (c === 'x') {
            ++k;
        } else if (k) {
            ++cnt[k];
            k = 0;
        }
    }
    let ans = 0;
    for (k = n - 1; k && budget; --k) {
        const t = Math.min(Math.floor(budget / (k + 1)), cnt[k]);
        ans += t * k;
        budget -= t * (k + 1);
        cnt[k - 1] += cnt[k] - t;
    }
    return ans;
}

Rust

impl Solution {
    pub fn max_potholes(road: String, budget: i32) -> i32 {
        let mut cs: Vec<char> = road.chars().collect();
        cs.push('.');
        let n = cs.len();
        let mut cnt: Vec<i32> = vec![0; n];
        let mut k = 0;

        for c in cs.iter() {
            if *c == 'x' {
                k += 1;
            } else if k > 0 {
                cnt[k] += 1;
                k = 0;
            }
        }

        let mut ans = 0;
        let mut budget = budget;

        for k in (1..n).rev() {
            if budget == 0 {
                break;
            }
            let t = std::cmp::min(budget / ((k as i32) + 1), cnt[k]);
            ans += t * (k as i32);
            budget -= t * ((k as i32) + 1);
            cnt[k - 1] += cnt[k] - t;
        }

        ans
    }
}

C#

public class Solution {
    public int MaxPotholes(string road, int budget) {
        road += '.';
        int n = road.Length;
        int[] cnt = new int[n];
        int k = 0;
        foreach (char c in road) {
            if (c == 'x') {
                ++k;
            } else if (k > 0) {
                ++cnt[k];
                k = 0;
            }
        }
        int ans = 0;
        for (k = n - 1; k > 0 && budget > 0; --k) {
            int t = Math.Min(budget / (k + 1), cnt[k]);
            ans += t * k;
            budget -= t * (k + 1);
            cnt[k - 1] += cnt[k] - t;
        }
        return ans;
    }
}