/*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...
