प्राचीन एल्गोरिथम जादू का एक अंश, या लीटकोड से कार्यों के एक दिलचस्प अनुक्रम को हल करना

कुछ समय पहले, मुझेleetcode.com वेबसाइट पर कार्यों की एक मनोरंजक श्रृंखला मिली। कार्य स्वयं बहुत कठिन नहीं हैं, लेकिन उनके समाधान काफी दिलचस्प हैं। इसके अलावा, इस प्रकार की समस्याएं अक्सर प्रमुख कंपनियों के साक्षात्कारों में सामने आती हैं, और उनके समाधान के तरीकों को समझना काफी फायदेमंद हो सकता है।

पहला कार्य 136 है। एकल संख्या (आसान)

पूर्णांकों की एक गैर-रिक्त सरणी को देखते हुए जहां एक को छोड़कर प्रत्येक तत्व दो बार दिखाई देता है, आपको जोड़े के बिना तत्व ढूंढना होगा। समस्या को O(n) समय जटिलता में और निरंतर अतिरिक्त मेमोरी के साथ हल करें।

उदाहरण 1:

इनपुट: अंक = [1, 3, 3, 2, 6, 2, 1]

आउटपुट: 6

उदाहरण 2:

इनपुट: संख्याएँ = [12, 1, 1, 7, 1, 12, 1]

आउटपुट: 7

उदाहरण 3:

इनपुट: अंक = [6]

आउटपुट: 6

हम XOR फ़ंक्शन प्रॉपर्टी का लाभ उठाएंगे, जो केवल 1 उत्पन्न करता है जब इसके ऑपरेंड भिन्न होते हैं। सरणी के सभी तत्वों को पार करके और उन पर बिटवाइज़ XOR निष्पादित करके, हम सभी समान बिट मानों को शून्य कर देंगे। परिणामस्वरूप, जो बचेगा वह वांछित परिणाम होगा।

यहाँ एक संक्षिप्त Python3 समाधान कोड है:

 def single_number(nums: list) -> int: result = 0 for el in nums: result ^= el return result

हम केवल उतनी ही अतिरिक्त मेमोरी का उपयोग करते हैं जितनी एक पूर्णांक घेरता है, और दिए गए सरणी के माध्यम से एक ही पास में समाधान ढूंढते हैं, जिससे हमें O(n) जटिलता मिलती है। यह एक संक्षिप्त और सुरुचिपूर्ण समाधान है.

दूसरी समस्या 137 है। एकल संख्या II (मध्यम कठिनाई)

पूर्णांकों की एक गैर-रिक्त सरणी को देखते हुए जहां एक को छोड़कर प्रत्येक तत्व तीन बार दिखाई देता है, और केवल एक तत्व एक बार दिखाई देता है, हमें इस अद्वितीय तत्व को खोजने की आवश्यकता है। समस्या को O(n) समय जटिलता में और निरंतर अतिरिक्त मेमोरी के साथ हल करें।

उदाहरण 1:

इनपुट: अंक = [3, 1, 3, 3]

आउटपुट: 1

उदाहरण 2:

इनपुट: संख्याएँ = [12, 1, 1, 5, 1, 12, 12]

आउटपुट: 5

उदाहरण 3:

इनपुट: अंक = [6]

आउटपुट: 6

दुर्भाग्य से, हम इस मामले में पिछली चाल का उपयोग नहीं कर सकते क्योंकि हम युग्मित बिट्स को आवश्यक स्थिति में शून्य में नहीं बदल सकते हैं। दिए गए एरे को पिछले कार्य के प्रारूप में बदलना और फिर इसे उसी तरह से हल करना आकर्षक होगा।

इस तरह से तर्क करने पर, यह नोटिस करना आसान है कि अगर हमें पता था कि सरणी को पार करते समय हम पहले से ही दो बार (या तीन बार) संख्या एन का सामना कर चुके हैं, तो हम जो योग प्राप्त कर रहे हैं उसमें एन के साथ एक अतिरिक्त एक्सओआर जोड़ सकते हैं। यह इस संख्या के साथ अंतिम XOR को सम बना देगा, जिससे इसे अंतिम योग से हटा दिया जाएगा, और जो बचेगा वह हमारा उत्तर होगा।

 def single_number_ii(nums: list) -> int: mem = {} result = 0 for el in nums: if not mem.get(el, False): mem[el] = 1 else: mem[el] += 1 if mem[el] == 2: result ^= el result ^= el return result

