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

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

  1 li = [1,3,5,7,8,25,4,20]
  2 def main():
  3     i = 0
  4     length = len(li)
  5     before = 0
  6     after = 0
  7     mark = 0
  8     balance = 0
  9     total = sum(li)
 10     while True:
 11         balance = i + 1
 12         if balance + 1 > length -1:
 13             return -1
 14         if li[i] == li[balance+1]:
 15             mark = balance
 16             return (mark,li[mark])
 17         else:
 18             before = before + li[i]
 19             other = total - before - li[balance]
 20             if before == other:
 21                 mark = balance
 22                 return (mark,li[mark])
 23         i += 1
 24 if __name__ == "__main__":
 25    print  main()

2.支配点问题：
支配数：数组中某个元素出现的次数大于数组总数的一半时就成为支配数，其所在位序成为支配点；比如int[] a = {3,3,1,2,3};3为支配数，0，1，4分别为支配点；
要求：返回任何一个支配点
本问题可归结为众数问题（统计学范畴），即一组数据中出现次数最多的那个数值，它可以没有也可以为多个。
下面是代码，如果你又更号的实现，不吝赐教。

  1 li = [1,3,4,3,3]
  2 def main():
  3     mid = len(li)/2
  4     for l in li:
  5         count = 0
  6         i = 0
  7         mark = 0
  8         while True:
  9             if l == li[i]:
 10                 count += 1
 11                 temp = i
 12             i += 1
 13             if count > mid:
 14                 mark = temp
 15                 return (mark,li[mark])
 16             if i > len(li) - 1:
 17                 break
 18      else:
 19          return -1
 20 if __name__ == "__main__":
 21    print  main()

最后，还有个一个中位数的问题，在很多笔试中也会遇到。
中位数：即数据从小到大排列，将数据分为两部分，一部分大于该数值，一部分小与该数值。中位数的位置是这样计算的：如果数据长度为奇数，中位数的位置为（N+1）/2,如果为偶数则为第N/2个数与第(N/2)+1的平均数。

评论

66 楼 borland 2010-12-08  

平衡点，
效率高，实现也简单

arr=[1,3,5,7,8,25,4,20]
def main():
    _sum = sum(arr);
    for v in arr :
        _sum-=v;
        if _sum==0 :
            print(v);
        _sum-=v;   
   
if __name__ == '__main__':
    main();

65 楼 ooNxt 2010-12-03  

def find(lists):
        for i in range(1,len(lists)):
            if sum(lists[0:i]) == sum(lists[i+1:]):
                print(lists[i])

64 楼 winie 2010-12-02  

第二个可以考虑正则表达式~ 用正则表达式来统计一个数据出现的次数！与数组总数的一半比较！这样不就少一次循环？

63 楼 umeit 2010-11-22  

meigm 写道

wayhome 写道

第一题:

>>> s = [1, 3, 5, 7, 8, 25, 4, 20]
>>> filter(lambda x:sum(s[:s.index(x)])==sum(s[s.index(x)+1:]),s)
    [25]
>>> s.append(30)
>>> filter(lambda x:sum(s[:s.index(x)])==sum(s[s.index(x)+1:]),s)
    []

题目中说平衡点是下标的值，所以稍微修改一下：

>>> s = [1, 3, 5, 7, 8, 25, 4, 20]
>>> filter(lambda x:sum(s[:x])==sum(s[x+1:]), range(1,len(s)-1))
[5]

如果数组最大呢？

62 楼 umeit 2010-11-19  

平衡点

ls = (1, 1, 1, 1, 1)
balance = len(ls) / 2
x = 0
while True:
    before = 0
    after = 0
    for i in ls[:balance]: before += i
    for i in ls[balance+1:]: after += i
    if before > after:
        balance -= 1
        x = 1
    elif before < after:
        balance += 1
        if x == 1:
            print "don't search the balance"
            break
    else:
        print 'balance is ', ls[balance], 'at ls[', balance, ']'
        break

61 楼 edison0951 2010-11-18  

楼上得写法很pythoner

60 楼 差沙 2010-11-03  

meigm 写道

wayhome 写道

第一题:

>>> s = [1, 3, 5, 7, 8, 25, 4, 20]
>>> filter(lambda x:sum(s[:s.index(x)])==sum(s[s.index(x)+1:]),s)
    [25]
>>> s.append(30)
>>> filter(lambda x:sum(s[:s.index(x)])==sum(s[s.index(x)+1:]),s)
    []

题目中说平衡点是下标的值，所以稍微修改一下：

