百度筆試題及答案解析-百度筆試題及答案解析

1、百度筆試題及答案-百度筆試題及答【各位讀友，本文僅供參考，望各位讀 者知悉，如若喜歡或者需要本文，可點(diǎn) 擊下載下載本文，謝謝！】祝人家工作順利】百度java筆試題（含答案）更多面試題， 百度面試筆試題解答答案 專家回答: 第一題 簡(jiǎn)評(píng) 百度的主要業(yè)務(wù)是搜索，搜索的基本原理如下1編寫(xiě)爬蟲(chóng)程序到互聯(lián)網(wǎng)上抓取網(wǎng)頁(yè)海量的網(wǎng)頁(yè)。2將抓取來(lái)的網(wǎng)頁(yè)通過(guò)抽取，定的格式保存在能快速檢索的文件系統(tǒng)3把用戶輸入的字符串進(jìn)行拆分成關(guān)鍵字去文件系統(tǒng)中查詢并返回結(jié)果。由以3 點(diǎn)可見(jiàn)，字符串的分析，抽取在搜索引擎中的地位是何等重要。因此，百度的筆試面試題中，出現(xiàn)這樣的題就變得理所當(dāng)然了。以下是該題的 java 實(shí)現(xiàn)，代碼如

2、下： 程序代碼 程序代碼import *;import *;import *;/* * author tzy * 在下測(cè)試通過(guò) */public class FileNameStat private String srcPath;/ 要統(tǒng)計(jì)的文件路徑private Map statMap;/ 用于統(tǒng)計(jì)的 mappublic FileNameStat(StringsrcPath)=srcPath; 軟件開(kāi)發(fā)網(wǎng)statMap=new TreeMap();/* 獲得要統(tǒng)計(jì)的 URL 的文件名 */publicStringgetFileName(String urlString)URL url=nul

