/*copyright@nciaebupt 转载请注明出处题目：数组中有一个数字出现的次数超过了数组长度的一半，找出这个数字。分析： 1.首先我们想到如果是一个排序好的数组，那么我们只需要遍历一次数组，统计好每个数字出现的次数，如果大于数组长度的一半就输出这个数字。或者只需要直接输出array[N/2]的值即可。 2.如果是杂乱无章的数据我们可能回想先排序，然后...
#if 0/*copyright@nciaebupt 转载请注明出处问题：给你一个字符串，找出该字符串中对称的子字符串的最大长度。所谓对称子字符串，就是这个子字符串要么是以其中一个词对称：比如 "aba"， "abcba"；要么就完全对称：比如"abba", "abccba"。首先，我们用字符数组 char[] array 来保持这个字符串，假设现在已经遍历到第 i 个字符，...
/*copyright@nciaebupt 转载请注明出处题目：实现函数double Power(double base,int exponent)，求base的exponent次方。不得使用库函数，同时不需要考虑大树问题。分析：这道题目有以下几点需要注意：1. 0的0次方是无意义的，非法输入2. 0的负数次方相当于0作为除数，也是无意义的，非法输入3. base如果非0，如...
/*copyright@nciaebupt 转载请注明出处题目：把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个排好序的数组的一个旋转，输出旋转数组的最小元素。例如数组{3, 4, 5, 1, 2}为{1, 2, 3, 4, 5}的一个旋转，该数组的最小值为1。 分析：这道题最直观的解法并不难。从头到尾遍历数组一次，就能找出最小的元素，时间复杂度显然...
/*copyright@nciaebupt 转载请注明出处题目：输入一个正整数数组，将它们连接起来排成一个数，输出能排出的所有数字中最小的一个。例如输入数组{32, 321}，则输出这两个能排成的最小数字32132。请给出解决问题的算法，并证明该算法。分析：这道题其实是希望我们能找到一个排序规则，根据这个规则排出来的数组能排成一个最小的数字。要确定排序规则，就得比较两个数字，也就是给出两...
/*题目：把n个骰子扔在地上，所有骰子朝上一面的点数之和为S。输入n，打印出S的所有可能的值出现的概率。分析：利用基本的概率论知识，而不需要统计所有可能的S出现的次数。为了方便，这里先讨论某个S出现的概率，设为P(S),则有 P(S) = P(S1) + P(S2) + ... + P(Sk)S1,S2...Sk表示和为S的各种骰子组合。另外， P(Si) = P(a1...
zz from http://blog.csdn.net/xianliti/article/details/5644118百度2010年某个部门（不记得是哪个了）的实习生笔试题第一题就是这种题，只是一点小小的改动而已。 原题依然来源于网络中某位大侠的BLOG，感谢提供素材：） 写这篇blog是因为原文中提到的方法和原文评论中的方法相关比较大，评论中的方法用到...
/*copyright@nciaebupt 转载请注明出处题目：从扑克牌中随机抽5张牌，判断是不是一个顺子，即这5张牌是不是连续的。2-10为数字本身，A为1，J为11，Q为12，K为13，而大小王可以看成任意数字。思路一:我们需要把扑克牌的背景抽象成计算机语言。不难想象，我们可以把5张牌看成由5个数字组成的数组。大小王是特殊的数字，我们不妨把它们都当成0，这样和其他扑克牌代表的数字...
/*copyright@nciaebupt 转载请注明出处题目：用递归颠倒一个栈。例如输入栈{1, 2, 3, 4, 5}，1在栈顶。颠倒之后的栈为{5, 4, 3, 2, 1}，5处在栈顶。分析：我们把栈{1, 2, 3, 4, 5}看成由两部分组成：栈顶元素1和剩下的部分{2, 3, 4, 5}。如果我们能把{2, 3, 4, 5}颠倒过来，变成{5, 4, 3, 2}，然后在把原来的...
/*copyright@nciaebupt 转载请注明出处题目：输入数字n，按顺序输出从1到最大的n位10进制数。比如输入3，则输出1、2、3一直到最大的3位数即999。分析：如果我们在数字前面补0的话，就会发现n位所有10进制数其实就是n个从0到9的全排列。也就是说，我们把数字的每一位都从0到9排列一遍，就得到了所有的10进制数。只是我们在输出的时候，数字排在前面的0我们不输出罢了。 ...
/*copyright@nciaebupt 转载请注明出处题目：我们把只包含因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含因子7。习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第1500个丑数。分析：寻找一个数是不是满足某种数（质数，水仙数）等，最简单的方法就是遍历，对于任意一个丑数必定可以写成2^m*3^n*5^p，因而对于一个...
/*copyright@nciaebupt 转载请注明出处题目：两个单向链表，找出它们的第一个公共结点。链表的结点定义为：struct ListNode{ int m_n Key ; ListNode * m_pNe xt ;};分析：这是一道微软的面试题。微软非常喜欢与链表相关的题目，因此在微软的面试题中，链表出现的概...
/*copyright@nciaebupt 转载请注明出处题目：输入一个链表的头结点，从尾到头反到来输出每个结点的值。链表结点定义如下：struct ListNode{int m_nKey;ListNode* m_pNext;};分析：这是一道很故含义的面试题。该题以及它的变体经常展目前各大公司的面试、笔试题中。看到这道题后，第一反响是过去到后输出比拟容易。于是很慷慨地想到把链...
/*copyright@nciaebupt 转载请注明出处题目：给定链表的头指针和一个结点指针，在O(1)时间删除该结点。链表结点的定义如下：struct ListNode{ int m_nKey; ListNode* m_pNext;};函数的声明如下：void DeleteNode( ListNode* pListHead, ListNo...
/*copyright@nciaebupt 转载请注明出处题目：输入一个整数数组，调整数组中数字的顺序，使得所有奇数位于数组的前半部分，所有偶数位于数组的后半部分。要求时间复杂度为O(n)。分析：如果不考虑时间复杂度，最简单的思路应该是从头扫描这个数组，每碰到一个偶数时，拿出这个数字，并把位于这个数字后面的所有数字往前挪动一位。挪完之后在数组的末尾有一个空位，这时把该偶数放入这个空位。...
/*copyright@nciaebupt 转载请注明出处问题：输入一个字符串，输出该字符串中字符的所有组合。举个例子，如果输入abc，它的组合有a、b、c、ab、ac、bc、abc。分析：用递归求解。可以考虑求长度为n的字符串中m个字符的组合，设为C(n,m)。原问题的解即为C(n, 1), C(n, 2),...C(n, n)的总和。对于求C(n,m)，从第一个字符开始扫描，每个字符有...
/*copyright@nciaebupt 转载请注明出处题目：输入一个字符串，打印出该字符串中字符的所有排列。例如输入字符串abc，则输出由字符a、b、c所能排列出来的所有字符串abc、acb、bac、bca、cab和cba。分析：这是个递归求解的问题。递归算法有四个特性：（1)必须有可达到的终止条件，否则程序将陷入死循环；（2）子问题在规模上比原问题小；（3）子问题可通过再次递归调用求解...
/*copyright@nciaebupt 转载请注明出处题目：输入一棵二元树的根结点，求该树的深度。从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度。例如：输入二元树： 10 ...
/*copyright@nciaebupt 转载请注明出处题目：输入一个表示整数的字符串，把该字符串转换成整数并输出。例如输入字符串"345"，则输出整数345。分析：这道题尽管不是很难，学过C/C++语言一般都能实现基本功能，但不同程序员就这道题写出的代码有很大区别，可以说这道题能够很好地反应出程序员的思维和编程习惯，因此已经被包括微软在内的多家公司用作面试题。建议读者在往下看之前自...
/*copyright@nciaebupt 转载请注明出处题目：输入两个整数 n 和 m，从数列1，2，3.......n 中 随意取几个数,使其和等于 m ,要求将其中所有的可能组合列出来.e.gn=6,m=6 1,2,3 2,4 1,5*/#include #include #include int vecsum(std::vector & ive...
