C++程序交换字符串中的字符

给定长度为 N 的字符串 S ，以及两个整数 B 和 C ，任务是从开头开始遍历字符，将一个字符与它后面第C个地方的字符交换位置，即交换位置为 i 和 (i + C)%N 的字符。重复进行这个过程 B 次，每次向前移动一个位置。您的任务是找到进行 B 次交换后的最终字符串。

例子：

输入： S = “ABCDEFGH”, B = 4, C = 3;
输出： DEFGBCAH
解释：
经过第一次交换：DBCAEFGH
经过第二次交换：DECABFGH
经过第三次交换：DEFABCGH
经过第四次交换：DEFGBCAH

输入： S = “ABCDE”, B = 10, C = 6;
输出： ADEBC
解释：
经过第一次交换：BACDE
经过第二次交换：BCADE
经过第三次交换：BCDAE
经过第四次交换：BCDEA
经过第五次交换：ACDEB
经过第六次交换：CADEB
经过第七次交换：CDAEB
经过第八次交换：CDEAB
经过第九次交换：CDEBA
经过第十次交换：ADEBC

Naive Approach：

对于较大的 B 值，每次循环 B 次，每次将第 i 个字符与 (i + C)%N 个字符交换，将导致高CPU时间。
解决此问题的技巧是观察每次迭代后的结果，每次迭代 N 次，其中 N 是字符串 S 的长度。
再次，如果 C 大于或等于 N ，则它等效于 C 除以 N 的余数。
此后，让我们将 C 视为小于 N 。

下面是该方法的实施：

// C++ Program to Swap characters in a String
#include <iostream>
#include <string>
 
using namespace std;
 
string swapCharacters(string s, int B, int C)
{
    int N = s.size();
    // If c is greater than n
    C = C % N;
    // loop to swap ith element with (i + C) % n th element
    for (int i = 0; i < B; i++) {
               swap(s[i % N], s[(i + C) % N]);
    }
    return s;
}
 
int main()
{
    string s = "ABCDEFGH";
    int B = 4;
    int C = 3;
    s = swapCharacters(s, B, C);
    cout << s << endl;
    return 0;
}
 
// This code is contributed by Susobhan Akhuli```

输出

DEFGBCAH

时间复杂度: O(B)，迭代B次。

空间复杂度: O(1)

高效做法:

如果我们观察每次连续交换后形成的字符串（假定称之为一个完整迭代），我们可以开始找到一种模式。
我们可以发现该字符串被分成两部分：长度为 C 的第一部分由 S 的前 C 个字符组成，第二个部分由其余字符组成。
两部分被旋转了一些位置。第一部分每次完整迭代向右旋转 (N % C) 个位置。
第二部分每次完整迭代向左旋转 C 个位置。
我们可以通过将 B 除以 N 来计算完整迭代数量 f 。
因此，第一部分将向左旋转 ( N % C ) * f 。这个值可能超过 C ，所以实际上是 ( ( N % C ) * f ) % C ，即第一部分将向左旋转 ( ( N % C ) * f ) % C 个位置。
第二部分将左移 C * f 个位置。由于此值可能超过第二部分的长度 ( N – C ) ，因此有效值为 ( ( C * f ) % ( N – C ) ) ，即第二部分将向左旋转 ( ( C * f ) % ( N – C ) ) 个位置。
经过 f 个完整迭代后，可能仍然剩余一些迭代以完成 B 个迭代。该值为 B % N ，小于 N 。在完整迭代后，我们可以按照朴素的方法处理这些剩余迭代，以获得结果字符串。

示例：

s = ABCDEFGHIJK; c = 4;

部分：ABCD EFGHIJK

一次完整迭代后：DABC IJKEFGH

两次完整迭代后：CDAB FGHIJKE

三次完整迭代后：BCDA JKEFGHI

四次完整迭代后：ABCD GHIJKEF

五次完整迭代后：DABC KEFGHIJ

六次完整迭代后：CDAB HIJKEFG

七次完整迭代后：BCDA EFGHIJK

八次完整迭代后：ABCD IJKEFGH

下面是该方法的实现：

// C++程序找到交换位置i和i+c后新的字符串
// b次，每次前进一位
#include <bits/stdc++.h>
using namespace std;
 
string rotateLeft(string s, int p)
{
     
    //将一个字符串向左转动p次，实际上是将前p个
    //字符剪切到字符串的末尾
    return s.substr(p) + s.substr(0, p);
}
 
//方法找到需要的字符串
string swapChars(string s, int c, int b)
{
     
    //获取字符串长度
    int n = s.size();
     
    //如果c大于或等于字符串长度，则实际上是
    //c除以字符串长度的余数
    c = c % n;
     
    if (c == 0)
    {
         
        //不会发生任何改变
        return s;
    }
    int f = b / n;
    int r = b % n;
     
    //将前c个字符旋转(n % c)*f%c**位**
    //位置f次
    string p1 = rotateLeft(s.substr(0, c),
                  ((n % c) * f) % c);
                   
    //将剩余的字符旋转n*f个位置
    string p2 = rotateLeft(s.substr(c),((c * f) % (n - c)));
                   
    //连接两个部分并将
    //完整迭代后形成的结果字符串转换为字符串数组
    //（用于最后的交换）
    string a = p1 + p2;
     
    //剩余交换
    for(int i = 0; i < r; i++)
    {
         
        //将第i个字符与
        //（i + c）th字符交换
        char temp = a[i];
        a[i] = a[(i + c) % n];
        a[(i + c) % n] = temp;
    }
     
    //返回最终字符串
    return a;
}
 
//驱动程序
int main()
{
     
    //给定值
    string s1 = "ABCDEFGHIJK";
    int b = 1000;
    int c = 3;
     
    //获取最终字符串并打印最终字符串
    cout << swapChars(s1, c, b) << endl;
}
 
//此代码由rag2127提供```

输出: