• 【C语言】经典编程题

    文章目录

    1. Fibonacci数列 ⭐️

    做题链接：Fibonacci数列

    Fibonacci数列是这样定义的：
    F[0] = 0
    F[1] = 1
    for each i ≥ 2: F[i] = F[i-1] + F[i-2]
    因此，Fibonacci数列就形如：0, 1, 1, 2, 3, 5, 8, 13, …，在Fibonacci数列中的数我们称为Fibonacci数。给你一个N，你想让其变为一个Fibonacci数，每一步你可以把当前数字X变为X-1或者X+1，现在给你一个数N求最少需要多少步可以变为Fibonacci数。

    • 输入描述：输入为一个正整数N(1 ≤ N ≤ 1,000,000)
    • 输出描述：输出一个最小的步数变为Fibonacci数"

    示例:

    • 输入：15
    • 输出：2

    思路：当 n 落在第一个斐波那契数的左边的时候似乎没有什么意义，它只有变成第一个斐波那契数的可能，没有最小步数。所以只有当 n 落在第一个斐波那契数和第二个斐波那契数的中间时，才求最少需要多少步可以变成斐波那契数。

    • 如果 n 等于第二个斐波那契数，步数就等于0。
    • 如果 n 小于第二个斐波那契数，分别求第一个斐波那契数和第二个斐波那契数分别减 n 的绝对值差，并比较大小。这里引用求绝对值的库函数abs，头文件 #include 。当 abs(f1-n)
    • 如果 n 不等于也不小于第二个斐波那契数，n 大于第二个斐波那契数的时候，我们这边用赋值进行下一组数的计算。

    代码如下：

    #include 
