<script type="text/javascript">
var arr = new Array();
var flag = new Array(1001);
for (var i = 1;i <= 1000;i++)
{
flag[i] = 0;
}
for (var i = 2;i <= 1000;i++)
{
if (flag[i] == 0)
{
flag[i] = 1;
arr.push(i);
for (var j = 1; j * i <= 100……
int Fibonacci(int n)
{
if (1 == n)
{
return 1;
}
if (2 == n)
{
return 2;
}
return Fibonacci(n-1) + Fibonacci(n-2);
}
int FibonacciIteration (int n)
{</p>
<p>int a = 1;
int b = 2;
if (n == 1)
return a;
if (n == 2)
return b;
……
题意很简单,给定一个n, 求一个最小的m,使得nm中的10进制表示只有0,1
方法1:Brute Force [大整数的情况需要考虑,何时终止,时间复杂度如何?]
bool CheckNumber(int number)
{
while(number)
{
if (number%10 != 0 && number%10 != 1)
return false;
number /= 10;
……
GCD: 最大公约数,能被m,n整数整除的最大的整数。
貌似很早的就有了欧几里得的辗转相除法法
GCD(x, y) = GCD(x, x%y)
x = k*y +b若d是x, y的最大公约数,那么d一定能被b整除,且d是x和b的最大公约数,b为x%y
代码如下:
// GCD
int GCD(int x, int y)
{
return y == 0 ? x : GCD(y, x % y);
}
在编程之美书中有对……
以下代码将问题简化为求无限循环小数的分数,至于有限的直接改成分数即可,不过涉及到另一个重要知识,就是求最大公约数,比较经典的是辗转相除法。
代码如下:
// GCD
int GCD(int x, int y)
{
return y == 0 ? x : GCD(y, x % y);
}</p>
<p>// Simplified conditions
x: 无线循环小数
n: 循环节的证书……
这个问题与寻找第k大/小 数等价。
方法1: 直接排序输出[编程之美书上说:不同的排序方法时间复杂度不一样,诚然,因为不需要n个数有序,只需要最大的k个数即可]
选用快速排序:
vector<</span>int> FindMostKSort(vector<</span>int>& vNumbers, int k)
{
sort(vNumbers.begin(),vNumber……
题意很简单,给定一个正整数n,求1-n中,1出现在各个数中的位数的次数之和。
比如针对特定的数12312,global count += 2;因为出现了两个1,输入n,要统计1-n的情况。
int VerifyCountOneNumberAns(int n)
{
int ans = 0;
for (int i = 1; i <= n;i++)
{
int tmp = i;
while(tmp)
{……
int FindMostIds(vector<</span>int> &ids)
{
map<</span>int,int>hashIds;
map<</span>int,int>::iterator it;
hashIds.clear();
for (int i = 0;i <</span> ids.size();i++)
{
it = hashIds.find(ids[i]);
if (hashIds.end() =……
1.
题意要求计算n!的value值后面有0的个数,实际上可以理解为n!的计算中有多少个5的倍数被乘入。
int CountZero(int n)
{
int cnt = 0;
for (int i = 1;i <= n;i++)
{
int tmp = i;
while (0 == i%5)
{
cnt++;
tmp /= 5;
}
}
return cn……
int CountOne(int val)
{
int cnt = 0;
while (val)
{
val &= val - 1;
cnt++;
}
return cnt;
}