3、l;String filePath=null;String fileName=null;try url=new URL(urlString);filePath=();int index=0;if (index=( “/ ”)!=-1)fileName=(index+1);elsefileName=catch(MalformedURLExceptione)return fileName;/* 統(tǒng)計(jì)指定文件名的個(gè)數(shù) */public void stat(String filename)Integer count=null;if(filename)!=null) count=(Integer)(fi

4、lename);count=new Integer()+1);else count=new Integer(1);(filename,count);/* 統(tǒng)計(jì)的主方法 */Iterator it=().iterator();FileNotFoundException,IOExceptionBufferedReader bfin=newBufferedReader(new FileReader();String temp=null;while(temp=()!=null) stat(getFileName(temp);/* 輸出統(tǒng)計(jì)結(jié)果 */ public void result()while(

5、)entry=()();().equals()?”空文件名” :() +的個(gè)數(shù)是” + ();public static voidmain(Stringargs) throws ExceptionFileNameStatfns=newFileNameStat( “);/ 指定成待統(tǒng)計(jì)文件();();第二題 簡(jiǎn)評(píng)： 這道題也與百度的業(yè)務(wù)有關(guān)，百度現(xiàn)在除了搜索外，還有貼吧，知道，博 社區(qū)化，包括前不久宣布進(jìn)軍電子商務(wù) 領(lǐng)域，搜索之外的這些產(chǎn)品，其主要功 能的實(shí)現(xiàn)主要是對(duì)數(shù)據(jù)庫(kù)的操作?？偷戎匾a(chǎn)品。同時(shí)也在積極的探索此，想進(jìn)入百度，也需要對(duì)數(shù)據(jù)庫(kù)有 定的認(rèn)識(shí)。 實(shí)現(xiàn)思路及數(shù)據(jù)庫(kù)設(shè)計(jì)：1 ，該論壇主要

6、有兩個(gè)實(shí)體對(duì)象， 用戶和 帖子 ;對(duì)于帖子對(duì)象，有一個(gè)問(wèn)題：的帖子是否應(yīng)該跟主題帖子存放在同 個(gè)表里?考慮到每天更新 10 萬(wàn)帖子，說(shuō)明帖子數(shù)比較多，為了方便主題的呈現(xiàn)，我般都把主題貼和回帖分別放在不同的 表中，把主題貼和回帖分開(kāi)可以提高查 詢效率 （300 萬(wàn)的訪問(wèn)量每天 ）。2，按照 1 中的思路， 該論壇由兩個(gè)對(duì)象 （用戶和帖子 ）變成三個(gè)實(shí)體對(duì)象，別是用戶，主題帖子，復(fù)帖子 ;3，述三個(gè)對(duì)象存在三個(gè)關(guān)系，別是：用戶 - 主題帖，一個(gè)用戶可以發(fā)個(gè)或多個(gè)帖子，一個(gè)帖子對(duì)應(yīng)一個(gè)用戶（一對(duì)多關(guān)系 ），題帖 -復(fù)帖：一個(gè)主題有 0 個(gè)或多個(gè)回復(fù)帖子，一個(gè)回復(fù)帖子對(duì)應(yīng)個(gè)主題 （一對(duì)多關(guān)系 ）;用戶

7、-復(fù)貼：個(gè)用戶可以個(gè)或多個(gè)帖，一個(gè)帖子對(duì)應(yīng)一個(gè)用戶 （對(duì)多關(guān)系 ）。還存在對(duì)回復(fù)貼的回復(fù)，這個(gè)考慮用 fatherId 來(lái)表示。4，由于三個(gè)關(guān)系 “用戶 - 主題帖，題帖 -復(fù)貼” 都是對(duì)多關(guān)系，根據(jù)表設(shè)計(jì)一般原則，可 以將這兩個(gè)關(guān)系獨(dú)立建立表，也可以不 另外建表而將一對(duì)多的關(guān)系體現(xiàn)在實(shí)體表中;然而，表間的連接查詢是非常耗資 源的，所以應(yīng)盡量減少表間連接，那么 對(duì)三個(gè)關(guān)系不應(yīng)該分別建表，而是把用 戶的 id 作為主題表和回帖表的外鍵，把題貼 id 作為回帖表的外鍵。5，鑒于以上考慮， 該論壇的三個(gè)表如下所示表名： t_user_info （ 用戶信息表 ）字段名 類型 缺省值中文含義 約束 備

8、注id Int用戶編號(hào)PRIAuto_incrementName Varchar(30)用戶名Email Varchar(50)Phone Varchar(30)Addr Varchar(200)其他字段略， 根據(jù)需要添加 表名：main_content_info ( 主題帖信息表 )字段名 類型 缺省值 中文含義 約束 備注id Int貼 編 號(hào) PRIAuto_incrementTitle Varchar(200)發(fā)帖標(biāo)題Content Text 發(fā)帖內(nèi)容UserID Int用戶編號(hào)外鍵其他字段略，根據(jù)需要添加表名：sub_content_info (復(fù)貼信息表）字段名 類型缺省值 中文含

9、義約束 備注idInt貼 編 號(hào) PRIAuto_incrementTitle Varchar(200)發(fā)帖標(biāo)題ContentText發(fā)帖內(nèi)容UserIDInt用戶編號(hào)FatherIDInt父編號(hào)MainIDInt題帖編號(hào)外鍵其他字段略，根據(jù)需要添加6，符合范式分析：述表中每個(gè)字段不可再分，首先滿足 1NF;然后數(shù)據(jù)庫(kù)表中的每個(gè)實(shí)例或行都是可以被惟一地區(qū)分 (id) ，不存在部分依 賴，因此滿足 2NF;t_user_info （ 用 戶 信 息 表 ） 和main_content_info（主題帖信息表 ）不存在任何傳遞依賴，至少屬于 BCNF;但是 sub_content_info （回復(fù)

10、貼信息表)不滿足3NF,因?yàn)榇嬖谌缦聜鬟f依id->FatherID,FatherID->MainID。范式并不是越高越好，sub_content_info 表只滿足 2NF 卻更有效率，也是當(dāng)今論壇較主流的設(shè)計(jì)。第三題 簡(jiǎn)評(píng)： 如何對(duì)海量數(shù)據(jù)進(jìn)行快速檢索，這是搜索引擎的必需考慮的問(wèn)題。這又涉及到數(shù)據(jù)結(jié)構(gòu)和算法。因此，要想進(jìn)入百度，就必須熟悉一些基本的算法和數(shù)據(jù)結(jié)構(gòu)。思路及解決方案如下：1: 設(shè)計(jì)用 TRIE 樹(shù)實(shí)現(xiàn)關(guān)鍵詞到其對(duì)應(yīng) id 的快速詞典查找TRIE 樹(shù)的每一個(gè)節(jié)點(diǎn)為一個(gè)包含256 個(gè)元素的數(shù)組，同時(shí)指針指向其下級(jí)節(jié)點(diǎn)點(diǎn)定義如下：struct trienodeint id;

11、struct trienode *child;TRIENODE;如果 TRIE 樹(shù)的某個(gè)節(jié)點(diǎn)的指針為NULL ，說(shuō)明從跟節(jié)點(diǎn)到當(dāng)前節(jié)點(diǎn)的路徑 構(gòu)成文件 B 中的一個(gè)關(guān)鍵詞，在其節(jié)點(diǎn)的 id 保存該關(guān)鍵詞的 id;如果指針不為 NULL ，則 id 對(duì)應(yīng)為 0 或 者一個(gè)無(wú)窮大的整數(shù)，標(biāo)志從根節(jié)點(diǎn)到當(dāng)前節(jié)點(diǎn)的路徑不是一個(gè)完整的關(guān)鍵詞。將關(guān)鍵詞轉(zhuǎn)化為二進(jìn)制無(wú)符號(hào) char型數(shù)組，即對(duì)于漢字等雙字節(jié)字符視為 兩個(gè)無(wú)符號(hào) char 型整數(shù)，每個(gè)元素的取值范圍在 0 到 255 之2：生成文件 b 的 TRIE 樹(shù) 步驟 1 ：依次讀取文件 b 的每一行，對(duì)每一行執(zhí)行步驟 2 到步驟 5步驟 2：讀取關(guān)

12、鍵詞 id 和關(guān)鍵詞，令為 key步驟 3：依次讀取 key 的每一個(gè)字 符，對(duì)每一個(gè)字符，執(zhí)行步驟 4;步驟 4：如果該字符對(duì)應(yīng)的指針為NULL ，則創(chuàng)建其兒子節(jié)點(diǎn) ;步驟 5：為當(dāng)前節(jié)點(diǎn)的對(duì)應(yīng)字符 id置為關(guān)鍵詞 id3：根據(jù) A 文件生成 C 文件 步驟 1：依次讀取文件 A 的每一行，對(duì)每一行執(zhí)行步驟 2 到步驟 5步驟 2：分別獲取當(dāng)前行關(guān)鍵詞、 ip地址和時(shí)間步驟 3 ：令關(guān)鍵詞 key=c1c2.cm對(duì) c1 到 cm 每個(gè)字符，執(zhí)行步驟 4步驟 4：獲取根節(jié)點(diǎn)的第 c1 個(gè)元素指針，轉(zhuǎn)移到節(jié)點(diǎn) node1 ，根據(jù) node1 的第 c2 個(gè)元素指針，轉(zhuǎn)移到 node2.根據(jù) n

13、odem 的第 cm 個(gè)元素，獲取關(guān)鍵詞的 id步驟 5：往文件c格式為關(guān)鍵詞的 id 、ip 地址和時(shí)間生成文件B的TRIE樹(shù)過(guò)程時(shí)間復(fù)雜度為 O(n*m) ，其中 n 為文件 b 行數(shù)，m 為文件 b 關(guān)鍵詞的最大長(zhǎng)度。 TRIE 的 空間復(fù)雜度為 O(n*m) ，n 和 m 含義同，但由于實(shí)際應(yīng)用中關(guān)鍵詞之間可能 會(huì)有很多前綴相同現(xiàn)象，所以實(shí)際耗費(fèi) 空間并不會(huì)很高。生成 C 文件的時(shí)間復(fù)雜度同樣為O(n*m) ，n 為文件 a 行數(shù)， m 為文件 a關(guān)鍵詞的最大長(zhǎng)度， 因?yàn)橛辛?TRIE 樹(shù)之 后，給定一個(gè)關(guān)鍵詞獲得其 id 的時(shí)間復(fù) 雜度為關(guān)鍵詞長(zhǎng)度。生成 C 文件的過(guò)程除了 TRIE

