三个算法的问题,哪个高手帮忙写一下,十分感谢.在线等.

Question

您好,我这里有三个算法问题想请教一下
1.有一数组[7,5,4,5,1,5,5]随便一个，找出出现频率最多的那个要符合频率数/数组长度>0.5，如果有就把这个数的下标打出来，如果没有返回-1  
   
2.有数组[3,1,-3,5,-4,3],打出正负算一个数，每个数的频率数   
   
3.有序列[5,0,2,-6,4]他的子序列可以有[5,0],[5,0,2][2,-6],[5,0,2,-6,4]但不能是[5,2],[5,-6]   
求最大的序列和，例子的最大序列是[5,0,2]=7  
求最简单合理的方法.
不知道还有多少分,都给了

Answer 1

前两个用MAP很容易实现
前两题import java.util.*;public class IntFreq
{
public static int maxFreq(int... ia)
{
Map<Integer, Integer> integers = new HashMap<Integer,Integer>(); for (int i : ia)
{
Integer freq = integers.get(i);
freq = (freq == null) ? 1 : freq + 1;
integers.put(i, freq);
} int maxFreq = Collections.max(integers.values()); for (Map.Entry<Integer,Integer> e : integers.entrySet())
{
int val = e.getValue();
if ((val == maxFreq) && (val*2 > ia.length)) return e.getKey();
} return -1;
} public static Map<Integer, Integer> frequences(int... ia)
{
Map<Integer, Integer> integers = new LinkedHashMap<Integer,Integer>(); for (int i : ia)
{
Integer freq = integers.get(i);
freq = (freq == null) ? 1 : freq + 1;
integers.put(i, freq);
} Map<Integer,Integer> result = new LinkedHashMap<Integer, Integer>();
for (int i : new LinkedHashSet<Integer>(integers.keySet()))
{
int freq = integers.remove(i);
Integer freq2 = integers.get(-i);
if (freq2 != null)
{
freq += freq2;
integers.put(-i, freq);
}
result.put(i, freq);
} return result;
} public static void main(String[] args)
{
System.out.println(maxFreq(7,5,4,5,1,5,5));
System.out.println(frequences(3,1,-3,5,-4,3));
}
}第一个方法是第一题，第二个方法是第二题
运行结果
5
{3=3, 1=1, -3=3, 5=1, -4=1}

Answer 2

是需要合并的,先谢谢了,我想问问,map是不是最简单的方法

Answer 3

第三题import java.util.*;public class MaxSub
{
public static Map<List<Integer>, Integer> maxSubList(int... ia)
{
int maxSum = Integer.MIN_VALUE;
int maxFrom = 0;
int maxTo = 0;
for (int start = 0; start < ia.length -1; start++)
{
for ( int end = start + 2; end <= ia.length; end++)
{
int[] subList = Arrays.copyOfRange(ia, start, end);
int sum = 0;
for (int i : subList)
{
sum+=i;
}
if (sum > maxSum)
{
maxSum = sum;
maxFrom = start;
maxTo = end;
}
}
} List<Integer> sub = new ArrayList<Integer>(); for (int index = maxFrom; index < maxTo; index++)
{
sub.add(ia[index]);
} Map<List<Integer>, Integer> result = new HashMap<List<Integer>, Integer>();
result.put(sub, maxSum);
return result;
} public static void main(String[] args)
{
System.out.println(maxSubList(5,0,2,-6,4));
}
}结果
{[5, 0, 2]=7}

Answer 4

最不最简单我可不敢说，应该是比较直接的方法吧
你要合并，我改下import java.util.*;public class IntFreq
{
public static int maxFreq(int... ia)
{
Map<Integer, Integer> integers = new HashMap<Integer,Integer>(); for (int i : ia)
{
Integer freq = integers.get(i);
freq = (freq == null) ? 1 : freq + 1;
integers.put(i, freq);
} int maxFreq = Collections.max(integers.values()); for (Map.Entry<Integer,Integer> e : integers.entrySet())
{
int val = e.getValue();
if ((val == maxFreq) && (val*2 > ia.length)) return e.getKey();
} return -1;
} public static Map<Integer, Integer> frequences(int... ia)
{
Map<Integer, Integer> integers = new LinkedHashMap<Integer,Integer>(); for (int i : ia)
{
if (i < 0) i = -i;
Integer freq = integers.get(i);
freq = (freq == null) ? 1 : freq + 1;
integers.put(i, freq);
}/* Map<Integer,Integer> result = new LinkedHashMap<Integer, Integer>();
for (int i : new LinkedHashSet<Integer>(integers.keySet()))
{
int freq = integers.remove(i);
Integer freq2 = integers.get(-i);
if (freq2 != null)
{
freq += freq2;
integers.put(-i, freq);
}
result.put(i, freq);
}*/ return integers;
} public static void main(String[] args)
{
System.out.println(maxFreq(7,5,4,5,1,5,5));
System.out.println(frequences(3,1,-3,5,-4,3));
}
}运行结果
5
{3=3, 1=1, 5=1, 4=1}