הכנסות מינימליות ליצירת פלינדרום עם תמורות מותרות


רמת קושי בינוני
נשאל לעתים קרובות אמזון בעברית CodeNation דירקטי Google אכן אינטואיט
תכנות דינמי מחרוזת

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

דוגמה

הכנסות מינימליות ליצירת פלינדרום עם תמורות מותרות

malyalam
1

הסבר

אם נוכל להוסיף 'a' למחרוזת הראשונית, נוכל ליצור palindrome.

madaam
1

הסבר

הוסף 'd' או 'a' כדי להפוך את המחרוזת המקורית לפלינדרום.

אַלגוֹרִיתְם

  1. הגדר את אורך המחרוזת ל- l ופלט ל -0.
  2. הכריז על מספר שלם מערך.
  3. אחסן ושמור על ספירת כל תו במחרוזת.
  4. חצה את המערך החל מ- 0 עד ש- i <26.
    1. תבדוק אם countChar [i] % 2 == 1,
      1. אם נכון, אז פלט ++.
  5. אם הפלט שווה ל- 0, אז החזר 0.
  6. פלט החזר אחר -1.

הסבר

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

אנו הולכים לספור כל תו במחרוזת הקלט ולאחסן אותו במערך. כפי שכבר הזכרנו, מחרוזת שהיא פלינדרום יכולה לכלול רק תו אחד המתרחש מספר מוזר של פעמים. כך שהפלט יהיה פחות מספירת התווים. לאחר אחסון כל התרחשות מחרוזת תווים במערך. לאחר מכן אנו מייצרים מערך העובר מ- i = 0 ל- i הוא פחות מ 26. זאת מכיוון שיש בסך הכל 26 תווים ועלינו להניח כי תהיה סבירות להתרחשות של 26 תווים במחרוזת נתונה.

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

קופונים

קוד C ++ למציאת הכנסות מינימליות ליצירת פלינדרום עם תמורות מותרות

#include<iostream>

using namespace std;

int getMinimumInsertion(string str)
{
    int l = str.length(),output = 0;

    int countChar[26] = { 0 };
    for (int i = 0; i < l; i++)
        countChar[str[i] - 'a']++;

    for (int i = 0; i < 26; i++)
        if (countChar[i] % 2 == 1)
            output++;

    return (output == 0) ? 0 : output - 1;
}
int main()
{
    string str = "malyalam";
    cout << getMinimumInsertion(str);

    return 0;
}
1

קוד Java למציאת הכנסות מינימליות ליצירת פלינדרום עם תמורות מותרות

class insertionToPalindrome
{
    public static int getMinimumInsertion(String str)
    {
        int l = str.length(),output = 0;

        int countChar[] = new int[26];

        for (int i = 0; i < l; i++)
            countChar[str.charAt(i) - 'a']++;

        for (int i = 0; i < 26; i++)
        {
            if (countChar[i] % 2 == 1)
                output++;
        }

        return (output == 0) ? 0 : output - 1;
    }
    public static void main(String[] args)
    {
        String str = "malyalam";
        System.out.println(getMinimumInsertion(str));
    }
}
1

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

מורכבות זמן

O (n) איפה "N" הוא מספר התווים במחרוזת הקלט.

מורכבות בחלל

O (1), כי יצרנו מערך נוסף בעל גודל קבוע. כך מורכבות החלל קבועה.