#include 
int main()
{
	int n = 0;
	scanf("%d", &n);
	int f1 = 0;
	int f2 = 1;
	int f3 = f1 + f2;
	while (1)
	{
		if (n == f2)
		{
			printf("0\n");
			break;
		}
		if (n < f2)
		{
			if (abs(f1 - n) < abs(f2 - n))
			{
				printf("%d\n", abs(f1 - n));
			}
			else
			{
				printf("%d\n", abs(f2 - n));
			}
			break;
		}
		//n>f2
		f1 = f2;
		f2 = f3;
		f3 = f1 + f2;
	}
	return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35

    在这里插入图片描述

    2. 替换空格 🌟

    做题链接：替换空格

    请实现一个函数，将一个字符串中的每个空格替换成“%20”。例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。

    这里有的人就会想将空格替换成%20有什么意义呢？是不是太闲了呢？
    在这里插入图片描述
    当我们在百度搜索栏中输入We Are Happy就会看到地址栏里出现We%20Are%20Happy，在搜索链接里会将空格替换成%20，这是为什么呢？因为空格的ASCII码值是20。

    在这里插入图片描述
    当我们点击链接会发现这道题在牛客网是这样的，这种是接口型的OJ题目。
    OJ题目分为两种：

    1. IO型：自己完成输入输出，包括 main 函数
    2. 接口型：只需要完成接口就可以了
      接口型的OJ题目要假定 main 函数已经有了，并且调用了replaceSpace(),传递了何时的参数。

    做题思路：

    • char *str,int length 这句代码的意思是把 str 指向的字符串里的空格替换成20，str指向的字符串长度是length。
    • 一个空格要被替换成%20，就是一个字符要变成3个字符，所以字符本质上要往后挪，遇到一个空格就要增长2个字符，假设有 n 个空格，字符串的长度就等于nx2+原字符串的长度。
    • 给两个标记，end1 标记替换之前的字符串的最后一个元素，end2 标记替换之后的字符串的最后一个元素，在 end1 没有遇到空格之前，把 end1 标记的元素挪移到 end2 标记的位置之后，end1 和 end2 都向前挪动，当 end1 遇到空格后，end1 向前挪动一步，把 end2 标记的位置依次写入02%（从后往前赋值），在写的过程中，每写一个字符，end2 向前移动一步，循环这个过程，直到把所有空格替换完成，当 end1 和 end2 指向同一个元素时替换完成。
      在这里插入图片描述
    #include 
#include 
void replaceSpace(char* str, int length) {
    int space_count = 0;//统计空格的个数
    char* cur = str;
    //*cur!=\0,开始遍历
    while (*cur)
    {
        if (*cur == ' ')
            space_count++;
        cur++;
    }
    //计算end1，end2
    char* end1 = str + length;
    char* end2 = str + length + 2 * space_count;
    while (end1 != end2)
    {
        if (*end1 != ' ')
        {
            *end2-- = *end1--;//后置--，先赋值再减
        }
        else
        {
            *end2-- = '0';//从后往前赋值
            *end2-- = '2';
            *end2-- = '%';
            end1--;
        }
    }
}
int main()
{
    char arr[40] = "We Are Happy";
    int len = strlen(arr);
    replaceSpace(arr, len);
    printf("%s\n", arr);
    return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38

    在这里插入图片描述

    3. 找单身狗 💫

    一个数组中只有两个数字是出现一次，其他所有数字都出现了两次。
    编写一个函数找出这两个只出现一次的数字。

    示例：

    • 输入数组的为：1 2 3 4 5 1 2 3 4 6
    • 输出：5 6

    思路：
    异或操作符^：相同为0；相异为1；异或操作符是支持交换律的。

    a^a = 0;
0^a = 0;
1^3^1 = 3;
1^1^3 = 3;

    • 1
    • 2
    • 3
    • 4

    找一个单生狗 1 2 3 4 5 1 2 3 4，用异或操作符就能找出单生狗是5了。
    找两个单生狗1 2 3 4 5 1 2 3 4 6，我们这里就需要给他分组，把5和6分到两个组里，每一个组里只有一个单生狗，其余的都是成对的。例如：A组：1 2 1 2 5；B组：3 4 3 4 6；或者A组 1 3 1 3 5；B组 2 4 2 4 6。怎样才能实现以上的分组你呢？5的二进制位101，6的二进制位110；5^6 = 011，异或的结果为011，证明他们的最低为和第二位都不相同。5的最低位是1，6的最低位是0；我们就将最低位为1的分到A组，最低位为0的分到B组。或者用第二位分组也可以。
    分组思想：

    1. 计算5和6二进制中的哪一位为1（第n位）
    2. 以第n位为标准，第n位为1的放一组，第n位为0的放一组。
    #include 
int main()
{
	int arr[] = { 1,2,3,4,5,1,2,3,4,6 };
	//所有数字异或
	int i = 0;
	int sz = sizeof(arr) / sizeof(arr[0]);
	int ret = 0;
	for (i = 0; i < sz; i++)
	{
		ret ^= arr[i];
	}
	//ret 就是5^6的结果，二进制中一定有1
	//计算ret的第几位是1
	int pos = 0;
	for (i = 0; i < 32; i++)
	{
		if ((ret >> i) & 1 == 1)
		{
			pos = i;
			break;
		}
	}
	//ret的pos位是1
	//把arr数组中的每个元素的第pos位为1的数字异或在一起
	int num1 = 0;
	int num2 = 0;
	for (i = 0; i < sz; i++)
	{
		if (((arr[i] >> pos) & 1) == 1)
		{
			num1 ^= arr[i];
		}
		else
		{
			num2 ^= arr[i];
		}
	}
	printf("%d %d", num1, num2);
	return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41

    在这里插入图片描述

    4. 模拟实现 atoi ✨

    atoi 把字符串转换成对应的数字

    atoi的使用：

    #include 
#include 
int main()
{
	int ret = atoi("123");
	printf("%d\n", ret);
	return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8

    在这里插入图片描述
    模拟实现atoi

    //模拟实现atoi会出现的情况
//my_atoi(NULL)//异常
//my_atoi("")//异常
//my_atoi("    +123")//正常
//my_atoi("-123")//正常
//my_atoi("123abc")//异常
//my_atoi("1111111111111111111111111")//异常
//my_atoi("-1111111111111111111111111")//异常

#include 
#include 
#include 
#include 
//枚举定义状态值
enum Status
{
	VALID,//合法
	INVALID //非法
};
enum Status status = INVALID;//定义一个全局的状态值为非法
//根据返回值判断是非法的还是合法的
int my_atoi(const char* str)
{
	if (str == NULL)
	{
		return 0;
	}
	if (*str == '\0')
	{
		return 0;
	}
	//空白字符
	while (isspace(*str))
	{
		str++;
	}
	int flag = 1;
	if (*str == '+')
	{
		flag = 1;
		str++;
	}
	else if (*str == '-')
	{
		flag = -1;
		str++;
	}
	//处理数字字符
	//123
	long long ret = 0;
	while (isdigit(*str))
	{
		ret = ret * 10 + flag * (*str - '0');
		if (ret<INT_MIN || ret>INT_MAX)//值越界了
		{
			return 0;
		}
		str++;
	}
	if (*str == '\0')
	{
		status = VALID; //定义一个局部的状态值为合法
		return (int)ret;
	}
	else
	{
		return (int)ret;
	}
}
int main()
{
	int ret = my_atoi("   -123");
	if (status == VALID)
		printf("合法转换：%d\n", ret);
	else
		printf("非法转换：%d\n", ret);
	return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78

    在这里插入图片描述

    本章到这里就结束啦，如果有哪里写的不好的地方，请指正。
    如果觉得不错并且对你有帮助的话请给个三连支持一下吧！
    Fighting!!!✊

  • 相关阅读:
    Protocol Buffers定义消息类型
    C++基础
    软考复习 -- 计算机网络
    mac本地安装PHP redis扩展
    电脑重装系统后如何把网站设为首页
    JSR-330 JAVA 依赖注入标准API说明
    sql常用语法总结
    关于在服务器配置MongoDB数据库——从入门到入土
    《Missing Parts》NFT 作品集第 5 系列上线 The Sandbox 市场平台
    AI 大战高考作文！实测 ChatGPT、文心一言、通义千问等 8 款“神器”
  • 原文地址：https://blog.csdn.net/qq_68661624/article/details/127474406