【23xiu.com-爱上秀-教育信息门户网】
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。