14、 樹(shù)空間外基本不需要太多額 外的空間，空間復(fù)雜度為 O(1) ，由于系 統(tǒng)有 1G 的可用內(nèi)存， TRIE 占用的空間 在幾十兆到 200M 之間 (與關(guān)鍵詞集合有關(guān))，因此本方法完全可行。更多面試題，百度網(wǎng)上筆試題及答編程： 1 編程： 用 C 語(yǔ)言實(shí)現(xiàn)一個(gè)revert 函數(shù)，它的功能是將輸入的字符串在原串上倒序 后返。 編程： 2 編*src,size_t n) 。 memmove函數(shù)的功能是拷貝 src 所指的內(nèi)存內(nèi)容前 n 個(gè)字到 dest 所指的 地址。 英文拼寫(xiě)糾錯(cuò)： 3 英文拼寫(xiě)糾錯(cuò)：在用戶輸入英文單詞時(shí)，經(jīng)常發(fā)生錯(cuò)誤，我們需要 對(duì)其進(jìn)行糾錯(cuò)。 假設(shè)已 經(jīng)有一個(gè)包含了 正確英文單

15、詞的詞典，請(qǐng)你設(shè)計(jì)一個(gè)拼 寫(xiě)糾錯(cuò)的程序。 請(qǐng)描述你解決這個(gè)問(wèn)題 的思路； 請(qǐng)給出主要的處理流程， 算法， 以及算法的復(fù)雜度； 請(qǐng)描述可能的改 進(jìn)。搜索引擎會(huì)通過(guò)日志文件把用戶每次檢 索使用的所有檢索串都記錄下來(lái)， 每個(gè)查詢串的長(zhǎng)度為 1-255 字節(jié)。假設(shè)目前有一千萬(wàn)個(gè)記錄， 這些查詢串的重復(fù)度比較高， 雖然總數(shù)是 1萬(wàn)，但如果除去重復(fù)后，不超過(guò) 3 百萬(wàn)個(gè)。一個(gè) 查 詢串的重復(fù)度越高，說(shuō)明查詢它的用戶 越多，也就是越熱門(mén)。請(qǐng)你統(tǒng)計(jì)最熱 的 10 個(gè)查詢串，要求使用的內(nèi)存不能 超過(guò) 1G。 請(qǐng)描述你解決這個(gè)問(wèn)題的思路； 請(qǐng)給出主要的處理流程，算法，以 合并 給定一個(gè)字符串的集合，格式如：及算法

