S obzirom na niz s i cijeli broj d zadatak je da se lijevo rotirati niz po d pozicije.
Primjeri:
Ulazni : s = 'GeeksforGeeks' d = 2
Izlaz : 'exforGeeksGe'
Obrazloženje : Nakon prve rotacije niz s postaje ' eeksforGeeksG' a nakon druge rotacije postaje ' exforGeeksGe' .Ulazni : s = 'qwertyu' d = 2
Izlaz : 'ertuqw'
Obrazloženje : Nakon prve rotacije niz s postaje ' Werq' a nakon druge rotacije postaje ' Ertuq' .
Sadržaj
- [Naivni pristup] Lijevo Rotirajte jedan po jedan
- [Bolji pristup] Korištenje privremenog niza znakova
- [Očekivani pristup - 1] Korištenje algoritma žongliranja
- [Očekivani pristup - 2] Korištenje algoritma za preokret
[Naivni pristup] Lijevo Rotirajte jedan po jedan
C++T ideja je pohraniti prvi znak u varijabli i pomaknuti sve preostalih likovi za lijevo za jedan položaj, a zatim postavite prvi znak na kraju niza. Ovaj proces se ponavlja d puta.
// 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);
Izlaz
eksforGeeksGe
Vremenska složenost: O(n*d) radi vanjska petlja d puta i unutarnja petlja radi n puta.
Pomoćni prostor: O(1) ako je niz promjenjiv kao u C++. Za nepromjenjivi nizovi kao u Javi C# Python i Javascript koristi se dodatni niz znakova veličine n tako da će prostorna složenost biti O(n).
[Bolji pristup] Korištenje privremenog niza znakova
C++Ideja je koristiti privremeni niz znakova veličine n (veličina originalnog niza). Ako smo lijevo rotirati niz za d pozicije posljednji n – d elementi će biti na ispred i prvi d elementi će biti na kraj .
- Kopiraj posljednji (n – d) elementi izvornog niza u prvi n – d položaji privremenog niza.
- Zatim kopirajte prvih d elemenata izvornog niza do kraja privremenog niza.
- Konačno pretvoriti privremeni niz znakova u niz.
// 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);
Izlaz
eksforGeeksGe
Vremenska složenost: O(n) jer svaki element posjećujemo samo dva puta.
Pomoćni prostor: O(n) jer koristimo dodatni niz znakova.
[Očekivani pristup - 1] Korištenje algoritma žongliranja
C++Ideja iza algoritma žongliranja je da možemo rotirati sve elemente u ciklusu. Svaki ciklus je nezavisna i predstavlja skupinu elemenata koji će se međusobno pomicati tijekom rotacije. Ako je počevši indeks ciklusa je ja tada će sljedeći elementi ciklusa biti prisutni u indeksima (i + d) % n (i + 2d) % n (i + 3d) % n ... i tako dalje dok se ne vratimo na indeks i. Ukupan broj ciklusa bit će GCD od n i d . I izvodimo a jedna lijeva rotacija unutar svakog ciklusa.
Da biste saznali više o algoritmu žongliranja, pogledajte ovaj članak - Algoritam žongliranja za rotaciju niza .
// 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);
Izlaz
eksforGeeksGe
Vremenska složenost: Na)
Pomoćni prostor: O(1) ako je niz promjenjiv kao u C++. Za nepromjenjivi nizovi kao u Javi C# Python i Javascript koristi se dodatni niz znakova veličine n tako da će prostorna složenost biti O(n).
[Očekivani pristup - 2] Korištenje algoritma za preokret
C++Ideja se temelji na zapažanju da ako lijevo okrenemo niz za d pozicije posljednji (n – d) elementi će biti na prednjoj strani i prvi d elementi će biti na kraju.
- Obrnuto podniz koji sadrži prvi d elementi niza.
- Obrnuto podniz koji sadrži posljednji (n – d) elementi niza.
- Konačno obrnuti sve elemente niza.
// 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);
Izlaz
eksforGeeksGe
Vremenska složenost: O(n) gdje je n veličina zadanog niza.
Pomoćni prostor: O(1) ako je niz promjenjiv kao u C++. Za nepromjenjivi nizovi kao u Javi C# python i Javascript koristi se dodatni niz znakova veličine n tako da će složenost prostora biti O(n).