顺序输出到N的所有数

4-25 1,272 views

          好吧,小伙伴肯定鄙视我这么简单的题目也拿上来做太没意思了,于是快速的告诉我可以这么做:

void printer(int n)
{
	int num = 1;
	int i = 0;
	while(i++ < n)
	{
		num *= 10;

		for(i = 1; i < num; ++i)
			printf("%dt", i);
	}
}

            我们来分析分析,并没有规定n的范围,当输入的n很大的时候,我们求的最大的n位数再使用整型(int)或者长整型(long long),差不多都会溢出?也就是说我们需要考虑大数问题了,这是一个很大的陷阱,如果是作为一道面试题,那就要小心了。

             考虑新的方式,我们使用字符串模拟数组,然后解决这个大数问题。用字符串表示数字的时候,最直观的方法就是字符串里每个字符都是‘0’到‘9’之间的某一个字符,用来表示数字的一位。因为数字最大是n位的,因此我们需要一个长度为n+1的字符串(字符串中最后一个是结束符号'')。当实际数字不够n位的时候,在字符串的前版部分补0.

      首先我们把字符串中的每一个数字都初始化为‘0’,然后每一次为字符串表示的数字加1,再打印出来。一边模拟数字加分,一边把字符串的数字打印出来。不过小心的是"0000001"为了用户体验,最后就输出1. 前面的0无视。

void printer(int n)
{
	if(n < 0)
		return;

	char *num = new char[n + 1];
	memset(num, '0', n);
	num[n] = '\0';

	while(!increment(num))
	{
		printerNum(num);
	}

	delete []num;
}

          在上面的代码中,函数increment实现在表示数字的字符串number上增加1,而函数printerNum打印出numbers。这两个看似简单的函数都暗藏着小小的玄机。 我们需要知道什么时候停止在number上增加1,即什么时候到了最大的n位数"999...9"(n个9)。一个最简单的办法是每次递增之后,都调用库函数strcmp比较表示数字的字符串number和最大的n位数"999...9",如果相等则表示已经到了最大的n位数并终止递增。虽然调用strcmp很简单,但对于长度为n的字符串,它的时间复杂度为O(n) 我们注意到只有对"999...9"加1的时候,才会在第一个字符(下标为0)的甚础上产生进位,而其他所有情况都不会在第一个字符上产生进位。因此当我们发现在加1时第一个字符产生了进位,则已经是最大的n位数,此时increment返回true,因此函数printer的whi 1e循环终止。如何在每一次增加1之后快速判断是不是到了最大的n位数是本题的一个小陷阱。下面是increment函数的参考代码,它实现了用O(1)时间判断是不是已经到了最大的n位数:

bool increment(char *num)
{
        bool isOverflow = false;
        int takeOver = 0;
        int length = strlen(num);
        for(int i = length - 1; i >= 0; i--)
	{
		int sum = num[i] - '0' + takeOver;
		if(i == length - 1)
			sum++;

		if(sum >= 10)
		{
			if(i == 0)
				isOverflow = true;
			else
			{
				takeOver = 1;
				num[i] = '0' + sum;
			}
		}
		else
		{
			num[i] = '0' + sum;
			break;
		}
	}
	return isOverflow;
}

           接下来我们再考虑如何打印用字符串表示的数字。虽然库函数printf可以很方便就能打印一个字符串,但在本题中调用printf并不是最合适的解决方案。前面我们提到,当数字不够n位的时候,我们在数字的前面补0,打印的时候这些补位的0不应该打印出来。比如输入3的时候,数字98用字符串表示成“098"。如果直接打印出098,就不符合我们的习惯。为此我们定义了函数printerNum(),在这个函数里,我们只有在碰到第一个非O的字符之后才开始打印,直至字符串的结尾。能不能按照我们的阅读习惯打印数字,是面试官设置的另外一个小陷阱。实现代码如下:

void printerNum(char* num)
{
	bool isBeginning0 = true;
	int length = strlen(num);

	for(int i = 0; i < lengthl; ++i)
	{
		if(isBeginning0 && num[i] != '0')
			isBeginning0 = false;
		if(!isBeginning0)
		{
			printf("%c", num[i]);
		}
	}
	printf("t");
}

简化代码,递归实现过程:

void printer2(int n)
{
    if(n <= 0)
        return;

    char* num = new char[n + 1];
    num[n] = '\0';

    for(int i = 0; i < 10; ++i)
    {
        num[0] = i + '0';
        printerRecursively(num, n, 0);
    }

    delete[] num;
}

void printerRecursively(char* num, int length, int index)
{
    if(index == length - 1)
    {
        PrintNumber(num);
        return;
    }

    for(int i = 0; i < 10; ++i)
    {
        num[index + 1] = i + '0';
        printerRecursively(num, length, index + 1);
    }
}

7.混合高斯模型(Mixtures of Gaussians)和 EM 算法

这篇讨论使用期望最大化算法(Expectation-Maximization)来进行密度估计(density estimation)。 与k-means 一样,给定的训练样本是{x (1), … ,x (m)},我...

阅读全文

6. K-means聚类算法

K-means也是聚类算法中最简单的一种了,但是里面包含的思想却是不一般。聚类属于无监督学习,以往的回归、朴素贝叶斯、SVM等都是有类别标签y的,也就是说样例...

阅读全文