3.求子數(shù)組的最大和
題目：
輸入一個(gè)整形數(shù)組，數(shù)組里有正數(shù)也有負(fù)數(shù)。
數(shù)組中連續(xù)的一個(gè)或多個(gè)整數(shù)組成一個(gè)子數(shù)組，每個(gè)子數(shù)組都有一個(gè)和。
求所有子數(shù)組的和的最大值。要求時(shí)間復(fù)雜度為O(n)。
例如輸入的數(shù)組為1, -2, 3, 10, -4, 7, 2, -5，和最大的子數(shù)組為3, 10, -4, 7, 2，
因此輸出為該子數(shù)組的和18。
第10題
翻轉(zhuǎn)句子中單詞的順序。
題目：輸入一個(gè)英文句子，翻轉(zhuǎn)句子中單詞的順序，但單詞內(nèi)字符的順序不變。
句子中單詞以空格符隔開。為簡(jiǎn)單起見，標(biāo)點(diǎn)符號(hào)和普通字母一樣處理。
例如輸入“I am a student.”，則輸出“student. a am I”。
第14題：
題目：輸入一個(gè)已經(jīng)按升序排序過的數(shù)組和一個(gè)數(shù)字，
在數(shù)組中查找兩個(gè)數(shù)，使得它們的和正好是輸入的那個(gè)數(shù)字。
要求時(shí)間復(fù)雜度是O(n)。如果有多對(duì)數(shù)字的和等于輸入的數(shù)字，輸出任意一對(duì)即可。
例如輸入數(shù)組1、2、4、7、11、15和數(shù)字15。由于4+11=15，因此輸出4和11。
第17題：
題目：在一個(gè)字符串中找到第一個(gè)只出現(xiàn)一次的字符。如輸入abaccdeff，則輸出b。
分析：這道題是2006年google的一道筆試題。
第20題：
題目：輸入一個(gè)表示整數(shù)的字符串，把該字符串轉(zhuǎn)換成整數(shù)并輸出。
例如輸入字符串"345"，則輸出整數(shù)345。
第25題：
寫一個(gè)函數(shù),它的原形是int continumax(char *outputstr,char *intputstr)
功能：
在字符串中找出連續(xù)最長(zhǎng)的數(shù)字串，并把這個(gè)串的長(zhǎng)度返回，
并把這個(gè)最長(zhǎng)數(shù)字串付給其中一個(gè)函數(shù)參數(shù)outputstr所指內(nèi)存。
例如："abcd12345ed125ss123456789"的首地址傳給intputstr后，函數(shù)將返回9，
outputstr所指的值為123456789
26.左旋轉(zhuǎn)字符串
題目：
定義字符串的左旋轉(zhuǎn)操作：把字符串前面的若干個(gè)字符移動(dòng)到字符串的尾部。
如把字符串a(chǎn)bcdef左旋轉(zhuǎn)2位得到字符串cdefab。請(qǐng)實(shí)現(xiàn)字符串左旋轉(zhuǎn)的函數(shù)。
要求時(shí)間對(duì)長(zhǎng)度為n的字符串操作的復(fù)雜度為O(n)，輔助內(nèi)存為O(1)。
37.
有n個(gè)長(zhǎng)為m+1的字符串，
如果某個(gè)字符串的最后m個(gè)字符與某個(gè)字符串的前m個(gè)字符匹配，則兩個(gè)字符串可以聯(lián)接，
問這n個(gè)字符串最多可以連成一個(gè)多長(zhǎng)的字符串，如果出現(xiàn)循環(huán)，則返回錯(cuò)誤。
45.雅虎：
1.對(duì)于一個(gè)整數(shù)矩陣，存在一種運(yùn)算，對(duì)矩陣中任意元素加一時(shí)，需要其相鄰（上下左右）
某一個(gè)元素也加一，現(xiàn)給出一正數(shù)矩陣，判斷其是否能夠由一個(gè)全零矩陣經(jīng)過上述運(yùn)算得到。
2.一個(gè)整數(shù)數(shù)組，長(zhǎng)度為n，將其分為m份，使各份的和相等，求m的最大值
比如{3，2，4，3，6} 可以分成{3，2，4，3，6} m=1;
{3,6}{2,4,3} m=2
{3,3}{2,4}{6} m=3 所以m的最大值為3
48.微軟：
一個(gè)數(shù)組是由一個(gè)遞減數(shù)列左移若干位形成的，比如{4，3，2，1，6，5}
是由{6，5，4，3，2，1}左移兩位形成的，在這種數(shù)組中查找某一個(gè)數(shù)。
51.和為n連續(xù)正數(shù)序列。
題目：輸入一個(gè)正數(shù)n，輸出所有和為n連續(xù)正數(shù)序列。
例如輸入15，由于1+2+3+4+5=4+5+6=7+8=15，所以輸出3個(gè)連續(xù)序列1-5、4-6和7-8。
分析：這是網(wǎng)易的一道面試題。
53.字符串的排列。
題目：輸入一個(gè)字符串，打印出該字符串中字符的所有排列。
例如輸入字符串a(chǎn)bc，則輸出由字符a、b、c所能排列出來的所有字符串
abc、acb、bac、bca、cab和cba。
分析：這是一道很好的考查對(duì)遞歸理解的編程題，
因此在過去一年中頻繁出現(xiàn)在各大公司的面試、筆試題中。
54.調(diào)整數(shù)組順序使奇數(shù)位于偶數(shù)前面。
題目：輸入一個(gè)整數(shù)數(shù)組，調(diào)整數(shù)組中數(shù)字的順序，使得所有奇數(shù)位于數(shù)組的前半部分，
所有偶數(shù)位于數(shù)組的后半部分。要求時(shí)間復(fù)雜度為O(n)。
56.最長(zhǎng)公共字串。
題目：如果字符串一的所有字符按其在字符串中的順序出現(xiàn)在另外一個(gè)字符串二中，
則字符串一稱之為字符串二的子串。
注意，并不要求子串（字符串一）的字符必須連續(xù)出現(xiàn)在字符串二中。
請(qǐng)編寫一個(gè)函數(shù)，輸入兩個(gè)字符串，求它們的最長(zhǎng)公共子串，并打印出最長(zhǎng)公共子串。
例如：輸入兩個(gè)字符串BDCABA和ABCBDAB，字符串BCBA和BDAB都是是它們的最長(zhǎng)公共子串，
則輸出它們的長(zhǎng)度4，并打印任意一個(gè)子串。
分析：求最長(zhǎng)公共子串（Longest Common Subsequence, LCS）是一道非常經(jīng)典的動(dòng)態(tài)規(guī)劃題，
因此一些重視算法的公司像MicroStrategy都把它當(dāng)作面試題。
63.在字符串中刪除特定的字符。
題目：輸入兩個(gè)字符串，從第一字符串中刪除第二個(gè)字符串中所有的字符。
例如，輸入”They are students.”和”aeiou”，
則刪除之后的第一個(gè)字符串變成”Thy r stdnts.”。
分析：這是一道微軟面試題。在微軟的常見面試題中，與字符串相關(guān)的題目占了很大的一部分，
因?yàn)閷懗绦虿僮髯址芎芎玫姆从澄覀兊木幊袒竟Α?/p>
69.旋轉(zhuǎn)數(shù)組中的最小元素。
題目：把一個(gè)數(shù)組最開始的若干個(gè)元素搬到數(shù)組的末尾，我們稱之為數(shù)組的旋轉(zhuǎn)。輸入一個(gè)排好序的數(shù)組的一個(gè)旋轉(zhuǎn)，
輸出旋轉(zhuǎn)數(shù)組的最小元素。例如數(shù)組{3, 4, 5, 1, 2}為{1, 2, 3, 4, 5}的一個(gè)旋轉(zhuǎn)，該數(shù)組的最小值為1。
分析：這道題最直觀的解法并不難。從頭到尾遍歷數(shù)組一次，就能找出最小的元素，
時(shí)間復(fù)雜度顯然是O(N)。但這個(gè)思路沒有利用輸入數(shù)組的特性，我們應(yīng)該能找到更好的解法。
73.對(duì)策字符串的最大長(zhǎng)度。
題目：輸入一個(gè)字符串，輸出該字符串中對(duì)稱的子字符串的最大長(zhǎng)度。
比如輸入字符串“google”，由于該字符串里最長(zhǎng)的對(duì)稱子字符串是“goog”，因此輸出4。
分析：可能很多人都寫過判斷一個(gè)字符串是不是對(duì)稱的函數(shù)，這個(gè)題目可以看成是該函數(shù)的加強(qiáng)版。
85.又見字符串的問題
1.給出一個(gè)函數(shù)來復(fù)制兩個(gè)字符串A和B。
字符串A的后幾個(gè)字節(jié)和字符串B的前幾個(gè)字節(jié)重疊。
分析：記住，這種題目往往就是考你對(duì)邊界的考慮情況。
2.已知一個(gè)字符串，比如asderwsde,尋找其中的一個(gè)子字符串比如sde的個(gè)數(shù)，
如果沒有返回0，有的話返回子字符串的個(gè)數(shù)。
88.2005年11月金山筆試題。編碼完成下面的處理函數(shù)。
函數(shù)將字符串中的字符'*'移到串的前部分，
前面的非'*'字符后移，但不能改變非'*'字符的先后順序，函數(shù)返回串中字符'*'的數(shù)量。
如原始串為：ab**cd**e*12，
處理后為*****abcde12，函數(shù)并返回值為5。（要求使用盡量少的時(shí)間和輔助空間）
93.在一個(gè)int數(shù)組里查找這樣的數(shù)，它大于等于左側(cè)所有數(shù)，小于等于右側(cè)所有數(shù)。
直觀想法是用兩個(gè)數(shù)組a、b。a[i]、b[i]分別保存從前到i的最大的數(shù)和從后到i的最小的數(shù)，
一個(gè)解答：這需要兩次遍歷，然后再遍歷一次原數(shù)組，
將所有data[i]>=a[i-1]&&data[i]<=b[i]的data[i]找出即可。
給出這個(gè)解答后，面試官有要求只能用一個(gè)輔助數(shù)組，且要求少遍歷一次。
94.微軟筆試題
求隨機(jī)數(shù)構(gòu)成的數(shù)組中找到長(zhǎng)度大于=3的最長(zhǎng)的等差數(shù)列9 d- x' W) w9 ?" o3 b0 R
輸出等差數(shù)列由小到大:
如果沒有符合條件的就輸出
格式：
輸入[1,3,0,5,-1,6]
輸出[-1,1,3,5]
要求時(shí)間復(fù)雜度，空間復(fù)雜度盡量小
96.08年中興校園招聘筆試題
1．編寫strcpy 函數(shù)
已知strcpy 函數(shù)的原型是
char *strcpy(char *strDest, const char *strSrc);
其中strDest 是目的字符串，strSrc 是源字符串。
不調(diào)用C++/C 的字符串庫函數(shù)，請(qǐng)編寫函數(shù) strcpy。
----------------
1.關(guān)于本微軟等公司數(shù)據(jù)結(jié)構(gòu)+算法面試100題系列V0.1版的鄭重聲明
http://blog.csdn.net/v_JULY_v/archive/2010/12/02/6050133.aspx
2.完整100題，請(qǐng)參見，
[珍藏版]微軟等數(shù)據(jù)結(jié)構(gòu)+算法面試100題全部出爐[100題首次完整亮相]
http://blog.csdn.net/v_JULY_v/archive/2010/12/06/6057286.aspx
3.更多詳情，請(qǐng)參見，本人博客：
My Blog：
http://blog.csdn.net/v_JULY_v
4.所有的資源（題目+答案）下載地址：
http://v_july_v.download.csdn.net/
5.本微軟等100題系列V0.1版，永久維護(hù)（網(wǎng)友，思路回復(fù)）地址：
http://topic.csdn.net/u/20101126/10/b4f12a00-6280-492f-b785-cb6835a63dc9.html