Giả sử chúng ta có N bóng đèn liên tiếp và chúng được đánh số từ 1 đến N. Lúc đầu, tất cả các bóng đèn đều tắt. Chúng ta có thể bật đúng một bóng đèn mỗi ngày cho đến khi tất cả các bóng đèn đều sáng sau N ngày. Nếu chúng ta có một dãy bóng đèn có chiều dài N trong đó bóng đèn [i] =x, điều này cho thấy rằng vào ngày thứ (i + 1), chúng ta sẽ bật bóng đèn ở vị trí x. Nếu chúng ta có một số nguyên K khác, sao cho số ngày tối thiểu sao cho tồn tại hai bóng đèn đang bật có đúng K bóng đèn giữa chúng đều tắt. Nếu không có ngày như vậy, hãy trả về -1.
Vì vậy, nếu đầu vào giống như bóng đèn:[1,3,2] và K =1, thì đầu ra sẽ là 2 là
-
Vào ngày đầu tiên:bóng đèn [0] =1, bóng đèn đầu tiên được bật:[1,0,0]
-
Vào ngày thứ hai:bóng đèn [1] =3, sau đó bóng đèn thứ ba được bật:[1,0,1]
-
Vào ngày thứ ba:bóng đèn [2] =2, sau đó bóng đèn thứ hai được bật:[1,1,1]
Chúng tôi sẽ trả lại 2 vì vào ngày thứ hai, có hai bóng đèn đang bật và một bóng đèn tắt giữa chúng.
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
-
n:=kích thước của bóng đèn
-
để khởi tạo i:=0, khi i
-
ngày [bóng đèn [i] - 1] =i + 1
-
-
left:=0, right:=k + 1, ret:=inf
-
để khởi tạo i:=0, khi right
-
nếu ngày [i]
-
nếu tôi giống đúng, thì -
-
ret:=tối thiểu là ret và tối đa là ngày [trái] và ngày [phải]
-
-
left:=i
-
phải:=i + k + 1
-
-
-
return (nếu ret giống với inf thì -1, ngược lại là ret)
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
Ví dụ
#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));
} Đầu vào
{1,3,2}, Đầu ra
2