两道比较复杂的轩辕互动面试题(Python实现)

public int balance(int[] numbers) {
int sum = sum(numbers);
int leftSum = 0;
for (int i = 1; i < numbers.length - 1; i++) {
leftSum += numbers[i - 1];
if ((sum - numbers[i]) / 2 == leftSum) {
return numbers[i];
}
}
throw new RuntimeException("数组：" + numbers.toString() + "没有平衡点");
}

平衡点问题

/**
 * 寻找平衡点
 * 
 * @author 陌上霜寒
 * Jun 26, 2009
 */
public class Equity {

	/**
	 * 返回一个数组的平衡点
	 * @param numbers
	 * @return 平衡点
	 */
	public static int equity(int[] numbers){
		//初始下标
		int initPoint = numbers.length/2;
		//平衡点下标
		int eqPoint = -1;
		
		for(int i = 0;i<numbers.length;i++){
			int frontSum = 0;
			int endSum = 0;
			
			//前部分元素之和
			for(int j = 0;j<initPoint;j++){
				frontSum +=numbers[j];
			}
			
			//后部分元素之和
			for(int k = initPoint+1;k<numbers.length;k++){
				endSum +=numbers[k];
			}
			
			if(frontSum == endSum){
				eqPoint = initPoint;
				break;
			}else if(frontSum < endSum){
				initPoint ++;
			}else{
				initPoint --;
			}
		}
		
		//另一个思路是：先求出所有的和，然后取得前一部分的和，然后就可以得到后半部分的和了，避免了再次循环
		return eqPoint;
	}
	
	public static void main(String[]args){
		int[] numbers = new int[]{1,8,7,8,25,4,49,30,23};
		System.out.println("The equity number index is === "+Equity.equity(numbers));
	}
}

支配者问题

import java.util.HashMap;
import java.util.Map;

/**
 * 寻找支配者
 * 
 * @author 陌上霜寒
 * Jun 26, 2009
 */
public class Dominator {

	/**
	 * 寻找支配者的下标
	 * @param a
	 * @return 支配者的下标
	 */
	public static int dominator(int a[]){
		Map<String,String> map = new HashMap<String,String>();
		String key = null;
		String value = null;

		for(int j:a){
			key = String.valueOf(j);
			value = map.get(key);

			if(map.get(key) != null){
				value = String.valueOf(Integer.parseInt(value)+1);
				map.put(key, value);
			}else{
				map.put(key, "1");
			}
		}
				
		int dominator = 0;

		for(String k:map.keySet()){
			float intValue = Float.parseFloat(map.get(k));
			if(intValue/a.length >0.5){
				dominator = Integer.parseInt(k);
				break;
			}
		}
		
		for (Map.Entry<String, String> entry : map.entrySet()) {  
			String eachCount = entry.getValue();  
		}
		
		int index = -1;	

		for(int i:a){
			if(a[i] == dominator){
				index = i;
				break;
			}
		}
		return index;
	}
	
	/**
	 * 主方法
	 * @param args
	 */
	public static void main(String[]args){
		int[]a = new int[]{2,4,4,2,4,5,4,3,4,4};
		System.out.println("The random index is === "+Dominator.dominator(a));
	}
}

轩辕互动机试不会还是这几道题吧

问一下LZ平衡点的问题，像这样的数组：[1, 0, 0]，第一个数 1 算平衡点吗？

而且我试过LZ的代码，似乎数组必须是5位或以上，才算做可以计算平衡点的数组？

因为下面两个数组都无法通过测试：

[1, 2, 1]        # 按LZ的说法，数字 2 的位序应该是平衡点

[1, 1, 3, 2]    # 数字 3 的位序应该是平衡点

还是这个平衡点算法对数组有其他要求，比如数组元素不能重复？

 

平衡点算法：

需要两次循环，sum一次，循环比较一次（len不知道算不算，要算就有三次了……）。另外，每次算after时都要从数组中按下标取（不过这不算什么吧）元素。下面的思路可以不计算after，但个人觉得性能节省可以忽略不计……

# 懒得想名字，大家包涵
def ping_heng(li):
    # before，after分别为的前后的总和
    before, after = 0, sum(li[1:])
    idx, li_len = 0, len(li)
    for num in li:
        if before == after:
            return (idx, num)
        if idx == li_len - 1:
            return (None, None)
        idx += 1
        # 随着循环，before不断增加，after不断减少
        before += num
        after -= li[idx]
        
if __name__ == '__main__':
    test_lists = (
        [1, 0, 0, 0],
        [1, 3, 5, 7, 8, 25, 4, 20],
        [1, 3, 5, 7, 8, 25, 7, 20],
    )
    for li in test_lists:
        print "list: %s" % li
        print "index: %s  number: %s\n" % ping_heng(li)

测试结果：

list: [1, 0, 0, 0]
index: 0  number: 1

