轩辕互动面试总结

一、上机答题
时间：一个半小时 环境：linux
提示：没有快捷键，只能自己手动打，结果只能知道编译能否通过，只能知道结果是否正确，不能提示在哪行，总之自己练习的时候一定严格按照时间一个一个打，不用提示，用题中的例子测试是否正确（自己练习）
1. 对于一个给定的整数数组,”支配者”是在这个数组中出现的频率超过一半的整数,例如:
[3,4,3,2,3,-1,3,3]
数值”3″出现过5次,5/8>0.5,所以数值”3″是一个”支配者”;而在这个数组中,这个”支配者”出现在数组下标:
0,2,4,6,7
请写一个函数,在给定的整数数组中找出”支配者”所在的任意一个数组下标,如果一个数组中没有这样的”支配者”,那么就返回-1;
要求:
文件名: Dominator.ext, 方法名: static public int dominator(int a[])
答案：package com.bluedot.struts.web;

import java.util.Iterator;
import java.util.Map;
import java.util.Set;
import java.util.TreeMap;

public class test {

public static int find(int[] v) {
Map map = new TreeMap();
Integer n = -1;
double size = v.length;
for (Integer i : v) {
if (map.get(i) == null) {
Integer count = 1;
map.put(i, count);
} else {
Integer count = map.get(i);
count = count + 1;
map.put(i, count);
}
}
Set set = map.keySet();
Iterator it = set.iterator();
while (it.hasNext()) {
Integer temp = it.next();
Iterator it2 = map.keySet().iterator();
while (it2.hasNext()) {
Integer temp2 = it2.next();
if (temp2 != temp) {

int nn = map.get(temp);
double d = nn / size;
if (d > 0.5) {
n = temp;
}
}
}
if (n != -1) {
break;
}
}
return n;
}

public static void main(String args[]) {
int[] v = { 3, 4, 3, 2, 3, -1, 3, 3 };
int n = find(v);
System.out.println(n);
}
}
2. “有序数组中绝对值不同的数的个数”指的是,一个已经排好序的整数数组中绝对值不相同的数字的个数;
例如:
[-5,-3,-1,0,3,6]
绝对值不同的数的个数为5,因为其中有5个不同的绝对值: 0, 1, 3, 5, 6
请返回给定有序数组中绝对值不同的数的个数.
要求:
文件名: AbsDistinct.java,方法名: static public int absDistinct(int a[])
3. 一个序列S的子序列是指在该序列S中拥有连续的数组下标的元素所组成的序列.例如,对于给定的序列
S[0]=3 S[1]=2 S[2]=-6 S[3]=4 S[4]=0
我们可以得到下面的子序列:
[2,-6,4,0] [3,2,-6,4,0] [2] [3,2,-6] [-6,4] [](空的子序列)
以及其他的子序列,子序列[]被称为空的子序列,因为其中不包括任何的元素.
下面的序列则不是给定序列的子序列:
[3,-6,0],[1],[3,2,-6,10]
最大的子序列之和是指一个序列中所有非空的子序列的元素的总和的最大值,用更精确的方式来表示:
Max(S[p]+S[p+1]+…..+S[q])
其中p,q都是整数并且p