字符串左旋右旋问题其实是同理的,下边以左旋为例:
方法一
思路:左旋一次就是将整个字符串向左移一个字符,第一个字符(arr[0]
)移动到最右侧。这样循环操作左旋次数就是最终左旋结果,如上图所示。
实现代码:
void LeftRotate1(char *arr,int count)
{assert(arr);int len = strlen(arr);//左旋count次while (count--){//从前往后移动之前先保存arr[0]char temp = arr[0];int i = 0;///左旋一次//将arr[1]到arr[len-1]往前移动while (i < len - 1){arr[i] = arr[i + 1];i++;}arr[len - 1] = temp;}
}
方法二:
思路:
先将前count
个字符逆置,再将剩余字符逆置,最后整体逆置。如下图所示:
实现代码:
//逆置
void reverse(char *arr, int left, int right)
{while (left < right){char temp = arr[left];arr[left] = arr[right];arr[right] = temp;left++;right--;}
}void LeftRotate2(char *arr, int count)
{int len = strlen(arr);//逆置前count个字符reverse(arr, 0, count - 1);//逆置后len-count个字符reverse(arr, count, len - 1);//整体逆置reverse(arr, 0, len - 1);
}
方法三:
思路:将整个字符串拷贝一份,组成一个长度是原字符串二倍的新字符串,然后从第count
向后取原字符串长度即可。如图所示:
实现代码:
void LeftRotate3(char *arr, int count)
{int len = strlen(arr);//扩容为原字符串长度二倍char *double_arr = (char *)malloc(sizeof(char)*(len * 2 + 1));//copy函数strcpy(double_arr, arr);//字符串连接strcat(double_arr, arr);int i = 0;从第count向后取原字符串长度for (i = 0; i < len; i++){arr[i] = double_arr[i + count];}free(double_arr);
}