>>> s = [1, 3, 5, 7, 8, 25, 4, 20]
>>> filter(lambda x:sum(s[:x])==sum(s[x+1:]), range(1,len(s)-1))
[5]

刚想写一个句话搞定的，就看到已经贴出来了，python做这个基本都能一句话搞定。

59 楼 asklxf 2010-10-13  

平衡点算法：设定指针起始位置为首尾元素，前后分别求和，哪个小先加哪个，直到两个指针相碰：

#!/usr/bin/env python
# -*- coding: utf-8 -*-

__author__ = 'Michael Liao ([e-mail])'

def get_balance(lst):
    if len(lst)==0:
        return None
    if len(lst)==1:
        return lst[1]
    sum_1, sum_2 = 0, 0
    pos_1, pos_2 = 0, len(lst) - 1
    while pos_1 < pos_2:
        if sum_1 < sum_2:
            sum_1 += lst[pos_1]
            pos_1 += 1
        elif sum_1 > sum_2:
            sum_2 += lst[pos_2]
            pos_2 -= 1
        else:
            # move pointer if current element is 0:
            if lst[pos_1]==0:
                pos_1 += 1
            elif lst[pos_2]==0:
                pos_2 -= 1
            else:
                sum_1 += lst[pos_1]
                pos_1 += 1
    if sum_1==sum_2:
        return lst[pos_1]
    return None

if __name__ == '__main__':
    print get_balance([1, 3, 5, 7, 8, 25, 4, 20]) # 25
    print get_balance([1, 3, 5, 7, 8, 25, 5, 20]) # None
    print get_balance([1, 0, 0]) # 1

58 楼 meigm 2010-09-06  

wayhome 写道

第一题:

>>> s = [1, 3, 5, 7, 8, 25, 4, 20]
>>> filter(lambda x:sum(s[:s.index(x)])==sum(s[s.index(x)+1:]),s)
    [25]
>>> s.append(30)
>>> filter(lambda x:sum(s[:s.index(x)])==sum(s[s.index(x)+1:]),s)
    []

题目中说平衡点是下标的值，所以稍微修改一下：

>>> s = [1, 3, 5, 7, 8, 25, 4, 20]
>>> filter(lambda x:sum(s[:x])==sum(s[x+1:]), range(1,len(s)-1))
[5]

57 楼 曾经de迷茫 2010-08-27  

平衡点算法

#!/usr/bin/env python
# -*- coding: cp936 -*-
def pinghengshu(data):
    '''
    平衡点：比如int[] numbers = {1,3,5,7,8,25,4,20};
    25前面的总和为24，25后面的总和也是24，25这个点就是平衡点；
    假如一个数组中的元素，其前面的部分等于后面的部分，那么这个点的位序就是平衡点
    要求：返回任何一个平衡点 
    '''
    try:
        if data.__len__()<=2 :
            return -1
        total=sum(data)
        begin=data[0]
        for i in range(1,data.__len__()-1):
            if begin<<1 == total-data[i]:
                print 'result found:\t%s'%data[i]
                return i
            else:
                begin+=data[i]
        print 'result not found'
        return -1
    except:
        print '输入数据不正确'

if __name__ =='__main__':
    print pinghengshu([1,3,5,7,8,25,4,20])
            

56 楼 jimmy1029 2010-07-07  

wqdcc 写道

平衡点

li = [1,3,5,7,8,25,4,20]

def getPoint(li,n=0):
    if n == len(li)-1:
        return 'no point'
    
    lsum = 0; rsum = 0
    for i in li[:n]:lsum += i
    for i in li[n+1:]:rsum += i
    if lsum == rsum:
        return li[n]
    else: 
        return getPoint(li,n+1)
        

print getPoint(li)

嘻嘻。。我写的跟这位朋友的差不多：
def GetBalanceItem(li, i  = 1):
if len(li) < 2:
return 'there is only one item in the list'

if i > len(li):
return 'the function did not find the balance item'
else:
index = i
if sum(li[:index]) == sum(li[index + 1:]):
return li[index]
else:
return GetBalanceItem(li, index + 1)

python提供sum方法啦，不用自己在累加哦

55 楼 mossmouser 2010-07-06  

惭愧，还是看java代码，再做了1次，想了半天才明白算法。
主要是 分别按顺序 倒序增加的值添入2个同样长度的数组，顺序开头/倒序结束的值置零。
然后按其中的一个顺序，2个数组元素同索引的值进行比较，得出相等值的时候就是平衡点了。

54 楼 shunh9hf 2010-06-13  

