cc2005726 发表于 2010-5-13 17:07

一个阿里巴巴笔试题

判断是否是数组a中任意几个数的之和
例如：
输入：x = 5；a = {1,1,2,3,4,5}
输出：5 = 5； 5 = 4 + 1； 5 = 3 + 2； 5 = 3 + 1 + 1；要求算法高效率
同学说先排序，再递归，求出组合。
各位的意见呢？

Rainyboy 发表于 2011-1-10 20:24

本帖最后由 Rainyboy 于 2011-1-10 20:25 编辑

回复 1 # cc2005726 的帖子

贴一个不完整的吧，算是抛砖引玉……
def main():
    SouceData =;
    SouceData.sort();
    MatchData = ;
    Search(5,SouceData,MatchData);
   
def Search(tag,SD,MD,st=0):
    if tag - SD == 0:
      print MD;
      return True;
    elif tag - SD > 0:
      if st == len(SD):
            return False;
      else:
            for i in range(1,len(SD)-st):
                MD.append(SD);
                re = Search(tag-SD,SD,MD,st+i)
                MD.pop();
                if re == True:
                  continue;
                else: #re == False
                  return True;
            return True;
    else:
      return False;


if __name__ == '__main__':
    main();
结果中存在一些重复的模式……








mistuning 发表于 2011-1-11 11:14

我只会循环着做，看来是铁定不能去阿里巴巴了

Rainyboy 发表于 2011-1-11 12:01

回复 3 # mistuning 的帖子

但是直接遍历也许是在面试时能想出的，实现最快、实现起来BUG最少的办法了……

agrimony 发表于 2012-5-16 14:37

算法的都是高人啊
页: [1]
查看完整版本: 一个阿里巴巴笔试题