轩辕互动笔试

刚去轩辕互动面试，linux下三道题

1个半小时的，两个15分钟的

下面是两道需要半个小时的题

1.平衡点问题
平衡点：比如int[] numbers = {1,3,5,7,8,25,4,20}; 25前面的总和为24，25后面的总和也是24，25这个点就是平衡点；假如一个数组中的元素，其前面的部分等于后面的部分，那么这个点的位序就是平衡点
要求：返回任何一个平衡点

public class Equity{

public static int equity(int[] numbers){
int total=0;

for(int i=0;i<numbers.length;i++){
total+=numbers[i];
}

int frontSum = 0;

for(int i=0;i<numbers.length;i++){
int backSum = total - frontSum - numbers[i];
System.out.println(i + "------" + frontSum);
System.out.println(i + "------" + backSum);
if(frontSum == backSum) { 
	return i;
}
frontSum += numbers[i];
}

return -1;
}
}

支配点问题：
支配数：数组中某个元素出现的次数大于数组总数的一半时就成为支配数，其所在位序成为支配点；比如int[] a = {3,3,1,2,3};3为支配数，0，1，4分别为支配点；
要求：返回任何一个支配点

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class Dominator {

@SuppressWarnings("unchecked")
public static int dominator(int[] a) {
if(a == null || a.length == 0)
return -1;

List intList = new ArrayList();

for(int i=0; i<a.length; i++) {
intList.add(a[i]);
}

System.out.println(intList);

Collections.sort(intList);

System.out.println(intList);

int maxCount = 0;
int maxCountElement = 0;
int maxCountTemp = 0;
int maxCountElementTemp = (Integer)intList.get(0);
for(int i=0; i<intList.size(); i++) {
if(intList.get(i).equals(maxCountElementTemp)) {
	maxCountTemp++;
} else {
	if(maxCountTemp > maxCount) {
	maxCountElement = maxCountElementTemp;
	maxCount = maxCountTemp;
	}
	maxCountElementTemp = (Integer)intList.get(i);
	maxCountTemp = 1;
}
System.out.println(i + "---------" + maxCount);
System.out.println(i + "---------" + maxCountElement);
System.out.println(i + "---------" + maxCountTemp);
System.out.println(i + "---------" + maxCountElementTemp);
}

if(maxCountTemp > maxCount) {
maxCountElement = maxCountElementTemp;
maxCount = maxCountTemp;
}

if(maxCount > a.length/2) {
for(int i=0; i<a.length/2; i++) {
	if(a[i] == maxCountElement) {
	return i;
	}
}
}

return -1;
}
}

评论

8 楼 爱园园真是太好了 2016-12-30  

package zj.hy.love;


/**
 * 平衡点：比如int[] numbers = {1,3,5,7,8,25,4,20};
 * 25前面的总和为24，25后面的总和也是24，25这个点就是平衡点；
 * 假如一个数组中的元素，其前面的部分等于后面的部分，
 * 那么这个点的位序就是平衡点 
 * 要求：返回任何一个平衡点 
 * @author ZJ
 * @since 2016-12-30
 */
public class Ques20161230_01 {
	
	
	/**
	 * 计算一个数字数组的平衡点<br>
	 * 返回平衡点的位置与元素
	 * @param array
	 * @return
	 */
	public String getBalancePoint_1(int[] array){
		
		int size = array.length;
				
		int suffixSum = 0;//后缀和		
		for (int i = 0; i < size; i++) {
			suffixSum += array[size-i-1];
			int prefixSum = 0;//前缀和
			for (int j = 0; j < size-i-2; j++) {
				prefixSum += array[j];
			}
			if(suffixSum == prefixSum){
				return "平衡点为："+(size-i-2)+",元素为"+array[size-i-2];
			}
		}
		
		return "没有平衡点！";
	}
	
    public String getBalancePoint_2(int[] array){
		
    	int sum = 0;
    	int size = array.length;
    	int prefixSum = 0;//前缀和
    	int suffixSum = 0;//后缀和
    	for (int i = 0; i < size; i++) {
			sum += array[i];
		}    	
    	for (int i = 0; i < size-1; i++) {
    		prefixSum +=array[i];
    		suffixSum = sum - prefixSum -array[i+1];
    		if(prefixSum == suffixSum){
    			return "平衡点为："+(i+1)+",元素为"+array[i+1];
    		}
		}
		return "没有平衡点！";
	}
	
	public static void main(String[] args) {

		Ques20161230_01 ques = new Ques20161230_01();
		int[] numbers = {1,3,5,7,8,25,4,20,9,20};
		String point = ques.getBalancePoint_2(numbers);
		System.out.println(point);
	}
}

7 楼 爱园园真是太好了 2016-12-30  

package zj.hy.love;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Set;


/**
 * 支配点问题： 
 * 支配数：数组中某个元素出现的次数大于数组总数的一半时就成为支配数，
 * 其所在位序成为支配点；比如int[] a = {3,3,1,2,3};
 * 3为支配数，0，1，4分别为支配点； 
 * 要求：返回任何一个支配点 
 * @author ZJ
 * @since 2016-12-29
 */
public class Ques20161230_02 {
	