16、的復(fù)雜度。 集合合并：5 集合aaa bbb ccc ， bbb ddd ，eee fff ， ggg ， ddd hhh 要求將其中交集不 為空的集合合并， 要求合并完成后 的集 合之間無(wú)交集，例如上例應(yīng)輸出 aaa bbb ccc ddd hhh ， eee fff ， ggg請(qǐng)描述你解決這個(gè)問(wèn)題的思路； 請(qǐng)給出要的處理流程，算法，以及算法的復(fù) 雜度 請(qǐng)描述可能的改進(jìn)。/ char *revert(char * str) int n=strlen(str); int i=0; char c; for(i=0;i c=str; str=str; str=c; return str; / 2v

17、oid * memmove(void *dest,constvoid*src,size_tn) assert(dest!=0)&&(src!=0); char * temp=(char * )dest; char * ss=(char * )src; int i=0; for(;i *temp =*ss ; /3 題 (1) 思路 : 字典以字母鍵樹(shù)組織，在用戶輸入同時(shí)匹配 (2) 流程 :!1!每輸入一個(gè)字母： 沿字典樹(shù)向下一層，a)若可以順利下行，則繼續(xù)至結(jié)束，給出結(jié)果；b)若該處不能匹配，糾錯(cuò)處理， 給出拼寫(xiě)建議 ,繼續(xù)至 a)；算法 : 1.在字典中查找單詞 1.在字典

