כתיבת קוד — שיעור 9

אלגוריתמיקה ומבני נתונים

כל 3 משימות הקוד שנשמרו מהשיעור מופיעות כאן, עם דרישות, דוגמאות וקוד פתיחה. אפשר לכתוב פתרון בעורך המקומי וללחוץ על „בדיקת AI” לקבלת ציון, רמזים והערות.

T2 · בסיסי200 נק'~15 דק'algorithmic

זוג שמסתכם ליעד

נתונה רשימת מספרים שלמים ומספר יעד. החזר True אם קיימים שני איברים *שונים במיקומם* שסכומם שווה ליעד, אחרת False. (זו דוגמת-הזהב A — משמשת כמשימת החימום של שיעור האלגוריתמיקה.)

דוגמאות

has_pair_sum([1,2,3], 5) → True

has_pair_sum([1,2,3], 7) → False

has_pair_sum([3,3], 6) → True

פתרון-ייחוס זוג שמסתכם ליעד ›

def has_pair_sum(nums, target):
    seen = set()
    for n in nums:
        if target - n in seen:
            return True
        seen.add(n)
    return False

הפתרון שלךהפתרון נשמר מקומית אוטומטית.

T3 · בינוני350 נק'~20 דק'algorithmic

קבוצת החזקה (Subsets)

נתונה רשימת מספרים ייחודיים nums. החזר את כל תת-הקבוצות שלה (קבוצת החזקה) לפי הסדר הקנוני: מתחילים מהקבוצה הריקה, ובכל צעד מוסיפים את האיבר הבא לכל תת-הקבוצות שנצברו עד כה. לדוגמה [1,2] → [[], [1], [2], [1,2]].

דוגמאות

subsets([]) → [[]]

subsets([1]) → [[], [1]]

subsets([1,2]) → [[], [1], [2], [1,2]]

פתרון-ייחוס קבוצת החזקה (Subsets) ›

def subsets(nums):
    res = [[]]
    for n in nums:
        res = res + [cur + [n] for cur in res]  # מכפיל את קבוצת-החזקה בכל צעד
    return res

הפתרון שלךהפתרון נשמר מקומית אוטומטית.

T3 · בינוני400 נק'~25 דק'algorithmic

ספירת מופעים במערך ממוין (Binary Search)

נתון מערך ממוין (לא יורד) arr ורשימת שאילתות queries. עבור כל שאילתה q החזר כמה פעמים q מופיע ב-arr, כרשימת תשובות באותו סדר. חובה O(log n) לשאילתה (חיפוש בינארי לגבול שמאלי וימני): קלט של מיליון איברים ועשרות אלפי שאילתות חייב לרוץ בזמן. סריקה לינארית לכל שאילתה (O(n·q)) תיפסל ב-timeout.

דוגמאות

count_occurrences([1,2,2,2,3], [2]) → [3]

count_occurrences([1,2,2,2,3], [4]) → [0]

count_occurrences([1,1,1], [1,2]) → [3, 0]

פתרון-ייחוס ספירת מופעים במערך ממוין (Binary Search) ›

import bisect
def count_occurrences(arr, queries):
    return [bisect.bisect_right(arr, q) - bisect.bisect_left(arr, q)
            for q in queries]              # O(log n) לכל שאילתה

הפתרון שלךהפתרון נשמר מקומית אוטומטית.