मान लीजिए हमारे पास nums नामक संख्याओं की एक सूची है और क्वेरी की एक सूची भी है। जहां प्रत्येक क्वेरी तत्व में [i, j] होता है। तो यह क्वेरी पूछ रहा है कि nums की सबलिस्ट [i, j] (दोनों समावेशी) एक अंकगणितीय अनुक्रम है या नहीं। इसलिए अंत में हमें उन क्वेरी की संख्या ढूंढनी है जो सत्य लौटाती हैं।
इसलिए, यदि इनपुट है nums = [2, 4, 6, 8, 7, 6, 5, 2], queries = [[3, 4], [0, 3], [2, 4]], तो आउटपुट होगा 2, क्योंकि [2, 4, 6, 8] एक अंकगणितीय अनुक्रम है, इसलिए क्वेरी [0, 3] सत्य है। और [8, 7] भी एक अंकगणितीय अनुक्रम है, इसलिए क्वेरी [3, 4] भी सत्य है। लेकिन [6, 8, 7] एक अंकगणितीय अनुक्रम नहीं है, इसलिए [2, 4] सत्य नहीं है।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे:
- यदि
numsखाली है, तो:0लौटाएं
n := numsका आकारdiff :=एक सूची जिसमें तत्व(nums[i + 1] - nums[i])हों प्रत्येकiके लिए 0 सेn - 2तक की रेंज मेंrle :=आकार(n - 1)की एक सूची और 0 से भरेंiके लिए 0 सेn - 2तक की रेंज में, करें:- यदि
i > 0औरdiff[i]diff[i - 1]के समान है, तो:rle[i] := rle[i - 1] + 1
- अन्यथा:
rle[i] := 1
- यदि
ans := 0- प्रत्येक
(i, j)के लिएqueriesमें, करें:- यदि
ijके समान है, तो:ans := ans + 1
- अन्यथा:
ans := ans + (1 यदि rle[j - 1] >= (j - i), अन्यथा 0)
- यदि
ansलौटाएं
उदाहरण
बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें:
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