? 程序員為什么要學(xué)數(shù)據(jù)結(jié)構(gòu)？

? ??在計(jì)算機(jī)發(fā)展的初期，人們使用計(jì)算機(jī)的主要目的是處理數(shù)值計(jì)算問題。使用計(jì)算機(jī)解決具體問題一般需要經(jīng)過以下幾個(gè)步驟：首先從具體問題抽象出適當(dāng)?shù)臄?shù)學(xué)模型，然后設(shè)計(jì)或選擇解此數(shù)學(xué)模型的算法，接著編寫程序并進(jìn)行調(diào)試、測(cè)試，直至得到最終的解答。

? ? 由于最初涉及的運(yùn)算對(duì)象是簡(jiǎn)單的整型、實(shí)型或布爾型數(shù)據(jù)，所以程序設(shè)計(jì)者的主要精力集中于程序設(shè)計(jì)的技巧上，而無需重視數(shù)據(jù)結(jié)構(gòu)。隨著計(jì)算機(jī)應(yīng)用領(lǐng)域的擴(kuò)大和軟硬件的發(fā)展，非數(shù)值計(jì)算問題顯得越來越重要，據(jù)統(tǒng)計(jì)，當(dāng)今處理非數(shù)值計(jì)算問題占用了90%以上的機(jī)器時(shí)間。這類問題涉及的數(shù)據(jù)結(jié)構(gòu)更為復(fù)雜，數(shù)據(jù)元素之間的相互關(guān)系一般無法用數(shù)學(xué)方程式加以描述。因此，解決這類問題的關(guān)鍵不再是數(shù)學(xué)分析和計(jì)算方法，而是要設(shè)計(jì)出合適的數(shù)據(jù)結(jié)構(gòu)。

? ? 著名的瑞士計(jì)算機(jī)科學(xué)家沃思（N.Wirth）教授曾提出：算法 + 數(shù)據(jù)結(jié)構(gòu)＝程序

? ? 程序設(shè)計(jì)的實(shí)質(zhì)是對(duì)實(shí)際問題設(shè)計(jì)/選擇好的數(shù)據(jù)結(jié)構(gòu)和好的算法，而好的算法在很大程度上取決于描述實(shí)際問題的數(shù)據(jù)結(jié)構(gòu)。

1、把二元查找樹轉(zhuǎn)變成排序的雙向鏈表

題目：輸入一棵二元查找樹，將該二元查找樹轉(zhuǎn)換成一個(gè)排序的雙向鏈表。

要求不能創(chuàng)建任何新的結(jié)點(diǎn)，只調(diào)整指針的指向。

2、設(shè)計(jì)包含min 函數(shù)的棧

題目：定義棧的數(shù)據(jù)結(jié)構(gòu)，要求添加一個(gè)min 函數(shù)，能夠得到棧的最小元素。

要求函數(shù)min、push 以及pop 的時(shí)間復(fù)雜度都是O(1)。

3、求子數(shù)組的最大和

題目：輸入一個(gè)整形數(shù)組，數(shù)組里有正數(shù)也有負(fù)數(shù)。數(shù)組中連續(xù)的一個(gè)或多個(gè)整數(shù)組成一個(gè)子數(shù)組，每個(gè)子數(shù)組都有一個(gè)和。

求所有子數(shù)組的和的最大值。要求時(shí)間復(fù)雜度為O(n)。

4、在二元樹中找出和為某一值的所有路徑

題目：輸入一個(gè)整數(shù)和一棵二元樹，從樹的根結(jié)點(diǎn)開始往下訪問一直到葉結(jié)點(diǎn)所經(jīng)過的所有結(jié)點(diǎn)形成一條路徑。

打印出和與輸入整數(shù)相等的所有路徑。

5、查找最小的k 個(gè)元素

題目：輸入n 個(gè)整數(shù)，輸出其中最小的k 個(gè)。

