ex3a.3 שרשרת חוליות

3a3.1 שרשרת המוכלת בשרשרת אחרת

link

במשימה זו, עליכם לממש פעולה סטטית בשם IsSubList במחלקת Solution. פעולה זו תקבל שתי רשימות מקושרות (שרשרת חוליות) ותקבע האם הרשימה הראשונה (list1) היא רשימה חלקית של הרשימה השנייה (list2).

דרישות:

1. שם הפעולה: isSubList
2. קלט:
3. list1: אובייקט מסוג Unit4.Node המייצג את ראש הרשימה המקושרת הראשונה.
4. list2: אובייקט מסוג Unit4.Node המייצג את ראש הרשימה המקושרת השנייה.
5. פלט: bool – תחזיר true אם list1 היא רשימה חלקית של list2, ו-false אחרת.

הגדרה של ‘רשימה חלקית’:

רשימה A נחשבת ל’רשימה חלקית’ של רשימה B אם קיים רצף של צמתים ב-B שערכיהם זהים באופן רציף לכל הערכים ב-A, ובאותו סדר.

1. לדוגמה, הרשימה [1, 2, 3] היא רשימה חלקית של [5, 1, 2, 3, 4].
2. רשימה ריקה (null) נחשבת תמיד לרשימה חלקית של כל רשימה אחרת (כולל רשימה ריקה).

הנחיות נוספות:

1. הפעולה isSubList צריכה להיות סטטית (static).
2. יש לטפל במקרים שבהם אחת או שתי הרשימות ריקות (כלומר, ראש הרשימה הוא null).

    public static bool IsSubList(Node<int> list1, Node<int> list2)
    {
        // Implement your solution here
        return false;
    }

3a3.2 הפיכת רצפים זהים למופע יחיד

link

בתרגיל זה, עליכם לממש פעולה סטטית בשם RemoveSequencesOfIdenticalNumbers בתוך מחלקה בשם Solution. הפעולה תקבל כפרמטר ראש של רשימה מקושרת של מספרים שלמים ותשנה את הרשימה כך שכל רצף של איברים זהים יוחלף במופע בודד של האיבר. כלומר, אם יש רצף של מספרים זהים (לדוגמה, 1, 1, 1), הוא יהפוך לאיבר בודד (1).

הנחיות:

שם הפעולה: RemoveSequencesOfIdenticalNumbers

חתימת הפעולה: הפעולה לא צריכה להחזיר ערך (void), אלא לשנות את הרשימה המקושרת במקום.

התנהגות:

אם הרשימה ריקה או מכילה איבר בודד, אין לבצע שינוי. הפעולה צריכה לעבור על הרשימה ולזהות רצפים של איברים זהים. עבור כל רצף כזה, יש להשאיר רק את האיבר הראשון ברצף ולהסיר את כל האיברים הבאים הזהים לו.

דוגמה לשינוי רשימה:

קלט: 1 -> 1 -> 2 -> 3 -> 3 -> 3 -> 4 -> 5 -> 5 -> null

פלט: 1 -> 2 -> 3 -> 4 -> 5 -> null

    public static void RemoveSequencesOfIdenticalNumbers(Node<int> head)
    {
        // Implement your solution here
    }

3a3.3 הסרת כפילויות גנרי

ניתן לפתור קודם את link

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

דרישות:

1. שם הפעולה: NoDuply
2. חתימה: הפעולה צריכה לקבל צומת ראשון (head) של רשימה מקושרת מסוג Unit4.Node ולהחזיר את הצומת הראשון של הרשימה המעודכנת.
3. התנהגות:
4. הפעולה צריכה להסיר את כל המופעים הכפולים של איברים, כך שכל איבר יופיע פעם אחת בלבד ברשימה הסופית.
5. סדר הופעת האיברים הייחודיים צריך להישמר כפי שהופיעו לראשונה ברשימה המקורית.
6. אם הרשימה ריקה (null) או מכילה איבר אחד בלבד, הפעולה צריכה להחזיר את הרשימה כמות שהיא.

###

    public static Node<T> NoDuply<T>(Node<T> head){
        // Implement your solution here
        return head;
    }

3a3.4 שרשור שתי שרשראות union

link

בתרגיל זה, עליכם לממש פעולה בשם ListsUnion שתקבל שתי רשימות מקושרות ותחזיר רשימה מקושרת חדשה המהווה את איחוד האיברים משתי הרשימות המקוריות.

