Duota eilutė s ir sveikasis skaičius d užduotis yra pasukti į kairę eilutę d pozicijų.
Pavyzdžiai:
Įvestis : s = 'GeeksforGeeks' d = 2
Išvestis : 'exforGeeksGe'
Paaiškinimas : Po pirmosios sukimosi eilutės s tampa ' eeksforGeeksG' ir po antrojo pasukimo tampa ' exforGeeksGe' .np taškasĮvestis : s = 'qwertyu' d = 2
Išvestis : "ertuqw"
Paaiškinimas : po pirmosios sukimosi eilutės s tampa ' Werq' ir po antrojo pasukimo tampa ' Ertuq' .
Turinio lentelė
spyruoklinis karkasas
- [Naivus požiūris] Kairėn Pasukti po vieną
- [Geresnis požiūris] Laikinojo char masyvo naudojimas
- [Numatomas metodas – 1] Žongliravimo algoritmo naudojimas
- [Numatomas metodas – 2] Naudojant apversimo algoritmą
[Naivus požiūris] Kairėn Pasukti po vieną
C++T jo idėja yra saugoti pirma simbolis kintamajame ir pamaina visi likę simbolių į paliko per vieną padėtį, tada padėkite pirma simbolis eilutės pabaigoje. Šis procesas kartojamas d kartų.
// C++ Program to left rotate the string by d // positions by rotating one element at a time #include #include using namespace std; void rotateString(string &s int d) { int n = s.size(); // Repeat the rotation d times for (int i = 0; i < d; i++) { // Left rotate the string by one position int first = s[0]; for (int j = 0; j < n - 1; j++) s[j] = s[j + 1]; // Place the first character at the end s[n - 1] = first; } } int main() { string s = 'GeeksforGeeks'; int d = 2; rotateString(s d); cout << s << endl; return 0; }
C // C Program to left rotate the string by d positions // by rotating one element at a time #include #include void rotateString(char s[] int d) { int n = strlen(s); // Repeat the rotation d times for (int i = 0; i < d; i++) { // Left rotate the string by one position char first = s[0]; for (int j = 0; j < n - 1; j++) s[j] = s[j + 1]; // Place the first character at the end s[n - 1] = first; } } int main() { char s[] = 'GeeksforGeeks'; int d = 2; rotateString(s d); printf('%sn' s); return 0; }
Java // 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 # 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# // 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 // 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);
Išvestis
eksforGeeksGe
Laiko sudėtingumas: O(n*d) veikia išorinė kilpa d laikus ir vidinės kilpos eiga n kartų.
Pagalbinė erdvė: O(1), jei eilutė yra kintamas kaip C++. Už nekintančios stygos kaip ir Java C# Python ir Javascript, naudojamas papildomas n dydžio simbolių masyvas, todėl erdvės sudėtingumas bus O(n).
[Geresnis požiūris] Laikinojo char masyvo naudojimas
C++Idėja yra naudoti laikiną simbolių masyvą n (originalios eilutės dydis). Jei palikome, pasukite eilutę d užima paskutinę vietą n – d elementai bus adresu priekyje ir pirmasis d elementai bus adresu pabaiga .
- Nukopijuokite paskutiniai (n – d) elementai originalios eilutės į pirmąją n – d laikino masyvo pozicijos.
- Tada nukopijuokite pirmieji d elementai pradinės eilutės iki laikinojo masyvo pabaigos.
- Pagaliau konvertuoti laikiną char masyvą į eilutę.
// C++ program to left rotate a string by d // position using a temporary array #include #include using namespace std; string rotateString(string &s int d) { int n = s.length(); // Handle cases where d > n d = d % n; char temp[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 to the string return string(temp n); } int main() { string s = 'GeeksforGeeks'; int d = 2; string rotatedString = rotateString(s d); cout << rotatedString << endl; return 0; }
Java // 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 # 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# // 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 // 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);
Išvestis
eksforGeeksGe
Laiko sudėtingumas: O (n), nes kiekvieną elementą aplankome tik du kartus.
Pagalbinė erdvė: O (n), nes naudojame papildomą simbolių masyvą.
[Numatomas metodas – 1] Žongliravimo algoritmo naudojimas
C++Žongliravimo algoritmo idėja yra ta, kad visus elementus galime pasukti ciklo metu. Kiekvienas ciklas yra nepriklausomas ir žymi elementų grupę, kuri sukimosi metu pasislinks tarpusavyje. Jei pradedant ciklo indeksas yra i tada kiti ciklo elementai bus indeksuose (i + d) % n (i + 2d) % n (i + 3d) % n ... ir taip toliau, kol grįžtame prie indekso i. Bendras ciklų skaičius bus n ir d GCD . Ir atliekame a vienas sukimasis į kairę per kiekvieną ciklą.
kino aktorė KajalNorėdami sužinoti daugiau apie žongliravimo algoritmą, skaitykite šį straipsnį - Žongliravimo algoritmas masyvo sukimui .
// C++ Program to left rotate the string by d positions // using Juggling Algorithm #include #include #include using namespace std; void rotateString(string &s int d) { int n = s.size(); // Handle the case where d > size of array d %= n; // Calculate the number of cycles in the rotation int cycles = __gcd(n d); // Perform a left rotation within each cycle for (int i = 0; i < cycles; i++) { // Start element of current cycle char startChar = s[i]; // Start index of current cycle int currIdx = i nextIdx; // Rotate elements till we reach the start of cycle while (true) { nextIdx = (currIdx + d) % n; if (nextIdx == i) break; // Update the next index with the current element s[currIdx] = s[nextIdx]; currIdx = nextIdx; } // Copy the start element of current cycle // at the last index of the cycle s[currIdx] = startChar; } } int main() { string s = 'GeeksforGeeks'; int d = 2; rotateString(s d); cout << s << endl; return 0; }
C // C Program to left rotate the string by d positions // using Juggling Algorithm #include #include void rotateString(char s[] int d) { int n = strlen(s); // Handle the case where d > size of array d %= n; // Calculate the number of cycles in the // rotation int cycles = gcd(n d); // Perform a left rotation within each cycle for (int i = 0; i < cycles; i++) { // Start element of the current cycle char startChar = s[i]; // Start index of the current cycle int currIdx = i nextIdx; // Rotate elements until we return to the // start of the cycle while (1) { nextIdx = (currIdx + d) % n; if (nextIdx == i) break; // Update the current index with the // element at the next index s[currIdx] = s[nextIdx]; currIdx = nextIdx; } // Place the start element of the current // cycle at the last index s[currIdx] = startChar; } } int gcd(int a int b) { if (b == 0) return a; return gcd(b a % b); } int main() { char s[] = 'GeeksforGeeks'; int d = 2; rotateString(s d); printf('%sn' s); return 0; }
Java // 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 # 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# // 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 // 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);
Išvestis
eksforGeeksGe
Laiko sudėtingumas: O(n)
Pagalbinė erdvė: O(1), jei eilutė yra kintamas kaip C++. Už nekintančios stygos kaip ir Java C# Python ir Javascript, naudojamas papildomas n dydžio simbolių masyvas, todėl erdvės sudėtingumas bus O(n).
[Numatomas metodas – 2] Naudojant apversimo algoritmą
C++Idėja pagrįsta pastebėjimu, kad jei paliktume, pasukite eilutę d užima paskutinę vietą (n – d) elementai bus priekyje ir pirmieji d elementai bus pabaigoje.
- Atvirkščiai poeilutė, kurioje yra pirmas d stygos elementai.
- Atvirkščiai poeilutė, kurioje yra paskutinis (n – d) stygos elementai.
- Pagaliau apverskite visus elementus iš stygos.
// C++ program to left rotate a string by d position // using Reversal Algorithm #include #include #include using namespace std; void rotateString(string &s int d) { int n = s.size(); // Handle the case where d > size of array d %= n; // Reverse the first d elements reverse(s.begin() s.begin() + d); // Reverse the remaining n-d elements reverse(s.begin() + d s.end()); // Reverse the entire string reverse(s.begin() s.end()); } int main() { string s = 'GeeksforGeeks'; int d = 2; rotateString(s d); cout << s << endl; return 0; }
Java // 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 # 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# // 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); } }
JavaScript // 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);
Išvestis
eksforGeeksGe
Laiko sudėtingumas: O(n) kur n yra nurodytos eilutės dydis.
Pagalbinė erdvė: O(1), jei eilutė yra kintamas kaip C++. Už nekintančios stygos kaip ir Java C# python ir Javascript, naudojamas papildomas n dydžio simbolių masyvas, todėl erdvės sudėtingumas bus O(n).