logo

Bir Dizinin Sola Dönüşü

Bir dize verildi S ve bir tamsayı D görev sola döndürme  dizeyi şuna göre:  D  pozisyonlar.

Örnekler:

Giriş : s = 'GeeksforGeeks' d = 2
Çıkış : 'exforGeeksGe'
Açıklama : İlk dönüşten sonra dize s ' olur eeksforGeeksG' ve ikinci dönüşten sonra ' olur exforGeeksGe' .



Giriş : s = 'qwertyu' d = 2
Çıkış : 'ertuqw'
Açıklama : İlk dönüşten sonra string s ' olur Werq' ve ikinci dönüşten sonra ' olur Ertuğ' .

İçerik Tablosu

[Naif Yaklaşım] Sola Teker teker Döndür

T onun fikri depolamaktır Birinci Bir değişkendeki karakter ve vardiya hepsi geriye kalan karakterler sol bir pozisyona getirin ve ardından Birinci dizenin sonundaki karakter. Bu işlem tekrarlanır D kez.

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

Çıkış
eksforGeeksGe 

Zaman Karmaşıklığı:  O(n*d) dış döngü çalışır  d   kez ve iç döngü çalışır N  kez.
Yardımcı Alan: O(1) eğer dize değişken C++'daki gibi. İçin değişmez dizeler Java C# Python ve Javascript'te olduğu gibi, n boyutunda ekstra bir karakter dizisi kullanılır, böylece alan karmaşıklığı O(n) olur.

[Daha İyi Yaklaşım] Geçici Karakter Dizisini Kullanma

Buradaki fikir, geçici bir karakter dizisi kullanmaktır. N (orijinal dizenin boyutu). Eğer diziyi sola döndürürsek D son pozisyonlar n – d unsurlar yer alacak ön ve ilk D unsurlar yer alacak son .

Java toplama çerçevesi
  • Kopyala son (n – d) elemanlar orijinal dizenin ilkine n – d geçici dizinin konumları.
  • Daha sonra kopyalayın ilk d elemanları orijinal dizenin geçici dizinin sonuna kadar.
  • Nihayet dönüştürmek dizeye geçici karakter dizisi.
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); 

Çıkış
eksforGeeksGe 

Zaman Karmaşıklığı:  O(n) çünkü her öğeyi yalnızca iki kez ziyaret ediyoruz.
Yardımcı Alan:  O(n) ek bir karakter dizisi kullandığımız için.

[Beklenen Yaklaşım - 1] Hokkabazlık Algoritmasını Kullanma

Hokkabazlık algoritmasının arkasındaki fikir, tüm elemanları döngü halinde döndürebilmemizdir. Her döngü bağımsız ve dönme sırasında kendi aralarında yer değiştirecek bir grup öğeyi temsil eder. Eğer başlangıç bir döngünün indeksi Ben o zaman döngünün sonraki unsurları endekslerde mevcut olacak (i + d) % n (i + 2d) % n (i + 3d) % n ... ve bu şekilde indeks i'ye ulaşana kadar devam ederiz. Toplam döngü sayısı n ve d'nin GCD'si . Ve biz bir performans sergiliyoruz tek sola dönüş her döngünün içinde.

Hokkabazlık algoritması hakkında daha fazla bilgi edinmek için bu makaleye bakın - Dizi Döndürme için Hokkabazlık Algoritması .

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

Çıkış
eksforGeeksGe 

Zaman Karmaşıklığı:  Açık)
Yardımcı Alan: O(1) eğer dize değişken C++'daki gibi. İçin değişmez dizeler Java C# Python ve Javascript'te olduğu gibi, n boyutunda ekstra bir karakter dizisi kullanılır, böylece alan karmaşıklığı O(n) olur.

[Beklenen Yaklaşım - 2] Tersine Çevirme Algoritmasının Kullanılması

Bu fikir, eğer sola dönersek dizeyi şu şekilde döndüreceğimiz gözlemine dayanmaktadır: D son pozisyonlar (n – d) elemanlar önde olacak ve ilk D Öğeler sonunda olacak.

  • Tersi içeren alt dize ilk d dizenin elemanları.
  • Tersi içeren alt dize son (n – d) dizenin elemanları.
  • Nihayet tüm öğeleri tersine çevir dize.
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); 

Çıkış
eksforGeeksGe 

Zaman Karmaşıklığı: O(n) burada n, verilen dizenin boyutudur.
Yardımcı Alan: O(1) eğer dize değişken C++'daki gibi. İçin değişmez dizeler Java C# python ve Javascript'te olduğu gibi, n boyutunda ekstra bir karakter dizisi kullanılır, böylece alan karmaşıklığı O(n) olur.

Test Oluştur