Dat o sfoară s și un număr întreg d sarcina este să roti la stânga șirul de d pozitii.
Exemple:
Intrare : s = „GeeksforGeeks” d = 2
Ieșire : „exforGeeksGe”
Explicaţie : După primul șir de rotație, s devine „ eeksforGeeksG' iar după a doua rotație devine " exforGeeksGe' .Intrare : s = 'qwertyu' d = 2
Ieșire : 'ertuqw'
Explicaţie : După primul șir de rotație, s devine „ Werq' iar după a doua rotație devine " Ertuq' .
Cuprins
- [Abordare naivă] Rotiți la stânga unul câte unul
- [Abordare mai bună] Utilizarea matricei de caractere temporare
- [Abordare așteptată - 1] Utilizarea algoritmului de jonglare
- [Abordare așteptată - 2] Utilizarea algoritmului de inversare
[Abordare naivă] Rotiți la stânga unul câte unul
C++T ideea este de a stoca primul caracter într-o variabilă și schimbare toate ramanand personaje la stânga de o poziție apoi plasați primul caracter la sfârșitul șirului. Acest proces se repetă d ori.
// C++ Program to left rotate the string by d // positions by rotating one element at a time #include
// C Program to left rotate the string by d positions // by rotating one element at a time #include
// Java Program to left rotate the string by d positions // by rotating one element at a time import java.util.Arrays; class GfG { static String rotateString(String s int d) { // Convert the string to a char array char[] charArray = s.toCharArray(); int n = charArray.length; // Perform the rotation d times for (int i = 0; i < d; i++) { // Store the first character char first = charArray[0]; // Shift each character one position to // the left for (int j = 0; j < n - 1; j++) charArray[j] = charArray[j + 1]; // Move the first character to the end charArray[n - 1] = first; } return new String(charArray); } public static void main(String[] args) { String s = 'GeeksforGeeks'; int d = 2; String rotatedString = rotateString(s d); System.out.println(rotatedString); } }
# python Program to left rotate the string by d # positions by rotating one element at a time def rotateString(s d): # Convert the string to a list of # characters s = list(s) n = len(s) # Perform the rotation d times for _ in range(d): # Store the first character first = s[0] # Shift each character one # position to the left for i in range(n - 1): s[i] = s[i + 1] # Move the first character to the end s[n - 1] = first # Convert the list back to a string return ''.join(s) s = 'GeeksforGeeks' d = 2 rotatedString = rotateString(s d) print(rotatedString)
// C# Program to left rotate the string by d positions // by rotating one element at a time using System; class GfG { static string rotateString(string s int d) { // Convert the string to a character array char[] charArray = s.ToCharArray(); int n = charArray.Length; // Perform the rotation d times for (int i = 0; i < d; i++) { // Store the first character char first = charArray[0]; // Shift each character one position to // the left for (int j = 0; j < n - 1; j++) charArray[j] = charArray[j + 1]; // Move the first character to the end charArray[n - 1] = first; } // Convert the character array to a string return new string(charArray); } static void Main() { string s = 'GeeksforGeeks'; int d = 2; string rotatedString = rotateString(s d); Console.WriteLine(rotatedString); } }
// Javascript Program to left rotate the string by d positions // by rotating one element at a time function rotateString(s d) { // Convert the string to an array let charArray = s.split(''); let n = charArray.length; // Perform the rotation d times for (let i = 0; i < d; i++) { // Store the first character let first = charArray[0]; // Shift each character one position to the left for (let j = 0; j < n - 1; j++) charArray[j] = charArray[j + 1]; // Move the first character to the end charArray[n - 1] = first; } // Convert the array back to a string return charArray.join(''); } let s = 'GeeksforGeeks'; let d = 2; let rotatedString = rotateString(s d); console.log(rotatedString);
Ieșire
eksforGeeksGe
Complexitatea timpului: O(n*d) bucla exterioară rulează d timpi și cicluri de buclă interioară n ori.
Spațiu auxiliar: O(1) dacă șirul este mutabil ca în C++. Pentru șiruri imuabile ca și în Java C# Python și Javascript, este utilizată o matrice suplimentară de caractere de dimensiune n, astfel încât complexitatea spațiului va fi O(n).
[Abordare mai bună] Utilizarea matricei de caractere temporare
C++Ideea este să folosiți o matrice temporară de caractere de dimensiune n (dimensiunea șirului original). Dacă am plecat rotiți șirul cu d poziționează ultimul n – d elementele vor fi la faţă iar primul d elementele vor fi la Sfârşit .
- Copiați ultimele (n – d) elemente de șir original în primul n – d pozițiile matricei temporare.
- Apoi copiați primele d elemente a șirului original până la sfârșitul matricei temporare.
- in sfarsit convertit matricea temporară de caractere la șir.
// C++ program to left rotate a string by d // position using a temporary array #include
// Java program to left rotate a string by d position // using a temporary array import java.io.*; class GfG { static String rotateString(String s int d) { int n = s.length(); // Handle cases where d > n d = d % n; char[] temp = new char[n]; // Copy the last (n - d) characters to the // start of temp array for (int i = 0; i < n - d; i++) temp[i] = s.charAt(d + i); // Copy the first d characters to the end of // temp array for (int i = 0; i < d; i++) temp[n - d + i] = s.charAt(i); // Convert the temp array back to the String return new String(temp); } public static void main(String[] args) { String s = 'GeeksforGeeks'; int d = 2; String rotatedString = rotateString(s d); System.out.println(rotatedString); } }
# Python program to left rotate a string # by d position using a temporary array def rotateString(s d): n = len(s) # Handle cases where d > n d = d % n # Create a temporary array of the # same length as s temp = [''] * n # Copy the last (n - d) characters # to the start of temp array for i in range(n - d): temp[i] = s[d + i] # Copy the first d characters to the #end of temp array for i in range(d): temp[n - d + i] = s[i] # Convert temp array back to the string return ''.join(temp) s = 'GeeksforGeeks' d = 2 rotatedString = rotateString(s d) print(rotatedString)
// C# program to left rotate a string by d position // using temporary array using System; class GfG { static string rotateString(string s int d) { int n = s.Length; // Handle cases where d > n d = d % n; char[] temp = new char[n]; // Copy the last (n - d) characters // to the start of temp array for (int i = 0; i < n - d; i++) temp[i] = s[d + i]; // Copy the first d characters to the end // of temp array for (int i = 0; i < d; i++) temp[n - d + i] = s[i]; // Convert temp array back to the string return new string(temp); } static void Main() { string s = 'GeeksforGeeks'; int d = 2; string rotatedString = rotateString(s d); Console.WriteLine(rotatedString); } }
// Javascript program to left rotate a string // by d position using temporary array function rotateString(s d) { let n = s.length; // Handle cases where d > n d = d % n; let temp = new Array(n); // Copy the last (n - d) characters to // the start of temp array for (let i = 0; i < n - d; i++) temp[i] = s[d + i]; // Copy the first d characters // to the end of temp array for (let i = 0; i < d; i++) temp[n - d + i] = s[i]; // Convert the array back to the string return temp.join(''); } let s = 'GeeksforGeeks'; let d = 2; let rotatedString = rotateString(s d); console.log(rotatedString);
Ieșire
eksforGeeksGe
Complexitatea timpului: O(n) deoarece vizităm fiecare element doar de două ori.
Spațiu auxiliar: O(n) deoarece folosim o matrice de caractere suplimentară.
[Abordare așteptată - 1] Utilizarea algoritmului de jonglare
C++Ideea din spatele algoritmului de jonglare este că putem roti toate elementele în ciclu. Fiecare ciclu este independent și reprezintă un grup de elemente care se vor deplasa între ele în timpul rotației. Dacă pornire indicele unui ciclu este i apoi următoarele elemente ale ciclului vor fi prezente la indici (i + d) % n (i + 2d) % n (i + 3d) % n ... și așa mai departe până ajungem înapoi la indexul i. Numărul total de cicluri va fi GCD de n și d . Și executăm a o singură rotație la stânga în cadrul fiecărui ciclu.
Pentru a afla mai multe despre algoritmul de jonglerie, consultați acest articol - Algoritmul de jonglare pentru rotația matricei .
// C++ Program to left rotate the string by d positions // using Juggling Algorithm #include
// C Program to left rotate the string by d positions // using Juggling Algorithm #include
// Java Program to left rotate the string by d positions // using Juggling Algorithm import java.io.*; class GfG { static String rotateString(String s int d) { int n = s.length(); // Handle the case where // d > size of the string d %= n; // Calculate the number of // cycles (GCD of n and d) int cycles = gcd(n d); // Convert string to character array char[] arr = s.toCharArray(); // Perform a left rotation within each cycle for (int i = 0; i < cycles; i++) { // Start element of current cycle char temp = arr[i]; int j = i; while (true) { int k = (j + d) % n; if (k == i) { break; } // Move the element to the next index arr[j] = arr[k]; j = k; } // Place the saved element in the // last position of the cycle arr[j] = temp; } // Convert the rotated character // array back to a string return new String(arr); } // function to calculate GCD of two numbers static int gcd(int a int b) { if (b == 0) { return a; } return gcd(b a % b); } public static void main(String[] args) { String s = 'GeeksforGeeks'; int d = 2; String rotatedString = rotateString(s d); System.out.println(rotatedString); } }
# python Program to left rotate the string by # d positions using Juggling Algorithm def gcd(a b): while b: a b = b a % b return a def rotateString(s d): n = len(s) # Handle the case where d > size of # the string d %= n # Calculate the number of cycles (GCD # of n and d) cycles = gcd(n d) # Convert string to a list of characters arr = list(s) # Perfrom a left rotation wihtin each cycle for i in range(cycles): # Start element of current cycle temp = arr[i] j = i while True: k = (j + d) % n if k == i: break # Move the element to the next # index arr[j] = arr[k] j = k # Place the saved element in the last # position of the cycle arr[j] = temp # Convert the list of characters back to # a string and return return ''.join(arr) s = 'GeeksforGeeks' d = 2 rotatedString = rotateString(s d) print(rotatedString)
// C# Program to left rotate the string by d positions // using Juggling Algorithm using System; class GfG { static int Gcd(int a int b) { while (b != 0) { int temp = b; b = a % b; a = temp; } return a; } static string rotateString(string s int d) { int n = s.Length; // Handle the case where d > size of the string d %= n; // Calculate the number of cycles (GCD of n and d) int cycles = Gcd(n d); // Convert string to a character array char[] arr = s.ToCharArray(); // Perform a left rotation within each cycle for (int i = 0; i < cycles; i++) { // Start element of the current cycle char temp = arr[i]; int j = i; while (true) { int k = (j + d) % n; if (k == i) break; // Move the element to the next index arr[j] = arr[k]; j = k; } // Place the saved element in the last position // of the cycle arr[j] = temp; } // Convert the character array back to a string return new string(arr); } static void Main() { string s = 'GeeksforGeeks'; int d = 2; string rotatedString = rotateString(s d); Console.WriteLine(rotatedString); } }
// JavaScript Program to left rotate the string by d // positions using Juggling Algorithm function gcd(a b) { while (b !== 0) { let temp = b; b = a % b; a = temp; } return a; } function rotateString(s d) { let n = s.length; // Handle the case where d > size of the string d %= n; // Calculate the number of cycles (GCD of n and d) let cycles = gcd(n d); // Convert string to a character array let arr = s.split(''); // Perform a left rotation within each cycle for (let i = 0; i < cycles; i++) { // Start element of the current cycle let temp = arr[i]; let j = i; while (true) { let k = (j + d) % n; if (k === i) { break; } // Move the element to the next index arr[j] = arr[k]; j = k; } // Place the first element in the last position // of the cycle arr[j] = temp; } // Convert the character array back to a string return arr.join(''); } let s = 'GeeksforGeeks'; let d = 2; let rotatedString = rotateString(s d); console.log(rotatedString);
Ieșire
eksforGeeksGe
Complexitatea timpului: Pe)
Spațiu auxiliar: O(1) dacă șirul este mutabil ca în C++. Pentru șiruri imuabile ca și în Java C# Python și Javascript, este utilizată o matrice suplimentară de caractere de dimensiune n, astfel încât complexitatea spațiului va fi O(n).
[Abordare așteptată - 2] Utilizarea algoritmului de inversare
C++Ideea se bazează pe observația că, dacă am plecat, rotim șirul d poziționează ultimul (n – d) elementele vor fi în față și primul d elementele vor fi la final.
- Verso subșirul care conține primul d elementele șirului.
- Verso subșirul care conține ultimul (n – d) elementele șirului.
- in sfarsit inversează toate elementele de sfoară.
// C++ program to left rotate a string by d position // using Reversal Algorithm #include
// Java program to left rotate a string by d position // using Reversal Algorithm import java.io.*; class GfG { static String rotateString(String s int d) { int n = s.length(); // Handle the case where d > size of string d %= n; // Convert string to a character array char[] temp = s.toCharArray(); // Reverse the first d elements reverse(temp 0 d - 1); // Reverse the remaining n-d elements reverse(temp d n - 1); // Reverse the entire array reverse(temp 0 n - 1); // Convert the array back to a string and return return new String(temp); } static void reverse(char[] temp int start int end) { while (start < end) { char c = temp[start]; temp[start] = temp[end]; temp[end] = c; start++; end--; } } public static void main(String[] args) { String s = 'GeeksforGeeks'; int d = 2; String rotatedString = rotateString(s d); System.out.println(rotatedString); } }
# Python program to left rotate a string by d positons # using Reversal Algorithm def rotateString(s d): n = len(s) # Handle cases where d > n d %= n # Convert the string to a list of characters temp = list(s) # Reverse the first d elements reverse(temp 0 d - 1) # Reverse the remaining n - d elements reverse(temp d n - 1) # Reverse the entire array reverse(temp 0 n - 1) # Convert the list back to a string and return return ''.join(temp) def reverse(temp start end): while start < end: temp[start] temp[end] = temp[end] temp[start] start += 1 end -= 1 s = 'GeeksforGeeks' d = 2 rotatedString = rotateString(s d) print(rotatedString)
// C++ program to left rotate a string by d positions // using Reversal Algorithm using System; class GfG { static string RotateString(string s int d) { int n = s.Length; // Handle cases where d > n d %= n; // Convert the string to a character array char[] temp = s.ToCharArray(); // Reverse the first d elements Reverse(temp 0 d - 1); // Reverse the remaining n - d elements Reverse(temp d n - 1); // Reverse the entire array Reverse(temp 0 n - 1); // Convert the character array back to a string return new string(temp); } static void Reverse(char[] temp int start int end) { while (start < end) { char c = temp[start]; temp[start] = temp[end]; temp[end] = c; start++; end--; } } static void Main() { string s = 'GeeksforGeeks'; int d = 2; string rotatedString = RotateString(s d); Console.WriteLine(rotatedString); } }
// C++ program to left rotate a string by d position // using Reversal Algorithm function rotateString(s d) { const n = s.length; // Handle cases where d > n d %= n; // Convert the string to a character array let temp = s.split(''); // Reverse the first d elements reverse(temp 0 d - 1); // Reverse the remaining n - d elements reverse(temp d n - 1); // Reverse the entire array reverse(temp 0 n - 1); // Convert the array back to a string return temp.join(''); } function reverse(temp start end) { while (start < end) { // Swap elements [temp[start] temp[end]] = [temp[end] temp[start]]; start++; end--; } } let s = 'GeeksforGeeks'; let d = 2; let rotatedString = rotateString(s d); console.log(rotatedString);
Ieșire
eksforGeeksGe
Complexitatea timpului: O(n) unde n este dimensiunea șirului dat.
Spațiu auxiliar: O(1) dacă șirul este mutabil ca în C++. Pentru șiruri imuabile ca și în Java C# python și Javascript, este folosită o matrice suplimentară de caractere de dimensiune n, astfel încât complexitatea spațiului va fi O(n).