Jewels and Stones
لديك سلسلتان من الأحرف. يشير كل حرف في jewels إلى نوع من الجواهر، ولا يتكرر أي حرف. ويمثل كل حرف في stones حجرًا تملكه. أعد عدد الأحجار التي تملكها وتُعد جواهر. الأحرف حساسة لحالة الأحرف: "a" و"A" نوعان مختلفان.
الدالة
- jewelsstring
- أنواع الأحجار التي تُعدّ جواهر، حرف واحد لكل نوع
- stonesstring
- الأحجار التي تملكها، حرف واحد لكل حجر
- تُرجعinteger
- عدد الأحجار التي يظهر حرفها في الجواهر
القيود
1 ≤ jewels.length ≤ 521 ≤ stones.length ≤ 104- تحتوي كلتا السلسلتين على أحرف إنجليزية فقط، صغيرة وكبيرة.
- جميع أحرف
jewelsمختلفة.
أمثلة
- المدخلات
- jewels = "rR"stones = "rubyRRr"
- المخرجات
- 4
- الشرح
- نوعا الجواهر هما
rوR. فيrubyRRr، تتطابق الأحجارrوRوRوr، بينما لا تتطابقuوbوy، لذا فالإجابة هي4.
- المدخلات
- jewels = "z"stones = "ZZZ"
- المخرجات
- 0
- الشرح
- نوع الجوهرة الوحيد هو الحرف الصغير
z. كل حجر هو الحرف الكبيرZ، وهو نوع مختلف، لذا لا يُحتسب أيٌّ منها.
+12 اختبارات مخفية عند الإرسال
تلميحات
افتحها واحدًا تلو الآخر. كل تلميح يكشف أكثر قليلًا.
بالنسبة إلى حجر واحد، ما السؤال الذي يحدد ما إذا كان يُحتسب؟
تسأل «هل هذا الحرف جوهرة؟» مرةً واحدةً لكل حجر. ما البنية التي تجيب عن هذا السؤال في زمن ثابت؟
ضع أحرف
jewelsفي مجموعة، ثم مرّ علىstonesوعدّ كل حرف تحتويه المجموعة. حافظ على حالة الأحرف كما هي.
الحل
تحتاج إلى إجابة واحدة لكل حجر: هل هذا الحرف جوهرة؟ إن البحث في السلسلة jewels عن كل حجر يكرر الفحص نفسه مرارًا وتكرارًا. ضع أحرف الجواهر في مجموعة مرة واحدة، وسيصبح كل حجر عملية بحث واحدة.
ابحث في الجواهر عن كل حجر
الفكرة
تناول الأحجار واحدًا تلو الآخر. لكل حجر، تفحّص jewels وتوقّف عند أول حرف يساويه. تضيف المطابقة 1 إلى العدد. في المثال الأول، يُقارَن الحجر u بـ r وR، ولا يجد أيًّا منهما، فلا يضيف شيئًا.
يمكنك التوقّف عند أول مطابقة لأن أحرف الجواهر كلها مختلفة، لذا لا يمكن للحجر أن يطابق أكثر من حرف واحد منها. أما الحجر الذي ليس جوهرة، فيجب مقارنته بكل حرف من أحرف الجواهر قبل أن تعرف ذلك.
مع j أنواع من الجواهر وs من الأحجار، يصل العدد إلى j × s مقارنة. هنا j ≤ 52، لذا حتى 10^4 حجر تتطلب نحو 5 × 10^5 مقارنة، وينتهي الفحص في الوقت المحدد. يظهر الهدر عندما يزداد عدد الأنواع: إذ يُعاد البحث نفسه لكل حجر.
الخوارزمية
- عيّن
countإلى0. - لكل حجر، قارنه بكل حرف في
jewels. - عند أول حرف مطابق، أضف
1إلىcountوانتقل إلى الحجر التالي. - أعِد
count.
def numJewelsInStones(jewels, stones):
count = 0
for stone in stones:
for jewel in jewels:
if stone == jewel:
count += 1
break # the kinds are distinct: no second match is possible
return countضع الجواهر في مجموعة
الفكرة
إجابة السؤال "هل هذا الحرف جوهرة؟" هي نفسها في كل مرة تطرح فيها السؤال عن الحرف نفسه. لذا أجب عنه مرة واحدة لكل نوع: أنشئ مجموعة من أحرف jewels. تحدد المجموعة العضوية بزمن ثابت، لذا تتطلب كل حصاة عملية بحث واحدة بدلًا من المسح.
في المثال الأول، المجموعة هي {r, R}. عند المرور على rubyRRr، تكون نتائج البحث: نعم، لا، لا، لا، نعم، نعم، نعم؛ أي أربع جواهر. يستغرق إنشاء المجموعة j خطوة، ويستغرق المرور s خطوة، لذا يكون الزمن الإجمالي O(j + s).
تحتوي المجموعة على 52 حرفًا كحد أقصى. وفي لغة لا تتضمن مجموعة مضمّنة، تؤدي مصفوفة من القيم المنطقية المفهرسة برمز الحرف المهمة نفسها.
الخوارزمية
- أنشئ مجموعة تحتوي على كل حرف من
jewels. - عيّن
countإلى0. - لكل حجر، أضف
1إلىcountإذا كانت المجموعة تحتوي عليه. - أعِد
count.
def numJewelsInStones(jewels, stones):
kinds = set(jewels)
count = 0
for stone in stones:
if stone in kinds:
count += 1
return count
أخطاء شائعة وحالات حدّية
تتكوّن الخوارزمية من حلقة واحدة. وتنتج الإجابات الخاطئة عن طريقة مقارنة الأحرف وعدّها.
- تجاهل حالة الأحرف. يجعل تحويل السلسلتين إلى أحرف صغيرة
zمطابقًا لـZ، وتُرجع النتيجة في المثال الثاني3بدلًا من0. - عدّ أنواع الجواهر المختلفة بدلًا من الأحجار. يحتوي
rubyRRrعلى نوعين من الجواهر، لكن على أربعة أحجار جواهر؛ إذ يُحتسب كل حجر، بما في ذلك الأحجار المكررة. - إنشاء المجموعة داخل حلقة الأحجار. تكلف إعادة إنشائها
jخطوة في كل مرة، وتعيد تعقيد المسح إلىO(j × s). أنشئها مرة واحدة قبل الحلقة. - تبديل الوسيطات. يجب أن تحتوي المجموعة على
jewels، ويجب أن تمر الحلقة علىstones. عند عكس الدورين، يعدّ المثال الثاني نوع الجوهرة الوحيدzمقابل الأحجار، ويظل الناتج0، لكن("a", "aaa")يُرجع1بدلًا من3.
أسئلة شائعة3
ما التعقيد الزمني لمسألة Jewels and Stones؟
باستخدام مجموعة، يكون التعقيد O(j + s): j خطوة لبناء المجموعة من jewels، وعمليات بحث بزمن ثابت لكل حجر من الأحجار الـs. أما البحث في jewels عن كل حجر فيكون تعقيده O(j × s).
لماذا نستخدم مجموعة تجزئة للأحجار الكريمة والحصى؟
يسأل كل حجر السؤال نفسه: هل حرفه جوهرة؟ تجيب مجموعة التجزئة عن ذلك في زمن ثابت، بينما يستغرق البحث في سلسلة jewels وقتًا يتناسب مع طولها. تدفع مرة واحدة لبناء المجموعة، وتوفّر الوقت مع كل حجر بعد ذلك.
هل يمكنك حلّها دون استخدام مجموعة؟
نعم. الحروف هي حروف إنجليزية، لذا تعمل مصفوفة من 128 أو 256 علامة، مفهرسة برمز الحرف، كمجموعة من دون أي تجزئة على الإطلاق. علّم على كل حرف من أحجار الزينة، ثم احسب الأحجار التي عُيّنت علامتها. تنفّذ stones.count(jewels) في Ruby المهمة بأكملها باستدعاء واحد، لكن مصفوفة العلامات توضّح ما يحدث في الخلفية.
مسائل مشابهة
مسائل تعتمد على الأفكار نفسها. حلّ اثنتين أو ثلاث منها يثبّت النمط.
Python
def numJewelsInStones(jewels, stones):
# اكتب الشيفرة هناالحالة 1
الحالة 2
المدخلات
jewels = "rR" stones = "rubyRRr"
المتوقع
4