דרישות:

הפעולה צריכה להחזיר רשימה מקושרת חדשה המכילה את כל האיברים הייחודיים (ללא כפילויות) משתי הרשימות המקוריות. אין חשיבות לסדר האיברים ברשימה המוחזרת. אין למיין את הרשימות המקוריות או את רשימת האיחוד.

קלט:

1. list1: ראש הרשימה המקושרת הראשונה יכולה להיות null אם הרשימה ריקה.
2. list2: ראש הרשימה המקושרת השנייה יכולה להיות null אם הרשימה ריקה.

פלט:

1. ראש רשימה מקושרת חדשה המכילה את איחוד האיברים הייחודיים משתי הרשימות המקוריות. אם שתי הרשימות המקוריות ריקות, הפלט יהיה null.

    public static Node<int> ListsUnion(Node<int> list1, Node<int> list2)
    {
        // Implement your solution here
        return null;
    }

3a3.5 intersect חיתוך שרשראות (במשמעות המתמטית)

link

תיאור המשימה

עליכם לממש פעולה סטטית בשם ListsIntersection במחלקה Solution. פעולה זו תקבל שתי רשימות מקושרות ותחזיר רשימה מקושרת חדשה המכילה את האיברים המשותפים לשתי הרשימות המקוריות, ללא כפילויות.

דרישות:

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

    public static Node<int> ListsIntersection(Node<int> list1, Node<int> list2)
    {
        // Implement your solution here
        return null;
    }

3a3.6 ספירת רצפים ממוינים

link

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

הגדרות

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

דרישות

כללים נוספים:

1. רצף חייב להיות באורך של 3 מספרים חיוביים לפחות.
2. המספר 0 משמש כמפריד רצפים. הוא אינו נחשב חלק מרצף ואינו נכלל בבדיקת המיון או באורך הרצף. הוא רק מאפס את המונה של הרצף הנוכחי.
3. רצף יכול להיות ממוין עולה בלבד או יורד בלבד. לדוגמה, [1, 2, 3] הוא רצף עולה, [5, 4, 3] הוא רצף יורד. [1, 3, 2] אינו רצף ממוין.
4. מספרים חיוביים בלבד נכללים ברצפים. כלומר, אם יש מספרים שליליים, הם אינם חלק מרצף ממוין ואינם נספרים.

    public static int CountSequences(Node<int> head)
    {
        // Implement your solution here
        return 0;
    }

link

דוגמאות

דוגמה 1: רשימה עם מספר רצפים

קלט (ייצוג רשימה מקושרת):[1, 2, 3, 0, 4, 4, 5, 1, 0, 5, 0, 1, 2, 0, 3, 2, 1, 0, 4, 3, 2, 1]

פלט צפוי:3

1. הסבר:
2. הרצף הראשון: [1, 2, 3] (ממוין עולה, אורך 3) - נספר.
3. הקטע [4, 4, 5, 1] אינו רצף ממוין (4,4,5 עולה, אבל 5,1 יורד).
4. הקטע [5] אינו רצף ממוין (אורך 1).
5. הקטע [1, 2] אינו רצף ממוין (אורך 2).
6. הרצף השני: [3, 2, 1] (ממוין יורד, אורך 3) - נספר.
7. הרצף השלישי: [4, 3, 2, 1] (ממוין יורד, אורך 4) - נספר.

דוגמה 2: רשימה ללא רצפים ממוינים

קלט:[1, 5, 2, 0, 8, 7, 9, 0, 3, 1]

פלט צפוי:0

דוגמה 3: רשימה עם רצף בודד

קלט:[10, 20, 30, 40, 0, 5, 4, 3]

פלט צפוי:1

1. הסבר:
2. הרצף הראשון: [10, 20, 30, 40] (ממוין עולה, אורך 4) - נספר.
3. הקטע [5, 4, 3] הוא רצף ממוין יורד, אבל הוא מופיע אחרי ה-0 השני, ולכן לא נספר כחלק מהרצף הראשון. אורך 3, נספר.
4. הדוגמה המקורית מהשאלה היא [1,2,3,0,4,4,5,1,0,5,0,1,2,0,3,2,1,0,4,3,2,1] והפלט הוא 3. בדוגמה זו, [4,4,5,1] אינו רצף ממוין כי יש בו גם עליה וגם ירידה, וגם [5] ו-[1,2] קצרים מדי. לכן, רק [1,2,3], [3,2,1] ו-[4,3,2,1] נספרים. הפלט 3 הוא נכון.

   דוגמאות

