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

1

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

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

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

1

          在上面的代码中,函数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位数:

1

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

1

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

1

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

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

阅读全文

6. K-means聚类算法

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

阅读全文