मान लीजिए हमारे पास संख्याओं की एक सूची है जिसे अंक कहा जाता है और प्रश्नों की सूची भी है। जहां प्रत्येक क्वेरी तत्व में [i, j] होता है। तो यह प्रश्न पूछ रहा है कि [i, j] (दोनों समावेशी) से अंकों की सबलिस्ट अंकगणितीय अनुक्रम है या नहीं। तो अंत में हमें उन प्रश्नों की संख्या का पता लगाना होगा जो सत्य लौटते हैं।
इसलिए, यदि इनपुट अंकों की तरह है =[2, 4, 6, 8, 7, 6, 5, 2] प्रश्न =[[3, 4], [0, 3], [2, 4]], तो आउटपुट 2 होगा, क्योंकि [2, 4, 6, 8] एक अंकगणितीय अनुक्रम है, इसलिए क्वेरी [0, 3] सत्य है। और [8, 7] के लिए भी एक अंकगणितीय अनुक्रम है, इसलिए क्वेरी [3, 4] भी सत्य है। लेकिन [6, 8, 7] एक अंकगणितीय अनुक्रम नहीं है, इसलिए [2, 4] सत्य नहीं है।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
- यदि अंक खाली हैं, तो
- वापसी 0
- n :=अंकों का आकार
- diff :=तत्वों के साथ एक सूची (nums[i + 1] - nums[i]) प्रत्येक i के लिए 0 से n - 2 तक
- rle :=आकार की एक सूची (n - 1) और 0 से भरें
- मैं के लिए 0 से n - 2 की सीमा में, करते हैं
- अगर i> 0 और diff[i], diff[i - 1] के समान है, तो
- rle[i] :=rle[i - 1] + 1
- अन्यथा,
- rle[i] :=1
- अगर i> 0 और diff[i], diff[i - 1] के समान है, तो
- उत्तर:=0
- प्रश्नों में प्रत्येक (i, j) के लिए, करें
- यदि i, j के समान है, तो
- उत्तर:=उत्तर + 1
- अन्यथा,
- उत्तर:=उत्तर + (1 यदि rle[j - 1]>=(j - i), अन्यथा 0)
- यदि i, j के समान है, तो
- वापसी उत्तर
उदाहरण
आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -
def solve(nums, queries): if not nums: return 0 n = len(nums) diff = [nums[i + 1] - nums[i] for i in range(n - 1)] rle = [0] * (n - 1) for i in range(n - 1): if i > 0 and diff[i] == diff[i - 1]: rle[i] = rle[i - 1] + 1 else: rle[i] = 1 ans = 0 for i, j in queries: if i == j: ans += 1 else: ans += rle[j - 1] >= (j - i) return ans nums = [2, 4, 6, 8, 7, 6, 5, 2] queries = [[3, 4],[0, 3],[2, 4]] print(solve(nums, queries))
इनपुट
[2, 4, 6, 8, 7, 6, 5, 2], [[3, 4],[0, 3],[2, 4]]
आउटपुट
2