דוגמה 1: רשימה עם מספר רצפים

קלט (ייצוג רשימה מקושרת):[1, 2, 3, 0, 4, 4, 5, 1, 0, 5, 0, 1, 2, 0, 3, 2, 1, 0, 4, 3, 2, 1]

פלט צפוי:3

1. הסבר:
2. הרצף הראשון: [1, 2, 3] (ממוין עולה, אורך 3) - נספר.
3. הקטע [4, 4, 5, 1] אינו רצף ממוין (4,4,5 עולה, אבל 5,1 יורד).
4. הקטע [5] אינו רצף ממוין (אורך 1).
5. הקטע [1, 2] אינו רצף ממוין (אורך 2).
6. הרצף השני: [3, 2, 1] (ממוין יורד, אורך 3) - נספר.
7. הרצף השלישי: [4, 3, 2, 1] (ממוין יורד, אורך 4) - נספר.

דוגמה 2: רשימה ללא רצפים ממוינים

קלט:[1, 5, 2, 0, 8, 7, 9, 0, 3, 1]

פלט צפוי:0

דוגמה 3: רשימה עם רצף בודד

קלט:[10, 20, 30, 40, 0, 5, 4, 3]

פלט צפוי:1

1. הסבר:
2. הרצף הראשון: [10, 20, 30, 40] (ממוין עולה, אורך 4) - נספר.
3. הקטע [5, 4, 3] הוא רצף ממוין יורד, אבל הוא מופיע אחרי ה-0 השני, ולכן לא נספר כחלק מהרצף הראשון. אורך 3, נספר.
4. הדוגמה המקורית מהשאלה היא [1,2,3,0,4,4,5,1,0,5,0,1,2,0,3,2,1,0,4,3,2,1] והפלט הוא 3. בדוגמה זו, [4,4,5,1] אינו רצף ממוין כי יש בו גם עליה וגם ירידה, וגם [5] ו-[1,2] קצרים מדי. לכן, רק [1,2,3], [3,2,1] ו-[4,3,2,1] נספרים. הפלט 3 הוא נכון.

3a3.7 פלינדרום ברשימה מקושרת

link

בתרגיל זה, עליכם לממש פעולה סטטית בשם IsPalindrome בתוך מחלקה בשם Solution. הפעולה תקבל כפרמטר ראש של רשימה מקושרת ותחזיר ערך בוליאני (true או false) המציין האם הרשימה המקושרת מהווה פלינדרום.

דרישות נוספות:

1. יש להתייחס למקרים הבאים:
2. רשימה ריקה.
3. רשימה עם איבר אחד.
4. הפעולה צריכה להיות יעילה ככל האפשר מבחינת זמן וזיכרון.

    public static bool isPalindrome(Node<int> head)
    {
        // Implement your solution here
        return false;
    }

3a3.8 מיון לפי זוגיות בשרשרת

link

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

דרישות:

1. לוגיקה:
2. קבעו את הזוגיות של האיבר הראשון ברשימה המקורית. זו תהיה ה’זוגיות הראשית’.
3. סדרו מחדש את הרשימה כך שכל האיברים בעלי ה’זוגיות הראשית’ יופיעו בתחילת הרשימה.
4. אחריהם, יופיעו כל האיברים בעלי הזוגיות הנגדית.
5. חשוב: הסדר היחסי של האיברים בתוך כל קבוצת זוגיות (זוגיות ראשית וזוגיות נגדית) חייב להישמר כפי שהיה ברשימה המקורית.
6. מבנה נתונים: כל הפעולות חייבות להשתמש במבנה הנתונים Unit4.Node המייצג שרשרת חוליות.

הנחיות נוספות:

1. עליכם לטפל במקרה שבו הרשימה ריקה או מכילה רק איבר אחד.
2. הפתרון צריך להיות יעיל ככל האפשר מבחינת זמן ריצה וזיכרון.
3. אין להשתמש במבני נתונים נוספים מלבד Unit4 (לדוגמה, אסור להשתמש במערכים או רשימות רגילות כדי לאחסן את האיברים באופן זמני).

    public static void ParityPartition(Node<int> head)
    {
        // Implement your solution here
    }