6、微軟亞院之編程判斷倆個(gè)鏈表是否相交

題目：給出倆個(gè)單向鏈表的頭指針，比如h1，h2，判斷這倆個(gè)鏈表是否相交。

為了簡(jiǎn)化問題，我們假設(shè)倆個(gè)鏈表均不帶環(huán)。

問題擴(kuò)展：

1.如果鏈表可能有環(huán)列?

2.如果需要求出倆個(gè)鏈表相交的第一個(gè)節(jié)點(diǎn)列?

7、判斷整數(shù)序列是不是二元查找樹的后序遍歷結(jié)果

題目：輸入一個(gè)整數(shù)數(shù)組，判斷該數(shù)組是不是某二元查找樹的后序遍歷的結(jié)果。

如果是返回true，否則返回false。

8、輸入一個(gè)已經(jīng)按升序排序過的數(shù)組和一個(gè)數(shù)字，在數(shù)組中查找兩個(gè)數(shù)，使得它們的和正好是輸入的那個(gè)數(shù)字。

要求時(shí)間復(fù)雜度是O(n)。如果有多對(duì)數(shù)字的和等于輸入的數(shù)字，輸出任意一對(duì)即可。

9、輸入一顆二元查找樹，將該樹轉(zhuǎn)換為它的鏡像，即在轉(zhuǎn)換后的二元查找樹中，左子樹的結(jié)點(diǎn)都大于右子樹的結(jié)點(diǎn)。

用遞歸和循環(huán)兩種方法完成樹的鏡像轉(zhuǎn)換。

10、輸入一顆二元樹，從上往下按層打印樹的每個(gè)結(jié)點(diǎn)，同一層中按照從左往右的順序打印。

11、n 個(gè)數(shù)字（0,1,…,n-1）形成一個(gè)圓圈，從數(shù)字0 開始，每次從這個(gè)圓圈中刪除第m 個(gè)數(shù)字（第一個(gè)為當(dāng)前數(shù)字本身，第二個(gè)為當(dāng)前數(shù)字的下一個(gè)數(shù)

字）。

當(dāng)一個(gè)數(shù)字刪除后，從被刪除數(shù)字的下一個(gè)繼續(xù)刪除第m 個(gè)數(shù)字。

求出在這個(gè)圓圈中剩下的最后一個(gè)數(shù)字。

12、定義Fibonacci 數(shù)列如下：

/ 0 n=0

f(n)= 1 n=1

\ f(n-1)+f(n-2) n=2

輸入n，用最快的方法求該數(shù)列的第n 項(xiàng)。

分析：在很多C 語言教科書中講到遞歸函數(shù)的時(shí)候，都會(huì)用Fibonacci 作為例子。

13、輸入一個(gè)表示整數(shù)的字符串，把該字符串轉(zhuǎn)換成整數(shù)并輸出。

例如輸入字符串"345"，則輸出整數(shù)345。

14、鏈表操作

（1）.單鏈表就地逆置，

（2）合并鏈表

15、寫一個(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

16、跳臺(tái)階問題

題目：一個(gè)臺(tái)階總共有n 級(jí)，如果一次可以跳1 級(jí)，也可以跳2 級(jí)。

求總共有多少總跳法，并分析算法的時(shí)間復(fù)雜度。

17、整數(shù)的二進(jìn)制表示中1 的個(gè)數(shù)

題目：輸入一個(gè)整數(shù)，求該整數(shù)的二進(jìn)制表達(dá)中有多少個(gè)1。

例如輸入10，由于其二進(jìn)制表示為1010，有兩個(gè)1，因此輸出2。

分析：這是一道很基本的考查位運(yùn)算的面試題

18、棧的push、pop 序列

題目：輸入兩個(gè)整數(shù)序列。其中一個(gè)序列表示棧的push 順序，判斷另一個(gè)序列有沒有可能是對(duì)應(yīng)的pop 順序。

為了簡(jiǎn)單起見，我們假設(shè)push 序列的任意兩個(gè)整數(shù)都是不相等的。

比如輸入的push 序列是1、2、3、4、5，那么4、5、3、2、1 就有可能是一個(gè)pop 系列。

因?yàn)榭梢杂腥缦碌膒ush 和pop 序列：

