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

tuple = [1,3,5,7,8,25,1,5,7,8,3]#1,3,4,3,3]#1, 1, 3, 5, 7, 8, 25, 4, 20, 1] #(1,3,5,7,8,25,4,20) 

endIn = len(tuple) - 1 
startIn = 0 
startSum = 0 
endSum = 0 
temp = 0 
i = endIn+1

while i > 0: 
    temp = tuple[startIn] 
    end = tuple[endIn] 
    if endSum >= startSum and endIn > startIn: 
        startSum += temp 
        startIn += 1 
    elif endSum < startSum: 
        endSum += end 
        endIn -= 1 
    else: 
        if endSum!=startSum: 
            print 'no found!' 
        else: 
            print 'ok' 
        break;        
    print 'startSum:%s  ' % str(startSum) + str(startIn) + ' endSum:%s ' % str(endSum) + str(endIn)        
    i -= 1

 

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;
	}
}

package com.blogspot.yiprogs.algorithms;

import java.util.HashMap;

public class FindDatum {

	public static void main(String[] args) {
		int[] test = {3,4,1,2,3};
		System.out.println(find(test) + "是支撑数");
	}
	
	private static int find(int[] data){
		int tmp;
		float m = (float)data.length / 2;
		HashMap<Integer, Integer> hm = new HashMap<Integer, Integer>();
		
		for(int i=0;i<data.length;i++){
			if(hm.get(data[i]) != null){
				tmp = hm.get(data[i]);
				if(tmp + 1 >= m){
					hm = null;
					return data[i];
				}else{
					hm.put(data[i], tmp + 1);
				}
			}else{
				hm.put(data[i], 1);
			}
		}
		
		return -1;
	}
}

int sum;
int sum_before;
int sum_after;
int point;
int[] array = {*,*,*,*,*,*,*,*,*};

public static void main(String[] args) {
    for(int i = 0; i < array.length(); i++) {
        sum += array[i];
    }

    for(int i = 0; sum_before < sum/2; i++) {
        sum_before += array[i];
        point = i;
    }

    for(int i = point + 1; i < array.length() - point; i++) {
        sum_after += array[i];
    }

    if(sum_after == sum_before) {
        syso(point + "is the num");
    } else {
        syso("none");
    }
}

 (define (part-sum lst k) ;列表lst前k个数之和
    (if (and (> (length lst) 0) (> k 0))
        (+ (car lst) (part-sum (cdr lst) (- k 1)))0))

 (define (balanced-point lst)
    (define (balanced-point-helper lst k) 
      ( cond ((>= k (length lst)) 0)
             ((= (part-sum lst k) (part-sum (reverse lst) (- (length lst) (+ k 1)))) k)
             (else (balanced-point-helper lst (+ k 1)))))
    (balanced-point-helper lst 2))

(define (find-bp lst) 
    (let ([lst (build-list 200 (lambda (x) (random 1000)))])
    (if (= 0 (balanced-point lst ))
        (find-bp '())
       (begin (display lst) 
              (newline)
              (display (balanced-point lst )))
        )))

/**
 * Created by IntelliJ IDEA.
 * User: benlinus
 * Date: 2010-3-3
 * Time: 10:25:44
 *  平衡点：比如int[] numbers = {1,3,5,7,8,25,4,20}; 25前面的总和为24，25后面的总和也是24，
 * 25这个点就是平衡点；假如一个数组中的元素，其前面的部分等于后面的部分，那么这个点的位序就是平衡点
要求：返回任何一个平衡点
 */
public class BalancePoint {
    private int[] numbers;
    private int start;
    private int end;
    
    public BalancePoint(int[] numbers){
        this.numbers = numbers;
        this.start = 0;
        this.end = numbers.length-1;
    }

    public int findBalancePoint(int pos){
        if(pos < end && pos > 0){
            int presum = 0;
            for(int i=0; i<pos; i++){
                presum = presum + numbers[i];
            }
            int postsum = 0;
            for(int i=pos+1; i<=end; i++){
                postsum = postsum + numbers[i];
            }
            if(presum == postsum)
                return pos;
            else
                return findBalancePoint(++pos);
        }else{
            return -1;
        }
    }

    public static void main(String[] args) {
        int number[] = {1,3,5,7,8,25,4,20};
        BalancePoint balancePoint = new BalancePoint(number);
        int pos = balancePoint.findBalancePoint(1);
        if(pos < 0 || pos >= number.length){
            System.out.println("can't find pos");
        }
        else{
            System.out.println("balance point is:"+number[pos]);
        }
    }
}