list: [1, 3, 5, 7, 8, 25, 4, 20]
index: 5  number: 25

list: [1, 3, 5, 7, 8, 25, 7, 20]
index: None  number: None

 

 

其实还有个思路，就是判断 before * 2 + current_num == total，这样就不需要计算after了。但最开始的求和还是省不了。问下有没有不求和，就一次循环搞定的？

 

支配点算法：

基本实现功能。一次循环，利用了Python的dictionary简化代码，这在纯算法题中该算是取巧了吧？不过我觉得利用语言特性也算是编程的一个方面

# 支配点算法：
def zhi_pei(li):
    dic = {}  # 用dictionary来存储每个数出现的次数
    mid = len(li) / 2
    for num in li:
        # 如果一个数重复出现，则把计数加1，否则当做第一次出现
        if num in dic.keys():
            dic[num] += 1
        else:
            dic[num] = 1
        if dic[num] > mid:
            return (num, dic[num])
    return (None, None)
    
if __name__ == '__main__':
    test_zp = (
        [1],
        [1, 2],
        [1, 2, 2],
        [3, 3, 1, 2, 3],
        [2, 2, 3, 3, 2, 2],
    )
    for li in test_zp:
        print "list: %s" % li
        print "number: %s  count: %s\n" % zhi_pei(li)

测试结果：

list: [1]  # 嗯，我觉得对于一个元素的数组，应该是这个结果……
number: 1  count: 1

list: [1, 2]
number: None  count: None

list: [1, 2, 2]
number: 2  count: 2

list: [3, 3, 1, 2, 3]
number: 3  count: 3

list: [2, 2, 3, 3, 2, 2]
number: 2  count: 4

if ((sum - numbers[i]) / 2 == leftSum) {
				return numbers[i];
			}

这句恐怕得改改，如果leftSum = 1， (sum - numbers[i]) = 3，结果会怎样？

不懂python，javascript写的，用java还要开编辑器太麻烦。

var a=[1,3,5,7,8,25,1,5,7,8,3];
var totalSum=(function(){
            var ret=0;
            for(var i=0,len=a.length;i<len;i++){
                ret+=a[i];
            }
            return ret;
        })();

var sum=a[0],points=[];
for(var i=1,len=a.length;i<len;i++){
    if(sum*2+a[i]==totalSum){
        points.push(a[i]);
    }
    sum+=a[i];
}

alert(points);


//支配点问题,用Map解决--------------------------------------
var a = [3,3,1,2,3];
var mid=parseInt(a.length/2);
var map={};
var points=[];
var record;

for(var i=0,len=a.length;i<len;i++){
   record=map[a[i]]?map[a[i]]:map[a[i]]={value:a[i],count:0,points:[]};
   record.count++;
   record.points.push(i);
}

for(var key in map){
   record=map[key];
   if(record.count>mid){
       points.push(record);
   }
}

for(var i=0;i<points.length;i++){
    alert("支配数:"+points[i].value+"\n支配点:"+points[i].points);
}

int[] numbers = {1,3,5,7,8,25,1,5,7,8,3};
int count = 0;
int nowcount = 0;
int zhi = 0;
for(int i=0;i<numbers.length;i++){
count += numbers[i];
}
for(int j=0;j<numbers.length;j++){
int now =  numbers[j];
int x = (count-now)/2;
if(nowcount==x){
zhi = now;
break;
}
nowcount += now;
}
System.out.println(zhi);

不敢当，小弟小本，09年7月份毕业。看过thinking in java(部分)，practical java(市场上很难找到了)，js，
感觉JavaScript的灵活性可以提高java水瓶，个人意见。

又是算法  哎 

复杂度估计也是O(N)

list=(1,3,5,7,8,25,4,20)
sump={}

def fib(n):
  global sump
  if n in sump:
    return sump[n]
  if n==0:
    return list[n]
  if n==-1:
    return list[-1]

  if n>0:
    sump[n] = fib(n-1) + list[n]
  else:
    sump[n] = fib(n+1) + list[n]
  return sump[n]

for n in range(1,len(list)-1):
  if fib(n-1) == fib( ( len(list) - n - 1 ) * -1 ):
    print 'found out',n

 

拙作

package com.blogspot.yiprogs.algorithms;

public class MiddleNum {
	public static void main(String[] args){
		int[] test = {1,2};
		System.out.println("第" + (showNum(test) + 1) + "个数是中间数");
	}
	
	private static int showNum(int[] array){
		int p = 0;
		int q = array.length - 1;
		int lt = array[p];
		int rt = array[q];
		
		if(p+2 > q){
			return -1000000;
		}
		
		while(p+2 != q){
			if(lt < rt){
				p++;
				lt += array[p];
			}else{
				q--;
				rt += array[q];
			}
		}
		return p + 1;
	}
}