9、三個警察和三個囚徒的過河問題

　　三個警察和三個囚徒共同旅行。一條河擋住了去路，河邊有一條船，但是每次只能載2人。存在如下的危險：無論在河的哪邊，當囚徒人數(shù)多于警察的人數(shù)時，將有警察被囚徒殺死。問題：請問如何確定渡河方案，才能保證6人安全無損的過河。

　　回答：警察囚徒過去，警察回來

　　囚徒囚徒過去，囚徒回來

　　警察警察過去，警察囚徒回來

　　警察警察過去，囚徒回來

　　囚徒囚徒過去，囚徒回來

　　囚徒囚徒過去

　　10、從300萬字符串中找到最熱門的10條

　　搜索的輸入信息是一個字符串，統(tǒng)計300萬輸入信息中的最熱門的前10條，我們每次輸入的一個字符串為不超過255byte，內(nèi)存使用只有1G。請描述，寫出算法(c語言)，空間和時間復雜度。

　　答案：

　　300萬個字符串最多(假設沒有重復，都是最大長度)占用內(nèi)存3M1K/4=0.75G。所以可以將所有字符串都存放在內(nèi)存中進行處理。

　　可以使用key為字符串(事實上是字符串的hash值)，值為字符串出現(xiàn)次數(shù)的hash來統(tǒng)計每個每個字符串出現(xiàn)的次數(shù)。并用一個長度為10的數(shù)組/鏈表來存儲目前出現(xiàn)次數(shù)最多的10個字符串。

　　這樣空間和時間的復雜度都是O(n)。

　　11、如何找出字典中的兄弟單詞。給定一個單詞a，如果通過交換單詞中字母的順序可以得到另外的單詞b，那么定義b是a的兄弟單詞�，F(xiàn)在給定一個字典，用戶輸入一個單詞，如何根據(jù)字典找出這個單詞有多少個兄弟單詞?

　　答案：

　　使用hash_map和鏈表。

　　首先定義一個key，使得兄弟單詞有相同的key，不是兄弟的單詞有不同的key。例如，將單詞按字母從小到大重新排序后作為其key，比如bad的key為abd，good的key為dgoo。

　　使用鏈表將所有兄弟單詞串在一起，hash_map的key為單詞的key，value為鏈表的起始地址。

　　開始時，先遍歷字典，將每個單詞都按照key加入到對應的鏈表當中。當需要找兄弟單詞時，只需求取這個單詞的key，然后到hash_map中找到對應的鏈表即可。

　　這樣創(chuàng)建hash_map時時間復雜度為O(n)，查找兄弟單詞時時間復雜度是O(1)。

　　12、找出數(shù)組中出現(xiàn)次數(shù)超過一半的數(shù)，現(xiàn)在有一個數(shù)組，已知一個數(shù)出現(xiàn)的次數(shù)超過了一半，請用O(n)的復雜度的算法找出這個數(shù)。

　　答案1：

　　創(chuàng)建一個hash_map，key為數(shù)組中的數(shù)，value為此數(shù)出現(xiàn)的次數(shù)。遍歷一遍數(shù)組，用hash_map統(tǒng)計每個數(shù)出現(xiàn)的次數(shù)，并用兩個值存儲目前出現(xiàn)次數(shù)最多的數(shù)和對應出現(xiàn)的次數(shù)。

　　這樣可以做到O(n)的時間復雜度和O(n)的空間復雜度，滿足題目的要求。

　　但是沒有利用“一個數(shù)出現(xiàn)的次數(shù)超過了一半”這個特點。也許算法還有提高的空間。

　　答案2：

　　使用兩個變量A和B，其中A存儲某個數(shù)組中的數(shù)，B用來計數(shù)。開始時將B初始化為0。

　　遍歷數(shù)組，如果B=0，則令A等于當前數(shù)，令B等于1;如果當前數(shù)與A相同，則B=B+1;如果當前數(shù)與A不同，則令B=B-1。遍歷結束時，A中的數(shù)就是要找的數(shù)。

　　這個算法的時間復雜度是O(n)，空間復雜度為O(1)。

　　13、找出被修改過的數(shù)字

　　n個空間(其中n<1M)，存放a到a+n-1的數(shù)，位置隨機且數(shù)字不重復，a為正且未知�，F(xiàn)在第一個空間的數(shù)被誤設置為-1。已經(jīng)知道被修改的數(shù)不是最小的。請找出被修改的數(shù)字是多少。

　　例如：n=6，a=2，原始的串為5,3,7,6,2,4�，F(xiàn)在被別人修改為-1,3,7,6,2,4�，F(xiàn)在希望找到5。

　　回答：

　　由于修改的數(shù)不是最小的，所以遍歷第二個空間到最后一個空間可以得到a的值。

　　a到a+n-1這n個數(shù)的和是total=na+(n-1)n/2。

　　將第二個至最后一個空間的數(shù)累加獲得sub_total。

　　那么被修改的數(shù)就是total-sub_total。