दुर्भाग्य से, इस समाधान के लिए मेमोरी के संदर्भ में अधिकतम (len(nums)-1)/3 की आवश्यकता होगी, जिसे निरंतर खपत नहीं माना जा सकता है, इसलिए हमें दूसरे समाधान की तलाश करनी होगी।

आइए अपना दृष्टिकोण बदलने का प्रयास करें।

पहले, हमने XOR का उपयोग किया था (जो अतिरिक्त मॉड्यूलो 2 का प्रतिनिधित्व करता है)। यदि हमने अतिरिक्त मॉड्यूलो 3 लागू किया होता, तो हम पिछले उदाहरण से युक्ति को आसानी से लागू कर सकते थे।

यदि हम पहली बार उत्तर मिलने पर उसमें एक संख्या डाल सकें, दूसरी बार उसे संचायक में डाल सकें, और तीसरी बार उत्तर और संचायक दोनों को शून्य कर सकें, तो इससे हमें समस्या को एक ही बार में हल करने में मदद मिलेगी अतिरिक्त मेमोरी खपत वाली सूची बिल्कुल दो पूर्णांकों के बराबर है, जो कार्य आवश्यकताओं को पूरा करती है।

तो, आइए थोड़ा और बिटवाइज़ जादू लागू करें:

 def single_number_137_ii(nums: list) -> int: ans, acc = 0, 0 for n in nums: ans = ans ^ n & ~acc acc = acc ^ n & ~ans return ans

इस तरह, सभी त्रिगुण संख्याएँ शून्य हो जाती हैं, और हमारे पास केवल वही संख्या बचती है जो केवल एक बार आती है।

तीसरा कार्य 260 है। एकल संख्या III (मध्यम कठिनाई)

पूर्णांकों की एक गैर-रिक्त सरणी को देखते हुए जहां प्रत्येक तत्व दो बार दिखाई देता है, दो तत्वों को छोड़कर जो केवल एक बार दिखाई देते हैं, हमें इन अद्वितीय तत्वों को खोजने की आवश्यकता है। लक्ष्य O(n) समय जटिलता में और निरंतर अतिरिक्त मेमोरी के साथ समस्या को हल करना है, और अद्वितीय तत्वों का क्रम कोई मायने नहीं रखता।

उदाहरण 1:

इनपुट: अंक = [1, 2, 1, 3, 2, 5]

आउटपुट: [3, 5]

उदाहरण 2:

इनपुट: अंक = [1, -2]

आउटपुट: [-2, 1]

जाहिर है, हम XOR ऑपरेशन का उपयोग करके सभी युग्मित संख्याओं को आसानी से समाप्त कर सकते हैं, जैसा कि हमने पहले कार्य को हल करने में किया था। कार्य की जटिलता किसी भी अद्वितीय संख्या की पहचान करने में निहित है, जिसके बाद दूसरे की गणना हमारे XOR योग के साथ XOR-ing द्वारा आसानी से की जा सकती है।

इसे प्राप्त करने के लिए, हमें बस इन अद्वितीय संख्याओं के बीच कोई भिन्न बिट ढूंढने की आवश्यकता है। फिर, हम सरणी के माध्यम से फिर से दोहराते हैं, एक्सओआर सारांश निष्पादित करते हैं और परिणामों को दो समूहों में विभाजित करते हैं - उन संख्याओं के लिए जहां यह बिट सेट है और उन लोगों के लिए जहां यह 0 है। परिणामस्वरूप, हम वांछित अद्वितीय तत्व प्राप्त करते हैं।

 def single_number_260(nums: list) -> int: res1, res2 = 0, 0 glob_xor = 0 for n in nums: glob_xor ^= n diff_bit = glob_xor & ~(glob_xor - 1) for n in nums: if n & diff_bit: res1 ^= n else: res2 ^= n return [res1, res2]

सरणी के माध्यम से दो बार पुनरावृति करने के बावजूद, जटिलता O(n) बनी हुई है, और मेमोरी खपत केवल 2 पूर्णांक है।

ध्यान दें: इस तथ्य के बावजूद कि पायथन में int अन्य भाषाओं में int के समान नहीं है, हम इसके आकार को एक स्थिर मानेंगे