C语言学习记录——삼십유 C语言部分题目（3）

指针进阶部分题目

实现一个函数，可以左旋字符串中的k个字符。比如ABCD左旋一个字符的到BCDA，ABCD变成CDAB

我们可以这样想象，abcdef，先把ab反过来，变成bacdef，再把cdef反过来，变成bafedc，之后整体反，变成cdefab，也就达到了最终效果

#include

void reverse(char* left, char* right)
{
    assert(left != NULL);
    assert(right != NULL);
    while (left < right)
    {
        char tmp = *left;
        *left = *right;
        *right = tmp;
        left++;
        right--;
    }
}

void left_move(char* arr, int k)
{
    assert(arr);
    int len = strlen(arr);
    assert(k <= len);
    reverse(arr, arr + k - 1);
    reverse(arr + k, arr + len - 1);
    reverse(arr, arr + len - 1);
}
int main()
{
    char arr[] = "abcdef";
    left_move(arr, 2);
    printf("%s\n", arr);
    return 0;
}

写一函数，判断一个字符串是否是另一个字符串旋转后的字符串

#include

void left_move(char* arr, int k)
{
    assert(arr);
    int len = strlen(arr);
    assert(k <= len);
    reverse(arr, arr + k - 1);
    reverse(arr + k, arr + len - 1);
    reverse(arr, arr + len - 1);
}

int is_left_move(char* s1, char* s2)
{
    int len = strlen(s1);
    int i = 0;
    for (i = 0; i < len; i++)
    {
        left_move(s1, 1);
        int ret = strcmp(s1, s2);
        if (ret == 0)
            return 1;
    }
    return 0;
}
int main()
{
    char arr1[] = "abcdef";
    char arr2[] = "cdefab";
    int ret = is_left_move(arr1, arr2);
    if (ret == 1)
    {
        printf("Yes\n");
    }
    else
    {
        printf("No\n")
    }
    return 0;
}

由于要旋转，所以声明两个字符串时要允许修改，所以char arr1[],而不是*arr1. 在之后的if循环语句前，left_move旋转完一次s1后，s1就变为旋转后的样子，所以不能在后面写上i，而是每次旋转1次。if循环中，加入ret==0，也就是两个字符串相等，可返回。不过需要全部旋转完后才能判断没有相等的字符串，才能下结论没有相等的。才能返回0。

还可以更高效

我们可以在abcdef后面追加一个abcdef，这样所有旋转的结果就都包含在里面了。这里可以用库函数来实现追加功能，先看strcat这个函数。这个函数的实现，比如两个字符串追加，“abc”,"def"，d会添加到\0处，然后追加ef，和def这个字符串的\0。但是如果相同的字符追加，比如abcdef\0，追加时，a替换掉\0，bcdef依次放置，但是这时候之前的字符串中的\0已经没有了，被a占据了，所以程序会崩掉，不能用这个函数。

而另一个函数strncat，括号里放三个参数，第三个参数就是要追加的字符数。这是追加的步骤。接下来要判断str2指向的字符串是否是str1指向的字符串的子串。 要用到一个找子串的函数strstr。

strstr(str1, str2) 比如str2指向cdefab，那么这个函数就会在str1中找和str2相同的字符串，如果能找到，就把c的地址传回来，找不到就返回一个空指针.

这提到的函数都要头文件string.h。

#include
#include  

int is_left_move(char* str1, char* str2)
{
    int len = strlen(str1);
    strncat(str1, str1, 6);
    char* ret = strstr(str1, str);
    if (ret == NULL)
    {
        return 0;
    }
    else
    {
        return 1;
    }
    return 0;
}
int main()
{
    char arr1[30] = "abcdef";
    char arr2[] = "cdefab";
    int ret = is_left_move(arr1, arr2);
    if (ret == 1)
    {
        printf("Yes\n");
    }
    else
    {
        printf("No\n")
    }
    return 0;
}

但是呢这还有个隐藏问题，如果arr2是一个cdef字符串，那么我们仍会得到Yes，但是实际却不是旋转得到的，所以里面要修改一下。

int is_left_move(char* str1, char* str2)
{
    int len1 = strlen(str1);
    int len2 = strlen(str2);
    if (len1 != len2)
        return 0;
    strncat(str1, str1, 6);
    char* ret = strstr(str1, str);
    if (ret == NULL)
    {
        return 0;
    }
    else
    {
        return 1;
    }
    return 0;
}

使用函数尽量使用库函数，实在也是看情况自定义函数。

杨氏矩阵

有一个数字矩阵，矩阵的每行从左到右是递增的，每列从上到下是递增的，编写程序在这样的矩阵中查找某个数字是否存在。要求时间复杂度小于O（N）。

可以声明一个二维数组，放入所有符合的数字，而时间复杂度，如果总共有n个数据，如果一个个查找，要遍历n个数据，时间复杂度就是O(N)，所以不能所有都遍历。

现在假设所有的数据

123

456

789

可看左下角的数字，如果要找5，把它与7比，小于，然后上到4这一行找，发现大于，然后+1，来到5，发现相同，就可以·输出找到了。同样，比较右上角数字也可。

#include
#include  

int FindNum(int arr[3][3], int k. int row, int col)
{
    int x = 0;
    int y = col - 1;
    while (x <= row - 1 && y >= 0)
    {
        if (arr[x][y] > k)
        {
            y--;
        }
        else if (arr[x][y] < k)
        {
            x++;
        }
        else
        {
            return 1;
        }
    }
    return 0;
}
int main()
{
    int arr[3][3] = { {1, 2, 3}, {4， 5， 6 }， {7， 8，9} };
    int k = 7;
    int ret = FindNum(arr, k, 3, 3);
    if (ret == 1)
    {
        printf("找到了\n");
    }
    else
    {
        printf("找不到\n");
    }
    return 0;
}

现在改变一下，找到时，要输出找到的下标。

int FindNum(int arr[3][3], int k. int *px, int *py)
{
    int x = 0;
    int y = *py - 1;
    while (x <= *px - 1 && y >= 0)
    {
        if (arr[x][y] > k)
        {
            y--;
        }
        else if (arr[x][y] < k)
        {
            x++;
        }
        else
        {
            *px = x;
            *py = y;
            return 1;
        }
    }
    return 0;
}
int main()
{
    int arr[3][3] = { {1, 2, 3}, {4， 5， 6 }， {7， 8，9} };
    int k = 7;
    int x = 3;
    int y = 3;
    //返回型参数
    int ret = FindNum(arr, k, &x, &y);
    if (ret == 1)
    {
        printf("找到了\n");
        printf("下标是：%d %d\n", x, y);
    }
    else
    {
        printf("找不到\n");
    }
    return 0;
}

现在先把xy的值声明出来，然后用传入他们的地址，用指针接收，那么在自定义函数内部，指针就能指向外面的xy.当找到时，把这时候的xy值赋给指针变量，也就改变了外面的xy值，所以这时候打印就可以输出正确的下标。这也就是返回型参数。

结束。