logo

TechCodeview

Linksdrehung einer Saite

Gegeben eine Zeichenfolge S und eine ganze Zahl D Die Aufgabe besteht darin nach links drehen  die Zeichenfolge von  D  Positionen.

Beispiele:

Eingang : s = 'GeeksforGeeks' d = 2
Ausgabe : 'exforGeeksGe'
Erläuterung : Nach der ersten Rotation wird string s zu ' eeksforGeeksG' und nach der zweiten Drehung wird es zu ' exforGeeksGe' .



Eingang : s = 'qwertyu' d = 2
Ausgabe : 'ertuqw'
Erläuterung : Nach der ersten Rotation wird string s zu ' Werq' und nach der zweiten Drehung wird es zu ' Ertuq' .

Java-Concat-String

Inhaltsverzeichnis

[Naiver Ansatz] Nach links drehen, eins nach dem anderen

T Die Idee ist, das zu speichern Erste Zeichen in einer Variablen und Schicht alle übrig Charaktere zum links um eine Position, dann platzieren Sie die Erste Zeichen am Ende der Zeichenfolge. Dieser Vorgang wird wiederholt D mal.

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

Ausgabe 
eksforGeeksGe

Zeitkomplexität:  O(n*d) die äußere Schleife läuft  d   Zeiten und innere Schleifenläufe N  mal.
Hilfsraum: O(1) wenn die Zeichenfolge ist veränderlich wie in C++. Für unveränderliche Zeichenfolgen Wie in Java C#, Python und Javascript wird ein zusätzliches Zeichenarray der Größe n verwendet, sodass die Raumkomplexität O(n) beträgt.

[Besserer Ansatz] Verwendung eines temporären Char-Arrays

Die Idee besteht darin, ein temporäres Zeichenarray mit einer bestimmten Größe zu verwenden N (Größe der Originalzeichenfolge). Wenn wir nach links drehen, drehen wir die Zeichenfolge um D positioniert den letzten n – d Elemente werden am sein Front und das erste D Elemente werden am sein Ende .

  • Kopieren Sie die letzte (n – d) Elemente der ursprünglichen Zeichenfolge in die erste n – d Positionen des temporären Arrays.
  • Dann kopieren Sie die erste d Elemente der ursprünglichen Zeichenfolge bis zum Ende des temporären Arrays.
  • Endlich konvertieren das temporäre char-Array zur Zeichenfolge.
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);

Ausgabe 
eksforGeeksGe

Zeitkomplexität:  O(n), da wir jedes Element nur zweimal besuchen.
Hilfsraum:  O(n), da wir ein zusätzliches Zeichenarray verwenden.

[Erwarteter Ansatz – 1] Verwendung des Jonglieralgorithmus

Die Idee hinter dem Jonglieralgorithmus ist, dass wir alle Elemente im Zyklus drehen können. Jeder Zyklus ist unabhängig und stellt eine Gruppe von Elementen dar, die sich während der Rotation untereinander verschieben. Wenn die beginnend Index eines Zyklus ist ich dann werden die nächsten Elemente des Zyklus in Indizes vorhanden sein (i + d) % n (i + 2d) % n (i + 3d) % n ... und so weiter, bis wir wieder bei Index i ankommen. Die Gesamtzahl der Zyklen beträgt GCD von n und d . Und wir führen eine einzelne Linksdrehung innerhalb jedes Zyklus.

So öffnen Sie eine Datei mit Java

Weitere Informationen zum Jonglieralgorithmus finden Sie in diesem Artikel: Jonglieralgorithmus für Array-Rotation .

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

Ausgabe 
eksforGeeksGe

Zeitkomplexität:  An)
Hilfsraum: O(1) wenn die Zeichenfolge ist veränderlich wie in C++. Für unveränderliche Zeichenfolgen Wie in Java C#, Python und Javascript wird ein zusätzliches Zeichenarray der Größe n verwendet, sodass die Raumkomplexität O(n) beträgt.

[Erwarteter Ansatz – 2] Verwendung des Umkehralgorithmus

Die Idee basiert auf der Beobachtung, dass sich die Zeichenfolge um dreht, wenn wir nach links drehen D positioniert den letzten (n – d) Elemente werden vorne und an erster Stelle stehen D Elemente werden am Ende sein.

  • Umkehren der Teilstring, der die enthält erste d Elemente der Zeichenfolge.
  • Umkehren der Teilstring, der die enthält zuletzt (n – d) Elemente der Zeichenfolge.
  • Endlich alle Elemente umkehren der Saite.
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);

Ausgabe 
eksforGeeksGe

Zeitkomplexität: O(n) wobei n die Größe der angegebenen Zeichenfolge ist.
Hilfsraum: O(1) wenn die Zeichenfolge ist veränderlich wie in C++. Für unveränderliche Zeichenfolgen Wie in Java C# Python und Javascript wird ein zusätzliches Zeichenarray der Größe n verwendet, sodass die Raumkomplexität O(n) beträgt.

Quiz erstellen