push 1，push 2，push 3，push 4，pop，push 5，pop，pop，pop，pop，

這樣得到的pop 序列就是4、5、3、2、1。

但序列4、3、5、1、2 就不可能是push 序列1、2、3、4、5 的pop 序列。

19、在從1 到n 的正數(shù)中1 出現(xiàn)的次數(shù)

輸入一個(gè)整數(shù)n，求從1 到n 這n 個(gè)整數(shù)的十進(jìn)制表示中1 出現(xiàn)的次數(shù)。

例如輸入12，從1 到12 這些整數(shù)中包含1 的數(shù)字有1，10，11 和12，1 一共出現(xiàn)了5 次。

分析：這是一道廣為流傳的google 面試題。

.

20、求一個(gè)矩陣中最大的二維矩陣(元素和最大).如:

1 2 0 3 4

2 3 4 5 1

1 1 5 3 0

中最大的是:

4 5

5 3

要求:(1)寫出算法;(2)分析時(shí)間復(fù)雜度;(3)用C 寫出關(guān)鍵代碼

21、谷歌筆試

n 支隊(duì)伍比賽，分別編號(hào)為0，1，2。。。。n-1，已知它們之間的實(shí)力對(duì)比關(guān)系，

存儲(chǔ)在一個(gè)二維數(shù)組w[n][n]中，w[i][j] 的值代表編號(hào)為i，j 的隊(duì)伍中更強(qiáng)的一支。

所以w[i][j]=i 或者j，現(xiàn)在給出它們的出場(chǎng)順序，并存儲(chǔ)在數(shù)組order[n]中，

比如order[n] = {4,3,5,8,1......}，那么第一輪比賽就是4 對(duì)3， 5 對(duì)8。.......

勝者晉級(jí)，敗者淘汰，同一輪淘汰的所有隊(duì)伍排名不再細(xì)分，即可以隨便排，

下一輪由上一輪的勝者按照順序，再依次兩兩比，比如可能是4 對(duì)5,直至出現(xiàn)第一名

編程實(shí)現(xiàn)，給出二維數(shù)組w，一維數(shù)組order 和用于輸出比賽名次的數(shù)組result[n]，

求出result。

22、有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ò)誤。

23、網(wǎng)易有道筆試

(1)求一個(gè)二叉樹中任意兩個(gè)節(jié)點(diǎn)間的最大距離，兩個(gè)節(jié)點(diǎn)的距離的定義是這兩個(gè)節(jié)點(diǎn)間邊的個(gè)數(shù)，比如某個(gè)孩子節(jié)點(diǎn)和父節(jié)點(diǎn)間的距離是1，和相鄰兄弟節(jié)點(diǎn)間的距離是2，優(yōu)化時(shí)間空間復(fù)雜度。

(2)求一個(gè)有向連通圖的割點(diǎn)，割點(diǎn)的定義是，如果除去此節(jié)點(diǎn)和與其相關(guān)的邊，有向圖不再連通，描述算法。

24、百度研發(fā)筆試題

（1）設(shè)計(jì)一個(gè)棧結(jié)構(gòu)，滿足一下條件：min，push，pop 操作的時(shí)間復(fù)雜度為O(1)。

（2）一串首尾相連的珠子(m 個(gè))，有N 種顏色(N<=10)，設(shè)計(jì)一個(gè)算法，取出其中一段，要求包含所有N 中顏色，并使長(zhǎng)度最短，并分析時(shí)間復(fù)雜度與空間復(fù)雜度。

