Count a Character

Q: האם מותר להשתמש בפונקציית ספירה מובנית בריאיון?

בדרך כלל כן, כל עוד אתה יכול לומר מה העלות. הפונקציה str.count של Python ופונקציות דומות עדיין קוראות את כל המחרוזת, ולכן הסיבוכיות שלהן היא O(n) . היה מוכן לכתוב את הלולאה אם המראיין יבקש זאת.

מתחיליםמערכים ומחרוזות

+10

מקבלים מחרוזת s ואות אחת c. החזירו את מספר הפעמים שבהן c מופיעה ב־s. ההתאמה מבחינה בין אותיות גדולות לקטנות: B ו־b הן תווים שונים.

פונקציה

countChar(s: string, c: string) → integer

sstring: מחרוזת האותיות באנגלית לחיפוש
cstring: האות האחת שיש לספור
מחזירהinteger: כמה תווים ב-s שווים ל-c

אילוצים

1 ≤ s.length ≤ 5 × 10⁴
s מכיל רק אותיות באנגלית (a עד z, A עד Z).
c היא בדיוק אות אחת באנגלית.

דוגמאות

קלט: s = "Mississippi"c = "s"
פלט: 4
הסבר: ב־Mississippi יש s באינדקסים 2, 3, 5 ו־6, לכן התשובה היא 4.

קלט: s = "Banana"c = "b"
פלט: 0
הסבר: Banana מתחילה באות גדולה B, ואתם מחפשים אות קטנה b. אין התאמות, ולכן התשובה היא 0.

שאלת המשך

מה אם c יכולה להיות מילה המורכבת מכמה אותיות, כמו ss? האם התאמות חופפות נחשבות, וכיצד משתנה הלולאה שלך?

רמזים

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

נפתחו 0 מתוך 3

פתרון

כל תו ב־s יכול להיות c, לכן עוברים על כל אחד מהם פעם אחת וסופרים את ההתאמות. שימו לב לאותיות גדולות וקטנות: אות גדולה היא תו שונה.

מחקו כל c והשוו את האורכים

האינטואיציה

צרו עותק של s והסירו ממנו כל c. כל הסרה מקצרת את העותק בתו אחד, ולכן ההפרש בין האורכים הוא מספר ההופעות. עבור Mississippi העותק הוא Miiippi: 11 פחות 7 הם 4.

זמן הריצה הוא O(n), אבל העותק דורש O(n) זיכרון נוסף שמונה אינו זקוק לו.

אלגוריתם

צרו עותק של s שמשמיט כל תו ששווה ל־c.
מדדו את האורך של s ואת האורך של העותק.
החזירו את האורך של s פחות את האורך של העותק.

def countChar(s, c):
    # Every c that disappears makes the string one character shorter.
    without = s.replace(c, "")
    return len(s) - len(without)

מעבר אחד עם מונה

האינטואיציה

ספרו תוך כדי קריאה במקום ליצור עותק. מונה מתחיל ב־0 ועולה ב־1 עבור כל תו ששווה ל־c. השוואת שוויון רגילה מונעת מאות גדולה להתאים לאות קטנה.

כל תו מושווה פעם אחת בלבד, ונשמר רק המונה: זמן O(n), מקום O(1). שום פתרון לא יכול להשתפר מזמן O(n), כי תו שעליו מדלגים עשוי להיות עוד c.

אלגוריתם

קרא את האות המבוקשת מתוך c והגדר count = 0.
עבור על s תו אחד בכל פעם.
אם התו שווה לאות המבוקשת, הוסף 1 ל־count.
החזר את count.

def countChar(s, c):
    count = 0
    for ch in s:
        if ch == c:
            count += 1
    return count

מלכודות ומקרי קצה

התעלמות מההבחנה בין אותיות גדולות לקטנות. המרת שני הצדדים לאותיות קטנות גורמת לכך שהשוואה של Banana עם b מחזירה 1; התשובה היא 0.
השוואה של תו למחרוזת. ב-Java, ב-C, ב-C++, ב-C# וב-Go, c מתקבל כמחרוזת, ואילו s[i] או s.charAt(i) הם תו אחד. קח את c[0] (או את c.charAt(0)) פעם אחת לפני הלולאה.
השוואת מחרוזות באמצעות == ב-Java. String.valueOf(s.charAt(i)) == c משווה זהות של אובייקטים, וכמעט תמיד מחזירה false. השווה ערכי char.
קריאה ל-strlen(s) בתנאי הלולאה ב-C. היא סורקת מחדש את המחרוזת בכל צעד, ולכן 5 × 10^4 תווים דורשים בערך 2.5 × 10^9 צעדים.

שאלות נפוצות3

איך סופרים את מספר הפעמים שתו מופיע במחרוזת?

עבור על המחרוזת פעם אחת עם מונה שמתחיל ב־0, והוסף 1 בכל פעם שהתו הנוכחי שווה לתו המבוקש. הפעולה אורכת O(n) זמן ודורשת O(1) זיכרון נוסף. כדי לספור בלי להבחין בין אותיות גדולות לקטנות, המר תחילה לאותיות קטנות גם את המחרוזת וגם את האות.

האם מותר להשתמש בפונקציית ספירה מובנית בריאיון?

בדרך כלל כן, כל עוד אתה יכול לומר מה העלות. הפונקציה str.count של Python ופונקציות דומות עדיין קוראות את כל המחרוזת, ולכן הסיבוכיות שלהן היא O(n). היה מוכן לכתוב את הלולאה אם המראיין יבקש זאת.

איך הייתם סופרים את כל התווים בבת אחת?

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

def countChar(s, c):
    # כתבו כאן קוד

בדיקה #1

בדיקה #2

ארגומנטים

s = "Mississippi"
c = "s"

הפלט הצפוי