पायथन का उपयोग करके आकार एम के नवीनतम समूह को खोजने का कार्यक्रम

मान लीजिए कि हमारे पास एक सरणी है, जिसमें 1 से n तक की संख्याओं का क्रमपरिवर्तन है। यदि हमारे पास आकार n की बाइनरी स्ट्रिंग है और शुरुआत में इसके सभी बिट्स शून्य पर सेट हैं। अब प्रत्येक चरण पर i (बाइनरी स्ट्रिंग और एआर दोनों के लिए 1 से अनुक्रमण शुरू होता है) 1 से n तक, स्थिति arr [i] पर बिट 1 पर सेट है। हमारे पास एक और मान m भी है, और हमें नवीनतम खोजने की आवश्यकता है जिस कदम पर m आकार के लोगों का एक समूह मौजूद है। यहाँ इकाई समूह का अर्थ 1s का सन्निहित विकल्प है, जिसे किसी भी दिशा में विस्तारित नहीं किया जा सकता है। हमें उस नवीनतम चरण का पता लगाना है जिस पर ठीक m लंबाई वाले इकाईयों का एक समूह मौजूद हो। अगर हमें ऐसा कोई समूह नहीं मिल रहा है, तो -1 लौटें।

इसलिए, यदि इनपुट arr =[3,5,1,2,4] m =3 जैसा है, तो आउटपुट 4 होगा, क्योंकि प्रारंभिक बाइनरी स्ट्रिंग "00000" है, फिर निम्नलिखित चरणों का पालन करें -

"00100", समूह:["1"]
"00101", समूह:["1", "1"]
"10101", समूह:["1", "1", "1"]
"11101", समूह:["111", "1"]
"11111", समूह:["11111"]

यहां नवीनतम चरण जिस पर आकार 3 का समूह मौजूद है वह चरण 4 है।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

n :=गिरफ्तारी का आकार
संख्या :=0
उत्तर :=-1
l :=आकार n की एक सरणी, और 0 से भरें
r :=आकार n की एक सरणी, और 0 से भरें
मैं के लिए 0 से n -1 की सीमा में, करो
- वक्र:=1
- आईडीएक्स:=गिरफ्तारी [i] - 1
- यदि r[idx], m के समान है, तो
  - अंक :=संख्या - 1
- अगर l[idx] m के समान है, तो
  - अंक :=संख्या - 1
- वक्र:=वक्र + एल[idx] + r[idx]
- num :=num + cur m के समान है
- अगर संख्या> 0, तो
  - उत्तर:=अधिकतम उत्तर, i + 1
- अगर idx - l[idx]> 0, तो
  - r[idx - l[idx] - 1] :=cur
- अगर idx + r[idx]
  - l[idx + r[idx] + 1] :=cur
वापसी उत्तर

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

उदाहरण

def solve(arr, m):
   n = len(arr)
   num = 0
   ans = -1
   l = [0] * n
   r = [0] * n
   for i in range(n):
      cur = 1
      idx = arr[i] - 1
      if r[idx] == m:
         num -= 1
      if l[idx] == m:
         num -= 1
      cur += l[idx] + r[idx]
      num += cur == m
      if num > 0:
         ans = max(ans, i + 1)
      if idx - l[idx] > 0:
         r[idx - l[idx] - 1] = cur
      if idx + r[idx] < n - 1:
         l[idx + r[idx] + 1] = cur
   return ans
arr = [3,5,1,2,4]
m = 3
print(solve(arr, m))

इनपुट

[3,5,1,2,4], 3