نظرا لسلسلة ق وعدد صحيح د المهمة هي تدوير اليسار السلسلة بواسطة د المواقف.
أمثلة:
مدخل : s = 'GeeksforGeeks' d = 2
الإخراج : 'exforGeeksGe'
توضيح : بعد أن تصبح سلسلة التدوير الأولى s ' eeksforGeeksG' وبعد الدورة الثانية يصبح " exforGeeksGe' .مدخل : s = 'qwertyu' d = 2
الإخراج : "ارتق"
توضيح : بعد سلسلة التدوير الأولى تصبح s ' ويرق وبعد الدورة الثانية يصبح " إرتوق .
جدول المحتويات
- [نهج ساذج] قم بالتدوير لليسار واحدًا تلو الآخر
- [نهج أفضل] استخدام مصفوفة الأحرف المؤقتة
- [النهج المتوقع - 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
تعقيد الوقت: O(n*d) تعمل الحلقة الخارجية d الأوقات وتشغيل الحلقة الداخلية ن مرات.
المساحة المساعدة: O(1) إذا كانت السلسلة متقلب كما هو الحال في C ++. ل سلاسل غير قابلة للتغيير كما هو الحال في Java C# Python وJavascript، يتم استخدام مجموعة أحرف إضافية بالحجم n بحيث يكون تعقيد المساحة هو O(n).
[نهج أفضل] استخدام مصفوفة الأحرف المؤقتة
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
تعقيد الوقت: O(n) لأننا نزور كل عنصر مرتين فقط.
المساحة المساعدة: O(n) لأننا نستخدم مصفوفة أحرف إضافية.
[النهج المتوقع - 1] استخدام خوارزمية ألعاب الخفة
C++الفكرة وراء خوارزمية اللعب هي أنه يمكننا تدوير جميع العناصر في الدورة. كل دورة هي مستقل ويمثل مجموعة من العناصر التي سوف تتحول فيما بينها أثناء الدوران. إذا البدء مؤشر الدورة هو أنا ثم العناصر التالية للدورة ستكون موجودة في المؤشرات (ط + د)٪ ن (ط + 2 د)٪ ن (ط + 3D)٪ ن ... وهكذا حتى نعود إلى الفهرس الأول. العدد الإجمالي للدورات سيكون GCD من ن ود . ونقوم أ دوران يسار واحد داخل كل دورة.
لمعرفة المزيد عن خوارزمية Juggling، راجع هذه المقالة - خوارزمية شعوذة لتدوير الصفيف .
// 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
تعقيد الوقت: على)
المساحة المساعدة: O(1) إذا كانت السلسلة متقلب كما هو الحال في C ++. ل سلاسل غير قابلة للتغيير كما هو الحال في Java C# Python وJavascript، يتم استخدام مجموعة أحرف إضافية بالحجم n بحيث يكون تعقيد المساحة هو O(n).
[النهج المتوقع - 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
تعقيد الوقت: O(n) حيث n هو حجم السلسلة المحددة.
المساحة المساعدة: O(1) إذا كانت السلسلة متقلب كما هو الحال في C ++. ل سلاسل غير قابلة للتغيير كما هو الحال في Java C# python وJavascript، يتم استخدام مجموعة أحرف إضافية بالحجم n بحيث يكون تعقيد المساحة هو O(n).