《一堆有趣算法题(1).doc》由会员分享，可在线阅读，更多相关《一堆有趣算法题(1).doc（25页珍藏版）》请在金锄头文库上搜索。
1、一串由17个数字排列成一个圆环，现在从第1个位置开始计数，沿着圆环去掉被3整除的位置和数字，最后留下的是哪些数字？ private void Test() List numbers = new List(); for (int i = 1; i 18; i+) numbers.Add(i); List results = this.Calculate(numbers, 3); Console.WriteLine(the remian is following numbers:); foreach (int i in results) Console.WriteLine(i.ToString()
2、; private List Calculate(List numbers, int interval) int remainAmount = numbers.Count % interval; List calculatedNumbers = new List(); for (int i = 0; i numbers.Count; i+) if (i.Equals(numbers.Count - remainAmount-1) for (int j = 0; j 0) return Calculate(calculatedNumbers, interval); else return cal
3、culatedNumbers; 最后结果是 剩下4和11。一个有趣的算法题10万个数丢了俩，如何找出从1到100000，随机取出2个数丢弃，剩余的数打乱顺序后放入数组array。要求遍历一次找到被取出的2个数。变量数不超过5个。1 不可另行开辟数组2 不可修改数组array内的元素代码:#define ARRAY_NUM(100000-2)int find(int n, const int a) /递归找到当前数组中小的没有的数，不知堆栈是否不够大而溢出，当然这个时间复杂度很高 for(int i=0;i if(ai=n+1) find(+n,ai); return n+1;int main(
4、void)int n1=0,n2;const int aARRAY_NUM;/要找的数组n1=find(n1,a);/找到丢掉中的小的n2=find(n1,a);/找到大的1. 怎样从100个杂乱的数中挑选出10个最大的数（不允许对这100个数排序）？要求时间复杂度和空间复杂度尽量小。2. 如果定义两个字符串中字母以及其个数相等，就说这两个字符串相等，比如：abbcdde 和 badcedb 就是相等的。写一个比较两个字符串相等的算法。要求时间复杂度和空间复杂度尽量小。3. 写一个算法，字符串移位，比如abcde移动三位是deabc。要求考虑时间和空间复杂度。4. 写一个算法，打印出一个字符串
5、的全排列.给定一个十进制数N，写下从1开始，到N的所有整数，然后数一下其中出现的所有1的个数。例如：N=2，写下1，2。这样只出现了1个1N=12,写下 1,2,3,4,5,6,7,8,9,10,11,12。这样1的个数是5请写出一个函数，返回1到N之间出现1的个数，比如 f(12)=5一开始看这个就想到遍历1-N，每个数里面的1数量加起来，这样算法复杂度为 N乘N的位数，即O(NLogN)。后来看了原作所写，这个问题有复杂度为o(LogN)的解，于是思考了一番，用递归实现了。同时写上O(NLogN)的遍历算法和原文作者的算法以作比较 1packagepuzzles; 2 3interface
6、Algrithm 4publicintresolve(intnumber); 5 6 7classRecursiveAlgrithmimplementsAlgrithm /按位递归算法,o(LogN) 8 Override 9publicintresolve(intnumber) 10if(number=0) 11return0;12 13intlength=(int) Math.log10(number);14if(length=0) 15return1;16 else17intcurrentLvl=scale(10, length);18inthead=number/currentLvl;
7、19if(head1) 20returncurrentLvl+(head)*resolve(currentLvl-1)21+resolve(number-head*currentLvl);22 else23returnnumber-currentLvl+1+(head)24*resolve(currentLvl-1)25+resolve(number-currentLvl);26 27 28 2930publicintscale(inta,intb) /指数运算31intres=1;32for(inti=0; ib; i+) 33 res=a*res;34 35returnres;36 373
8、839classEnumerateAlgrithmimplementsAlgrithm /遍历算法,o(NLogN)4041 Override42publicintresolve(intnumber) 43intsum=0;44for(inti=0; i0) 53if(number%10=1) 54 res+;55 56 number=number/10;57 58returnres;59 606162classReferedAlgrithmimplementsAlgrithm /原作者的算法,o(LogN)63 Override64publicintresolve(intn) 65intcount=0;66intfactor=1;67intlower;68intcurrent;69inthigher;70while(n/factor!=0) 71 lower=n-(n/factor)*factor;72 current=(n/factor)%10;73 higher=n/(factor*10);74switch(current) 75c