	/**
	 * 传入一个数字型的数组，<br>
	 * 返回key为数组支配数，
	 * value 为该数组所有支配点的Map<br>
	 * 其中多有支配点以英文逗号分隔，例如：2,3,5
	 * @param array
	 * @return
	 */
	public Map<Integer,String> getControlPoint(int[] array){
		
		Map<Integer,String> pointMap = new HashMap<Integer, String>();
		if(array == null|| array.length == 0){
			return pointMap;
		}
		int[] tempArray = new int[array.length];
		System.arraycopy(array, 0, tempArray, 0, array.length);
		//tempArray = array.clone(); clone 方法速度慢效率比较低
		Arrays.sort(tempArray);//将数组排序
		int temp = 0;
		int count = 0;	
		int controlElement = 0;
		// 寻找支配数
		for (int i = 0; i < tempArray.length; i++) {			
			if(temp == tempArray[i]){
				if(++count > array.length/2){
					controlElement = temp;
					break;
				}
			}else{
				count = 1;
				temp = tempArray[i];				
			}			
		}	
		//获取支配点
		StringBuilder str = new StringBuilder();
		for (int i = 0; i < array.length; i++) {					
			if(array[i] == controlElement){
				str.append(i+",");
			}
		}
		if(!str.toString().isEmpty()){
			String index = str.toString().substring(0, str.length()-1);	
			pointMap.put(controlElement, index);
		}
		return pointMap;
	}
	
	public static void main(String[] args) {
		
		Ques20161230_02 ques = new Ques20161230_02();
		int[] a = {3,3,1,2,3};
		Map<Integer, String> controlMap= ques.getControlPoint(a);
		Set<Integer> keySet = controlMap.keySet();
		for (Integer i : keySet) {
			System.out.println("支配数为："+i+",其所有的支配点为:"+controlMap.get(i));
		}
	}
}

6 楼 爱园园真是太好了 2016-12-30  

package zj.hy.love;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Set;


/**
* 支配点问题：
* 支配数：数组中某个元素出现的次数大于数组总数的一半时就成为支配数，
* 其所在位序成为支配点；比如int[] a = {3,3,1,2,3};
* 3为支配数，0，1，4分别为支配点；
* 要求：返回任何一个支配点
* @author ZJ
* @since 2016-12-29
*/
public class Ques20161230_02 {

/**
* 传入一个数字型的数组，<br>
* 返回key为数组支配数，
* value 为该数组所有支配点的Map<br>
* 其中多有支配点以英文逗号分隔，例如：2,3,5
* @param array
* @return
*/
public Map<Integer,String> getControlPoint(int[] array){

Map<Integer,String> pointMap = new HashMap<Integer, String>();
if(array == null|| array.length == 0){
return pointMap;
}
int[] tempArray = new int[array.length];
System.arraycopy(array, 0, tempArray, 0, array.length);
//tempArray = array.clone(); clone 方法速度慢效率比较低
Arrays.sort(tempArray);//将数组排序
int temp = 0;
int count = 0;
int controlElement = 0;
// 寻找支配数
for (int i = 0; i < tempArray.length; i++) {
if(temp == tempArray[i]){
if(++count > array.length/2){
controlElement = temp;
break;
}
}else{
count = 1;
temp = tempArray[i];
}
}
//获取支配点
StringBuilder str = new StringBuilder();
for (int i = 0; i < array.length; i++) {
if(array[i] == controlElement){
str.append(i+",");
}
}
if(!str.toString().isEmpty()){
String index = str.toString().substring(0, str.length()-1);
pointMap.put(controlElement, index);
}
return pointMap;
}

public static void main(String[] args) {

Ques20161230_02 ques = new Ques20161230_02();
int[] a = {3,3,1,2,3};
Map<Integer, String> controlMap= ques.getControlPoint(a);
Set<Integer> keySet = controlMap.keySet();
for (Integer i : keySet) {
System.out.println("支配数为："+i+",其所有的支配点为:"+controlMap.get(i));
}
}
}

5 楼 爱园园真是太好了 2016-12-30  

鄙人刚开始看这个每日一题，下面是我写的这个找平衡点的代码

4 楼 爱园园真是太好了 2016-12-30  

引用

第一个逻辑不是很清楚，第二个代码有问题，吧数组排序了以后序号还能和原来一抹一样么？

3 楼 laolinshi 2010-05-24  

zuojc7 写道

我认为 不应该是这么写的 呵呵


import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class Dominator {
public static int getDominator(int[] a){
if(a == null && a.length == 0){
return -1;
}
List<Integer> intList = new ArrayList<Integer>();
for (int  n : a) {
intList.add(n);
}
Collections.sort(intList);
int count =1;
for (int i =0; i < a.length;i++) {
if(i+1 < a.length){
if(intList.get(i) == intList.get(i+1)){
count++;
if(count > a.length/2){
return i;
}
}else{
count = 1;
}
}
}
return -1;
}
public static void main(String[] args) {
int[] a = {3,3,1,2,3};
System.out.println(getDominator(a));
}
}

你打印出来的数组元素位置不对啊

2 楼 ryan.liu 2010-04-22  

平衡点

int i=0;
int j=numbers.length-1;
int frontSum=0;
int backSum=0;
while(i<=j) {
   if (frontSum<=backSum)
      i++;
   else
      j--;
}
return (frontSum==backSum) ? numbers[i] : -1;

1 楼 zuojc7 2010-04-20  

我认为 不应该是这么写的 呵呵


import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class Dominator {
public static int getDominator(int[] a){
if(a == null && a.length == 0){
return -1;
}
List<Integer> intList = new ArrayList<Integer>();
for (int  n : a) {
intList.add(n);
}
Collections.sort(intList);
int count =1;
for (int i =0; i < a.length;i++) {
if(i+1 < a.length){
if(intList.get(i) == intList.get(i+1)){
count++;
if(count > a.length/2){
return i;
}
}else{
count = 1;
}
}
}
return -1;
}
public static void main(String[] args) {
int[] a = {3,3,1,2,3};
System.out.println(getDominator(a));
}
}