K ช่องว่างใน C++

สมมุติว่าเรามีหลอดไฟ N เรียงกัน และมีเลขตั้งแต่ 1 ถึง N ในตอนแรก หลอดทั้งหมดจะปิด เราสามารถเปิดหลอดไฟได้หนึ่งหลอดทุกวันจนกว่าหลอดไฟทั้งหมดจะเปิดหลังจาก N วัน ถ้าเรามีหลอดอาร์เรย์ที่มีความยาว N โดยที่ bulbs[i] =x แสดงว่าในวันที่ (i+1) เราจะเปิดหลอดไฟที่ตำแหน่ง x หากเรามีจำนวนเต็ม K อีกจำนวนหนึ่ง โดยให้ระบุจำนวนวันขั้นต่ำซึ่งมีหลอดไฟเปิดอยู่สองหลอดซึ่งมีหลอด K อยู่ระหว่างหลอดที่ปิดทั้งหมด หากไม่มีวันนั้นให้คืน -1

ดังนั้น หากอินพุตเป็นเหมือนหลอดไฟ:[1,3,2] และ K =1 เอาต์พุตจะเป็น 2 เป็น

ในวันแรก:bulbs[0] =1, เปิดหลอดไฟแรก:[1,0,0]
ในวันที่สอง:หลอดไฟ[1] =3 จากนั้นหลอดที่สามก็เปิด:[1,0,1]
ในวันที่สาม:หลอดไฟ[2] =2 จากนั้นหลอดที่สองก็เปิด:[1,1,1]

เราจะคืน 2 อันเพราะในวันที่สองมีหลอดไฟสองดวงโดยมีหนึ่งหลอดอยู่ระหว่างกัน

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

n :=ขนาดของหลอดไฟ
สำหรับการเริ่มต้น i :=0 เมื่อ i
- วัน[bulbs[i] - 1] =i + 1
ซ้าย :=0, ขวา :=k + 1, ret :=inf
สำหรับการเริ่มต้น i :=0 เมื่อถูกต้อง
- ถ้าวัน[i] <วัน[ซ้าย] หรือวัน[i] <=วัน[ขวา] แล้ว −
  - ถ้าฉันเหมือนกันถูกต้องแล้ว −
    - ret :=ขั้นต่ำของ ret และสูงสุดของวัน[ซ้าย] และวัน[ขวา]
  - ซ้าย :=ฉัน
  - ขวา :=i + k + 1
return (ถ้า ret เหมือนกับ inf แล้ว -1 มิฉะนั้น 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},

K ช่องว่างใน C++

ตัวอย่าง

อินพุต

ผลลัพธ์