18、中查找單詞 字典采用 27 叉樹(shù)組織 ,每個(gè)點(diǎn)對(duì)應(yīng)一個(gè)字母 ,查找就是一個(gè)字母?jìng)€(gè)字母匹配 .算法時(shí)間就是單詞的長(zhǎng)度NIR!1!k. 2.糾錯(cuò)算法 2.糾錯(cuò)算法 情況 :當(dāng)輸入的最后一個(gè)字母不能匹配時(shí)就提示出錯(cuò)!1!簡(jiǎn)化出錯(cuò)處理，動(dòng)態(tài)提示 可能 處理方 法：(a)當(dāng)前字母前缺少了一個(gè)字母：搜索 樹(shù)上兩層到當(dāng)前的匹配作為建議； (b)當(dāng)前字母拼寫(xiě)錯(cuò)誤：當(dāng)前字母的鍵盤(pán)相 鄰作為提示； 根據(jù)分析字典特征和用戶 單詞已輸入部分選擇 (a),(b) 處理 復(fù)雜性 分析：影響算法的效率主要是字典的實(shí) 現(xiàn)與糾錯(cuò)處理(a)字典的實(shí)現(xiàn)已有成熟 的算法，改進(jìn)不大，也不會(huì)成為瓶頸； (b)糾錯(cuò)策略要簡(jiǎn)單有效 ,如前述

19、情況，是線性復(fù)雜度； (3) 改進(jìn) (3) 改進(jìn) 策略選擇 最是重要，可以采用統(tǒng)計(jì)學(xué)習(xí)的方法改/ 4 題 (1)思路 (1)思路：用哈希做思路 (2) 首先逐次讀入查詢串，算哈希值，保存在內(nèi)存數(shù)組中，同時(shí)統(tǒng)計(jì)頻度 簡(jiǎn)單不過(guò)了。哈希的設(shè)計(jì)是關(guān)鍵選出前十的頻度，取出對(duì)應(yīng)的日 志串，心、/ / 5 題 思路：先將集合按照大 小排列后 ,優(yōu)先考慮小的集合是否與大的集合有交 思路 集。有就合并，如果小 集合與所有其他集合都沒(méi)有交集，則獨(dú) 立。獨(dú)立的集合 在下一輪的比較中不用 考慮。這樣就可以盡量減少字符串的比 較次數(shù)。當(dāng)所有 集合都獨(dú)立的時(shí)候，就 終止處理流程： 處理流程：1.將集合按照大小排序，組成集

20、合合并待處理列表 2.選擇最小的集合，找出與之有交集的集 合，如果有，合并之；如果無(wú)，則與 其 它集合是獨(dú)立集合， 從待處理列表 中刪 除。 3.重復(fù)直到待處理列表為空 算法： 算法： 1。將集合按照大小從小到大排序,組成待處理的集合列表。 2。取出待處理集合列表中最小的集合，對(duì)于集合 的每個(gè)元素，依次在其他集合中搜索是 否有此元素存在： 1> 若存在，則將此 小集合與大集合合并，并根據(jù)大小插入 對(duì)應(yīng)的位置 。轉(zhuǎn) 3。 2> 若不存在，則在該集合中取下一個(gè)元素。如果無(wú)下 個(gè)元素，即所有元素都 不存在于其他集 合。則表明此集合獨(dú)立，從待處理集合加入結(jié) 果集合列表。轉(zhuǎn)3。 3。如果待處

