資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究C++ 中的燈泡開關 III
假設我們有一個房間裡有 n 個燈泡，從左到右從 1 到 n 編號排列。最初，所有燈泡都是關著的。在時刻 k（對於 0 到 n - 1 範圍內的 k），我們開啟 light[k] 燈泡。只有當一個燈泡處於開啟狀態，並且其左邊的所有燈泡也都處於開啟狀態時，這個燈泡才變為藍色。我們必須找出所有開啟燈泡都為藍色的時刻的數量。這是一個示例 −
輸出將是 3，因為時刻為 1、2 和 4。
為了解決這個問題，我們將按照以下步驟操作 −
ret := 0，定義一個集合 x、n := 列表陣列的大小、定義一個對映 m
定義基於最大堆的優先佇列 pq
對於 0 到 n - 1 範圍內的 I
m[light[i]] := i，並將 i 插入到 pq 中
對於 1 到 n 範圍內的 I
將 m[i] 插入 x 中
當 pq 不為空，且 pq 的頂部元素在集合 x 中時，
從 pq 中刪除
當 (pq 為空或 pq 的頂部>= i) 時，ret:= ret + 1，否則為 0
返回 res
示例 (C++)
讓我們看看以下實現，以便更好地理解 −
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int numTimesAllBlue(vector<int>& light) {
int ret = 0;
set <int> x;
int n = light.size();
map <int, int> m;
priority_queue <int, vector <int>, greater <int> > pq;
for(int i = 0; i < n; i++){
m[light[i]] = i;
pq.push(i);
}
for(int i = 1; i <=n; i++){
x.insert(m[i]);
while(!pq.empty() && x.count(pq.top()))pq.pop();
ret += (pq.empty() || (pq.top() >= i));
}
return ret;
}
};
main(){
vector<int> v = {2,1,3,5,4};
Solution ob;
cout << (ob.numTimesAllBlue(v));
}輸入
[2,1,3,5,4]
輸出
3
更新於: 2020 年 4 月 29 日
370 次瀏覽
廣告