טופס מספר מינימלי מהרצף הנתון


רמת קושי בינוני
נשאל לעתים קרובות נאמן אמזון בעברית קנאות גולדמן זאקס אדג 'מידע Snapchat
מערך לערום מחרוזת

הבעיה "טופס מספר מינימלי מרצף נתון" קובעת שקיבלת דפוס כלשהו של אני ו D's רק. המשמעות של I מייצג הגדלה וירידה שמספקים לנו D. הצהרת הבעיה מבקשת להדפיס את המספר המינימלי העונה על הדפוס הנתון. עלינו להשתמש בספרות שבין 1-9 ואין לחזור על ספרות.

דוגמה

DIID
21354

הסבר

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

כך שהפלט יהפוך ל 2 1 3 5 4

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

אלגוריתם ליצירת מספר מינימלי מרצף נתון

  1. בדוק אם אורך הרצף הנתון גדול או שווה ל 9, אם נכון אז החזר -1.
  2. הכריז על מערך שאר בגודל n + 1 והגדר את ערך הספירה ל- 1.
  3. התחל לחצות את המערך בין 0 ל n (כולל).
    1. תבדוק אם i שווה ל n או שהתו הנוכחי של המחרוזת שווה ל"אני ", אם נכון אז
      1. חצו את המערך מהערך הקודם עד -1.
        1. עדכן את הערכים של מערך הפלט על ידי ביצוע השלבים הבאים.
          1. הגדל את ערך הספירה ושמור אותו במערך הפלט.
          2. תבדוק אם j הוא אינדקס הנוכחי גדול מ- 0, וגם התו הנוכחי של המחרוזת הוא "אני", ואז, הפסקה.
  4. החזר תוצאה.

הסבר

בהינתן מחרוזת ושל אני ו- D בלבד, אנו מתבקשים להדפיס את התבנית שניתן ליצור עם הנתון מחרוזת. כאן I מתייחס להגדלה כלומר עלינו ליצור או ליצור מספר מינימלי שיכול להצדיק את הרצף הנתון. נניח שאם אנו אומרים DI, שם D מייצג ירידה במספר המינימלי כך ש- 2 ואחריו יוצרים 21 כמספר מינימלי. לא ניתן לחזור על הספרות, המספר יכול להכיל את הספרות רק בין 1-9. אחרי זה, "אני" שם, עלינו ליצור מספר גדל מינימלי. מאז 21 כבר שם. אנו שואפים ליצור מספר הולך וגדל. לפיכך 1 ואחריו 3, מכיוון ש -2 כבר נמצא בשימוש, ואחריו 3 הוא המספר היחיד שאפשר לחבר אליו.

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

חצו את המחרוזת שקיבלנו כקלט. אם האינדקס הנוכחי שווה לאורך המחרוזת או שהתו הנוכחי שווה ל"אני ". ואז רק אנחנו ממשיכים הלאה. לאחר מכן התחל לעבור מהערך הקודם לערך הנוכחי (i), עד שמגיעים ל -1. בתוך לולאה זו אנו ממשיכים להגדיל את ערך הספירה ולאחסן במערך הפלט באינדקס j + 1. ואז בדוק אם הערך של j גדול או שווה ל- 0 וגם אם הדמות הנוכחית היא "אני". אם נכון, שבור את הלולאה והמשיך הלאה לקבלת תווים נוספים.

קופונים

קוד C ++ ליצירת מספר מינימלי מהרצף הנתון

#include<iostream>

using namespace std;

string getMinimumNumberSeq(string str)
{
    int n = str.length();

    if (n >= 9)
        return "-1";

    string output(n+1, ' ');

    int count = 1;

    for (int i = 0; i <= n; i++)
    {
        if (i == n || str[i] == 'I')
        {
            for (int j = i - 1 ; j >= -1 ; j--)
            {
                output[j + 1] = '0' + count++;
                if(j >= 0 && str[j] == 'I')
                    break;
            }
        }
    }
    return output;
}
int main()
{
    string inputs[] = { "DIID", "ID", "II", "DI", "DDII", "IDID", "IDIDID"};

    for (string input : inputs)
    {
        cout << getMinimumNumberSeq(input) << "\n";
    }
    return 0;
}
21354
132
123
213
32145
13254
1325476

קוד Java כדי ליצור מספר מינימלי מהרצף הנתון

class minimumNumberID
{
    static String getMinimumNumberSeq(String str)
    {
        int n = str.length();

        if (n >= 9)
            return "-1";

        char output[] = new char[n + 1];

        int count = 1;

        for (int i = 0; i <= n; i++)
        {
            if (i == n || str.charAt(i) == 'I')
            {
                for (int j = i - 1; j >= -1; j--)
                {
                    output[j + 1] = (char) ((int) '0' + count++);
                    if (j >= 0 && str.charAt(j) == 'I')
                        break;
                }
            }
        }
        return new String(output);
    }
    public static void main(String[] args)
    {
        String inputs[] = { "DIID", "ID", "II", "DI", "DDII", "IDID", "IDIDID" };

        for(String input : inputs)
        {
            System.out.println(getMinimumNumberSeq(input));
        }
    }
}
21354
132
123
213
32145
13254
1325476

ניתוח מורכבות

מורכבות זמן

עַל) איפה "N" הוא אורך מחרוזת השאילתה. ראשית בדוק שאנחנו נכנסים בתוך הלולאה המקוננת, רק אם הגענו לסוף או אם המדד הנוכחי הוא I. והלולאה המקוננת עוברת בכיוון אחורה ואנחנו יוצאים מהלולאה אם ​​נתקלים ב- I. אז נוכל לומר שאנחנו נכנסים ללולאה המקוננת כאשר אנו נתקלים ב- I ועובדים על מדדים שמאוחסנים בהם D. מכיוון שלכל אינדקס יכולים להיות אני או ד. אנחנו עוברים על כל דמות אחת בלבד. לפיכך מורכבות הזמן היא לינארית.

מורכבות בחלל

עַל), כי יצרנו מערך תווי פלט לאחסון התוצאה. מורכבות החלל לבעיה היא גם לינארית.