Jewels and Stones

Q: מהי סיבוכיות הזמן של Jewels and Stones?

בעזרת קבוצה, זמן הריצה הוא O(j + s) : j צעדים לבניית הקבוצה מתוך jewels , וחיפוש אחד בזמן קבוע עבור כל אחת מ־ s האבנים. סריקת jewels עבור כל אבן היא O(j × s) .

Q: האם תוכל לפתור את זה בלי קבוצה?

כן. האותיות הן אותיות באנגלית, ולכן מערך של 128 או 256 דגלים, שמאונדקסים לפי קוד התו, פועל כקבוצה ללא שימוש בגיבוב כלל. סמנו כל אות של תכשיט, ואז ספרו את האבנים שהדגל שלהן מסומן. stones.count(jewels) של Ruby עושה את כל העבודה בקריאה אחת, אבל מערך הדגלים מראה מה קורה מתחת לפני השטח.

מתחיליםגיבוב

+10

מקבלים שתי מחרוזות של אותיות. כל אות ב־jewels מציינת סוג אחד של אבן חן, ואין אות שחוזרת. כל אות ב־stones מייצגת אבן שברשותך. יש להחזיר כמה מהאבנים שלך הן אבני חן. אותיות תלויות רישיות: "a" ו־"A" הן סוגים שונים.

פונקציה

numJewelsInStones(jewels: string, stones: string) → integer

jewelsstring: סוגי האבנים שנחשבים לאבני חן, אות אחת לכל אחת
stonesstring: האבנים שבבעלותך, אות אחת לכל אבן
מחזירהinteger: מספר האבנים שהאות שלהן מופיעה בתכשיטים

אילוצים

1 ≤ jewels.length ≤ 52
1 ≤ stones.length ≤ 10⁴
שתי המחרוזות מכילות אותיות באנגלית בלבד, קטנות וגדולות.
כל האותיות ב־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 בדיקות נסתרות בשליחה

רמזים

פתחו אותם אחד אחד. כל רמז חושף קצת יותר.

נפתחו 0 מתוך 3

פתרון

לכל אבן דרושה תשובה אחת: האם האות הזאת היא אבן חן? חיפוש במחרוזת 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 and Stones?

כל אבן מציבה את אותה שאלה: האם האות שלה היא אבן חן. קבוצת גיבוב עונה על כך בזמן קבוע, בעוד שחיפוש במחרוזת jewels אורך זמן יחסי לאורך שלה. משלמים פעם אחת כדי לבנות את הקבוצה, וחוסכים זמן בכל אבן לאחר מכן.

האם תוכל לפתור את זה בלי קבוצה?

כן. האותיות הן אותיות באנגלית, ולכן מערך של 128 או 256 דגלים, שמאונדקסים לפי קוד התו, פועל כקבוצה ללא שימוש בגיבוב כלל. סמנו כל אות של תכשיט, ואז ספרו את האבנים שהדגל שלהן מסומן. stones.count(jewels) של Ruby עושה את כל העבודה בקריאה אחת, אבל מערך הדגלים מראה מה קורה מתחת לפני השטח.

Python

def numJewelsInStones(jewels, stones):
    # כתבו כאן את הקוד

מקרי בדיקה

מקרה 1

מקרה 2

קלט

jewels = "rR"
stones = "rubyRRr"

צפוי