PPLive笔试题（刚出炉的）
1、假设一个客户，他的手机中存放有全中国人民的手机号，他的手机通信录顺序很乱而且里面可能有些重复了，现在客户想让我们设计一个程序，帮他把通讯录整理一下，删除重复手机号，说机上能利用的内存只有10M，但是有无限大的硬盘，请给出设计思路，并评估算法性能。
2、有一组数字，如14,26,5,30,0，-2,108，和一个给定的整数a，是否存在其中一个或几个，它们的和等于a。
请实现方法int findNIntendo（int arr[],int count,int a)，存在返回1，否则返回0.
3、实现反转字符串。
4、以下关于红黑树的恶说法错误的是：
A、红黑树上插入操作的最差情况下的时间复杂度为O（log n)
B、红黑树上任意节点的左右子树高度差绝对不大于1
C、红黑树上删除操作最差情况的时间复杂度为O(log n)
D、红黑树上查找操作最差情况下的时间复杂度为O(log n)
5、unsigned short hash(unsigned short key){
return (key>>4)%256
}
请问hash(16)，hash(256)的值分别是______、______
6、有98个元素的排序好的数组，用二分法查找，最多需要查找几次？
7、下列哪种排序算法和数据结构是不稳定的？
A、插入排序 B、快速排序 C、基数排序 D、（选项忘了）
[最优解释]
好题mark
[其他解释]
findNIntendoHelp(arr,count,left,M,++c))==1){
M[left]=1;
return 1;
}else{
M[left]=0;
return 0;
}
}
int findNIntendo(int arr[],int count,int a){
stdext::hash_map<int,int> M;
int c=0;
int left=a;
return findNIntendoHelp(arr,count,left,M,c);
}
第三题：
void inversestr(char* str){
int r=strlen(str)-1;
int l=0;char temp;
while(r>l){
temp=str[r];
str[r--]=str[l];
str[l++]=temp;
}
}
第四题：
B
第五题：
1 16
第六题
7次。
第七题：
快排
第八题：
看不清
第九题：
A
第十题
B
[其他解释]
周末人怎么都不见了？出来冒个泡啊~~
[其他解释]
第一个：放到一个set里面，自动就删除重复的了。不过我想出题的人想考的应该是解题思路。
我的思路是按手机号分别存放到不同的文件当中，比如132的放到一个文件中，133的放到一个文件中。
遍历文件的时候，第一次遍历只读取132的，10M的空间存储132开头的手机号，重复的删除（Set集合就行了），最后剩余的存到132文件中。
然后第二次遍历只读取133的，依次下去。
第二个：我能想到的思路只有双层for循环了。算法就不写了，挺简单的，就是效率上有可能有点低。
第三个:把字符串放到一个List或者map（key和字符成映射）中，遍历list的时候用反转遍历，map就按Key值从大到小读取呗。
第四个：我不知道叫红黑树
后面的先不做了，有空继续做。
[其他解释]
谁能写出具体的实现，太笼统了作为菜鸟的我接受不了呀
[其他解释]
这个坐等思路，我是没办法啊
[其他解释]
第二题，贪心算法
[其他解释]
表示不会~~
[其他解释]
第一个，应用文件的归并排序
[其他解释]
第二道题不知道这样行不行
import java.util.ArrayList;
public class Find{
public static final int MAX = 100;
public static ArrayList<Integer> array = new ArrayList<Integer>();
public static void main(String[] args) {
int arr[] = { 2, 4, 6, 7, 100 };
int flag = findNIntendo(arr, 3, 110);
System.out.println(flag);
}
public static int findNIntendo(int arr[], int count, int a) {
int i;
int[] a1 = new int[MAX];
int[] b1 = new int[MAX];
for (i = 1; i < 100; i++)
a1[i - 1] = i;
combine(a1, arr.length, count, b1, count,arr);
for (int j = 0; j < array.size(); j++)
if (array.get(j) == a)
return 1;
return 0;
}
public static void combine(int a[], int n, int m, int b[], int M,int[] arr) {
int i, j;
for (i = n; i >= m; i--) {
b[m - 1] = i - 1;
if (m > 1)
combine(a, i - 1, m - 1, b, M,arr);
else {
int sum = 0;
for (j = M - 1; j >= 0; j--)
sum += arr[a[b[j]]-1];
array.add(sum);
}
}
}
}
package com.zf.test;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
/**
* @author Administrator
*/
public class CompomentTest {
/**
* @param array要组合的源数组
* @param n 以每n个元素作为一个组合
* @param sum 组合内所有元素的和
* @return组合后的集合
*/
public static List<int[]> combination(int[] array , int n ,int sum){
List<int[]> combinations = new ArrayList<int[]>();
if(n <= 0 && n > array.length)
return null ;
LinkedList<Integer> tmp = new LinkedList<Integer>();
for(int i = 0; i < array.length ;i++){
if(i < n)
tmp.add(1);
else
tmp.add(0);
}
boolean flag = true ;
List<LinkedList<Integer>> indexgraph = new ArrayList<LinkedList<Integer>>();
indexgraph.add(tmp);
//得到所有元素的排列
do{
//寻找到第一个 1 0
int last = tmp.get(0);
int targetIndex = 1 ;
for (; targetIndex < tmp.size() ; targetIndex++) {
int current = tmp.get(targetIndex) ;
if( current == 0 && last == 1)
break ;
last = current;
}
if(targetIndex == tmp.size()) //已经排列完所有
{
flag = false;
}
if(flag){
LinkedList<Integer> graph = new LinkedList<Integer>() ;
for (int i = 0; i < targetIndex -1 ; i++) {//保存targetIndex之前的部分
int l = tmp.get(i);
if(l == 1)
graph.addFirst(l);
else
graph.addLast(l);
}
graph.add(0);
graph.add(1);
for (int i = targetIndex + 1; i < tmp.size(); i++) {
graph.add(tmp.get(i));
}
indexgraph.add(graph);
tmp = graph ;
}
}while(flag);
//从array中取出相对应的元素
for (LinkedList<Integer> queue : indexgraph) {
int[] t = new int[n];
int index = 0 ;
for (int i = 0; i < queue.size(); i++) {
int k = queue.get(i);
if(k == 1){
t[index++] = array[i];
}
}
combinations.add(t);
}
//取除所有元素之和不等于给定值的组合
Iterator<int[]> it = combinations.iterator();
while(it.hasNext()){
int[] t = it.next();
int s = 0 ;
for (int i : t) {
s+= i ;
}
if(s != sum){
it.remove();
}
}
return combinations ;
}
public static void main(String[] args) {
List<int[]> result = combination(new int[]{0,1,2,3,4,5,8} , 3 , 10);
for (int[] is : result) {
System.out.println(Arrays.toString(is));
}
}
}
运行结果：
[2, 3, 5]
[1, 4, 5]
[0, 2, 8]
