मान लीजिए हमारे पास nums नामक संख्याओं की एक सूची है, हमें यह जांचना है कि क्या हर संख्या को निम्नलिखित नियमों में से एक का उपयोग करके समूहीकृत किया जा सकता है: 1. सन्निकट जोड़े (a, a) 2. सन्निकट ट्रिपलेट (a, a, a) 3. सन्निकट ट्रिपलेट (a, a + 1, a + 2)
तो, यदि इनपुट nums = [7, 7, 3, 4, 5] जैसा है, तो आउटपुट True होगा, क्योंकि हम [7, 7] को एक साथ और [3, 4, 5] को एक साथ समूहित कर सकते हैं।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे:
- n := nums का आकार
- dp := आकार n+1 की एक सूची, पहला मान True, अन्य False
- i को 2 से n तक की रेंज में लिए, करें
- यदि i >= 2 और dp[i-2] 0 नहीं है, तो
- यदि nums[i-1], nums[i-2] के समान है, तो dp[i] := True
- यदि i >= 3 और dp[i-3] 0 नहीं है, तो
- यदि (nums[i-1], nums[i-2], nums[i-3]) समान हैं या (nums[i-1], nums[i-2]+1, nums[i-3]+2 समान हैं), तो dp[i] := True
- यदि i >= 2 और dp[i-2] 0 नहीं है, तो
- dp[n] लौटाएं
बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें:
उदाहरण
class Solution:
def solve(self, nums):
n = len(nums)
dp = [True] + [False] * n
for i in range(2, n + 1):
if i >= 2 and dp[i - 2]:
if nums[i - 1] == nums[i - 2]:
dp[i] = True
if i >= 3 and dp[i - 3]:
if (nums[i - 1] == nums[i - 2] == nums[i - 3]) or (nums[i - 1] == nums[i - 2] + 1 == nums[i - 3] + 2):
dp[i] = True
return dp[n]
ob = Solution()
nums = [8, 8, 4, 5, 6]
print(ob.solve(nums))
इनपुट
[8, 8, 4, 5, 6]आउटपुट
True
