欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

字符串循环左|右移实现(C|C++)

程序员文章站 2022-03-08 14:17:39
...

一、字符串循环右移K位

(1)图解思考

字符串循环左|右移实现(C|C++)

(2)代码实现

  • 时间复杂度O(n) | 空间复杂度O(1)
// 三次翻转实现
#include <iostream>
#include <cstring>

void reverse(char str[],int start,int end){
    for( ;start < end; start++,end--){
        char tmp = str[start];
        str[start] = str[end];
        str[end] = tmp;
        // start++;
        // end--;
    }
}

void rotateStrRight(char str[], int offset,int len){
        if(str == nullptr || len == 0){
            return;
        }
        offset = offset % len;
        // 三次翻转
        reverse(str, 0, len-offset-1);
        reverse(str, len-offset, len-1);
        reverse(str, 0, len-1);
}

int main(){
    int  steps = 2;
    char str[] = "12ab";
    int  len = strlen(str);
    //printf("len = %d\n",len);
    printf("移动前: %s\n", str);
    rotateStrRight(str,steps,len);
    printf("移动后:%s\n", str);
}

二、字符串循环左移K位

(1)说明

 # 字符串循环左移1)左移与右移同理,只是划分段的方向相反,交换区间自然有区别
(2)例如:1234ab,循环左移4(从左划分)31234|ab -> 4321|ab -> 4321|ba -> ab1234
(4)例如:1234ab,循环右移4位
(512|34ab -> 21|34ab -> 21|ba43 -> 34ab12

(2)代码实现

// 三次翻转实现
#include <iostream>
#include <cstring>

void reverse(char str[],int start,int end){
    for( ;start < end; start++,end--){
        char tmp = str[start];
        str[start] = str[end];
        str[end] = tmp;
    }
}

void rotateStrLeft(char str[], int offset,int len){
    if(str == nullptr || len == 0){
        return;
    }
    offset = offset % len;
    // 三次翻转
    reverse(str, 0, offset-1);
    reverse(str, offset, len-1);
    reverse(str, 0, len-1);
}

int main(){
    int  steps = 3;
    char str[] = "1234ab"; // 4ab123
    int  len = strlen(str);
    //printf("len = %d\n",len);
    printf("移动前: %s\n", str);
    rotateStrLeft(str,steps,len);
    printf("移动后:%s\n", str);
}

三、循环左右移结果相同条件

(1)str.length / 2 = offset
(2)测试结果(8/2 = 4)
字符串循环左|右移实现(C|C++)