21、理集合列表不為空， 轉(zhuǎn)2。 如果待處理集合列表為空，成功退 出，則結(jié)果集合列表就是最終的輸出。算法復(fù)雜度分析： 算法復(fù)雜度分析： 假 設(shè)集合的個(gè)數(shù)為 n ，最大的集合元素為m 排 序 的 時(shí) 間 復(fù) 雜 度 可 以 達(dá) 到n*log(n) 然后對(duì)于元素在其他集合中 查找，最壞情況下為 *m 查找一個(gè) 集合 是否與其他集合有交集的最壞情況是m*m*(n-1) 合并的時(shí)間復(fù)雜度不會(huì)超過(guò)查找集合有交集的最壞情況。所以最 終最壞時(shí)間復(fù)雜度為 O(m*m*n*n) 需 要說(shuō)明 的是：此算法的平均時(shí)間復(fù)雜度會(huì)很低， 因?yàn)闊o(wú)論是查找還是合 需要說(shuō)明的是 并，都是處于最壞情況的概率很小，而 且排序后優(yōu)先用最小

22、集合作為判斷是否 獨(dú)立的對(duì)象，優(yōu)先與最大的集合進(jìn)行比較，這些都最大的回避了最壞情況。 (3)可能的改進(jìn)： (3) 可能的改進(jìn)：可能的改進(jìn) 首先可以實(shí)現(xiàn)將每個(gè)集合里面的 字符串按照字典序進(jìn)行排列，這樣就可 以 將查找以及合并的效率增高。另外， 可能采取恰當(dāng)?shù)臄?shù)據(jù)結(jié)構(gòu)也可以將查找 以 及合并等操作的效率得到提高。百度 11 月 4 日網(wǎng)上筆試題及答案 （僅供百度 11 月 4 日網(wǎng)上筆試題及答案編程：1 用 C 語(yǔ)言實(shí)現(xiàn)一個(gè) revert 函數(shù)，它的 功能是將輸入的字符串在原串上倒序后2 編程： 用 C 語(yǔ) 言 實(shí) 現(xiàn) 函 數(shù) void *memmove(void *dest,const void

23、 *src,size_tn)。 memmove函數(shù)的功能是拷貝 src所指的內(nèi)存內(nèi)容前 n 個(gè)字節(jié) 到 dest 所指的地址3 英文拼寫(xiě)糾錯(cuò)：在用戶輸入英文單詞時(shí)，經(jīng)常發(fā)生錯(cuò)誤，我們需要對(duì)其進(jìn)行糾錯(cuò)。假設(shè)已經(jīng)有個(gè)包含了正確英文單詞的詞典，請(qǐng)你設(shè)計(jì) 個(gè)拼寫(xiě)糾錯(cuò) 的程序。請(qǐng)描述你解決這個(gè)問(wèn)題的思路； 請(qǐng)給出主要的處理流程，算法，以及算 法的復(fù)雜度； 請(qǐng)描述可能的改進(jìn)。4 尋找熱門(mén)查詢： 搜索引擎會(huì)通過(guò)日志文件把用戶每次檢 索使用的所有檢索串都記錄下來(lái)，每個(gè) 查詢串 的長(zhǎng)度為 1-255 字節(jié)。假設(shè)目前有萬(wàn)個(gè)記錄，這些查詢串的重復(fù)度比較高，雖然總數(shù)是1萬(wàn)，但如果除去重復(fù)后，不超過(guò)3 百萬(wàn)個(gè) 。一個(gè)查

