数据结构与算法-二维数组

Posted by 周思进 on August 31, 2019

写一个程序,输出从 1 到 n 数字的字符串表示。

  1. 如果 n 是3的倍数,输出“Fizz”;

  2. 如果 n 是5的倍数,输出“Buzz”;

3.如果 n 同时是3和5的倍数,输出 “FizzBuzz”。

来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/fizz-buzz


char ** fizzBuzz(int n, int* returnSize)

上面是官方给的C语言实现接口声明,从接口来看,存放结果的指针地址并不是由外部传入,而是由接口返回。那么就需要在接口内部申请内存空间,外部进行释放。

这道题我个人觉得主要考察的是对二维数组,或者说是二级指针的理解。
这个好久没接触,的确是好好想了下。

char **array;

二维数组可以当做一维数组来对待,比如 int a[10]; char b[10];这样的一维数组其实就是数组元素的类型不相同而已。抽象一下就是 TYPE array[num];

套到二维数组,那么这里的TYPE 就是 char *,也就是数组的元素是一个char型的指针。当然题目中一维数组的个数也是动态的,需要手动申请内存,所以

array = malloc(n * 单个元素存储大小)

而这里单个元素存储大小就是 sizeof(char *),需要注意这里不是想当然的就当做4了,在32位系统中,指针的存储大小是4字节,在64位系统中就是8字节了。

然后对array一维素组进行下标取值操作,其结果就是一个指向char型的指针,该指针指向对应存储的字符串结果,如题目中的”Fizz”或”4”。
这里的指针所指向的存储空间大小本题中就定10个元素的存储空间大小。

下面是一开始想到的实现方式:

char ** fizzBuzz(int n, int* returnSize)
{
	char **array = NULL;
	int i = 0;
	*returnSize = n;

	array = malloc(n * sizeof(char *));	
	if (NULL == array)
	{
		return NULL;
	}

	printf("sizeof(char *) = %lu\n", sizeof(char *));	// 打印 %lu

	for (i = 1; i <= n; i++)	// 注意下标从1开始
	{
		if (i % 3 == 0 && i % 5 == 0 )
		{
			// 没有申请内存,不能进行拷贝操作,但可以指向字符串常量,节省一定的内存空间
			//memcpy(*(array + i), "FIZZBUZZ", strlen("FIZZBUZZ"));
			array[i - 1] = "FizzBuzz";	//  *(array + i-1) = "FIZZBUZZ";
			
		}
		else if (i % 3 == 0)
		{
			array[i - 1] = "Fizz";
		}
		else if (i % 5 == 0)
		{
			array[i - 1] = "Buzz";
		}
		else
		{
			#define INTER_STR 10	// 这里要申请了,定义10个字节存储
			array[i - 1] = malloc(INTER_STR * sizeof(char));
			memset(array[i - 1], 0, INTER_STR * sizeof(char));
			snprintf(array[i - 1], INTER_STR, "%d", i);
		}
	}

	return array;
}

看了官方解答,可以通过字符串拼接的方式,少做判断,如下:


char ** fizzBuzz_v2(int n, int* returnSize)
{
    ...
    
	for (i = 1; i <= n; i++)	// 注意下标从1开始
	{
		#define INTER_STR 10	// 这里要申请了,定义10个字节存储
		array[i - 1] = malloc(INTER_STR * sizeof(char));
		memset(array[i - 1], 0, INTER_STR * sizeof(char));
	
		if (i % 3 == 0)
		{
			strncpy(array[i - 1], "Fizz", INTER_STR);		// strncpy保证会\0结尾的
		}
		
		if (i % 5 == 0)
		{
			strncat(array[i - 1], "Buzz", INTER_STR-strlen(array[i - 1]));
		}
		
		if (strlen(array[i - 1]) == 0)
		{
			snprintf(array[i - 1], INTER_STR, "%d", i);
		}
	}

	return array;
}

还有散列表的方式,先搁置。