函数与指针的习题

1、杨氏矩阵

杨氏矩阵：每行从左到右递增，每列从上到小递增

编写程序查找杨氏矩阵中的数字，并返回其下标（时间复杂度小于O(n)）

分析：对于矩阵右上角的元素，若目标值大于该值则目标值不在该行，若目标值小于该值则目标值不在该列。通过上述特点进行判断，并通过位移数组指针指向以缩小范围，最终确定目标值

int main()
{
    int arr[3][3] = { 1,2,3,4,5,6,7,8,9 };
    int k = 7;
    int col = sizeof arr[0] / sizeof arr[0][0];
    int x = 0;
    int y = col - 1;

    while (x <= col - 1 && y >= 0)
    {
        if (arr[x][y] > k)
        {
            y--;
        }
        else if (arr[x][y] < k)
        {
            x++;
        }
        else
        {
            printf("已经找到，下标为[%d][%d]\n", x, y);
            break;
        }
    }
    if (x > col - 1 || y < 0)
    {
        printf("未找到\n");
    }

    return 0;
}

2、字符串翻转

给出翻转个数，对字符串进行翻转

如：当翻转个数为2时，字符串"abcde"翻转结果为"cdeab"

分析：存在两种解题思路

• 循环位移法

每一次进行向左移动1位操作，共执行k次

向左移动1位操作：可分为3步

1. 保存第一个字符于临时变量
2. 位移1位操作
3. 赋值最后一位

void LeftMove(char str[], int k)
{
    assert(str != NULL);        
    int len = strlen(str);
    for (int i = 0; i < k; i++)
    {
        // left move one
        // 1. save str[0]
        char tmp = *str;
        // 2. move
        for (int j = 0; j < len - 1; j++)
        {
            str[j] = str[j + 1];
        }
        // 3. last element
        str[len - 1] = tmp;
    }
}

• 三步反转法

1. 根据翻转个数k将字符串分为两部分
2. 分别对两部分的元素进行反转
3. 对整体字符串进行反转

void Reverse(char* str,int startIndex, int endIndex)
{
    int left = startIndex;
    int right = endIndex;
    while (left < right)
    {
        int tmp = *(str + left);
        *(str + left) = *(str + right);
        *(str + right) = tmp;
        left++;
        right--;
    }
}

void LeftMove(char str[], int k)
{
    assert(str != NULL);
    int len = strlen(str);
    assert(k <= len);
    // left part reverse
    Reverse(str, 0, k - 1);
    // right part reverse
    Reverse(str, k, len - 1);
    // whole part reverse
    Reverse(str, 0, len - 1);
}

给两个字符串，判断其中1个字符串是否为另一个的翻转字符串

分析：存在两种解题思路

• 枚举法

对一个长度为i的字符串，其最多的翻转次数为i，故可遍历i次，查看是否为翻转后的字符串

int IsMove(char tar[], char src[])
{
    int tar_len = strlen(tar);
    int src_len = strlen(src);
    if (tar_len == src_len)
    {
        for (int i = 1; i <= tar_len; i++)
        {
            LeftMove(src, 1);
            if (strcmp(src, tar) == 0)
            {
                return 1;
            }
        }
        return 0;
    }
    else
    {
        return 0;
    }
}

• 追加字符、判断子串

对目标字符串追加字符，使其在原基础上再向后复制一份原字符串，而若为翻转字符串则该字符串为其子串。

int IsMove(char tar[], char src[])
{
    assert(tar != NULL && src != NULL);
    int src_len = strlen(src);
    int tar_len = strlen(tar);
    if (src_len == tar_len)
    {
        // 1. 追加
        strncat(src, src, src_len);
        // 2. 判断子串
        char* ret = strstr(src, tar);
        if (ret == NULL)
        {
            return 0;
        }
        else
        {
            return 1;
        }
    }
    else
    {
        return 0;
    }
}