資料結構
網路
關係資料庫管理系統 (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 次檢視
廣告