V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
推荐学习书目
Learn Python the Hard Way
Python Sites
PyPI - Python Package Index
http://diveintopython.org/toc/index.html
Pocoo
值得关注的项目
PyPy
Celery
Jinja2
Read the Docs
gevent
pyenv
virtualenv
Stackless Python
Beautiful Soup
结巴中文分词
Green Unicorn
Sentry
Shovel
Pyflakes
pytest
Python 编程
pep8 Checker
Styles
PEP 8
Google Python Style Guide
Code Style from The Hitchhiker's Guide
RicardoScofileld
V2EX  ›  Python

今天面试的一道算法题,求教

  •  
  •   RicardoScofileld · 2018-03-21 22:27:09 +08:00 · 9284 次点击
    这是一个创建于 2441 天前的主题,其中的信息可能已经有所发展或是发生改变。

    需求是从数组 N 中获取长度为 M 的集合 example N = [1,2,3,4,5] M=3, 那么输出为 [{1,2,3}{1,2,4},{1,2,5},{2,3,4},{2,3,5}{3,4,5}]

    54 条回复    2018-03-25 22:04:57 +08:00
    264768502
        1
    264768502  
       2018-03-21 22:57:41 +08:00 via Android
    itertools groupby
    siyemiaokube
        2
    siyemiaokube  
       2018-03-21 23:09:05 +08:00 via iPhone
    排列组合都不会吗。。
    siyemiaokube
        3
    siyemiaokube  
       2018-03-21 23:09:41 +08:00 via iPhone
    一个数字标记数字的使用情况,然后搜索即可
    264768502
        4
    264768502  
       2018-03-21 23:15:40 +08:00 via Android
    itertools 的 combinations 就够了
    acros
        5
    acros  
       2018-03-21 23:18:08 +08:00   ❤️ 1
    如果只能有序,为啥 1、3、5 不行?
    xiaol825
        6
    xiaol825  
       2018-03-21 23:26:35 +08:00   ❤️ 1
    itertools 的逻辑,可以参考下官方给的代码。

    def combinations(iterable, r):
    # combinations('ABCD', 2) --> AB AC AD BC BD CD
    # combinations(range(4), 3) --> 012 013 023 123
    pool = tuple(iterable)
    n = len(pool)
    if r > n:
    return
    indices = list(range(r))
    yield tuple(pool[i] for i in indices)
    while True:
    for i in reversed(range(r)):
    if indices[i] != i + n - r:
    break
    else:
    return
    indices[i] += 1
    for j in range(i+1, r):
    indices[j] = indices[j-1] + 1
    yield tuple(pool[i] for i in indices)
    gclove
        7
    gclove  
       2018-03-21 23:26:53 +08:00
    1,3,5 为什么不行,@acros 机智
    lance6716276
        8
    lance6716276  
       2018-03-21 23:43:21 +08:00 via Android
    C5,3 是 10 啊…要有十个啊…
    whoami9894
        9
    whoami9894  
       2018-03-21 23:57:34 +08:00 via Android
    @gclove 对呀 1.3.4 为啥也不行
    junkiedon
        10
    junkiedon  
       2018-03-22 00:02:37 +08:00
    DFS
    kunluanbudang
        11
    kunluanbudang  
       2018-03-22 00:15:01 +08:00
    把自己在 leetcode 上的垃圾代码粘贴一次
    :)


    ```
    class Solution:
    def __init__(self, ):
    self._res = []

    def combine(self, n,k):
    if (n <= 0) or (k <= 0) or (k > n):
    return []
    else:
    c = []
    self.generate_combinations(n, k, 1, c)
    return self._res

    def generate_combinations(self, n, k, start, c):
    if len(c) == k:
    self._res.append(copy.deepcopy(c))
    return
    else:
    i = start
    maxI = n - (k-len(c) )+ 1
    while i <= maxI:
    print(c)
    c.append(i)
    self.generate_combinations(n, k, i+1, c)
    c.pop()

    i += 1
    return
    ```
    takeoffyoung
        12
    takeoffyoung  
       2018-03-22 00:23:09 +08:00
    kkzxak47
        13
    kkzxak47  
       2018-03-22 00:24:23 +08:00 via Android
    一帮不看题的,做完说题出错了
    neoblackcap
        14
    neoblackcap  
       2018-03-22 00:44:30 +08:00
    @kkzxak47 从题主描述问题就是一个排列问题 Combination(5,3)=10,但是跟题目期望不同,要不题目少了条件,否则就是题主记错例子。
    ujued
        15
    ujued  
       2018-03-22 00:44:57 +08:00 via iPhone
    这 m 个数,前 m-1 个是连续的,整体递增的。这样还不好实现?
    kkzxak47
        16
    kkzxak47  
       2018-03-22 01:03:20 +08:00 via Android
    @neoblackcap 你还在这排列组合……
    neoblackcap
        17
    neoblackcap  
       2018-03-22 01:24:10 +08:00
    @kkzxak47 这题不考排列组合考什么呢?我看了 5 分钟,没看出其他意思,的确没看出排列以外的意思。
    markx
        18
    markx  
       2018-03-22 01:26:31 +08:00
    @kkzxak47 题目确实没说清楚。“获取长度为 M 的集合”, 如果是要数组元素的集合的话,那这个确实是求排列,跟例子不符啊。

    要不然你说一说你对题目的理解?
    markx
        19
    markx  
       2018-03-22 01:27:34 +08:00
    @kkzxak47 啊…… 不是排列,是组合。
    VincentBu
        20
    VincentBu  
       2018-03-22 02:16:30 +08:00
    典型的 backtracking 题目
    pyufftj
        21
    pyufftj  
       2018-03-22 08:09:06 +08:00
    @264768502 哈哈,当时面试的时候我也有类似的经历。当时让我统计某种特征最多的几个数,我当时使用 Counter 库,两行代码搞定,面试官都蒙了。不过肯定是让你实现底层代码,这样做面试官肯定不满意吧
    Hopetree
        22
    Hopetree  
       2018-03-22 08:54:05 +08:00
    为什么不是 [{1, 2, 3}, {1, 2, 4}, {1, 2, 5}, {1, 3, 4}, {1, 3, 5}, {1, 4, 5}, {2, 3, 4}, {2, 3, 5}, {2, 4, 5}, {3, 4, 5}]
    rebeccaMyKid
        23
    rebeccaMyKid  
       2018-03-22 08:59:28 +08:00
    @Hopetree 对啊,怎么才这么几个呀。我都准备贴代码了
    faceRollingKB
        25
    faceRollingKB  
       2018-03-22 09:26:37 +08:00
    简单想下,数组 N 长度 M 的集合 Arr(N)*L(M)=n1*Arr(N-n1)*L(M-1)+Arr(N-n1)*L(M)
    一个递归甩上去呗
    crane2018
        26
    crane2018  
       2018-03-22 09:55:33 +08:00
    就是说输出结果数组的 index 顺序还要满足源数组的 index 大小顺序,而且输出结果数组的前两个数在源数组中相邻,and that's all
    cs5791393
        27
    cs5791393  
       2018-03-22 09:55:50 +08:00
    用递归写个循环不就能解决了吗
    di94sh
        28
    di94sh  
       2018-03-22 10:17:00 +08:00
    ``` python
    def combination(numlist, m, low=0):
    if m==0:
    yield []
    else:
    for i in range(low, len(numlist)):
    for rest in combination(numlist, m - 1, i + 1):
    yield [numlist[i]] + rest

    def combinations(numlist, m):
    return list(combination(numlist, m))
    numlist = [1, 2, 3, 4, 5]
    print(combinations(numlist, 3))
    ```
    di94sh
        29
    di94sh  
       2018-03-22 10:26:14 +08:00
    UnknownR
        30
    UnknownR  
       2018-03-22 10:40:26 +08:00
    @rebeccaMyKid 一点显示 gist 代码,chrome 就卡成狗。。。滚屏特别卡
    mathzhaoliang
        31
    mathzhaoliang  
       2018-03-22 10:52:06 +08:00
    @di94sh 递归的话效率不高,而且 python 里面有层数限制。
    kkzxak47
        32
    kkzxak47  
       2018-03-22 12:28:58 +08:00 via Android
    @neoblackcap

    题目的输出样例是摆看的吗?
    {1,2,3}{1,2,4},{1,2,5},
    {2,3,4},{2,3,5}
    {3,4,5}
    为什么一旦题设不符合你的思维定势,就无所适从,真的不能稍微多想一点点吗?
    yao978318542
        33
    yao978318542  
       2018-03-22 12:33:08 +08:00
    <?php
    //悄悄的进村---------
    $a=array(1,2,3,4,5);
    $num=count($a)-1;
    foreach($a as $key=>$b){
    $x=$key+1;
    foreach($a as $key2=>$c){
    $y=$x+1;
    if($x<=$num) {
    foreach ($a as $d) {

    if ($y <= $num) {

    $aaa[]=array($b, $a[$x], $a[$y]);
    }
    $y++;
    }
    }
    $x++;
    }
    }
    print_r($aaa);die();
    ?>
    dcalsky
        34
    dcalsky  
       2018-03-22 12:48:45 +08:00
    neoblackcap
        35
    neoblackcap  
       2018-03-22 13:30:01 +08:00
    @kkzxak47

    1. 你的推测只是你个人推测,并没有实据,编程是科学。所谓的找规律,我能找更多的满足题意但是是其他的规律。难道不可能推测最后一个元素限定是[3,4,5]这三个数字中的一个?
    2. 你推测有额外的规则就是正常,难道我就不能推测题目有问题?这样就思维定式了?就算是面试也是允许询问的。题是人出的就会有错,这很正常的事情。
    kkzxak47
        36
    kkzxak47  
       2018-03-22 15:40:33 +08:00 via Android
    @neoblackcap 目瞪狗呆。你赢了啊,八辈子都赢了。
    shihty5
        37
    shihty5  
       2018-03-22 16:05:55 +08:00
    @RicardoScofileld 楼主快出来把题目说清楚
    liqueur
        38
    liqueur  
       2018-03-22 16:49:30 +08:00
    N = [1, 2, 3, 4, 5]
    M = 3
    '''
    output = [{1,2,3}{1,2,4},{1,2,5},{2,3,4},{2,3,5}{3,4,5}]
    '''

    output = []

    for ix, x in enumerate(N):
    for iy, y in enumerate(N[ix + 1:]):
    for iz, z in enumerate(N[iy + 1:]):
    if(y - x) == 1 and z > y:
    output.append({x, y, z})

    print(output)
    liqueur
        39
    liqueur  
       2018-03-22 16:50:15 +08:00
    @liqueur 哇 v2 的代码支持不行啊
    zacard
        40
    zacard  
       2018-03-22 17:16:32 +08:00
    juicy
        41
    juicy  
       2018-03-22 17:24:18 +08:00
    题目只有一条测试用例么,那一句 if..else..就可以了。。
    sikariba
        42
    sikariba  
       2018-03-22 17:59:03 +08:00
    坐等楼主出来改题目
    yidinghe
        43
    yidinghe  
       2018-03-22 18:59:29 +08:00
    我这刚好昨天写了个组合遍历:
    https://segmentfault.com/a/1190000013899418

    虽然语言是 Java,但思路写在里面了:通过将解集看作树节点来遍历,而不是递归,可以做到:

    1. 内存使用较小,因为只存储一个解;
    2. 因为是在遍历树节点,所以可以从任何一个解开始遍历,或者叫“断点续历(?)”
    3. 通过对树节点进行分派,可以实现多线程并发遍历。
    MeteorCat
        44
    MeteorCat  
       2018-03-22 19:02:11 +08:00 via Android
    暴力穷举,无需动脑,上去就是莽
    wwww961h
        45
    wwww961h  
       2018-03-22 19:19:58 +08:00
    直接随机数组下标,然后排除重复,走 1000 次,不怕出不来,
    Betsy
        46
    Betsy  
       2018-03-22 20:25:22 +08:00 via Android
    阿里的实习面试?
    cs5791393
        47
    cs5791393  
       2018-03-23 08:53:13 +08:00
    swfit

    func arrangement(index: Int, arr: Array<String>) {
    for i in index ... list.count-1{
    let newArr = arr + [list[i]]
    if newArr.count >= m{
    print(newArr)
    }else if i+1 < list.count{
    arrangement(index:i+1,arr: newArr)
    }
    }
    }
    lepig
        48
    lepig  
       2018-03-23 09:17:55 +08:00
    楼主放完题 就不来关注回复了。 简直没诚意请教。楼下都散了吧
    zhijian
        49
    zhijian  
       2018-03-23 10:27:48 +08:00
    c#代码:

    private static void Main(string[] args)
    {
    var m = new List<int> {1, 2, 3, 4, 5};
    var result = new List<string>();
    GetResult(m, ref result);
    Console.Read();
    }

    private static void GetResult(List<int> m, ref List<string> result)
    {
    for (var i = 0; i < m.Count - 2; i++)
    {
    for (var k = i + 2; k < m.Count; k++)
    {
    result.Add(string.Format("{0},{1},{2}", m[i], m[i + 1], m[k]));
    }
    }
    }
    titachi
        50
    titachi  
       2018-03-23 11:39:33 +08:00
    ```python
    def req(seq, m, idx=1):
    n = len(seq)
    sidx = idx - 1
    eidx = m + sidx - 1
    if m > n or n - sidx < m:
    raise '大于 list 长度'
    l, t = [], []
    while eidx < n:
    for i in seq[eidx:]:
    l = seq[sidx:eidx]
    l.append(i)
    t.append(l)
    sidx = sidx + 1
    eidx = eidx + 1
    return t


    if __name__ == '__main__':
    print(req([1, 2, 3, 4, 5], 3))

    ```
    xpresslink
        51
    xpresslink  
       2018-03-23 17:59:51 +08:00
    这么简单的一道题还用这么费劲。
    算法是:
    ( 1 )取列表前两个元素依次和剩余每个元素组合
    ( 2 )递归下一次,列表取第一个元素后面部分按步骤( 1 )执行
    ( 3 )结束条件:列表剩三个元素直接返回列表

    def solution(n, m):
    □□□□if len(n) == m:
    □□□□□□□□return [n]
    □□□□else:
    □□□□□□□□return [n[:2] + [i] for i in n[2:]] + solution(n[1:], m)

    N=[1,2,3,4,5]
    M=3

    print(solution(N, M))
    # [[1, 2, 3], [1, 2, 4], [1, 2, 5], [2, 3, 4], [2, 3, 5], [3, 4, 5]]
    xpresslink
        52
    xpresslink  
       2018-03-23 18:08:31 +08:00
    上面的给写死了,应该是按 M 可以变的
    https://paste.ubuntu.com/p/jtnHCJmFp5/

    def solution(n, m):
    □□□□if len(n) == m:
    □□□□□□□□return [n]
    □□□□else:
    □□□□□□□□return [n[:m-1] + [i] for i in n[m-1:]] + solution(n[1:], m)

    N=[1,2,3,4,5]
    M=3

    print(solution(N, M))
    # [[1, 2, 3], [1, 2, 4], [1, 2, 5], [2, 3, 4], [2, 3, 5], [3, 4, 5]]
    RicardoScofileld
        53
    RicardoScofileld  
    OP
       2018-03-25 21:59:29 +08:00
    @acros 135 是可以的 我没列出来 就是数学中的组合
    RicardoScofileld
        54
    RicardoScofileld  
    OP
       2018-03-25 22:04:57 +08:00
    @lepig 抱歉 这两天有事都没上
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   5456 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 39ms · UTC 09:03 · PVG 17:03 · LAX 01:03 · JFK 04:03
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.