24、詢串的重復(fù)度越高，說(shuō)明查詢 它的用戶越多， 也就是越熱門(mén)。 請(qǐng)你統(tǒng)計(jì)最熱門(mén)的 10 個(gè) 查詢串，要求使用的內(nèi)存不能超過(guò) 1G 。請(qǐng)描述你解決這個(gè)問(wèn)題的思路； 請(qǐng)給出主要的處理流程，算法，以及算 法的復(fù)雜度。5 集合合并：給定一個(gè)字符串的集合，格式如：aaa bbb ccc ， bbb ddd ，eee fff ，ggg ， ddd hhh要求將其中交集不為空的集合合并，要 求合并完成后的集合之間無(wú)交集，例如例應(yīng)輸出aaa bbb ccc ddd hhh ， eee fff ，ggg請(qǐng)描述你解決這個(gè)問(wèn)題的思路； 請(qǐng)給出主要的處理流程，算法，以及算 法的復(fù)雜度請(qǐng)描述可能的改進(jìn)。/1 char *r

25、evert(char * str) int n=strlen(str);int i=0;char c;for(i=0;i c=str;str=str;str=c;return str;/ void * memmove(void *dest,const void *src,size_t n) assert(dest!=0)&&(src!=0);char * temp=(char * )dest;char * ss=(char * )src;int i=0;for(;i *temp+=*ss+;return temp;/ /字典以字母鍵樹(shù)組織，在用戶輸入同時(shí) 匹配流程:每輸入一個(gè)字

26、母： 沿字典樹(shù)向下一層，a）若可以順利下行，則繼續(xù)至結(jié)束，給出結(jié)果；b） 若該處不能匹配，糾錯(cuò)處理，給出拼NIR!1!寫(xiě)建議 ,繼續(xù)至 a）；算法:1. 在字典中查找單詞字典采用 27 叉樹(shù)組織 ,每個(gè)節(jié)點(diǎn)對(duì)應(yīng)個(gè)字母 ,查找就是一個(gè)字母?jìng)€(gè)字母匹配 .算法時(shí)間就是單詞的長(zhǎng)度NIR!1!k.2. 糾錯(cuò)算法情況 :當(dāng)輸入的最后一個(gè)字母不能匹配時(shí)NIR!1!就提示出錯(cuò) ,簡(jiǎn)化出錯(cuò)處理，動(dòng)態(tài)提示可能 處理方法 :(a)當(dāng)前字母前缺少了一個(gè)字母：搜索樹(shù) (b) 當(dāng)前字母拼寫(xiě)錯(cuò)誤：當(dāng)前字母的鍵盤(pán)兩層到當(dāng)前的匹配作為建議；NIR!1!相鄰作為提示； 根據(jù)分析字典特征和用戶單詞已輸入部 分選擇 (a),(b) 處理復(fù)雜性分析：影響算法的效率主要是字 典的實(shí)現(xiàn)與糾錯(cuò)處理字典的實(shí)現(xiàn)已有成熟的算法， 改進(jìn)不大， 也不會(huì)成為瓶頸；(b) 糾錯(cuò)策略要簡(jiǎn)單有效 ,如前述情況，是線性復(fù)雜度；(3)改進(jìn)策略選擇最是重要，可以采用 統(tǒng)計(jì)學(xué)習(xí)的方法改進(jìn)。/ /用哈希做(2)首先逐次讀入查詢串，算哈希值，保存 在內(nèi)存數(shù)組中，同時(shí)統(tǒng)計(jì)頻度 選出前十的頻度，取出對(duì)應(yīng)的日志串， 簡(jiǎn)單不過(guò)了。哈希的設(shè)計(jì)是關(guān)鍵。/ /思路：先將集合按照大小排列后 ,優(yōu)先考慮小的集合是否與大的集合有交集。有就合并，如果小集合