算法水题练习(二)（算法题模板）

给你一个长度为 n ( n ≤ 100 ) n (n \le 100)n(n≤100) 的正整数数组 arr ，
请你计算所有可能的奇数长度子数组的和。
子数组 定义为原数组中的一个连续子序列。请你返回 arr 中 所有奇数长度子数组的和 。
//这个问题输入的是一个数组，输出一个数。这个数是所有 奇数长度 子数组 的和。首先可以枚举长度，再枚举起点，然后就是统计一段区间的和， 时间复杂度为 O ( n 3 ) ，可以利用前缀和把时间复杂度降低到 O ( n 2 )
//然而这个问题没必要，因为 n  的范围比较小。
int sumOddLengSubarray(int* arr, int arrSize) {
	int len, start, i, sum = 0;
	for (len = 1; len <= arrSize; len += 2)//枚举长度
	{
		for (start = 0; start + len <= arrSize; start++)//枚举区间起点
		{
			for (i = start; i < start + len; i++) {
				sum += arr[i];//计算区间和
			}
		}
	}
	return sum;
}



//缺失的一个正数
给你一个 n ( n ≤ 5 × 1 0 5 ) 个元素的未排序的整数数组 n u m s，
数组元素范围为整型，请你找出其中没有出现的最小的正整数。
//问题分析
1）定义 m a x n maxnmaxn 为 500001；
2）如果在 1 到 m a x n maxnmaxn 之间的数字，映射到哈希数组中；
3）然后从 1 开始遍历哈希数组，第一个没有被哈希的就是答案；
4）所有数字都遍历完毕，仍然没有找到，则答案为 n + 1 n+1n+1。
#define maxn 50001   //定义
int hash[50001], cases = 0;
int firstMissingPositive(int* nums, int numsSize)
{
	int i;
	cases++;
	for (i = 0; i < numsSize; i++)
	{
		if (nums[i] > 0 && nums[i] < maxn)
			hash[nums[i]] = cases;//如果在1-maxn映射到哈希数组中.没有被哈希的说明就没有
	}
	for (i = 1; i <= numsSize; i++)
	{
		if (hash[i] < cases) {//从1开始遍历,没有被哈希的就是答案
			return i;
		}
	}
	return  numsSize + 1;//所有数字都遍历完毕,没有找到答案就是numsSize + 1
}



//排序数组
一个数组,升序排列
//a代表数组中某个元素的地址 (int*)a代表将地址转换成指向整数的地址
//*(int*)a取实际地址的值  
//这2个数相减.返回三种数,<0 ,>0,=0.来决定是否对数据元素进行交换
int cmp(const void*a, const void* b)
{
	return *(int*)a - *(int*)b;
}
int* sortArray(int* nums, int numsSize, int* returnSize)
{
	qsort(nums, numsSize, sizeof(int), cmp);//调用排序库函数
	*returnSize = numsSize;//外部调用sortArray时,只会返回一个指针首地址,具体有多少元素是不知道的.所以
	//需要一个returnSize作为返回值返回出去.让调用方知道返回数组的长度是多少.
	return nums; //返回排序数组首地址
}


给定一个字符串，请将字符串里的字符按照出现的频率降序排列。
/*
结构体排序 通过一个cmp比较函数实现自动以的关键字比较.从而实现排序
定义一个结构体,两个字段.一个是字符字段  用于标记 一个是数量字段,用于排序
遍历一遍字符串,统计填充完这个长度为256的结构体数组(ASCII)
*/

typedef struct Data {//定义一个结构体,两个字段.一个是字符字段  用于标记 一个是数量字段,用于排序
	int cnt;
	int ch;
}Data;
int cmp(const void*a, const void*b)//转换成结构体后逆序排序
{
	return-((Data*)a)->cnt + ((Data*)b)->cnt;
}
char *frequencySort(char* s)
{
	int i, size = 0;
	Data ans[256];
	for (i = 0; i < 256; i++)//初始化每个字符初始量为0
	{
		ans[i].cnt = 0;
		ans[i].ch = 0;
	}
	for (i = 0; s[i]; i++)
	{
		++ans[s[i]].cnt;//遍历字符串,对每个字符计数
	}
	qsort(ans, 256, sizeof(Data), cmp);//对结构体排序
	for (i = 0; i < 256; i++)
	{
		while (ans[i].cnt) {
			--ans[i].cnt;
			s[size++] = ans[i].ch;//按照排序顺序将字符串一个一个填充用语返回的字符串
		}
	}
	s[size] = '\0';//字符串结尾加上结束标记
	return s;
}

//二进制链表转整数
给你一个单链表的引用结点head。链表中每个结点的值不是 0 就是 1 。
已知此链表是一个整数数字的二进制表示形式。请你返回该链表所表示数字的 十进制值。
//二进制转十进制,只不过存储方式变成了链式存储
int getDecimaValue(struct ListNode* head) {
	int s = 0;
	while (head)
	{
		s = s * 2 + head->val;//进制转换的递推
		head = head->next;//执行链表的遍历
	}
	return s;
}

给你一个十进制整数 n ( n ≤ 100 ) 和一个基数 k ( k ≤ 10 )
请你将 n  从 十进制 表示转换为 k  进制 表示
计算并返回转换后各位数字的 总和 。
转换后，各位数字应当视作是 十进制数字，且它们的总和也应当按 十进制表示返回。
//就是一个进制转换.顺便在转换的过程中,将每一位数字加和 用while迭代除k求解
int sumBase(int n, int k)
{
	int sum = 0;
	while (n)
	{
		sum += n%k;
		n /= k;
	}
	return sum;
}

