算法面试100题-读书笔记

1、第6 题不会腾讯面试题：给你10 分钟时间，根据上排给出十个数，在其下排填出对应的十个数要求下排每个数都是先前上排那十个数在下排出现的次数。上排的十个数如下：【0，1，2，3，4，5，6，7，8，9】举一个例子，数值: 0,1,2,3,4,5,6,7,8,9分配: 6,2,1,0,0,0,1,0,0,00 在下排出现了6 次，1 在下排出现了2 次，2 在下排出现了1 次，3 在下排出现了0 次.以此类推.不用乘法或加法增加8 倍。现在用同样的方法增加7 倍。增加8倍：x<<3增加7倍: 有两种方法：7 = 8 - 1 则：(x<<3)-x7 = (16-2)/2 则：

2、(x<<4 - x<<1)>>1第10 题翻转句子中单词的顺序。题目：输入一个英文句子，翻转句子中单词的顺序，但单词内字符的顺序不变。句子中单词以空格符隔开。为简单起见，标点符号和普通字母一样处理。例如输入“I am a student.”，则输出“student. a am I”。Answer：先把句子全部翻转， 再翻转每个单词。第15题：题目：输入一颗二元查找树，将该树转换为它的镜像，即在转换后的二元查找树中，左子树的结点都大于右子树的结点。用递归和循环两种方法完成树的镜像转换。  例如输入：   8 

3、/ /6  10/ / / /5 7 9 11输出：    8   / /  10  6/ / / /11 9 7  5定义二元查找树的结点为：struct BSTreeNode / a node in the binary search tree (BST)  int m_nValue; / value of node  BSTreeNode *m_pLeft; / left child of node  BSTreeNode *m_pRight; / right chil

4、d of node;/就是递归翻转树，有子树则递归翻转子树。/July、2010/10/19void Revertsetree(list *root)    if(!root)       return;    list *p;    p=root->leftch;    root->leftch=root->rightch;    root->rightch=p

5、;    if(root->leftch)      Revertsetree(root->leftch);    if(root->rightch)      Revertsetree(root->rightch); 由于递归的本质是编译器生成了一个函数调用的栈，因此用循环来完成同样任务时最简单的办法就是用一个辅助栈来模拟递归。首先我们把树的头结点放入栈中。在循环中，只要栈不为空，弹出栈的栈顶结点，交

6、换它的左右子树。如果它有左子树，把它的左子树压入栈中；如果它有右子树，把它的右子树压入栈中。这样在下次循环中就能交换它儿子结点的左右子树了。/再用辅助栈模拟递归，改成循环的（有误之处，望不吝指正）：void Revertsetree(list *phead)    if(!phead)       return;    stack<list*> stacklist;    stacklist.push(phead); 

