|
精华帖 (0) :: 良好帖 (3) :: 新手帖 (0) :: 隐藏帖 (0)
|
|
|---|---|
| 作者 | 正文 |
|
发表时间：2010-04-16
5年前在轩辕互动面试过，并且拿到offer。公司的风格挺好，但因为上班太远放弃了，现在想起来还是有点遗憾。
|
| 返回顶楼 | |
|
发表时间：2010-05-21
最后修改：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)
|
| 返回顶楼 | |
|
发表时间：2010-06-08
关于支配点的问题，这个算法是否合理。
先把数据进行从小到大排序，因为必须一个数出现的次数大于该数组的总数的一半，所以这个数可定出现在这个数组的中间位置，然后分别对前一半数据和后一半数据的中间数进行比较，发现都是和中间数相同，那么这个点必支配点数。 效率不知道是否是高 |
| 返回顶楼 | |
|
发表时间：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)
|
| 返回顶楼 | |
|
发表时间：2010-07-06
惭愧，还是看java代码，再做了1次，想了半天才明白算法。
主要是 分别按顺序 倒序增加的值添入2个同样长度的数组，顺序开头/倒序结束的值置零。 然后按其中的一个顺序，2个数组元素同索引的值进行比较，得出相等值的时候就是平衡点了。 |
| 返回顶楼 | |
|
发表时间：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方法啦，不用自己在累加哦 |
| 返回顶楼 | |
|
发表时间：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])
|
| 返回顶楼 | |
|
发表时间：2010-09-06
最后修改：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] |
| 返回顶楼 | |
|
发表时间：2010-10-13
平衡点算法：设定指针起始位置为首尾元素，前后分别求和，哪个小先加哪个，直到两个指针相碰：
#!/usr/bin/env python
# -*- coding: utf-8 -*-
__author__ = 'Michael Liao (askxuefeng@gmail.com)'
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
|
| 返回顶楼 | |
|
发表时间：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做这个基本都能一句话搞定。 |
| 返回顶楼 | |