（3）)設(shè)計(jì)一個(gè)系統(tǒng)處理詞語搭配問題，比如說中國(guó)和人民可以搭配，則中國(guó)人民人民中國(guó)都有效。要求：

*系統(tǒng)每秒的查詢數(shù)量可能上千次；

*詞語的數(shù)量級(jí)為10W；

*每個(gè)詞至多可以與1W 個(gè)詞搭配

當(dāng)用戶輸入中國(guó)人民的時(shí)候，要求返回與這個(gè)搭配詞組相關(guān)的信息。

25、遞歸和非遞歸倆種方法實(shí)現(xiàn)二叉樹的前序遍歷。

26、騰訊面試題

1、設(shè)計(jì)一個(gè)魔方（六面）的程序。

2、有一千萬條短信，有重復(fù)，以文本文件的形式保存，一行一條，有重復(fù)。

請(qǐng)用5 分鐘時(shí)間，找出重復(fù)出現(xiàn)最多的前10 條。

3、收藏了1 萬條url，現(xiàn)在給你一條url，如何找出相似的url。（面試官不解釋何為相似）

27、雅虎：

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

28、微軟

一個(gè)數(shù)組是由一個(gè)遞減數(shù)列左移若干位形成的，比如{4，3，2，1，6，5}是由{6，5，4，3，2，1}左移兩位形成的，在這種數(shù)組中查找某一個(gè)數(shù)。

29、1.求一個(gè)二叉樹中任意兩個(gè)節(jié)點(diǎn)間的最大距離，兩個(gè)節(jié)點(diǎn)的距離的定義是這兩個(gè)節(jié)點(diǎn)間邊

的個(gè)數(shù)，比如某個(gè)孩子節(jié)點(diǎn)和父節(jié)點(diǎn)間的距離是1，和相鄰兄弟節(jié)點(diǎn)間的距離是2，優(yōu)化時(shí)間空間復(fù)雜度。

2.求一個(gè)有向連通圖的割點(diǎn)，割點(diǎn)的定義是，如果除去此節(jié)點(diǎn)和與其相關(guān)的邊，有向圖不再連通，描述算法。

30、和為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。

數(shù)據(jù)結(jié)構(gòu)與算法的重要性已不言而喻，最近，我整理出十大經(jīng)典排序算法、五大常用算法總結(jié)，今天特意整理出微軟面試的100題，由于篇幅過長(zhǎng)，將分開分享，若有不足之處，歡迎指正！很多人都會(huì)想要答案，但是我認(rèn)為沒有標(biāo)準(zhǔn)答案，答案表現(xiàn)的是個(gè)人思維，歡迎大家在評(píng)論區(qū)討論，進(jìn)行思維的碰撞。

如何學(xué)習(xí)才能快速入門并精通呢？

當(dāng)真正開始學(xué)習(xí)時(shí)難免不知從何入手，從而導(dǎo)致效率低下影響繼續(xù)學(xué)習(xí)的信心。

但最重要的是不知道需要重點(diǎn)掌握哪些技術(shù)，學(xué)習(xí)時(shí)頻繁踩坑，最終浪費(fèi)大量時(shí)間。

為了讓學(xué)習(xí)變得輕松高效， 現(xiàn)在給大家提供一個(gè)學(xué)習(xí)平臺(tái)，讓你在實(shí)踐中積累經(jīng)驗(yàn)掌握原理。主要方向是JAVA架構(gòu)師，在這里你可以學(xué)習(xí)Java工程化、高性能及分布式、深入淺出、性能調(diào)優(yōu)、Spring，MyBatis，Netty源碼分析和大數(shù)據(jù)等知識(shí)點(diǎn)?？梢约尤?b>Java后端技術(shù)群：819940388，群里有阿里大牛直播講解技術(shù)，或是關(guān)注微信公眾號(hào)：Java資訊庫，回復(fù)“架構(gòu)”，免費(fèi)的大型互聯(lián)網(wǎng)Java技術(shù)視頻分享給大家。