9、三個(gè)警察和三個(gè)囚徒的過河問題

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

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

　　囚徒囚徒過去，囚徒回來

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

　　警察警察過去，囚徒回來

　　囚徒囚徒過去，囚徒回來

　　囚徒囚徒過去

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

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

　　答案：

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

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

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

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

　　答案：

　　使用hash_map和鏈表。

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

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

　　開始時(shí)，先遍歷字典，將每個(gè)單詞都按照key加入到對(duì)應(yīng)的鏈表當(dāng)中。當(dāng)需要找兄弟單詞時(shí)，只需求取這個(gè)單詞的key，然后到hash_map中找到對(duì)應(yīng)的鏈表即可。

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

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

　　答案1：

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

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

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

　　答案2：

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

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

　　這個(gè)算法的時(shí)間復(fù)雜度是O(n)，空間復(fù)雜度為O(1)。

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

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

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

　　回答：

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

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

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

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