C语言——oj刷题——字符串左旋和轮转数组

简介: C语言——oj刷题——字符串左旋和轮转数组

第一题:字符串左旋

问题:

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

例如:

ABCD左旋一个字符得到BCDA

ABCD左旋两个字符得到CDAB

实现:

当我们谈到字符串左旋时,我们指的是将字符串中的字符向左移动一定数量的位置。这个问题在编程中非常常见,特别是在字符串处理和算法实现中。

在C语言中,我们可以使用一种简单而有效的方法来完成字符串的左旋操作。下面是一个示例代码,演示了如何实现字符串左旋:

#include <stdio.h>
#include <string.h>
 
void reverse(char* str, int start, int end) {
    while (start < end) {
        char temp = str[start];
        str[start] = str[end];
        str[end] = temp;
        start++;
        end--;
    }
}
 
void leftRotateString(char* str, int k) {
    int len = strlen(str);
    k = k % len;  // 处理k大于字符串长度的情况
    reverse(str, 0, k - 1);  // 反转前k个字符
    reverse(str, k, len - 1);  // 反转剩余的字符
    reverse(str, 0, len - 1);  // 整体反转字符串
}
 
int main() {
    char str[] = "abcdefg";
    int k = 2;  // 左旋2个位置
 
    printf("原始字符串: %s\n", str);
    leftRotateString(str, k);
    printf("左旋后的字符串: %s\n", str);
 
    return 0;
}

在上面的示例代码中,我们定义了两个辅助函数:reverse和leftRotateString。


reverse函数用于反转字符串中指定范围内的字符。它使用两个指针(start和end)来遍历字符串,交换对应位置上的字符,直到两个指针相遇。


leftRotateString函数是实现字符串左旋的核心函数。它首先计算旋转位置k与字符串长度的余数,以处理k大于字符串长度的情况。然后,它分别对前k个字符、剩余字符和整个字符串进行反转操作,最终完成字符串的左旋。


在main函数中,我们定义了一个示例字符串"abcdefg"和旋转位置k为2。我们先打印出原始字符串,然后调用leftRotateString函数进行左旋操作,最后打印出左旋后的字符串。


运行上述代码,输出将是:

原始字符串: abcdefg

左旋后的字符串: cdefgab

这就是用C语言完成字符串左旋的方法和示例代码。希望对你有所帮助!如果有任何问题,请随时提问。

第二题:轮转数组(力扣189)

解法一:(暴力解法)

利用循环每次移动一位,代码如下:

//暴力做法

void rotate(int* nums, int numsSize, int k){
    k=k%numsSize;
    int temp;
    while(k--)
    {
        temp=nums[numsSize-1];
        for(int i=numsSize-1;i>0;i--)
        {
            nums[i]=nums[i-1];
        }
        nums[0]=temp;
    }

这种做法应该很好理解,但它的时间复杂度是O(n^2)的,会超时。

解法二:(时间换空间)

利用额外的数组实现,把移动完的数据放在一个新的数组里面去,然后再拷贝回来,代码如下:

void rotate(int*nums,int numsSize,int k)
{
    k=k%numsSize;
    int i,j;
    int a[100000];
    j=numsSize-k;
    for(i=0;i<k;i++) a[i]=nums[j++];
    j=0;
    for(;i<numsSize;i++) a[i]=nums[j++];
    for(i=0;i<numsSize;i++)
    {
        nums[i]=a[i];
    }
}

这样的解法时间复杂度符合要求,但是需要额外的空间实现。

解法三:(前后翻转)

先旋转前面的那部分,在旋转后面的那部分,然后再旋转整个数组。

void swap(int *a,int *b)
{
    int t;
    t=*a;
    *a=*b;
    *b=t;
}
void reverse(int *begin,int *end)
{
    while(begin<end)
    {
        swap(begin,end);
        begin++;
        end--;
    }
}
void rotate(int* nums, int numsSize, int k)
{
    k=k%numsSize;
    reverse(nums,nums+numsSize-k-1);
    reverse(nums+numsSize-k,nums+numsSize-1);
    reverse(nums,nums+numsSize-1);
}

解法四:(环状旋转)

解题思路:

把数组看成一个环状的。按照题目的意思,我们应当让每一个元素往后面走k步,假设x为元素下标,那么它应该到(x+k)%numsSize的地方上去,如图:

我们想把1挪到4的位置上去,直接挪的话,4就会消失,那怎么办呢?可以这样做,申请一个变量temp,先让temp=nums[0],然后temp与nums[3]交换

此时,1已经到4的位置上去了,而4被保留在temp当中,接下来当然是让4到它应当去的位置。

接下来同理:

我们要做到把所有的元素都遍历一遍,都找到它应该去的位置就可以了,我们可以用一个cnt变量来记录遍历了多少个元素,起初从nums[0]开始走,如果走了一圈之后还有元素没有遍历到的话,那就接下来从nums[1]开始走再走一圈,以此类推,显然我们需要两层循环,当cnt==numsSize的时候,就可以结束遍历了。虽然是两重循环,但是时间复杂度是O(N),因为每个元素只被遍历一次。代码如下:

void swap(int* a, int* b)
{
    int t;
    t = *a;
    *a = *b;
    *b = t;
}
void rotate(int* nums, int numsSize, int k)
{
    int cnt = 0;
    int temp, p;
    for (int start = 0; start < numsSize; start++)
    {
        temp = nums[start];
        p = start;
        do
        {
            p = (p + k) % numsSize;
            swap(&temp, &nums[p]);
            cnt++;
        } while (p != start);
        if (cnt == numsSize) break;
    }
 
}
相关文章
|
23小时前
|
安全 C语言
C语言8 数组与字符串
C语言8 数组与字符串
|
16天前
|
安全 C语言 开发者
C语言中的字符串
C语言中的字符串
13 0
|
17天前
|
C语言
C语言刷题(函数)
C语言刷题(函数)
|
17天前
|
C语言
C语言刷题(循环结构程序设计)
C语言刷题(循环结构程序设计)
|
17天前
|
C语言
C语言刷题(数组)
C语言刷题(数组)
|
18天前
|
存储 C语言
【C语言刷题系列】求一个数组中两个元素a和b的和最接近整数m
【C语言刷题系列】求一个数组中两个元素a和b的和最接近整数m
|
2月前
|
存储 编译器 C语言
在C语言中的数组和字符串
在C语言中的数组和字符串
|
11月前
|
存储 机器学习/深度学习 Linux
【C语言】语言篇——数组和字符串
【C语言】语言篇——数组和字符串
42 0
|
11月前
|
存储 C语言
C语言之指针(指针数组以及指针的指针和字符串)
C语言之指针(指针数组以及指针的指针和字符串)
79 0
|
C语言
c语言 字符数组,字符串
char str[5] = { ‘A’,66,‘C’ ,‘D’ ,69 }; / / 66换成大写字母就是B,69就是E char str[5] = { ‘A’,66,‘C’ }; / / 初始化部分元素,其余默认是0 char str[ ] = { ‘A’,66,‘C’ ,‘D’ ,69 }; / / 这样初始化时,可以不写个数
116 0