House Robber: लेना या छोड़ना पुनरावृत्ति
लूटने या छोड़ने के निर्णय को DP पुनरावृत्ति के रूप में मॉडल कीजिए, स्थान को दो चरों तक घटाइए और समाधान को वृत्ताकार घरों तक बढ़ाइए।
House Robber: लेना या छोड़ना पुनरावृत्ति, CoddyKit पर कोडिंग साक्षात्कार की तैयारी का एक निःशुल्क पाठ है। यह 4 में से 1वाँ पाठ है। आप नीचे पूरा पाठ निःशुल्क पढ़ सकते हैं—फिर अंतर्निहित कोड संपादक और 24/7 एआई ट्यूटर के साथ ब्राउज़र में इसका व्यावहारिक अभ्यास कर सकते हैं। यह कोडिंग साक्षात्कार की तैयारी सीखने के मार्ग का हिस्सा है और आपकी प्रगति वेब तथा CoddyKit ऐप पर सिंक होती रहती है। कोडिंग साक्षात्कार की तैयारी पाठ्यक्रम में कुल 4 पाठ शामिल हैं।
घर-लूट की समस्या
घर-लूट समस्या में पूछा जाता है: गैर-ऋणात्मक पूर्णांकों की एक सरणी दी गई है, जिसमें प्रत्येक घर में धनराशि दर्शाई गई है; दो आसन्न घरों में चोरी किए बिना अधिकतम कितनी राशि चुराई जा सकती है? उदाहरण के लिए, [2, 7, 9, 3, 1] से 12 प्राप्त होता है (घर 0, 2 और 4 में चोरी करके)। यह एक पारंपरिक 1D DP समस्या है, जिसमें प्रत्येक चरण पर द्विआधारी निर्णय लिया जाता है।
nums = [2, 7, 9, 3, 1]
# Can't rob adjacent houses
# Options: rob index 0 and 2 and 4 → 2+9+1=12
# or rob index 1 and 3 → 7+3=10
print('Max profit:', 12) # answer is 12पुनरावृत्ति संबंध को परिभाषित करना
dp[i] को पहले i+1 घरों से चुराई जा सकने वाली अधिकतम राशि मानिए। प्रत्येक घर i पर आपके पास दो विकल्प होते हैं: उसे छोड़ देना (dp[i-1] लेना) या उसमें चोरी करना (nums[i] + dp[i-2] लेना)। पुनरावृत्ति संबंध है dp[i] = max(dp[i-1], nums[i] + dp[i-2])। यह मूलभूत लेना-या-छोड़ना प्रतिरूप है, जो कई DP समस्याओं में दिखाई देता है।
# Recurrence: dp[i] = max(dp[i-1], nums[i] + dp[i-2])
# Base cases:
# dp[0] = nums[0] (only one house, rob it)
# dp[1] = max(nums[0], nums[1]) (take the richer of the two)
def rob(nums):
n = len(nums)
if n == 1: return nums[0]
dp = [0] * n
dp[0] = nums[0]
dp[1] = max(nums[0], nums[1])
for i in range(2, n):
dp[i] = max(dp[i-1], nums[i] + dp[i-2])
return dp[-1]
print(rob([2, 7, 9, 3, 1])) # 12DP सारणी का क्रम से अनुशीलन
[2, 7, 9, 3, 1] के लिए आइए सारणी का क्रम से अनुशीलन करें: dp[0] = 2, dp[1] = max(2, 7) = 7, dp[2] = max(7, 9+2) = 11, dp[3] = max(11, 3+7) = 11, dp[4] = max(11, 1+11) = 12। अंतिम उत्तर dp[4] = 12 है। सारणी का हाथ से अनुशीलन करने पर पुष्टि होती है कि पुनरावृत्ति संबंध प्रत्येक स्थान पर लेने और छोड़ने, दोनों को सही ढंग से संभालता है।
nums = [2, 7, 9, 3, 1]
dp = [0] * len(nums)
dp[0] = 2
dp[1] = max(2, 7) # 7
for i in range(2, len(nums)):
skip = dp[i-1]
take = nums[i] + dp[i-2]
dp[i] = max(skip, take)
print(f'dp[{i}] = max({skip}, {nums[i]}+{dp[i-2]}) = {dp[i]}')
print('Answer:', dp[-1])स्थान को O(1) तक घटाना
DP सारणी केवल दो स्थान पीछे तक देखती है, इसलिए पूरी सरणी को दो चरों से बदला जा सकता है: prev2 (दो चरण पीछे) और prev1 (एक चरण पीछे)। प्रत्येक पुनरावृत्ति के बाद इन्हें खिसकाइए: prev2 = prev1 और prev1 = current। इससे समय जटिलता O(n) बनाए रखते हुए स्मृति O(n) से O(1) हो जाती है।
def rob_optimised(nums):
if not nums: return 0
if len(nums) == 1: return nums[0]
prev2 = nums[0]
prev1 = max(nums[0], nums[1])
for i in range(2, len(nums)):
curr = max(prev1, nums[i] + prev2)
prev2 = prev1
prev1 = curr
return prev1
print(rob_optimised([2, 7, 9, 3, 1])) # 12
print(rob_optimised([1, 2, 3, 1])) # 4संभालने योग्य सीमांत मामले
अपना समाधान हमेशा सीमांत मामलों पर जाँचिए: खाली सरणी (0 लौटाएँ), एक-तत्व वाली सरणी (वही तत्व लौटाएँ), और दो-तत्व वाली सरणी (दोनों में से बड़ा लौटाएँ)। साक्षात्कार में इन मामलों का उल्लेख करना और उन्हें संभालना आपकी पूर्णता दर्शाता है। if n == 1 सुरक्षा-जाँच, dp[1] के लिए nums[1] तक पहुँचते समय अनुक्रमणिका-सीमा से बाहर जाने से रोकती है।
def rob(nums):
if not nums: return 0
if len(nums) == 1: return nums[0]
prev2 = nums[0]
prev1 = max(nums[0], nums[1])
for i in range(2, len(nums)):
curr = max(prev1, nums[i] + prev2)
prev2, prev1 = prev1, curr
return prev1
print(rob([])) # 0
print(rob([5])) # 5
print(rob([3, 10])) # 10
print(rob([10, 3])) # 10घर-लूट II: वृत्ताकार घर
वृत्ताकार रूपांतर (LeetCode 213) में घरों को एक वृत्त में रखा जाता है, जिससे पहला और अंतिम घर आसन्न हो जाते हैं। आप रैखिक पुनरावृत्ति संबंध को सीधे लागू नहीं कर सकते। मुख्य विचार यह है: या तो आप पहले घर में चोरी करें और अंतिम को छोड़ दें, या पहले को छोड़ दें और अंतिम को शामिल करें। दोनों उप-सरणियों पर रैखिक घर-लूट समाधान चलाइए और अधिकतम मान चुनिए।
def rob_linear(nums):
prev2, prev1 = 0, 0
for n in nums:
prev2, prev1 = prev1, max(prev1, n + prev2)
return prev1
def rob_circular(nums):
if len(nums) == 1: return nums[0]
# Either include first (exclude last) or include last (exclude first)
return max(rob_linear(nums[:-1]), rob_linear(nums[1:]))
print(rob_circular([2, 3, 2])) # 3
print(rob_circular([1, 2, 3, 1])) # 4यहाँ लालची विधि क्यों विफल होती है
एक सरल लालची तरीका हमेशा उपलब्ध सबसे बड़े घर में चोरी करने का प्रयास कर सकता है। हालाँकि, यह [2, 1, 1, 2] जैसे इनपुट पर विफल होता है: लालची विधि घर 0 (मान 2), फिर घर 3 (मान 2) चुनती है और कुल 4 प्राप्त करती है, लेकिन घर 0 और 2 में चोरी करने पर भी 3 ही मिलते हैं। रुकिए — इस मामले में लालची विधि काम करती है! लेकिन [1, 3, 1, 3, 100] आज़माइए: लालची विधि 3 और 3 (अनुक्रमणिकाएँ 1 और 3) चुनकर 6 प्राप्त करती है और सर्वोत्तम 1+1+100=102 से चूक जाती है। DP आवश्यक है, क्योंकि स्थानीय रूप से सर्वोत्तम चुनाव वैश्विक सर्वोत्तम परिणाम की गारंटी नहीं देते।
# Greedy failure example
nums = [1, 3, 1, 3, 100]
# Greedy: pick max each step
# picks 3 (index 1), then 3 (index 3) → total 6
# DP optimal: pick 1 (index 0) + 1 (index 2) + 100 (index 4) → 102
def rob(nums):
prev2, prev1 = 0, 0
for n in nums:
prev2, prev1 = prev1, max(prev1, n + prev2)
return prev1
print(rob(nums)) # 102लेना-या-छोड़ना प्रतिरूप को पहचानना
लेना-या-छोड़ना प्रतिरूप का उपयोग घर-लूट से आगे भी होता है। जब भी आप किसी सरणी पर चलते हुए प्रत्येक स्थान पर वर्तमान तत्व को शामिल करने (और पिछले तत्व को छोड़ने) या उसे छोड़ने (और पिछला परिणाम बनाए रखने) में से कोई एक विकल्प चुनते हैं, तो आपके पास लेना-या-छोड़ना DP होता है। दो आसन्न तत्व नहीं या अतिव्यापी अंतराल नहीं जैसी शर्तों को इस प्रतिरूप को लागू करने के संकेतों के रूप में देखिए।
# General take-or-skip template
def take_or_skip(values, gap=1):
'''Max sum where selected elements must be at least gap+1 apart.'''
n = len(values)
if n == 0: return 0
# dp[i] = best up to index i
dp = [0] * (n + gap)
for i in range(n):
take = values[i] + (dp[i - 1] if i >= 1 else 0)
skip = dp[i + gap - 1] if i + gap - 1 < len(dp) else 0
dp[i + gap] = max(skip, take)
return dp[-1]
print(take_or_skip([2, 7, 9, 3, 1])) # house robber-likeहटाएँ और कमाएँ रूपांतर
हटाएँ और कमाएँ (LeetCode 740) में पूछा जाता है: आपके द्वारा चुनी गई प्रत्येक संख्या के लिए आपको num × count(num) मिलता है, लेकिन आपको num-1 और num+1 की सभी आवृत्तियाँ हटानी पड़ती हैं। यह सीधे घर-लूट समस्या में बदल जाता है: सभी मानों के लिए earn[v] = v × count(v) वाली सरणी बनाइए, फिर इस सरणी पर घर-लूट चलाइए। समस्याओं को सरल रूप में बदलना साक्षात्कार का एक महत्वपूर्ण कौशल है।
from collections import Counter
def delete_and_earn(nums):
if not nums: return 0
count = Counter(nums)
max_val = max(nums)
# earn[v] = total points from taking all v's
earn = [v * count[v] for v in range(max_val + 1)]
# Now run house robber on earn
prev2, prev1 = 0, 0
for e in earn:
prev2, prev1 = prev1, max(prev1, e + prev2)
return prev1
print(delete_and_earn([3, 4, 2])) # 6 (take 3+3=no, take 4+2=6)
print(delete_and_earn([2, 2, 3, 3, 3, 4])) # 9 (take all 3s)घर-लूट III: द्विआधारी वृक्ष
घर-लूट III में घरों को द्विआधारी वृक्ष के रूप में व्यवस्थित किया जाता है। आप किसी नोड और उसके प्रत्यक्ष जनक, दोनों में एक साथ चोरी नहीं कर सकते। एक सहायक परिभाषित कीजिए, जो दो मान लौटाए: rob(node) → (rob_root, skip_root)। यदि आप मूल में चोरी करते हैं, तो दोनों बच्चों के छोड़ने वाले मानों का योग लीजिए। यदि आप मूल को छोड़ते हैं, तो प्रत्येक बच्चे के सर्वोत्तम मान का योग लीजिए। यह पश्च-क्रम DFS है, जिसमें प्रत्येक नोड पर लेना-या-छोड़ना निर्णय लिया जाता है।
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def rob_tree(root):
def dfs(node):
if not node: return (0, 0) # (rob, skip)
l_rob, l_skip = dfs(node.left)
r_rob, r_skip = dfs(node.right)
rob = node.val + l_skip + r_skip
skip = max(l_rob, l_skip) + max(r_rob, r_skip)
return (rob, skip)
return max(dfs(root))
# Tree: 3 -> 2,3 -> None,3,None,1
root = TreeNode(3, TreeNode(2, None, TreeNode(3)), TreeNode(3, None, TreeNode(1)))
print(rob_tree(root)) # 7जटिलता और साक्षात्कार चर्चा
रैखिक घर-लूट दो चरों वाले अनुकूलन के साथ O(n) समय और O(1) स्थान में चलती है। वृत्ताकार रूपांतर भी O(n) समय में चलता है, क्योंकि यह रैखिक रूपांतर को दो बार चलाता है। वृक्ष वाला रूपांतर O(n) समय और O(h) स्थान में चलता है, जहाँ h वृक्ष की ऊँचाई है। साक्षात्कार में कोड लिखने के बाद हमेशा जटिलता बताइए और स्थान के अनुकूलन का उल्लेख कीजिए — इससे पता चलता है कि आप पहले काम करने वाले समाधान से आगे भी सोचते हैं।
# Summary of complexities
# Linear House Robber:
# Time: O(n), Space: O(1) with two-variable trick
# Circular House Robber:
# Time: O(n), Space: O(1) (two passes)
# Tree House Robber:
# Time: O(n), Space: O(h) call stack
# Quick benchmark
import time
import random
nums = [random.randint(0, 100) for _ in range(10**6)]
start = time.time()
prev2 = prev1 = 0
for n in nums:
prev2, prev1 = prev1, max(prev1, n + prev2)
print(f'1M elements in {time.time()-start:.3f}s, result={prev1}')त्वरित जाँच
इस पाठ में पढ़ी गई डेटा संरचनाओं और एल्गोरिदम — कोडिंग साक्षात्कार की तैयारी से जुड़ी अवधारणाओं की अपनी समझ जाँचिए।
पाठ का पुनरावलोकन
इस पाठ में आपने सीखा: चुनने या छोड़ने वाली पुनरावृत्ति dp[i] = max(dp[i-1], nums[i] + dp[i-2]), दो क्रमिक रूप से बदलने वाले चर की सहायता से O(n) स्थान को O(1) तक कम करना, और इस प्रतिरूप को वृत्ताकार सरणियों और द्विआधारी वृक्षों तक विस्तारित करना। इसके बाद हम कडेन के एल्गोरिदम का उपयोग करके अधिकतम उप-सरणी और अधिकतम गुणनफल उप-सरणी की समस्याओं का अध्ययन करेंगे।
एआई शिक्षक के साथ कोडिंग साक्षात्कार की तैयारी सीखें — निःशुल्क
अपने ब्राउज़र में वास्तविक कोड लिखें और चलाएँ, चौबीसों घंटे एआई शिक्षक से तुरंत सहायता पाएँ, और वेब या ऐप पर वहीं से शुरू करें जहाँ आपने छोड़ा था।
- पाठ्यक्रम
- 90
- पाठ
- 360
अक्सर पूछे जाने वाले प्रश्न
क्या “House Robber: लेना या छोड़ना पुनरावृत्ति” पाठ निःशुल्क है?
हाँ—“House Robber: लेना या छोड़ना पुनरावृत्ति” का पूरा पाठ यहाँ वेब पर निःशुल्क पढ़ा जा सकता है। इंटरैक्टिव अभ्यास (अंतर्निहित कोड संपादक और 24/7 एआई ट्यूटर) करने और कोडिंग साक्षात्कार की तैयारी पाठ्यक्रम का बाकी हिस्सा अनलॉक करने के लिए CoddyKit PRO लें। कोडिंग साक्षात्कार की तैयारी पाठ्यक्रम में कुल 4 पाठ शामिल हैं।
“House Robber: लेना या छोड़ना पुनरावृत्ति” में मैं क्या सीखूँगा?
लूटने या छोड़ने के निर्णय को DP पुनरावृत्ति के रूप में मॉडल कीजिए, स्थान को दो चरों तक घटाइए और समाधान को वृत्ताकार घरों तक बढ़ाइए। आप ब्राउज़र में सीधे चलाए जाने वाले व्यावहारिक कोड के साथ कोडिंग साक्षात्कार की तैयारी का अभ्यास करते हैं, और पाठ पूरा करते समय 24/7 एआई ट्यूटर आपके प्रश्नों के उत्तर देता है।
क्या कोडिंग साक्षात्कार की तैयारी शुरू करने के लिए मुझे किसी अनुभव की आवश्यकता है?
पहले के अनुभव की आवश्यकता नहीं है। CoddyKit पर कोडिंग साक्षात्कार की तैयारी शुरुआती से लेकर उन्नत शिक्षार्थियों तक सभी के लिए व्यवस्थित किया गया है, इसलिए आप यहीं से या शुरुआत से सीखना शुरू कर सकते हैं और अपनी गति से आगे बढ़ सकते हैं। यह 4 में से 1वाँ पाठ है।
“House Robber: लेना या छोड़ना पुनरावृत्ति” पाठ पूरा करने में कितना समय लगता है?
CoddyKit का अधिकांश पाठ लगभग 5–10 मिनट में पूरा हो जाता है। हर पाठ छोटा और संवादात्मक है, इसलिए आप लगातार प्रगति करते हैं और वेब या ऐप पर वहीं से सीखना जारी रख सकते हैं जहाँ आपने छोड़ा था।
क्या मैं इस कोडिंग साक्षात्कार की तैयारी पाठ में कोड लिख और चला सकता हूँ?
हाँ। हर कोडिंग साक्षात्कार की तैयारी पाठ में एक अंतर्निर्मित कोड संपादक शामिल है, जिससे आप सीधे अपने ब्राउज़र में वास्तविक कोड लिख और चला सकते हैं और तुरंत एआई प्रतिक्रिया पा सकते हैं—स्थानीय सेटअप की आवश्यकता नहीं है।
इस पाठ्यक्रम के सभी पाठ
- House Robber: लेना या छोड़ना पुनरावृत्ति
- अधिकतम उपऐरे और अधिकतम गुणनफल उपऐरे
- Word Break और स्ट्रिंग विभाजन
- Decode Ways और पथों की गिनती