logo

סיבוב שמאלה של מיתר

ניתן מחרוזת ס ומספר שלם ד המשימה היא ל סיבוב שמאלה  המחרוזת על ידי  ד  עמדות.

10 מיליון

דוגמאות:

קֶלֶט : s = 'GeeksforGeeks' d = 2
תְפוּקָה : 'exforGeeksGe'
הֶסבֵּר : לאחר הסיבוב הראשון מחרוזת s הופכת ל' eeksforGeeksG' ואחרי הסיבוב השני זה הופך ל' exforGeeksGe' .



קֶלֶט : s = 'qwertyu' d = 2
תְפוּקָה : 'ertuqw'
הֶסבֵּר : לאחר המחרוזת הסיבוב הראשונה s הופך ל' ורק' ואחרי הסיבוב השני זה הופך ל' Ertuq' .

תוכן עניינים

טבלת ascii ב-c

[גישה נאיבית] שמאלה סובב אחד אחד

ט הרעיון הוא לאחסן את רֵאשִׁית תו במשתנה ו מִשׁמֶרֶת כל ה נוֹתָר תווים ל שְׁמֹאל לפי עמדה אחת ואז מקם את רֵאשִׁית תו בסוף המחרוזת. תהליך זה חוזר על עצמו ד פִּי.

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).

[גישה טובה יותר] שימוש במערך Char Temporary

הרעיון הוא להשתמש במערך תווים זמני של גודל נ (גודל המחרוזת המקורית). אם יצאנו לסובב את המיתר על ידי ד מציב את האחרון נ – ד אלמנטים יהיו ב חֲזִית והראשון ד אלמנטים יהיו ב סוֹף .

  • העתק את אלמנטים אחרונים (n - ד). של המחרוזת המקורית לתוך הראשון נ – ד עמדות של מערך זמני.
  • לאחר מכן העתק את אלמנטים ד הראשונים של המחרוזת המקורית עד סוף המערך הזמני.
  • לְבָסוֹף לְהַמִיר מערך ה-char הזמני למחרוזת.
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] שימוש באלגוריתם ג'אגלינג

הרעיון מאחורי אלגוריתם הג'אגלינג הוא שאנחנו יכולים לסובב את כל האלמנטים במחזור. כל מחזור הוא עַצמָאִי ומייצג קבוצה של אלמנטים שיעברו בינם לבין עצמם במהלך הסיבוב. אם ה מתחיל אינדקס של מחזור הוא אֲנִי אז האלמנטים הבאים של המחזור יהיו נוכחים במדדים (i + d) % n (i + 2d) % n (i + 3d) % n ... וכן הלאה עד שנגיע חזרה לאינדקס i. המספר הכולל של המחזורים יהיה GCD של n ו-d . ואנחנו מבצעים א סיבוב שמאלה בודד בתוך כל מחזור.

למידע נוסף על אלגוריתם הג'אגלינג עיין במאמר זה - אלגוריתם ג'אגלינג לסיבוב מערך .

C++
// 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).

פקודות kali linux

[גישה צפויה - 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).

צור חידון