记录刷题历程,实时进行中.....

# C 语言库函数的实现

strlen函数
//strlen 函数能统计字符串中的字符个数
// 递归版本 (不使用局部变量)
/*
如下 a 字符数组 "12345",假如需要计算其字符串长度,
就需要计算数组 "2345",假如需要计算其字符串长度,
就需要计算数组 "345",假如需要计算其字符串长度,
就需要计算数组 "45",假如需要计算其字符串长度,
就需要计算数组 "5",直到只剩字符 "\0"(终止符),
而此字符不需要计算长度,因此返回 0 即可。
strlen ("12345" 地址) -> 1 + strlen ("2345" 地址) ->
1 + 1 + strlen ("345" 地址) -> 1 + 1 + 1 + strlen ("45" 地址) ->
1 + 1 + 1 + 1 + strlen ("5" 地址) —> 1 + 1 + 1 + 1 + 1 + strlen ("\0" 地址) ->
1 + 1 + 1 + 1 + 0 -> 返回 5
*/
#include<stdio.h>
int strlen(const char* str)//const 防止值被改变
{
	if (!(*str))// 非真为 0,'\0' 终止符 ASCII 码为 0
		return 0;
	else
		return 1 + strlen(str + 1);
}
int main()
{
	char a[] = "12345";
	printf("%d",strlen(a));
	return 0;
}
// 计数器版本
/*
当向函数传递数组名时,接收的是数组的首地址,
数组在内存中是一段连续的地址,
通过地址向后移动的操作可实现数组中不同元素值的获取,
只要当前字符数组地址的值不是终止符 ('\0') 就不会停止并使计数器加一。
*/
#include<stdio.h>
#include<assert.h>
int strlen(const char* str)//const 防止值被改变
{
	assert(str);// 断言,判断 str 是否为 NULL (空指针)
	int counting = 0; // 计数器
	while (*str)// 非真为 0,'\0' 终止符 ASCII 码为 0
	{
		counting++;
		str++; // 地址后移
	}
	return counting;
}
int main()
{
	char a[] = "aaa";
	printf("%d", strlen(a));
	return 0;
}
// 地址减法版本
/*
双指针
通过定义一个字符指针指向数组首地址,
再通过地址向后移动的操作实现数组中不同元素值的获取,
由于终止符不在需要统计的字符之内,
所以此时经过移动的地址减去数组首地址就是数组元素个数。
*/
#include<stdio.h>
#include<assert.h>
int strlen(const char* str)//const 防止值被改变
{
	assert(str);// 断言,判断 str 是否为 NULL (空指针)
	char* head = str;// 记录目标数组的首地址
	while (*str)// 非真为 0,'\0' 终止符 ASCII 码为 0
		str++;
	return str - head;
}
int main()
{
	char a[] = "1111";
	printf("%d", strlen(a));
	return 0;
}
strcpy函数
/*
strcpy 函数能将一个字符串数组拷贝到另一个目标数组中,
但目标数组需要足够大的空间。
*/
/*
双指针 (地址值交换易读版本)
通过地址移动的方式,将需要拷贝的字符数组内的元素依次
复制到目标数组对应位置中直到终止符为止。
*/
#include<stdio.h>
#include<assert.h>
void strcpy(char* str1, const char* str2)//const 防止值被改变
{
	assert(str1);// 断言,判断 str1 是否为 NULL (空指针)
	assert(str2);
	while (*str1)// 非真为 0,'\0' 终止符 ASCII 码为 0
	{
		*str1 = *str2;// 指针所指向的地址值进行交换
		str1++;// 地址后移
		str2++;// 地址后移
	}
}
int main()
{
	char a1[] = "@@@@@@@@@@";
	char a2[] = "wellcome";
	strcpy(a1, a2);
	printf("%s", a1);
	return 0;
}
// 双指针 (地址值交换优化版本)
/*
基本操作同上,
最后通过返回拷贝好的目标数组的首地址。
*/
#include<stdio.h>
#include<assert.h>
char* strcpy(char* str1, const char* str2)
{
	assert(str1);// 断言,判断 str1 是否为 NULL (空指针)
	assert(str2);
	
	char* head = str1;// 记录目标数组的首地址
	while (*str1++ = *str2++)// 非真为 0,'\0' 终止符 ASCII 码为 0
	{
		;
	}
	return head;
}
int main()
{
	char a1[] = "@@@@@@@@@@";
	char a2[] = "wellcome";
	printf("%s", strcpy(a1, a2));
	return 0;
}
strcat函数
//strcat 函数能追加字符串,但需要追加的目标数组空间足够大
/*
双指针
通过终止符先确定目标字符串的末尾,
再将需要追加的字符通过地址传递直到下个终止符为止。
*/
#include<stdio.h>
#include<assert.h>
char* strcat(char* str1, const char* str2)
{
	assert(str1 && str2);// 断言,判断 str1 与 str2 是否存在 NULL (空指针)
	char* head = str1;// 记录目标数组的首地址
	while (*str1)// 目标数组末尾终止符处
		str1++;
	while (*str1++ = *str2++)// 字符追加
		;
	return head;
}
int main()
{
	char* s1 = "abcf";
	char* s2 = "abcfee";
	printf("%s", strcat(s1, s2));
	return 0;
}
strcmp函数
/*
strcmp 函数通过比较两个字符串之间各个字符的 ASCII 码大小,
直到出现第一个不同的字符为止。
str1 > str2  返回 >0 的数
str1 = str2  返回 0
str1 < str2  返回 <0 的数
*/
/*
双指针
比较两个字符串直到两者地址存储的值出现不同为止
*/
//Linux Gcc 编译器效果写法
#include<stdio.h>
#include<assert.h>
int strcmp(const char* str1, const char* str2)
{
	assert(str1 && str2);// 断言,判断 str1 与 str2 是否存在 NULL (空指针)
	
	// 寻找不同字符,当存在有一个字符数组到达末端就不需要寻找了
	while (*str1 && *str2 && (*str1 == *str2))
	{
		str1++;
		str2++;
	}
	return *str1 - *str2;//ASCII 码值相减
}
int main()
{
	char* s1 = "abcf";
	char* s2 = "abcfee";
	printf("%d", strcmp(s1, s2));
	return 0;
}
//windows VS 编译器效果写法,原理同上
#include<stdio.h>
#include<assert.h>
int strcmp(const char* str1, const char* str2)
{
	assert(str1 && str2);
	while (*str1 && *str2 && (*str1 == *str2) )
	{
		str1++;
		str2++;
	}
	if (0 == (*str1 - *str2))
		return 0;
	else if ((*str1 - *str2) > 0)
		return 1;
	else
		return -1;
}
int main()
{
	char* s1 = "abcf";
	char* s2 = "abcf11";
	printf("%d", strcmp(s1, s2));
	return 0;
}
strncpy函数
/*
相比于 strcpy,
strncpy 中多了一个拷贝位数的参数,
当所需拷贝的位数高于目的地字符串时,
被拷贝的字符串被拷贝完后以零进行扩充,
当被拷贝的字符串长度高于所需拷贝数时,
以目的地字符串的终止符为止。
*/
#include<stdio.h>
#include<assert.h>
char* strncpy(char* str1,const char* str2, size_t num)
{
	assert(str1 && str2);
	char* head = str1;
	while (num--)
	{
		*str1++ = *str2++;
	}
	return head;
}
int main()
{
	char s1[40] = "abcdef";
	char s2[] = "e";
	printf("%s\n",strncpy(s1, s2, 8));
	return 0;
}
strncat函数
/*
相较于 strcat,
strncat 多了一个位数,
当位数高于字符串长度时,
以字符串的终止符为止。
*/
#include<stdio.h>
#include<assert.h>
char* strncat(char* str1,const char* str2, size_t num)
{
	assert(str1 && str2);
	char* head = str1;
	while (*str1)
		str1++;
	while (num--)
	{
		*str1++ = *str2++;
	}
	return head;
}
int main()
{
	char s1[30] = "aeee";
	char s2[20] = "bbbbeeee";
	printf("%s\n", strncat(s1, s2, 10));
	return 0;
}
strncmp函数
/*
相比于 strcmp,
strncmp 多了一个比较位数,
当位数高于字符串长度时,
并不影响比较,
只需考虑终止符即可。
*/
#include<stdio.h>
#include<assert.h>
int strncmp(const char* str1,const char* str2, size_t num)
{
	assert(str1 && str2);
	while (num--)
	{
		if (*str1++ != *str2++)
			return *str1 - *str2;
	}
	return *str1 - *str2;
}
int main()
{
	char* s1 = "abcdbbb";
	char* s2 = "abcaaaaa";
	printf("%d\n", strncmp(s1, s2, 4));
	return 0;
}