给定一个非负整数 num，反复将各个位上的数字相加，直到结果为一位数。
/对于每个数字不断除10,每次迭代过程中取最低位进行累加,结果小于10返回
int addDigits(int num)
{
	int sum = 0;
	if (num < 10)
	{
		return num;//base case
	}
	while (num)
	{
		sum += num % 10;//除10在累加
		num /= 10;//取模
	}
	return addDigits(num);//递归重复计算
}


给定一个整数num，将其转化为 七进制，并以字符串形式输出。
/*
返回的字符串必须是堆内存 ,所以需要malloc进行申请内存,不能用栈上的内存
考虑负数和零的情况
用栈来存储中间结果
返回c字符串需要'\0'结尾
*/
#define manx 20
char *convertToBase7(int num) {
	char*ret = (char*)malloc(manx * sizeof(char));//堆内存
	int stack[maxn], top = 0;
	int returnSize = 0;
	if (num < 0) {  //对于负数的情况,再返回的字符串前面加上'-';
		ret[returnSize++] = '-';
		num = -num;
	}
	if (num == 0)//对于0的情况单独入栈一个0
	{
		stack[top++] = 0;
	}
	else {//否则将7进制的转换后每个数位---入栈
		while (num) {
			stack[top++] = num % 7;
			num /= 7;
		}
	}
	while (top--)//将所有的是数字为从栈顶弹出后组成字符串
	{
		ret[returnSize++] = stack[top] + '0';
	}
	ret[returnSize] = '\0';
	return ret;
}


给定一个整数，编写一个算法将这个数转换为十六进制数。
对于负整数，我们通常使用 补码运算 方法。
/*
由于负数是采用补码的形式.而计算机内存存储也是补码.所以直接用位运算更加方便
不用区分正负,但是要考虑0的情况
*/
char getChar(int num)//数字可以转换成字符的函数
{
	if (num <= 9) {
		return num + '0';
	}
	return num - 10 + 'a';
}
char *toHex(int num) {
	int stack[20], top = 0;
	char *ret = (char*)malloc(20 * sizeof(char));//申请一块用于返回的内存空间,不要用栈上的空间
	int returnSize = 0;
	if (num == 0) {//当为0时,单独处理
		ret[returnSize++] = '0';
		ret[returnSize] = '\0';
		return ret;
	}
	
	while (num) {
		stack[top++] = num & 0xf;//模16
		num >>= 4;//除16
		num &= ((1 << 28) - 1);//右移最高位补1.把1减掉
	}
	while (top--) {
		ret[returnSize++] = getChar(stack[top]);
	}
	ret[returnSize] = '0';
	return ret;
}


给你一个长度为 n 的整数数组 nums 。
请你构建一个长度为 2 n  的答案数组 a n s  ，数组下标 从 0 开始计数 ，
0<=i<n
ans[i]=nums[i];
ans[i+n]==nums[i];
ans 由两个 nums 数组 串联 形成。返回数组 ans 。
//循环枚举.返回一个数组.malloc申请内存
int* getConcatenation(int* nums, int numsSize, int* returnSize)
{
	int i;
	int *ret = (int*)malloc(2 * numsSize * sizeof(int));//申请一块2倍的数组内存
	*returnSize = 2 * numsSize;
	//returnSize 是一个指向一个变量地址的指针.这个变量的目的就是告诉调用方
	//这个getConcatenation函数返回数组的长度.如果没有这个值.光凭返回值的数组首地址无法知道数组实际长度
	//要去2倍.所以指向2 * numsSize
	
	for (i = 0; i < numsSize; i++)
	{
		ret[i + numsSize] = ret[i] = nums[i];
	}
	return ret;
}


给你一个数组 nums ，数组中有 2 n  个元素
按[x1,x2....y1,y2]格式排列
请你按[x1,y1,x2,y2.....]排列.返回重排后的数组
/*
对于数组的映射关系,对于第i位置有奇数偶数情况区别
奇数:是在原先的n+i/2位置 
偶数:是在原先i+1/2位置
*/

int* shuffle(int* nums, int numsSize, int n, int* returnSize) {
	int i;
	int *ret = (int *)malloc(sizeof(int) * numsSize);  // (1)//堆内存
	for (i = 0; i < numsSize; ++i) {
		if (i & 1) {
			ret[i] = nums[n + i / 2];                      // (2)是在原先的n+i/2位置 
		}
		else {
			ret[i] = nums[(i + 1) / 2];                      // (3)是在原先i+1/2位置
		}
	}
	*returnSize = numsSize;                              // (4)返回数组长度.这个上面详细说了
	return ret;
}



输入数字 n ，按顺序打印出从 1 到最大的 n 位十进制数。
比如输入 3，则打印出 1、2、3 一直到最大的 3 位数 999。

/*
利用n次循环计算.再来一次循环对数组填充
*/

int* printNumbers(int n, int* returnSize) {
	int i;
	int f = 1;
	int *ret;

	for (i = 0; i < n; ++i) {
		f *= 10;                               // (1)计算10的n次方
	}
	--f;                                       // (2)计算10的n次方-1
	*returnSize = f;                           // (3)设置数组长度用于返回
	ret = (int *)malloc(f * sizeof(int));    // (4)申请堆内存用于填充
	for (i = 1; i <= f; ++i) {
		ret[i - 1] = i;                          // (5)填充数组返回
	}
	return ret;
}