9、三个警察和三个囚徒的过河问题

　　三个警察和三个囚徒共同旅行。一条河挡住了去路，河边有一条船，但是每次只能载2人。存在如下的危险：无论在河的哪边，当囚徒人数多于警察的人数时，将有警察被囚徒杀死。问题：请问如何确定渡河方案，才能保证6人安全无损的过河。

　　回答：警察囚徒过去，警察回来

　　囚徒囚徒过去，囚徒回来

　　警察警察过去，警察囚徒回来

　　警察警察过去，囚徒回来

　　囚徒囚徒过去，囚徒回来

　　囚徒囚徒过去

　　10、从300万字符串中找到最热门的10条

　　搜索的输入信息是一个字符串，统计300万输入信息中的最热门的前10条，我们每次输入的一个字符串为不超过255byte，内存使用只有1G。请描述思想，写出算法(c语言)，空间和时间复杂度。

　　答案：

　　300万个字符串最多(假设没有重复，都是最大长度)占用内存3M*1K/4=0.75G。所以可以将所有字符串都存放在内存中进行处理。

　　可以使用key为字符串(事实上是字符串的hash值)，值为字符串出现次数的hash来统计每个每个字符串出现的次数。并用一个长度为10的数组/链表来存储目前出现次数最多的10个字符串。

　　这样空间和时间的复杂度都是O(n)。

　　11、如何找出字典中的兄弟单词。给定一个单词a，如果通过交换单词中字母的顺序可以得到另外的单词b，那么定义b是a的兄弟单词。现在给定一个字典，用户输入一个单词，如何根据字典找出这个单词有多少个兄弟单词?

　　答案：

　　使用hash_map和链表。

　　首先定义一个key，使得兄弟单词有相同的key，不是兄弟的单词有不同的key。例如，将单词按字母从小到大重新排序后作为其key，比如bad的key为abd，good的key为dgoo。

　　使用链表将所有兄弟单词串在一起，hash_map的key为单词的key，value为链表的起始地址。

　　开始时，先遍历字典，将每个单词都按照key加入到对应的链表当中。当需要找兄弟单词时，只需求取这个单词的key，然后到hash_map中找到对应的链表即可。

　　这样创建hash_map时时间复杂度为O(n)，查找兄弟单词时时间复杂度是O(1)。

　　12、找出数组中出现次数超过一半的数，现在有一个数组，已知一个数出现的次数超过了一半，请用O(n)的复杂度的算法找出这个数。

　　答案1：

　　创建一个hash_map，key为数组中的数，value为此数出现的次数。遍历一遍数组，用hash_map统计每个数出现的次数，并用两个值存储目前出现次数最多的数和对应出现的次数。

　　这样可以做到O(n)的时间复杂度和O(n)的空间复杂度，满足题目的要求。

　　但是没有利用一个数出现的次数超过了一半这个特点。也许算法还有提高的空间。

　　答案2：

　　使用两个变量A和B，其中A存储某个数组中的数，B用来计数。开始时将B初始化为0。

　　遍历数组，如果B=0，则令A等于当前数，令B等于1;如果当前数与A相同，则B=B+1;如果当前数与A不同，则令B=B-1。遍历结束时，A中的数就是要找的数。

　　这个算法的时间复杂度是O(n)，空间复杂度为O(1)。

　　13、找出被修改过的数字

　　n个空间(其中n<1M)，存放a到a+n-1的数，位置随机且数字不重复，a为正且未知。现在第一个空间的数被误设置为-1。已经知道被修改的数不是最小的。请找出被修改的数字是多少。

　　例如：n=6，a=2，原始的串为5,3,7,6,2,4。现在被别人修改为-1,3,7,6,2,4。现在希望找到5。

　　回答：

　　由于修改的数不是最小的，所以遍历第二个空间到最后一个空间可以得到a的值。

　　a到a+n-1这n个数的和是total=na+(n-1)n/2。

　　将第二个至最后一个空间的数累加获得sub_total。

　　那么被修改的数就是total-sub_total。