# 位操作符与移位操作符

不定义第三个变量交换两个整数变量的值
// 密码编码盒子 (中间局部变量减法),两个整型相加有溢出风险。
/*
假如有整数 a,b。
通过两数之和来创建中间局部变量并放入到 a 中,
中间局部变量减去 b 就可以得到 a 的值,将此值存入到 b 中,
中间局部变量再减去 b 就得到原来 b 的值,将此值存入到 a 中,
这样就实现两数之间的交换了。
*/
#include<stdio.h>
int main()
{
	int a = 3;
	int b = 5;
	a = a + b;//8
	b = a - b;//8 - 5 = 3
	a = a - b;//8 - 3 = 5 
	printf("%d, %d", a, b);
	return 0;
}
// 密码编码盒子 (位操作符)
/*
假如有整数 a,b。
通过两数按位异或 (^) 来创建中间局部变量并放入到 a 中,
中间局部变量与 b 按位异或就可以得到 a 的值,将此值存入到 b 中,
中间局部变量再与 b 按位异或就得到原来 b 的值,将此值存入到 a 中,
这样就实现两数之间的交换了。
*/
#include<stdio.h>
int main()
{
	int a = 3;//~0011
	int b = 5;//~0101
	a = a ^ b;//6 - ~0110
	b = a ^ b;//3 - ~0011
	a = a ^ b;//5 - ~0101
	printf("%d, %d", a, b);
	return 0;
}
计算整型数值二进制中1的个数
//&(按位与) 和 >>(右移操作符)
/*
通过位操作使整数值二进制的最低位与整数 `1` 的
最低位进行按位与操作,由于两者都是 1,
所以返回值为 1,当计算整数值二进制的下一位时,
通过使整型值二进制按位右移 1 位,
这样原来的最低位会被抛弃并由其上一位代替。
例子,整数 3
  ~00000011
&
  ~00000001
->
  ~00000001
  ~00000011 3
-> 
  ~00000001 (3>> 1)
*/
#include<stdio.h>
int bin_one(int a)
{
	int c = 0;
	int i = 0;
	for (i = 0; i < 32; i++)//32 位系统有 32 个比特位
		if (1 & (a >> i))//1 & (a>> i) 的值为 0 时,判断为假
			c++;
	return c;
}
int main()
{
	int a = 14;//~01110
	printf("%d", bin_one(a));//3
	return 0;
}

