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

##
#2.支配点问题：
#支配数：数组中某个元素出现的次数大于数组总数的一半时就成为支配数，其所在位序成为支配点；比如int[] a = {3,3,1,2,3};3为支配数，0，1，4分别为支配点；
puts "支配点问题" + "* " * 20
h_count = {} #用于存储数量
h_index = {} #用于存储位置
Hash
a = [3,3,1,2,3]
a.each_index do |i|
  h_count[a[i]]=0 if h_count[a[i]].nil?  
  h_count[a[i]] += 1
  h_index[a[i]] = [] if h_index[a[i]].nil?
  h_index[a[i]] << i
end

list = h_count.sort {|a,b| b[1]<=> a[1]}
puts "支配数是:#{list[0][0]} 数量:#{list[0][1]}"
puts "支配点数:#{h_index[list[0][0]].join(",")}"

#!/usr/bin/perl

my @num=(1,2,3,8,9,10,4);
sub getBalance
{
     my($balance,@temp)=@_;
     my($templeft,$tempright)=(0,0);
     for $i (0..$balance-1)
     {
     	$templeft+=$temp[$i];
     }
     for $i($balance+1..@temp-1)
     {
     	$tempright+=$temp[$i];
     }
     print $balance,"\t",  $templeft,"\t", $tempright,"\n";
     if($templeft==$tempright)
     {
     	return $temp[$balance];
     }
     elsif($templeft<$tempright)
     {
     	getBalance($balance+1,@temp) ;
     }
     else
     {
     	getBalance($balance-1,@temp) ;
     }
}
print     getBalance(6,@num);
exit;

#!/usr/bin/perl

@num=(1,1,1,1,2,2,2,2,3,3,3,3,4,5,6,7,8,9,10);

sub getCount
{
    my @temp=@_;
   # print @temp."\n";
    my %count;
    my %result=();
    for $i (0..@temp-1)
    {
       # print $temp[$i]."\n";
        $count{$temp[$i]}.=$i.',';
    }
    my $templength=0;
    foreach $key (keys(%count))
    {
       # print $key."\n";
    $count{$key} =~s/,$//;
    my @position=split(',',$count{$key});
        if ( @position>$templength){
        undef %result=();
        $templength= @position;
                $result{$key}=$count{$key};
        }
        elsif(@position==$templength)
        {
             $result{$key}=$count{$key};
        }
    }
    return  %result;
}
%temp1 = getCount(@num);
foreach $key (keys(%temp1))
{
print $key."---".$temp1{$key}."\n";
}
exit;

def calcBalance(array):
    left = 0
    right = sum(array)
    for i,offset in range(len(array)):
        if left + i == right:
            return offset,i
        left += i
        right -= i
    else:
        return None

public class BalanceElement {

    public static void main(String[] argc) {
        //测试数据：{1,1,1,1,2,1};
        int[] elements = new int[]{1, 3, 5, 7, 8, 25, 4, 20};

        findBalance(elements);
    }

    public static void findBalance(int[] elements) {
        //判断不合理情况
        if (elements == null || elements.length < 3) {
            System.out.println("==bad elements ==");
            return;
        }

        int pos = 0;          //最终找到的平衡点的位置
        int element = 0;      //平衡点的值

        int n = elements.length;        //当前判断剩余的元素，初始值为元素总长度
        int headPos = -1;               //循环判断中头部元素位置
        int tailPos = elements.length;  //循环判断中尾部元素位置
        int head = 0;                   //头部值的累加和
        int tail = 0;                   //尾部值的累加和
        boolean headStep = true;        //头部累加在循环判断中下一步是否前进
        boolean tailStep = true;        //尾部累加在循环判断中下一步是否前进

        //循环判断
        do {
            if (headStep) {
                head += elements[++headPos];
                n--;
            }
            if (tailStep) {
                tail += elements[--tailPos];
                n--;
            }

            if (head < tail) {
                headStep = true;
                tailStep = false;

            } else if (head > tail) {
                headStep = false;
                tailStep = true;

            } else if(n==1){   //注意此处n==1的判断
                pos = headPos + 1;
                element = elements[pos];
            }

        } while (n > 1);

        //输出结果
        if (pos != 0) {
            System.out.println("==find balance element pos is:" + pos
                    + ",and value is:" + element);
        } else {
            System.out.println("==can't find balance element ==");
        }
    }
   
}

	public static void getBalancePoint(int[] arg){
		if(arg==null){
			System.out.println("array is null...");
			return;
		}
		if(arg.length<3){
			System.out.println("array's length is smaller than 3...no balance...");
			return;			
		}
		if(arg.length==3){
			if(arg[0]==arg[2]){
				System.out.println("array's balance is : "+arg[1]);
			}else{
				System.out.println("array has no balance...");
			}
			return;
		}
		int totalHead=0; //前部分总和(假设数组下标小的部分表示前)
		int totalEnd=0; //后部分总和
		int head=0; //前部分的数组下标
		int end=arg.length-1; //后部分的数组下标
		boolean addHead=true; //是否累加前部分
		boolean addEnd=true; //是否累加后部分
		int addCount=0; //总共累加次数
		while(head<end){
			if(addHead){ //前部分依次累加
				totalHead+=arg[head];
				addCount++;
			}
			if(addEnd){ //后部分依次累加
				totalEnd+=arg[end];
				addCount++;
			}
			if(totalHead<totalEnd){ //只允许前部分累加
				head++;
				addHead=true;
				addEnd=false;
			}else if(totalHead>totalEnd){ //只允许后部分累加
				end--; 
				addHead=false;
				addEnd=true;
			}else{ //前后同时累加
				head++;
				end--;
				addHead=true;
				addEnd=true;
			}
		} //end while
		if(addCount==(arg.length-1)){
			System.out.println("array's balance is : "+arg[head]);
		}else{
			System.out.println("array has no balance...");
		}
	}