def test(numbers):
    lnum=0
    rnum=-1
    for num in xrange(2,len(numbers)):
        if cmp(sum(numbers[:lnum]),sum(numbers[rnum:]))<=0:
            lnum+=1
        else:
            rnum-=1
    else:
        return numbers[lnum] if sum(numbers[:lnum])==sum(numbers[rnum:]) else None

if __name__=="__main__":
    numbers = [1,3,5,7,8,25,1,5,7,8,3]
    print test(numbers)

53 楼 winipon 2010-06-08  

关于支配点的问题，这个算法是否合理。

先把数据进行从小到大排序，因为必须一个数出现的次数大于该数组的总数的一半，所以这个数可定出现在这个数组的中间位置，然后分别对前一半数据和后一半数据的中间数进行比较，发现都是和中间数相同，那么这个点必支配点数。


效率不知道是否是高

52 楼 wqdcc 2010-05-21  

平衡点

li = [1,3,5,7,8,25,4,20]

def getPoint(li,n=0):
    if n == len(li)-1:
        return 'no point'
    
    lsum = 0; rsum = 0
    for i in li[:n]:lsum += i
    for i in li[n+1:]:rsum += i
    if lsum == rsum:
        return li[n]
    else: 
        return getPoint(li,n+1)
        

print getPoint(li)

51 楼 rockis 2010-04-16  

5年前在轩辕互动面试过，并且拿到offer。公司的风格挺好，但因为上班太远放弃了，现在想起来还是有点遗憾。

50 楼 helloppx 2010-04-13  

请多多指教~

#coding:utf-8
#1
li = [1,3,5,7,8,25,1,5,7,8,3]
flag = 0
for i in range(1, --len(li)):
    if sum(li[:i]) == sum(li[i+1:]):
        print 'balance point', li[i]#可能有多个平衡点
        flag = 1

if 0 == flag:
    print 'not find'

#2
li = [1,3,4,3,3]  
foo = {}
mid = len(li)>>1
for i in range(--len(li)):
    if li[i] not in foo.keys():
        foo[li[i]] = [1,i]
    else:
        foo[li[i]] += [i]
        foo[li[i]][0] += 1
        if foo[li[i]][0] > mid: 
            print 'assign point', li[i], foo[li[i]][1:]
            break#只能有一个分配点

else:
    print 'not find'

 
        

49 楼 banditjava 2010-04-08  

刚学习python，针对这两题，写出了我的解题答案。python要求代码简洁，写函数时就考虑到如何最简洁写出代码。

def balance(): 
    li = [1,3,5,7,8,1,25,1,4,20] 
    for i in range(len(li)-2):   
        if(sum(li[:i+1])==sum(li[i+2:])):
            return li[i+1:i+2][0]

def dominate():
    li =[3,5,5,5,5,3,1,2,3] 
    dict = {}
    index =0
    maxcount=0
    for i in li:
        tmp =dict.get(i)
        if(tmp):            
            iarray = dict[i]
            iarray.append(index)
            if len(iarray)>maxcount:
                maxcount = i
        else:
            dict[i]=[index]
        index+=1
    return "The number is %d,the all indexs are %s,and the first index is %d" \
            % (maxcount,str(dict[maxcount]),dict[maxcount][0])
        
if __name__ == "__main__":  
    print  balance()  
    print dominate()

48 楼 tianling536 2010-03-19  

wayhome 写道

不考虑效率的话，两道题都只要一行就够了

第一题:

>>> s = [1, 3, 5, 7, 8, 25, 4, 20]
>>> filter(lambda x:sum(s[:s.index(x)])==sum(s[s.index(x)+1:]),s)
    [25]
>>> s.append(30)
>>> filter(lambda x:sum(s[:s.index(x)])==sum(s[s.index(x)+1:]),s)
    []

s.index(x) 还得遍历list 用list comprehension 就够了

>>>l = [1,3,5,7,8,25,4,20]
>>>[ l[i] for i in range(len(l)) if sum(l[:i]) == sum(l[i+1:]) ]

   [25]

47 楼 joeycn 2010-03-18  

wayhome 写道

不考虑效率的话，两道题都只要一行就够了

第一题:

>>> s = [1, 3, 5, 7, 8, 25, 4, 20]
>>> filter(lambda x:sum(s[:s.index(x)])==sum(s[s.index(x)+1:]),s)
    [25]
>>> s.append(30)
>>> filter(lambda x:sum(s[:s.index(x)])==sum(s[s.index(x)+1:]),s)
    []

第二题:

>>> s = [1, 2, 2, 3, 2]
>>> list(set(filter(lambda x:s.count(x)>len(s)/2,s)))
    [2]

受教了...