数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装学
法学C++中的空槽
假设我们有一排N个灯泡，编号从1到N。一开始，所有灯泡都是关着的。我们每天可以打开 exactly 一个灯泡，直到N天后所有灯泡都打开。如果我们有一个长度为N的数组bulbs，其中bulbs[i] = x表示在第(i+1)天，我们将打开位置x处的灯泡。如果我们还有另一个整数K，使得存在两个打开的灯泡之间 exactly 有K个关着的灯泡，则返回满足此条件的最小天数。如果没有这样的天数，则返回-1。
因此，如果输入类似于bulbs: [1,3,2] 和 K = 1，则输出将为2，因为：
第一天：bulbs[0] = 1，第一个灯泡打开：[1,0,0]
第二天：bulbs[1] = 3，第三个灯泡打开：[1,0,1]
第三天：bulbs[2] = 2，第二个灯泡打开：[1,1,1]
我们将返回2，因为在第二天，有两个打开的灯泡之间有一个关闭的灯泡。
为了解决这个问题，我们将遵循以下步骤：
n := bulbs的长度
for i := 0 to n-1 do −
days[bulbs[i] - 1] = i + 1
left := 0, right := k + 1, ret := inf
for i := 0 to right < n do −
if days[i] < days[left] or days[i] <= days[right], then −
if i == right, then −
ret := min(ret, max(days[left], days[right]))
left := i
right := i + k + 1
return (if ret == inf then -1 else ret)
让我们看看下面的实现来更好地理解：
示例
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int kEmptySlots(vector<int>& bulbs, int k) {
int n = bulbs.size();
vector<int> days(n);
for (int i = 0; i < n; i++) {
days[bulbs[i] - 1] = i + 1;
}
int left = 0;
int right = k + 1;
int ret = INT_MAX;
for (int i = 0; right < n; i++) {
if (days[i] < days[left] || days[i] <= days[right]) {
if (i == right) {
ret = min(ret, max(days[left], days[right]));
}
left = i;
right = i + k + 1;
}
}
return ret == INT_MAX ? -1 : ret;
}
};
main(){
Solution ob;
vector<int> v = {1,3,2};
cout << (ob.kEmptySlots(v, 1));
}输入
{1,3,2},输出
2
更新于：2020年7月11日
279 次查看
广告