# 查找

查找升序不重复整型数组中的某个数字的下标
// 二分查找
/*
通过缩减区间范围的方法来减少查找时间,
当数组两端区间的中间值大于要查找的数值,
则该值的范围就可能在数组左端到数组中间的上一位,
同理,当数组两端区间的中间值小于要查找的数值,
则该值的范围就可能在中间值的下一位到数组右端的区间范围内。
*/
#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
int double_search(int num[], int sz, int sn)
{
	int left = 0;
	int right = sz - 1;
	while (left <= right)
	{
		int mid = left + (right - left) / 2;
		if (num[mid] == sn)
			return mid;
		else if (num[mid] > sn)
			right = mid - 1;
		else if (num[mid] < sn)
			left = mid + 1;
	}
	return right;
}
int main()
{
	int s_num = 0;
	int a[] = { 1,2,3,4,5,6,7,8,9 };
	int size = sizeof(a) / sizeof(a[0]);
	scanf("%d", &s_num);
	printf("%d\n", double_search(a, size, s_num));
	return 0;
}

# 斐波那契数列

青蛙跳台阶
/*
题目:一只青蛙一次可以跳上 1 级台阶,也可以跳上 2 级。
     求该青蛙跳上一个 n 级的台阶总共有多少种跳法?
*/
/*
当有 1 级台阶时,只可以跳 1 级
当有 2 级台阶时,可以跳 2 级,那就先能跳 1 级台阶
当有 3 级台阶时,(),那就先能跳 2 级台阶,那就也先能跳 1 级台阶
当有 n 级台阶时,(),那就先能跳 n-2 级台阶,那就也先能跳 n-1 级台阶
() 内删除部分为 `可以跳两级`,
由于可以跳 2 级台阶时就已经能跳两级了,因此重复无意义。
由此可见
F (1) = 1
F (2) = 1 + F (1) = 2
F (3) = F (2) + F (1) = 3
满足 F (n) = F (n - 1) + F (n - 2)
*/
// 递归方法
#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
int couting_method(int num)
{
	if (1 == num)
		return 1;
	if (2 == num)
		return 2;
	else
		return couting_method(num - 2) + couting_method(num - 1);
}
int main()
{
	int stairs_num = 0;
	scanf("%d", &stairs_num);
	printf("%d",couting_method(stairs_num));
	return 0;
}
// 避免迭代产生的大内存消耗的循环方法
#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
int couting_method(int num)
{
	int i = 0;
	int head = 1;
	int tail = 2;
	int ans = 3;
	if (1 == num)
		return 1;
	if (2 == num)
		return 2;
	for (i = 4; i < num + 1; i++)
	{
		head = tail;
		tail = ans;
		ans = head + tail;
	}
	return ans;
}
int main()
{
	int stairs_num = 0;
	scanf("%d", &stairs_num);
	printf("%d",couting_method(stairs_num));
	return 0;
}
青蛙跳台阶变种
/*
一只青蛙一次可以跳上 1 级台阶,也可以跳上 2 级…… 它也可以跳上 n 级,
此时该青蛙跳上一个 n 级的台阶总共有多少种跳法?
*/
/*
假如有 1 级台阶,能跳 1 级
假如有 2 级台阶,可以跳 2 级,那就先能跳 1 级台阶
假如有 3 级台阶,可以跳 3 级,那就先能跳 2 级台阶,那就也先能跳 1 级台阶
假如有 n 级台阶,可以跳 n 级,那就先能跳 n-1 级台阶,那就也先能跳 n-2 级台阶,
	        那就也先能跳 n-3 级台阶,....,那就也先能跳 n-(n-2) 级台阶,
	        那就也先能跳 1 级台阶。
由此可见
F (1) = 1
F (2) = 1 + F (1) = 2
F (3) = 1 + F (2) + F (1) = 4
F (n) = 1 + F (n-1) + F (n-2) + F (n-3) +.....+ F (1)
*/
// 递归
#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
int couting_method(int num)
{
	if (1 == num)
		return 1;
	else
	{
		int couting = 1;
		while (num > 1)
		{
			couting += couting_method(num - 1);
			num--;
		}
		return couting;
	}
}
int main()
{
	int stairs = 0;
	scanf("%d", &stairs);
	printf("%d\n", couting_method(stairs));
	return 0;
}
// 留一下大数解法
/*
①F (n) = F (n-1) + F (n-2) + F (n-3) + .... + F (n-(n-1))
②F (n-1) = F (n-2) + F (n-3) + .... + F (n-(n-1))
由①-②得
F (n) - F (n-1) = F (n-1) -> F (n) = 2F (n-1)
*/

# 未归类算法

求两个整数的最大公约数
// 辗转相除法
/*
假如有两个数 a,b。
如算法名字一样,将两个数取模 (a% b),
之后,先将 b 的值传递给 a, 再用 b 接收取模的值,
以此往复,直到取模为 0 时,b 的值就为最大公约数。
*/
#include<stdio.h>
int main()
{
	int m = 24;
	int n = 18;
	while (m % n)// 当 m % n == 0 时为假,循环终止
	{
		int r = m % n;
		m = n;
		n = r;
	}
	printf("%d", n);
	return 0;
}