מחרוזת הפוכה ללא משתנה זמני  


רמת קושי בינוני
נשאל לעתים קרובות Adobe אמזון בעברית Google Hulu מיקרוסופט מעבדות מונפרוג
Bitwise-XOR מחרוזת

הצהרת בעיה  

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

פורמט הכנסה  

השורה הראשונה המכילה את המחרוזת "s".

פורמט פלט  

הדפס את המחרוזת שהופכת למחרוזת הנתונה.

אילוצים  

  • 1 <= | s | <= 10 ^ 6
  • [i] חייב להיות אלפבית קטן

דוגמה  

tutorialcup
puclairotut

הסבר: "Puclairotut" הוא ההפך מ- "tutorialcup".

אלגוריתם למחרוזת הפוכה ללא משתנה זמני  

1. אחסן את אינדקס ההתחלה ברמה הנמוכה ואינדקס הסיום הגבוה.

2. כאן, מבלי ליצור משתנה זמני להחלפת תווים, אנו משתמשים ב- xor (^).

3. חצו את מחרוזת הקלט "s".

4. החלף בין משתנה ראשון לסוף באמצעות xor.

  • בצע xor s [high] עם s [low] ושמור אותו ב- s [low].
  • כעת, עשה xor של s [low] עם s [high] ושמור אותו ב- s [high].
  • עכשיו שוב, בצע xor s [high] עם s [low] ושמור אותו ב- s [low].

5. החזר את מחרוזת הפלט הסופית.

יישום  

תכנית C ++ להפיכת מחרוזת ללא משתנה זמני

#include <bits/stdc++.h>
using namespace std;
int main()
{
   string s;
   cin>>s;
   int n=s.length();
   int start=0,end=n-1;
   while(start<end)
   {
       s[start]^=s[end];
       s[end]^=s[start];
       s[start]^=s[end];
       start++;
       end--;
   }
   cout<<s<<endl;
   return 0;
}

תוכנית Java להפוך מחרוזת ללא משתנה זמני

import java.util.Scanner;

class sum
{ 
  public static void main(String[] args) 
  { 
    Scanner sr = new Scanner(System.in); 
                String s = sr.next();
                char a[] = s.toCharArray();
    int n = s.length();
                int start = 0, end=n-1;
                while(start<end)
                {
                    a[start]^=a[end];
                    a[end]^=a[start];
                    a[start]^=a[end];
                    end--;
                    start++;
                }
                for(int i=0;i<n;i++)
                System.out.print(a[i]);
                System.out.println();
  } 
} 
answer
rewsna

ניתוח מורכבות למחרוזת הפוכה ללא זמני_משתנה  

מורכבות זמן

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

ראה גם
קידומת להמרה לאינפיקס

מורכבות בחלל

O (1) כי איננו משתמשים בשום שטח עזר כאן. אנו מבצעים את אופרטור ה- xor שלוש פעמים כדי להחליף את הערכים בין שני האינדקסים.