开发者

C/C++左旋字符串实现代码举例

目录
  • 题目
  • 改进一:
  • 改进二:
  • 补充:右旋字符串
  • 总结 

题目

实现一个函数,可以左旋字符串中的k个字符。

例如:ABCD左旋一个字符得到BCDA     ABCD左旋两个字符得到CDAB。

设计循环使其可以旋1次,然后让他执行n次是一个最简单的思路:

长度为5的情况下,旋转6、11、16...次相当于1次,7、12、17...次相当于2次,以此类推。

void leftRound(char * src, int time)
{
	int i, j, tmp;
  int len = strlen(src);
  time %= len; 
	for (i = 0; i < time; i++) //执行k次的单次平移
	{
		tmp = src[0];
		for(j = 0; j < len - 1; j++) //单次平移
		{
			src[j] = src[j + 1];
		}
		src[j] = tmp;
	}
}

改进一:

一次一次转比较麻烦,我们可以选择拼接法,一次到位:

void leftRound(char * src, int time)
{
	int l编程客栈en = strlen(src);
	int pos = time % len; //断开位置的下标
	char tmp[256] = { 0 }; //更准确的话可以选择malloc len + 1个字节的空间来做这个tmp
	
	strcpy(tmp, src + pos); //先将后面的全部拷过来
	strncat(tmp, src, pos); //然后将前面几个接上
	strcpy(src, tmp); //最后拷回去
}

改进二:

这个方法要用到一个数组形成的辅助空间,让人觉得有点不爽,还可以有更好的选择,例如ABCDEFG,左旋3次后变成DEFGABC,有一个特殊的操作方式:

先将要左旋的前三个家伙逆序(CBADEFG),然后将后半段也逆序(CBAGFED),最后整体逆序(DEFGABC)即可。这样只需要做数值交换即可,可以写一个函数帮我们完成局部逆序,代码如下:

void reverse_part(char *str, int start, int end) //将字符串从start到end这一段逆序
{
	int i, j;
	char tmp;

	for (i = start, j = end; i < j; i++, j--)
	{
		tmp = str[i];
		str[i] = str[j];
		str[j] = tmp;
	}
}

void leftRound(char * src, int time)
{
	int len = strlen(src);
	int pos = time % len;
	reverse_part(src, 0, pos - 1); //逆序前段
	reverse_part(src, pos, len - 1); //逆序后段
	reverse_part(src, 0, len - 1); //整体逆序
}

补充:右旋字符串

右旋字符串可以通过左旋字符串‘string.size()-k’步来实现。比如,对于字符串abcdefg和右旋2步,我们可以先计算需要左旋的步数为string.size()-2,然后再调用左旋函数即可。

以下为右旋字符串的C++实现代码:

#include <IOStream>
#include <string>

using namespace std;

// 翻转字符串中[start, end]部分
void reverse(string& str, int start, int end) {
    while (start < end) {
        swap(str[start], str[end]);
        start++;
        end--;
    }    
}

// 字android符串右旋k步
string rightRotateString(string str, int k) {
    int len = str.size();
    int left = len-k%len;   // 需要左旋的步数
    // 翻转前left个字符和剩余字符
    reverse(str, 0, left-1);
    reverse(str, left, len-1);
    // 整个字符串翻转
    reverse(str, 0, len-1);
    return str;
}

int main() {
    string str = "abcdefg";
    int k = 2;
    string res = rightRotateStpythonring(str, k);
    cout << "右旋 " << k << " 步后:" << res << endl;
    return 0;
}

在上述代码中,我们定义了与左旋函数相同的翻转函数,并实现了字符串的右旋函数rightRotateString。在函数中,我们先计算需要左旋的步数为string.size()-k,然后调用左旋函数即可。具体来说,我们分别翻转前left个字符和剩余字javascript符,然后再翻转整个字符串。最后,我们将结果返回。在主函数中,我们使用字符串abcdefg,并右旋2步,输出结果为fgabcde

总结 

到此这篇关于C/C++左旋字符串实现的文章就介绍到这了,更多相关C/C++左旋字符串内容请搜索编程客栈(www.devze.com)以前的文章或继续浏览下编程客栈面的相关文章希望大家以后多多支持编程客栈(www.devze.com)!

0

上一篇:

下一篇:

精彩评论

暂无评论...
验证码 换一张
取 消

最新开发

开发排行榜