Greedylocally best choice · exchange argument · counterexamples · sort then pick · farthest reach
الـ greedy معناه: في كل خطوة خد أحسن اختيار دلوقتي، ومترجعش فيه أبدًا. لما ينفع، بيدّيك حل O(n) أو O(n log n) في كام سطر. ولما ما ينفعش، بيدّيك إجابة غلط بثقة تامة. الفصل ده عن الفرق بين الحالتين.
هتطلع من الفصل ده وإنت عارف
- يعني إيه greedy بالظبط، وفرقه عن الـ DP والـ backtracking.
- تقنع نفسك إن الـ greedy صح بالـ exchange argument بكلام بسيط، وتكسره بـ counterexample صغير لو غلط.
- الـ patterns الأساسية: sort then pick، collect every gain، farthest reach، reset لما الحساب يبقى سالب.
- تحل Assign Cookies و Stock II و Jump Game I و II و Gas Station و Partition Labels و Non-overlapping Intervals، كل واحدة بتضيف فكرة واحدة.
يعني إيه Greedy؟
في الفصل اللي فات كنا بنجرّب كل الاختيارات ونفتكر نتيجة كل واحد (DP). دلوقتي السؤال العكسي: إمتى تقدر تاخد أحسن اختيار قدامك وتمشي، من غير ما تبص على الباقي ولا ترجع؟
| الطريقة | بتعمل إيه | بترجع في قرارها؟ | السرعة |
|---|---|---|---|
| Backtracking | تجرّب كل الطرق | أيوه، بتعمل undo | exponential |
| DP | تجرّب كل الطرق بس تفتكر النتايج | مش بترجع، بتقارن كل الاختيارات | polynomial، غالبًا O(n²) أو O(n × m) |
| Greedy | تاخد الأحسن دلوقتي وبس | أبدًا | غالبًا O(n) أو O(n log n) بعد sort |
الـ greedy أسرع حاجة فيهم، بس فيه شرط: لازم يكون أحسن اختيار دلوقتي جزء من أحسن حل في الآخر. لو الشرط ده مش متحقق، الـ greedy بيطلّع إجابة غلط من غير ما يحس.
- ترتيب تنازلي عشان نبص على الأكبر الأول.
b - aمشa - b. - ليه
>=مش>؟ لو الباقي 50 والورقة 50، لازم ناخدها. مع>هنسيبها ونكمّل بورق أصغر. - ناخد الورقة ونكمّل بنفس الورقة، لأن ممكن تنفع تاني (زي 1 + 1).
- لو فضل باقي، يبقى الـ greedy اتزنق (مثلًا مفيش عملة 1). بنرجّع
null.
6 ورقات، وده فعلًا أقل عدد. بس هل ده بيحصل مع أي عملات؟
طب إزاي تعرف إن المسألة greedy أصلًا؟ ده الجزء الجاي.
إزاي تعرفه من المسألة
الـ constraints بتقول كتير: n لحد 10⁵ معناها لازم O(n log n) أو أحسن، فالـ DP بتاع O(n²) مش هيعدّي، والـ greedy مرشح قوي. ولو المطلوب "عدد الطرق"، ده عدّ، والعدّ محتاج تشوف كل الاختيارات، فده DP مش greedy.
| الـ pattern | الفكرة | مسائل |
|---|---|---|
| Sort then pick | رتّب بالحاجة اللي بتفرق، وخد بالترتيب | Assign Cookies، Non-overlapping Intervals، Arrows |
| Collect every gain | كل مكسب محلي خده، والخسارة سيبها | Stock II |
| Farthest reach | افتكر أبعد نقطة تقدر توصلها لحد دلوقتي | Jump Game I و II، Partition Labels |
| Reset when negative | لو الحساب بقى سالب، ابدأ من جديد بعد النقطة دي | Gas Station، Maximum Subarray (Kadane) |
flowchart TD
A["Choose step by step?"] --> B{"Asks for number of ways?"}
B -- yes --> D["DP"]
B -- no --> C{"Can you find a small counterexample?"}
C -- yes --> D
C -- no --> E{"Can you argue: swapping in my choice never hurts?"}
E -- yes --> G["Greedy: sort or scan once"]
E -- no --> F["Stress test greedy vs brute force first"]
السؤال الأهم في النص: تقدر تلاقي counterexample؟
السؤال ده هو قلب الفصل: إزاي تتأكد إن الـ greedy صح، وإزاي تكسره لو مش صح؟
صح ولا غلط؟ الـ exchange argument والـ counterexample
اكسره الأول: counterexample
قبل ما تثبت حاجة، حاول تكسرها. خد عملات [1, 3, 4] والمبلغ 6، وشغّل نفس الكود اللي فوق:
الـ greedy خد الـ 4 لأنها أكبر حاجة، والـ 4 دي ورّطته في 1 + 1. الحل الأحسن 3 + 3، عملتين بس. يعني أحسن اختيار دلوقتي (4) مش جزء من أحسن حل. عشان كده مسألة Coin Change (322) بأي عملات محتاجة DP، وده اللي اتشرح هناك.
ولو مش لاقي counterexample: الـ exchange argument
ده الإثبات اللي بيتقال في الانترفيو، وفكرته بسيطة:
- خد أي حل optimal (مش لازم تعرفه، بس افترض إنه موجود).
- لو أول اختيار فيه هو نفس اختيار الـ greedy، تمام.
- لو مختلف: ورّي إنك تقدر تبدّل اختياره باختيار الـ greedy، والحل يفضل valid ومش أوحش.
- كرر ده على كل خطوة. في الآخر الحل الـ optimal اتحوّل لحل الـ greedy من غير ما يوحش. يبقى الـ greedy optimal.
هتشوف الـ argument ده بيتطبّق في كل مثال محلول تحت، بجملة أو اتنين.
كل الـ greedy solutions تقريبًا ليها نفس الهيكل. يلا نكتبه مرة واحدة.
الهيكل العام
- نص الـ greedy problems بتبدأ بـ sort، والسؤال الحقيقي: بإيه؟ (بالـ start ولا الـ end؟ تصاعدي ولا تنازلي؟). الـ exchange argument هو اللي بيقولك.
- الـ state صغير دايمًا: رقم أو اتنين. لو لقيت نفسك محتاج تفتكر حاجات كتير، غالبًا ده DP.
- القاعدة المحلية: قرار بيتاخد بالـ item ده والـ state بس، من غير ما تبص لقدّام.
- مفيش undo. ده اللي بيخلّيه O(n) بعد الـ sort، وده اللي بيخلّيه يغلط لو القاعدة غلط.
الـ complexity: O(n log n) لو فيه sort، و O(n) لو scan بس، والـ memory غالبًا O(1).
أبسط تطبيق: sort الاتنين وطابق.
مثال محلول 1: Assign Cookies
كل طفل ليه "طمع" g[i]: مش هيرضى غير بكوكي حجمها >= g[i]. وعندك كوكيز بأحجام s[j]. كل طفل ياخد كوكي واحدة بالكتير. أكبر عدد أطفال تقدر ترضيهم؟
نفكّر فيها مع بعض
- Brute force: جرّب كل طرق التوزيع. ده exponential.
- الـ key insight: الطفل الأقل طمع هو الأسهل. ادّيله أصغر كوكي تكفّيه. ليه أصغر واحدة؟ عشان الكوكيز الكبيرة تفضل للأطفال الأطمع.
- الـ exchange argument: لو حل optimal ادّى الطفل ده كوكي أكبر، بدّلها بالأصغر اللي تكفّيه. الكبيرة رجعت متاحة، فمفيش حاجة وحشت.
- الخطة: رتّب الاتنين، وامشي بـ two pointers: لو الكوكي تكفّي الطفل، طابقهم. لو لأ، الكوكي دي صغيرة على كل اللي فاضلين، ارميها.
- الحالات الطرفية: مفيش كوكيز، كل الكوكيز صغيرة، كوكيز أكتر من الأطفال.
- الـ comparator لازم.
[10, 9, 1].sort()بتطلع[1, 10, 9]لأنها بترتّب كنصوص. - نقف لما يخلص الأطفال أو الكوكيز. الاتنين بـ
<لأنهم indices. >=لأن الكوكي اللي حجمها بالظبط قد الطمع بتكفّي.- الكوكي بتتحرك في الحالتين. لو اتاخدت، خلصت. لو صغيرة على الطفل ده، هتبقى صغيرة على كل اللي بعده (أطمع منه)، فنرميها.
childهو عدد اللي اتطابقوا، لأنه بيزيد بس مع كل تطابق.
التعقيد: الـ sort O(n log n + m log m)، والـ loop O(n + m). الـ memory O(1) غير الـ sort.
هنا رتّبنا عشان نطابق. طب لو مفيش حاجة نرتّبها، والقرار محلي في كل يوم؟
مثال محلول 2: Best Time to Buy and Sell Stock II
prices[i] سعر سهم في اليوم i. تقدر تشتري وتبيع كام مرة ما تحب، بس تمسك سهم واحد بالكتير في نفس الوقت. أكبر مكسب؟
نفكّر فيها مع بعض
- الجديد هنا: مفيش sort. القرار بيتاخد يوم بيوم، وكل مكسب صغير بنلمّه.
- الـ key insight: لو اشتريت بـ 1 وبعت بـ 8 والسعر طالع على طول (1، 4، 8)، المكسب
8 - 1 = 7هو نفسه(4 - 1) + (8 - 4). يعني أي صفقة على طلعة = مجموع الطلعات اليومية. - فالقاعدة: كل يوم السعر فيه أعلى من امبارح، خد الفرق. كل يوم أقل، سيبه. مفيش يوم نازل ممكن يزوّد المكسب.
- الحالات الطرفية: يوم واحد (0)، أسعار نازلة على طول (0).
- ليه
i = 1؟ عشان بنقارن بـprices[i - 1]. لو بدأنا من 0 هنقراprices[-1]ودهundefined. >مش>=: يوم بنفس السعر مكسبه صفر، فمش فارقة، بس>أوضح.- ده "اشتري امبارح وبيع النهارده" على كل طلعة. في الحقيقة مش لازم تعمل الصفقات دي فعلًا، المجموع بس هو اللي بيساوي.
التعقيد: O(n) وقت و O(1) memory.
هنا كل يوم قراره لوحده. طب لو القرار محتاج تفتكر حاجة من اللي فات، زي "أبعد مكان وصلتله"؟
مثال محلول 3: Jump Game
إنت واقف عند index 0. الرقم nums[i] هو أقصى عدد خطوات تقدر تنطّها لقدّام من i (تقدر تنط أقل). تقدر توصل لآخر index؟
نفكّر فيها مع بعض
- الجديد هنا: بنشيل state من اللي فات: أبعد index نقدر نوصله لحد دلوقتي (farthest).
- Brute force: من كل index جرّب كل نطة ممكنة، recursion أو DP. ده O(n²).
- الـ key insight: مش محتاجين نعرف إزاي وصلنا لـ index، كفاية نعرف إنه reachable. ولو
ireachable، فكل اللي قبله reachable برضه (نطيت فوقهم). يعني الـ reachable دايمًا prefix متصل[0..farthest]. - الخطة: امشي من الشمال. لو
i > farthestيبقى اتزنقنا. غير كده كبّر الـ farthest بـi + nums[i]. - الحالات الطرفية: array فيها عنصر واحد (true، إنت واقف عليه)، صفر في الأول.
- بنبدأ بـ 0 لأننا واقفين عند index 0، فهو reachable.
>مش>=: لوi === farthestيبقىireachable بالظبط، وينفع ننط منه.- من
iنقدر نوصل لحدi + nums[i]. الـ max لأن الـ farthest عمره ما بيقل. nums.length - 1هو آخر index، مش الطول. وده early return: مش محتاجين نكمّل.
التعقيد: O(n) وقت و O(1) memory.
عرفنا نوصل ولا لأ. طب لو مضمون إننا هنوصل، والسؤال بقى: أقل عدد نطات كام؟
مثال محلول 4: Jump Game II
نفس الـ array، ومضمون إن آخر index ممكن توصله. أقل عدد نطات توصّلك له؟
نفكّر فيها مع بعض
- الجديد هنا: نفس الـ farthest، بس بنقسم الـ array لـ windows: كل window هي الـ indices اللي توصلها بنفس عدد النطات.
- الـ key insight: بنطة واحدة من 0 بتوصل لـ
[1..2]. بنطتين بتوصل لأي حاجة توصلها من أي index في[1..2]، يعني لحد أبعد farthest منهم. ده BFS بالظبط، كل window مستوى، بس من غير queue. - الخطة:
endهو آخر index في الـ window الحالية. وإحنا ماشيين بنحدّث الـ farthest. لماiيوصلend، خلصنا الـ window: نطة جديدة، والـ window الجاية بتخلص عند الـ farthest. - الحالات الطرفية: عنصر واحد (0 نطات)، نطة واحدة توصل على طول.
- بـ 0 نطات نوصل لـ index 0 بس، فالـ window الأولى
[0..0]، وend = 0. - ليه
nums.length - 1مشnums.length؟ لما توصل لآخر index خلاص وصلت، مش محتاج تنط منه. لو لفيت عليه وكانi === end، هتعد نطة زيادة. جرّب[0]: الصح 0، ومع< nums.lengthهيطلع 1. - زي Jump Game بالظبط.
- آخر window. أي index بعدها محتاج نطة زيادة، وأبعد حاجة نقدر نوصلها بالنطة دي هي الـ farthest اللي جمعناه من الـ window كلها.
التعقيد: O(n) وقت و O(1) memory. والـ DP البديهي O(n²).
هنا كنا بنكبّر حاجة (الـ reach). طب لو الحساب ممكن يبقى سالب، ولازم نبدأ من جديد؟
مثال محلول 5: Gas Station
محطات بنزين على دايرة. في المحطة i بتاخد gas[i]، والطريق منها للي بعدها بيصرف cost[i]. العربية بتبدأ بتانك فاضي. من أنهي محطة تبدأ عشان تلف الدايرة كلها؟ لو مفيش رجّع -1 (والإجابة لو موجودة واحدة بس).
نفكّر فيها مع بعض
- الجديد هنا: الـ state ممكن يبقى سالب، ولما يحصل ده بنعمل reset ونبدأ من جديد بعد النقطة دي.
- Brute force: جرّب كل محطة كبداية ولف الدايرة. O(n²).
- أول ملاحظة: لو مجموع البنزين أقل من مجموع الصرف، مستحيل. ولو مش أقل، فيه إجابة (المسألة بتضمن إنها واحدة).
- حجة الـ reset: بدأنا من
startوالتانك بقى سالب عندi. أي محطة بينstartوiبرضه هتفشل قبلi + 1: إحنا وصلنالها بتانك>= 0، فلو بدأنا منها بتانك صفر هنبقى أوحش أو زي ما إحنا. يبقى نرمي الكل ونجرّبi + 1. - الحالات الطرفية: محطة واحدة، المجموع بالظبط صفر (ينفع).
- المكسب الصافي من المحطة دي للي بعدها. ممكن يبقى سالب.
- اتنين حسابات:
totalللدايرة كلها (هل فيه إجابة أصلًا؟)، وtankمنstartبس (هل الـ start ده نافع؟). < 0مش<= 0: تانك صفر معناه وصلت بآخر نقطة بنزين، وده مسموح.i + 1مشi. المحطةiنفسها جزء من الفشل (حجة الـ reset بتشمل start..i كلهم).- ليه بنثق في
startمن غير ما نلف تاني؟ الـ tank منstartلآخر الـ array ما بقاش سالب، واللي قبلstartكان مجموعه سالب. فلوtotal >= 0، الجزء منstartللآخر كبير كفاية يغطي العجز اللي في الأول.
التعقيد: لفة واحدة، O(n) وقت و O(1) memory.
الـ farthest رجع تاني في المثال الجاي، بس على حروف: "الجزء ده لازم يمتد لحد فين؟".
مثال محلول 6: Partition Labels
قسّم string لأكبر عدد ممكن من الأجزاء المتصلة، بحيث كل حرف يظهر في جزء واحد بس. رجّع أطوال الأجزاء بالترتيب.
نفكّر فيها مع بعض
- الجديد هنا: بنحسب معلومة مساعدة الأول (آخر ظهور لكل حرف)، وبعدين farthest reach عليها.
- الـ key insight: لو الجزء بدأ بـ
a، لازم يمتد على الأقل لحد آخرa. وكل حرف جوه الجزء ده بيفرض نفس الحاجة: الجزء لازم يوصل لآخر ظهور ليه. فالـ end بيكبر كل ما نقابل حرف آخر ظهوره أبعد. - إمتى نقطع؟ لما
iيوصل للـ end. ساعتها كل حرف شفناه آخر ظهور ليه جوه الجزء، فالقطع آمن. وبنقطع أول ما ينفع عشان نطلّع أكبر عدد أجزاء. - الحالات الطرفية: حرف واحد، كل الحروف مختلفة (كل واحد جزء)، string كله حرف واحد متكرر (جزء واحد).
- لفة أولى: كل حرف بيكتب الـ index بتاعه فوق اللي قبله، فاللي بيفضل هو آخر ظهور.
- نفس
farthest = Math.max(...)بتاعة Jump Game، بس الـ reach هنا هو آخر ظهور للحرف. i === end: وصلنا للحد اللي كل اللي جوه محتاجينه، يبقى نقطع.+ 1لأننا بنعدّ عناصر: الجزء من index 0 لـ 4 فيه 5 حروف. ده عكس الـ width في Container With Most Water اللي كان مسافة.- الجزء الجاي بيبدأ بعد القطع على طول.
التعقيد: لفتين، O(n) وقت. الـ memory O(1) لأن الحروف 26 بس.
آخر مثال بيرجع للـ sort، بس السؤال الصعب فيه: نرتّب بإيه؟
مثال محلول 7: Non-overlapping Intervals
عندك intervals [start, end]. أقل عدد تشيله عشان الباقي ما يتداخلش؟ اللي بيلمسوا بعض بس ([1, 2] و [2, 3]) مش متداخلين.
شفنا المسألة دي في فصل الـ intervals. هنا هنبص عليها من زاوية الـ greedy: ليه الترتيب بالـ end بالذات صح؟
نفكّر فيها مع بعض
- الجديد هنا: الـ sort مش واضح. اختيار المفتاح الغلط (الـ start أو الطول) بيدّي إجابة غلط، والـ exchange argument هو اللي بيختار.
- اقلبها: أقل عدد نشيله = n ناقص أكبر عدد نسيبه من غير تداخل.
- الـ key insight: أول interval نسيبه لازم يبقى اللي بيخلص بدري. ليه؟ عشان بيسيب أكبر مساحة للباقيين.
- الـ exchange argument: أي حل optimal، أول interval فيه بيخلص عند
e. اللي بيخلص بدري (e' <= e) ينفع ياخد مكانه: كل اللي بعده كانوا بيبدأوا بعدe، فأكيد بعدe'. نفس العدد، مفيش خسارة. - الخطة: رتّب بالـ end، وامشي: لو الـ interval بيبدأ بعد آخر end سبناه (أو عنده)، سيبه. لو لأ، شيله.
- الترتيب بالـ end (
a[1])، مش بالـ start. ده القرار كله. -Infinityعشان أول interval يتساب دايمًا مهما كان الـ start بتاعه (حتى لو سالب).>=مش>: اللي بيلمسوا بس مش متداخلين.[1, 2]و[2, 3]:2 >= 2فنسيب الاتنين.- بيتداخل مع آخر واحد سبناه. واللي سبناه بيخلص قبله أو معاه (بسبب الترتيب)، فشيل الجديد أحسن.
كل صف interval، والخانات المليانة هي الوقت اللي بيغطيه. الأرقام فوق هي الوقت:
التعقيد: الـ sort O(n log n)، والـ loop O(n).
في كل مثال فيه قاعدة صغيرة لو اتكتبت غلط الحل بيقع. يلا نجمعهم.
غلطات مشهورة
1. greedy من غير ما تحاول تكسره
قبل ما تكتب أي greedy، جرّب 2 أو 3 inputs صغيرة فيها تعارض. لو لقيت counterexample، روح DP.
2. ترتّب بالمفتاح الغلط
الـ interval اللي بيبدأ بدري ممكن يكون طويل جدًا ويقفل الطريق. اللي بيخلص بدري هو اللي بيسيب مساحة. (فيه حل صح بالـ start بس لما يحصل تداخل لازم تسيب اللي بيخلص بدري منهم، وده أعقد.)
3. Jump Game II بتلف لحد آخر index
لما توصل لآخر index، مش محتاج تنط منه. اسأل نفسك عن كل loop: هل آخر عنصر محتاج نفس المعاملة؟
4. Gas Station: الـ reset لـ i بدل i + 1
التانك بقى سالب بعد ما صرفنا cost[i]، يعني المحطة i جزء من الرحلة الفاشلة. البداية الجديدة لازم تبقى بعدها.
5. sort() من غير comparator
نص مسائل الـ greedy بتبدأ بـ sort، فالغلطة دي بتبوّظ الحل كله من أول سطر. مع أرقام أقل من 10 الـ test هيعدّي بالصدفة، فخلي بالك.
6. off-by-one في الأطوال
عدّ العناصر من start لـ end (الاتنين داخلين) = end - start + 1. المسافة بينهم = end - start. اسأل نفسك: بعدّ ولا بقيس؟
دلوقتي جرّب نفسك: كام سؤال سريع، وتمرين تفكّر فيه قبل ما تفتح الحل.
اختبر نفسك
عملات [1, 5, 6, 9] والمبلغ 11. الـ greedy (أكبر عملة الأول) هيستخدم كام عملة، والأحسن كام؟
- الاتنين 2
- الـ greedy 3 (9 + 1 + 1)، والأحسن 2 (5 + 6)
- الـ greedy 2، والأحسن 3
- الـ greedy هيتزنق ويرجّع -1
الـ 9 شكلها أحسن اختيار، بس بتسيب 2 ومفيش غير 1 + 1. ده counterexample تاني لـ Coin Change بالـ greedy.
في Non-overlapping Intervals، نرتّب بإيه عشان الـ greedy يبقى صح؟
- بالـ start تصاعدي
- بالـ end تصاعدي
- بالطول من الأقصر
- مش فارقة
اللي بيخلص بدري بيسيب أكبر مساحة للباقيين، وأي حل optimal تقدر تبدّل أول interval فيه بيه من غير خسارة. الأقصر مش كفاية: interval قصير ممكن يقع في نص اتنين طوال ويبوّظهم الاتنين.
Gas Station: مجموع gas هو 9 ومجموع cost هو 10. الإجابة؟
- 0
- المحطة اللي فيها أكبر gas
- -1 من غير ما تلف أصلًا
- محتاج تجرّب كل محطة
البنزين كله أقل من الصرف كله، فمهما بدأت منين مش هتكمّل الدايرة. ده الـ total >= 0 في آخر الكود.
Stock II على [5, 4, 3, 2, 1]. المكسب؟
- 0
- 4
- -4
- 1
مفيش ولا يوم السعر طلع فيه، فمفيش ولا فرق يتلم. والمكسب عمره ما يبقى سالب: لو مفيش صفقة كويسة، ما تعملش صفقات.
في Jump Game، ليه farthest لوحده كفاية ومش محتاجين نعرف إزاي وصلنا لكل index؟
- عشان الـ array مترتبة
- عشان الـ reachable دايمًا prefix متصل
[0..farthest]، فرقم واحد بيوصفه كله - عشان كل نطة طولها 1
- مش كفاية، محتاجين DP
لو وصلت لـ index، يبقى عدّيت على أو فوق كل اللي قبله، وكلهم reachable. فمفيش فراغات، والـ farthest هو كل المعلومة.
تمرين: فكّر قبل ما تفتح
كل بالونة interval أفقي [start, end]. سهم رأسي عند x بيفرقع كل بالونة فيها start <= x <= end. أقل عدد أسهم يفرقع الكل؟
تلميح 1
دي أخت 435. البالونة اللي بتخلص بدري لازم سهم يفرقعها في وقت ما قبل نهايتها. فين أحسن مكان للسهم ده؟
تلميح 2
رتّب بالـ end. اضرب أول سهم عند نهاية أول بالونة: أبعد مكان لسه بيفرقعها، فبيلحق أكبر عدد بالونات بعدها. أي بالونة الـ start بتاعها <= مكان السهم اتفرقعت. أول واحدة بعده محتاجة سهم جديد عند نهايتها.
الحل
لاحظ start > pos هنا مش >=: لو البالونة بتبدأ عند مكان السهم بالظبط، السهم فرقعها (اللمس هنا بيتحسب). ده عكس 435 اللي اللمس فيها مش تداخل. نفس الكود تقريبًا، والفرق في حرف واحد جاي من نص المسألة. O(n log n).
لو الأسئلة عدّت معاك، روح على LeetCode بالترتيب اللي تحت.
اتمرن على LeetCode بالترتيب
في كل مسألة، قبل ما تكتب، قول لنفسك الـ exchange argument في جملة، أو دوّر على counterexample دقيقتين. لو قعدت أكتر من 25 دقيقة، ارجع للمثال اللي شبهها.
- Assign Cookiesالمثال المحلول 1: sort then match.
- Lemonade Changeرجّع الباقي بالأكبر الأول، والعملات هنا بتخلّي الـ greedy صح. اسأل نفسك ليه.
- Best Time to Buy and Sell Stock IIلم كل طلعة.
- Maximize Sum Of Array After K Negationssort واقلب أصغر الأرقام السالبة الأول. وفكّر في الـ k اللي فاضل.
- Jump Gamefarthest reach.
- Jump Game IIwindows زي BFS. خلي بالك من
n - 1. - Gas Stationالـ reset لما الحساب يبقى سالب.
- Partition Labelsآخر ظهور + farthest reach.
- Non-overlapping Intervalssort بالـ end، والـ exchange argument.
- Minimum Number of Arrows to Burst Balloonsالتمرين اللي فوق: نفس الفكرة، والفرق في
>. - Hand of Straightsأصغر كارت لازم يبدأ مجموعة: greedy مع Map للعدّ.
- Valid Parenthesis Stringبدل عدّاد واحد، range [أقل، أكتر] للأقواس المفتوحة.
- Candyاختياري: لفتين، من الشمال ومن اليمين، وخد الـ max.
وآخر حاجة: الفصل كله في صفحة واحدة ترجعلها قبل أي انترفيو.
الخلاصة
| السؤال | الإجابة |
|---|---|
| greedy ولا DP؟ | جرّب counterexample صغير. لو لقيت، DP. لو المطلوب "عدد الطرق"، DP. |
| إزاي أثبت؟ | exchange argument: أبدّل أول اختيار في أي حل optimal باختياري من غير خسارة. |
| أرتّب بإيه؟ | بالحاجة اللي بتسيب أكبر مساحة للباقي (غالبًا الـ end في الـ intervals). |
| Complexity؟ | O(n log n) لو فيه sort، O(n) لو scan، و O(1) memory غالبًا. |
| الـ off-by-one المشهورة؟ | n - 1 في Jump II، و + 1 في الأطوال، و i + 1 في الـ reset. |
الفصل الجاي: آخر أداة في الدليل: Bit Manipulation. بدل ما تتعامل مع الرقم كقيمة، هتتعامل مع الـ 0 و 1 اللي جواه، ومسائل كانت محتاجة hash map أو loop هتتحل في سطر.