Дат низ с и цео број д задатак је да лево ротирати стринг би д позиције.
Примери:
Инпут : с = 'ГеексфорГеекс' д = 2
Излаз : 'екфорГеексГе'
Објашњење : Након прве ротације стринг с постаје ' еексфорГеексГ' а после друге ротације постаје ' екфорГеексГе' .Инпут : с = 'квертиу' д = 2
Излаз : 'ертукв'
Објашњење : Након прве ротације стринг с постаје ' Верк' а после друге ротације постаје ' Ертук' .
Садржај
- [Наивни приступ] Лево Ротирајте један по један
- [Бољи приступ] Коришћење привременог низа знакова
- [Очекивани приступ - 1] Коришћење алгоритма жонглирања
- [Очекивани приступ - 2] Коришћење алгоритма преокрета
[Наивни приступ] Лево Ротирајте један по један
C++Т његова идеја је да се складишти прво знак у променљивој и смена све преостали ликови на лево за једну позицију, а затим поставите прво знак на крају стринга. Овај процес се понавља д пута.
// 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);
Излаз
eksforGeeksGe
Временска сложеност: О(н*д) спољна петља се покреће d времена и кретања унутрашње петље н пута.
Помоћни простор: О(1) ако је стринг променљиво као у Ц++. За непроменљиви низови као у Јава Ц# Питхон и Јавасцрипт, користи се додатни низ знакова величине н тако да ће комплексност простора бити О(н).
[Бољи приступ] Коришћење привременог низа знакова
C++Идеја је да се користи привремени низ знакова величине н (величина оригиналног низа). Ако смо отишли, ротирајте низ д позиционира последње н – д елементи ће бити на фронт и први д елементи ће бити на крај .
- Копирај последњи (н – г) елементи оригиналног низа у први н – д позиције привременог низа.
- Затим копирајте први д елементи оригиналног низа до краја привременог низа.
- Коначно конвертовати привремени низ знакова у стрингу.
// 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);
Излаз
eksforGeeksGe
Временска сложеност: О(н) пошто сваки елемент посећујемо само два пута.
Помоћни простор: О(н) пошто користимо додатни низ знакова.
[Очекивани приступ - 1] Коришћење алгоритма жонглирања
C++Идеја иза алгоритма за жонглирање је да можемо ротирати све елементе у циклусу. Сваки циклус је независни и представља групу елемената који ће се померати између себе током ротације. Ако је почевши индекс циклуса је и тада ће следећи елементи циклуса бити присутни у индексима (и + д) % н (и + 2д) % н (и + 3д) % н ... и тако даље док се не вратимо на индекс и. Укупан број циклуса ће бити ГЦД од н и д . И ми изводимо а појединачна лева ротација унутар сваког циклуса.
Да бисте сазнали више о алгоритму жонглирања, погледајте овај чланак - Алгоритам жонглирања за ротацију низа .
// 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);
Излаз
eksforGeeksGe
Временска сложеност: О(н)
Помоћни простор: О(1) ако је стринг променљиво као у Ц++. За непроменљиви низови као у Јава Ц# Питхон и Јавасцрипт, користи се додатни низ знакова величине н тако да ће комплексност простора бити О(н).
[Очекивани приступ - 2] Коришћење алгоритма преокрета
C++Идеја се заснива на запажању да ако одемо ротирати низ д позиционира последње (н – д) елементи ће бити на предњој страни и први д елементи ће бити на крају.
- Реверсе подниз који садржи прво д елементи низа.
- Реверсе подниз који садржи последњи (н – д) елементи низа.
- Коначно обрнути све елементе од низа.
// 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);
Излаз
eksforGeeksGe
Временска сложеност: О(н) где је н величина датог низа.
Помоћни простор: О(1) ако је стринг променљиво као у Ц++. За непроменљиви низови као у Јава Ц# питхон и Јавасцрипт, користи се додатни низ знакова величине н тако да ће комплексност простора бити О(н).