7、60;       /首先把树的头结点放入栈中。    while(stacklist.size()    /在循环中，只要栈不为空，弹出栈的栈顶结点，交换它的左右子树          list* pnode=stacklist.top();      stacklist.pop();     &

8、#160;  list *ptemp;      ptemp=pnode->leftch;      pnode->leftch=pnode->rightch;      pnode->rightch=ptemp;      if(pnode->leftch)        stackli

9、st.push(pnode->leftch);   /若有左子树，把它的左子树压入栈中      if(pnode->rightch)        stacklist.push(pnode->rightch);  /若有右子树，把它的右子树压入栈中    32.有两个序列a,b，大小都为n,序列元素的值任意整数，无序；要求：通过交换a,b中的元素，使序列a元素的和与序列b元素的和之间的差最小。例如

10、: var a=100,99,98,1,2, 3;var b=1, 2, 3, 4,5,40;求解思路：    当前数组a和数组b的和之差为    A = sum(a) - sum(b)    a的第i个元素和b的第j个元素交换后，a和b的和之差为    A' = sum(a) - ai + bj - （sum(b) - bj + ai)          

11、= sum(a) - sum(b) - 2 (ai - bj)           = A - 2 (ai - bj)    设x = ai - bj    |A| - |A'| = |A| - |A-2x|    假设A > 0,    当x 在 (0,A)之间时，做这样的交换才能使得交换后的a和b的和之差变小，x越接近A/2效果越好,  &

12、#160; 如果找不到在(0,A)之间的x，则当前的a和b就是答案。    所以算法大概如下：    在a和b中寻找使得x在(0,A)之间并且最接近A/2的i和j，交换相应的i和j元素，重新计算A后，重复前面的步骤直至找不到(0,A)之间的x为止。/算法1. 将两序列合并为一个序列，并排序，为序列Source 2. 拿出最大元素Big，次大的元素Small 3. 在余下的序列S:-2进行平分，得到序列max，min 4. 将Small加到max序列，将Big加大min序列，重新计算新序列和，和大的为max

13、，小的为min。/def mean( sorted_list ):    if not sorted_list:        return (,)     big = sorted_list-1    small = sorted_list-2    big_list, small_list = mean(sorted_list:-2)     big_l

14、ist.append(small)    small_list.append(big)     big_list_sum = sum(big_list)    small_list_sum = sum(small_list)     if big_list_sum > small_list_sum:        return ( (big_list, small_list)

15、60;   else:        return ( small_list, big_list) tests =    1,2,3,4,5,6,700,800,            10001,10000,100,90,50,1,            r

16、ange(1, 11),            12312, 12311, 232, 210, 30, 29, 3, 2, 1, 1            for l in tests:    l.sort()    print    print "Source List:/t&

17、quot;, l    l1,l2 = mean(l)    print "Result List:/t", l1, l2    print "Distance:/t", abs(sum(l1)-sum(l2)    print '-*'*40输出结果Source List:    1, 2, 3, 4, 5, 6, 700, 800Result List:   

18、; 1, 4, 5, 800 2, 3, 6, 700Distance:       99-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*Source List:    1, 50, 90, 100, 10000, 10001Result List:    50, 90, 10000 1, 100, 10001Distance:   &

19、#160;   38-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*Source List:    1, 2, 3, 4, 5, 6, 7, 8, 9, 10Result List:    2, 3, 6, 7, 10 1, 4, 5, 8, 9Distance:       1-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*

20、-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*Source List:    1, 1, 2, 3, 29, 30, 210, 232, 12311, 12312Result List:    1, 3, 29, 232, 12311 1, 2, 30, 210, 12312Distance:       2137.有n个长为m+1的字符串，如果某个字符串的最后m个字符与某个字符串的前m个字符匹配，则两个字符串可以联接，问这n个字

21、符串最多可以连成一个多长的字符串，如果出现循环，则返回错误。恩，好办法引用 5 楼 hblac 的回复:37. 把每个字符串看成一个图的顶点，两个字符串匹配就连一条有向边。相当于判断一个有向图是否有环以及求它的直径38.百度面试：1.用天平（只能比较，不能称重）从一堆小球中找出其中唯一一个较轻的，使用x次天平，最多可以从y个小球中找出较轻的那个，求y与x的关系式因为已知“坏球”是较轻的，因此采用三分法效率最高。即1到3球需1次；4到9球需2次；10到27球需3次。则关系式有：Y=3的X次方。或表示成X=【Log3底Y】。【】表示向上取整数符号。44.腾讯面试题：1.设计一个魔方（六面）的程序。

22、第一题魔方 其实也很简单！ 先说面，每面有四边，因此要建立4个句柄对应：上下左右，四个去面，就像双向链表节点有上下两面一样，然后面里有方块矩阵，2级的数组，加完数组写个方法函数，叫旋转,参数是行列号/旋向 ，旋向上下时行列号为行号，旋向左右时行列号为列号，意思是把某行某列往某方向旋转。矩阵里有方块，方块有 创建六个面，按照魔方的样子，将第一面为正面，往下是底面（把第二面拿过来），底面往下是背面，背面往下联就是上面，上面往下是正面，现在回到正面，正面往左联就是左面，左面往左联就是后面，后面往左就是右面，右面往左是正面。（这里不用罗索了，自己看明白了就知道怎么做了）六个面创建完

23、并上下左右连通后，这个程序就完成了2.有一千万条短信，有重复，以文本文件的形式保存，一行一条，有重复。请用5 分钟时间，找出重复出现最多的前10 条。2，建立一个红黑树a;遍历短信,对每条短信取MD5值，对每个MD5值在a中做操作：如果有值，这个key对应的值就+1，否则就=1；遍历完后对红黑树取值最大的10个数，复杂度为10*lgn。3.收藏了1 万条url，现在给你一条url，如何找出相似的url。（面试官不解释何为相似）51.和为n连续正数序列。题目：输入一个正数n，输出所有和为n连续正数序列。例如输入15，由于1+2+3+4+5=4+5+6=7+8=15，所以输出3个连续序列1-5、4

24、-6和7-8。分析：这是网易的一道面试题。这道题和本微软面试100题系列V0.1版的第14题有些类似。我们可用两个数small和big分别表示序列的最小值和最大值。首先把small初始化为1，big初始化为2。如果从small到big的序列的和大于n的话，我们向右移动small，相当于从序列中去掉较小的数字。如果从small到big的序列的和小于n的话，我们向右移动big，相当于向序列中添加big的下一个数字。一直到small等于(1+n)/2，因为序列至少要有两个数字。 基于这个思路，我们可以写出如下代码:void PrintContinuousSequence(int small

25、, int big);/ Find continuous sequence, whose sum is nvoid FindContinuousSequence(int n)      if(n < 3)            return;      int small = 1;       int big = 2;&#

26、160;     int middle = (1 + n) / 2;      int sum = small + big;      while(small < middle)                  / we are lucky and find the sequence

27、0;           if(sum = n)                  PrintContinuousSequence(small, big);            / if the current sum

28、 is greater than n,             / move small forward            while(sum > n)                  &

29、#160;           sum -= small;                  small +;                  / we ar

30、e lucky and find the sequence                  if(sum = n)                        PrintContinuousSeq

31、uence(small, big);                        / move big forward            big +;         

32、60;  sum += big;      / Print continuous sequence between small and bigvoid PrintContinuousSequence(int small, int big)      for(int i = small; i <= big; + i)            printf("%d &

33、quot;, i);      printf("/n"); 54.调整数组顺序使奇数位于偶数前面。题目：输入一个整数数组，调整数组中数字的顺序，使得所有奇数位于数组的前半部分，所有偶数位于数组的后半部分。要求时间复杂度为O(n)。讨论：上面的代码有三点值得提出来和大家讨论：函数isEven判断一个数字是不是偶数并没有用%运算符而是用&。理由是通常情况下位运算符比%要快一些；这道题有很多变种。这里要求是把奇数放在偶数的前面，如果把要求改成：把负数放在非负数的前面等，思路都是都一样的。在函数Reorder中，用

34、函数指针func指向的函数来判断一个数字是不是符合给定的条件，而不是用在代码直接判断（hard code）。这样的好处是把调整顺序的算法和调整的标准分开了（即解耦，decouple）。当调整的标准改变时，Reorder的代码不需要修改，只需要提供一个新的确定调整标准的函数即可，提高了代码的可维护性。例如要求把负数放在非负数的前面，我们不需要修改Reorder的代码，只需添加一个函数来判断整数是不是非负数。这样的思路在很多库中都有广泛的应用，比如在的很多算法函数中都有一个仿函数（functor）的参数（当然仿函数不是函数指针，但其思想是一样的）。如果在面试中能够想到这一层，无疑能给面试官留下很好

35、的印象。56.最长公共子序列。题目：如果字符串一的所有字符按其在字符串中的顺序出现在另外一个字符串二中，则字符串一称之为字符串二的子串。注意，并不要求子串（字符串一）的字符必须连续出现在字符串二中。请编写一个函数，输入两个字符串，求它们的最长公共子串，并打印出最长公共子串。例如：输入两个字符串BDCABA和ABCBDAB，字符串BCBA和BDAB都是是它们的最长公共子串，则输出它们的长度4，并打印任意一个子串。 分析：求最长公共子串（Longest Common Subsequence, LCS）是一道非常经典的动态规划题，因此一些重视算法的公司像MicroStrategy都把它当作

36、面试题。完整介绍动态规划将需要很长的篇幅，因此我不打算在此全面讨论动态规划相关的概念，只集中对LCS直接相关内容作讨论。如果对动态规划不是很熟悉，请参考相关算法书比如算法讨论。 先介绍LCS问题的性质：记Xm=x0, x1,xm-1和Yn=y0,y1,yn-1为两个字符串，而Zk=z0,z1,zk-1是它们的LCS，则：1.       如果xm-1=yn-1，那么zk-1=xm-1=yn-1，并且Zk-1是Xm-1和Yn-1的LCS；2.       如果xm-1

37、yn-1，那么当zk-1xm-1时Z是Xm-1和Y的LCS；3.       如果xm-1yn-1，那么当zk-1yn-1时Z是Yn-1和X的LCS； 下面简单证明一下这些性质：1.       如果zk-1xm-1，那么我们可以把xm-1（yn-1）加到Z中得到Z，这样就得到X和Y的一个长度为k+1的公共子串Z。这就与长度为k的Z是X和Y的LCS相矛盾了。因此一定有zk-1=xm-1=yn-1。既然zk-1=xm-1=yn-1，那如果我们删除zk-1（xm-1、y

38、n-1）得到的Zk-1，Xm-1和Yn-1，显然Zk-1是Xm-1和Yn-1的一个公共子串，现在我们证明Zk-1是Xm-1和Yn-1的LCS。用反证法不难证明。假设有Xm-1和Yn-1有一个长度超过k-1的公共子串W，那么我们把加到W中得到W，那W就是X和Y的公共子串，并且长度超过k，这就和已知条件相矛盾了。2.       还是用反证法证明。假设Z不是Xm-1和Y的LCS，则存在一个长度超过k的W是Xm-1和Y的LCS，那W肯定也X和Y的公共子串，而已知条件中X和Y的公共子串的最大长度为k。矛盾。3.  

39、0;    证明同2。 有了上面的性质，我们可以得出如下的思路：求两字符串Xm=x0, x1,xm-1和Yn=y0,y1,yn-1的LCS，如果xm-1=yn-1，那么只需求得Xm-1和Yn-1的LCS，并在其后添加xm-1（yn-1）即可；如果xm-1yn-1，我们分别求得Xm-1和Y的LCS和Yn-1和X的LCS，并且这两个LCS中较长的一个为X和Y的LCS。 如果我们记字符串Xi和Yj的LCS的长度为ci,j，我们可以递归地求ci,j：        

40、0; /      0                               if i<0 or j<0ci,j=         

41、 ci-1,j-1+1                    if i,j>=0 and xi=xj         /       max(ci,j-1,ci-1,j        

42、   if i,j>=0 and xixj 上面的公式用递归函数不难求得。但从前面求Fibonacci第n项(本微软等100题系列第19题）的分析中我们知道直接递归会有很多重复计算，我们用从底向上循环求解的思路效率更高。 为了能够采用循环求解的思路，我们用一个矩阵（参考代码中的LCS_length）保存下来当前已经计算好了的ci,j，当后面的计算需要这些数据时就可以直接从矩阵读取。另外，求取ci,j可以从ci-1,j-1 、ci,j-1或者ci-1,j三个方向计算得到，相当于在矩阵LCS_length中是从ci-1,j-1，ci,j-1或者ci-1

43、,j的某一个各自移动到ci,j，因此在矩阵中有三种不同的移动方向：向左、向上和向左上方，其中只有向左上方移动时才表明找到LCS中的一个字符。于是我们需要用另外一个矩阵（参考代码中的LCS_direction）保存移动的方向。58.从尾到头输出链表。题目：输入一个链表的头结点，从尾到头反过来输出每个结点的值。链表结点定义如下：struct ListNode      int       m_nKey;      ListNode* m_p

44、Next;分析：这是一道很有意思的面试题。该题以及它的变体经常出现在各大公司的面试、笔试题中。 看到这道题后，第一反应是从头到尾输出比较简单。于是很自然地想到把链表中链接结点的指针反转过来，改变链表的方向。然后就可以从头到尾输出了。反转链表的算法详见此微软100题系列第24题，在此不再细述。但该方法需要额外的操作，应该还有更好的方法。 接下来的想法是从头到尾遍历链表，每经过一个结点的时候，把该结点放到一个栈中。当遍历完整个链表后，再从栈顶开始输出结点的值，此时输出的结点的顺序已经反转过来了。该方法需要维护一个额外的栈，实现起来比较麻烦。既然想到了栈来实现这个函数，而递归本质

45、上就是一个栈结构。于是很自然的又想到了用递归来实现。要实现反过来输出链表，我们每访问到一个结点的时候，先递归输出它后面的结点，再输出该结点自身，这样链表的输出结果就反过来了。 60.在O（1）时间内删除链表结点。题目：给定链表的头指针和一个结点指针，在O(1)时间删除该结点。链表结点的定义如下：struct ListNode      int        m_nKey;      ListNode*  m

46、_pNext;函数的声明如下：void DeleteNode(ListNode* pListHead, ListNode* pToBeDeleted);分析：这是一道广为流传的Google面试题，能有效考察我们的编程基本功，还能考察我们的反应速度，更重要的是，还能考察我们对时间复杂度的理解。在链表中删除一个结点，最常规的做法是从链表的头结点开始，顺序查找要删除的结点，找到之后再删除。由于需要顺序查找，时间复杂度自然就是O(n) 了。 我们之所以需要从头结点开始查找要删除的结点，是因为我们需要得到要删除的结点的前面一个结点。我们试着换一种思路。我们可以从给定的结点得到它的下一个结点。这

47、个时候我们实际删除的是它的下一个结点，由于我们已经得到实际删除的结点的前面一个结点，因此完全是可以实现的。当然，在删除之前，我们需要需要把给定的结点的下一个结点的数据拷贝到给定的结点中。此时，时间复杂度为O(1)。 上面的思路还有一个问题：如果删除的结点位于链表的尾部，没有下一个结点，怎么办？我们仍然从链表的头结点开始，顺便遍历得到给定结点的前序结点，并完成删除操作。这个时候时间复杂度是O(n)。 (自己理解：因为最后一节节点的next须为null)那题目要求我们需要在O(1)时间完成删除操作，我们的算法是不是不符合要求？实际上，假设链表总共有n个结点，我们的算法在n-1总情况下时间

48、复杂度是O(1)，只有当给定的结点处于链表末尾的时候，时间复杂度为O(n)。那么平均时间复杂度(n-1)*O(1)+O(n)/n，仍然为O(1)。63 例如，输入”They are students.”和”aeiou”，则删除之后的第一个字符串变成”Thy r stdnts.”。思路：不成避免的是遍历第一个字符串，若是遍历一个字符，都须要去第二个字符串中查找其存不存在，那么错杂度会是O（nm），当然因为字符数有限，所以m是个常量。关于查找速度最快的当然是hash表，对于8位字符，size=28足矣。关于删除字符，后面的字符要往前移，若是每删除一个就移一次，O（n2）这错杂度其实太高，仅仅用快慢

49、指针就可以搞定，这个办法很是有效，比如求解轮回链表。初始化：快慢指针指向第一个字符轮回：若是快指针指的是不须要的字符，将值赋给慢指针后，快慢指针同时+;若是快指针指向待删除字符，那么直接+；终止：快指针指向""0"" n个骰子的点数和分类： 优化时间和空间效率2012-04-14 11:01 37人阅读 评论(0) 收藏 举报原题依然来源于网络中某位大侠的BLOG，感谢提供素材：） 写这篇blog是因为原文中提到的方法和原文评论中的方法相关比较大，评论中的方法用到了DP，效率好很多。后

50、来仔细想想，这种实现方法用“表格法”来解释更恰当，至底向上填写表格，最终得到结果。另外，这种至底向上的填表法，当前表格的值只与下一层表格的值有关，所以实现中并没有分配所有表格空间，只用了两行，一行保存上一次的结果，另一行保存现在正在计算的值，这里是可以节省很多空间的。这种方法我记得在算法导论的“动态规划”一章有详述。  题目：把n个骰子扔在地上，所有骰子朝上一面的点数之和为S。输入n，打印出S的所有可能的值出现的概率。 先分析思路，再看实现。 首先解决前提性的问题：一个骰子的点数只可能是1,6,所以S的值的取值范围是n,6n，这里当然只考虑整数。

51、0;思路一：统计各个S值出现的次数，然后       各个S值出现的概率 = 各个S值出现的次数 / n个骰子所有点数的排列数  其中，n个骰子所有点数的排列数等于6n,而各个S值出现的次数就需要建立一个数组来进行统计。这时，问题就变成怎样来求各个S出现的次数了。方法我直接引用原文的文字如下：  =  以下文字引用自原文 = 分析：玩过麻将的都知道，骰子一共6个面，每个面上都有一个点数，对应的数字是1到 6之间的一个数字。所以，n个骰子的点数和的最小值为n，最大值为

52、6n。因此，一个直观的思路就是定义一个长度为6n-n的数组，和为S的点数出现的次数保存到数组第S-n个元素里。另外，我们还知道n个骰子的所有点数的排列数6n。一旦我们统计出每一点数出现的次数之后，因此只要把每一点数出现的次数除以6n，就得到了对应的概率。该思路的关键就是统计每一点数出现的次数。要求出n个骰子的点数和，我们可以先把n个骰子分为两堆：第一堆只有一个，另一个有n-1个。单独的那一个有可能出现从1到6的点数。我们需要计算从1到6的每一种点数和剩下的n-1个骰子来计算点数和。接下来把剩下的n-1个骰子还是分成两堆，第一堆只有一个，第二堆有n-2个。我们把上一轮那个单独骰子的点数和这一轮单

53、独骰子的点数相加，再和剩下的n-2个骰子来计算点数和。分析到这里，我们不难发现，这是一种递归的思路。递归结束的条件就是最后只剩下一个骰子了。 =  以上文字引用自原文 = 思路一明晰了，代码应该不难写，同样引用原文的代码： c-sharp view plaincopyint g_maxValue = 6;         void PrintSumProbabilityOfDices(int number)

54、            if(number < 1)            return;             int maxSum = number *

55、60;g_maxValue;        int* pProbabilities = new intmaxSum - number + 1;        for(int i = number; i <= maxSum; +i)    

56、60;       pProbabilitiesi - number = 0;             SumProbabilityOfDices(number, pProbabilities);             

57、;int total = pow(float)g_maxValue, number);        for(int i = number; i <= maxSum; +i)                   &

58、#160;float ratio = (float)pProbabilitiesi - number / total;            printf("%d: %f/n", i, ratio);             &#

59、160;       void SumProbabilityOfDices(int number, int* pProbabilities)            for(int i = 1; i <= g_maxValue; +i)     

60、       SumProbabilityOfDices(number, number, i, 0, pProbabilities);             void SumProbabilityOfDices(int original, int current, int value, 

61、int tempSum, int* pProbabilities)            if(current = 1)                    int sum = value 

62、;+ tempSum;            pProbabilitiessum - original+;                else            

63、        for(int i = 1; i <= g_maxValue; +i)                            int su

64、m = value + tempSum;                SumProbabilityOfDices(original, current - 1, i, sum, pProbabilities);           

65、;               思路二：利用基本的概率论知识，而不需要统计所有可能的S出现的次数。为了方便，这里先讨论某个S出现的概率，设为P(S),则有    P(S) = P(S1) + P(S2) + . + P(Sk)S1,S2.Sk表示和为S的各种骰子组合。另外，     P(Si) = P(a1) + P(a2) + . + P(an)其中，P(ai)表示第i个骰子

66、出现值为ai的概率。很简单的，就是一个概率论的东西，很基本的。不需要统计所有可能的S出现的次数，而直接计算和为S的各种可能的骰子组合的概率，然后把所有组合的概率相加，就得到了和为S的概率了。先把代码贴出来吧，没上机测试，细节上有什么问题不太清楚，关键是主程序应该是没问题的。代码来源于原文的评论中。c-sharp view plaincopy#include <iostream>  int main()      const int N =

67、60;20; double a26*N+1 =(0.0),0.0;      for (int i = 1;i<=6;i+) a1i = 1.0/6; int flag = 1;      for (int k = 2;k<=N;k+)    &#

68、160;      for (int i = 0;i<=6*N;i+)               a1-flagi = 0; int j = 1;           &#

69、160;  while (j<=i && j<=6)   a1-flagi += aflagi-j+/6;                    flag = 1-flag;      

70、60;     for (int i = 1;i<=6*N;i+)  std:cout<<i<<": "<<aflagi <<std:endl;     如果看懂了代码就不用看下面的了，下文只是代码的一个注释，以免以后老了脑子不好使看不懂这种方法是DP中的表格法，用至底向上填表的方式，把结果求出来。用表格法，一行代表一个骰子，列表示各个S值，所

71、以一共有6*N列。本来是要用N行的，可是这里只用了一个二维的数组，因为现在计算的值只与前一次计算的值相关，所以其中一行保存上一次计算的结果，另一行保存正在计算的结果，这样可以节省大量的空间。代码中的N是指有几个骰子，或者说是掷了几次骰子。第一个for循环表示第一个骰子的情况，然后第二个for循环中的k表示第k个骰子。当到了第k个骰子时，内层的for循环开始对和个S的值进行分析，i表示的就是各个不同的S。在这个循环里，考虑第k个骰子的6种不同取值（j表示的就是骰子的点数），然后在while循环里把所有可能的得到和为S的组合的概率进行相加。flag的作用很简单，就是在二维数组里对当时值和已经计算得

72、到的值进行区别，他只出现在数组的行号处。  画个图的话，就容易理解了。有时间再上图吧。68.把数组排成最小的数。题目：输入一个正整数数组，将它们连接起来排成一个数，输出能排出的所有数字中最小的一个。例如输入数组32, 321，则输出这两个能排成的最小数字32132。请给出解决问题的算法，并证明该算法。分析：这是09 年6 月份百度的一道面试题，从这道题我们可以看出百度对应聘者在算法方面有很高的要求。下面写我的思路。 刚拿到这题，我没想到用字符串来做，而是想把整数拆开成一位一位的数字来进行比较。这种方法在原文的评论中，有其他人也是这么想的。原文的分析已经说得比较明白

73、了，这个题其实就是要明确一种两个数之间的比较策略，也就是一组数的排序规则，具体点说，就是要重写compare方法，如果是java语言，只要重载compareTo方法，然后用sort方法就行了。 假设有两个数：A和B，其中，A由m个数字组成，表示成a1a2.am,B由n个数字组成，表示成b1b2.bn.比较的规则是这样的,从左到右比较，即从最高位开始，到最低位（个位）1、如果ai= bi,则比较下一位数；2、如果ai< bi,则A应该排到B前面；3、如果A的所有位和B的前m位相同，即a1=b1,a2=b2,.,am=bm,另外，n>m。则继续比较a1和bm+1。利用上面那个规则进行比较，直到确定A和B之间的关系72. 题目：设计一个类，我们只能生成该类的一个实例。分析：只能生成一个实例的类是实现了Singleton 模式的类型。ANSWER单例模式用法很多，下面算是比较通用的一种：class Singleton private static Singleton s;