| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 1472 人关注过本帖, 1 人收藏
标题:公司一道面试题,求大神给思路!
只看楼主 加入收藏
子弹上膛
Rank: 1
等 级:新手上路
帖 子:22
专家分:4
注 册:2012-12-5
结帖率:50%
收藏(1)
 问题点数:0 回复次数:14 
公司一道面试题,求大神给思路!
输入1234
输出
1
2
3
4
12
13
14
23
24
34
123
124
234
1234
我的思路是,全排列,然后按条件输出,但是空间复杂度和时间复杂度都挺高,求其他思路!
搜索更多相关主题的帖子: 空间 
2015-05-01 20:23
BuilderZ
Rank: 3Rank: 3
等 级:论坛游侠
威 望:1
帖 子:82
专家分:123
注 册:2014-9-22
收藏
得分:0 
这就是全部了?那岂不是可以直接输出,能不能具体点,如果不能直接输出那就用字符数组排列输出就行了, 挺简单的,你先试试想, 想不到我再帮你
2015-05-02 01:16
林月儿
Rank: 16Rank: 16Rank: 16Rank: 16
来 自:湖南
等 级:版主
威 望:138
帖 子:2277
专家分:10647
注 册:2015-3-19
收藏
得分:0 
回复 楼主 子弹上膛
楼主java,c都无所谓的吗

剑栈风樯各苦辛,别时冰雪到时春
2015-05-02 08:09
pycansi
Rank: 9Rank: 9Rank: 9
等 级:蜘蛛侠
威 望:5
帖 子:418
专家分:1060
注 册:2012-7-26
收藏
得分:0 
程序代码:
#include "stdio.h"
#include "string.h"

char f_p[] = {"%.0s"};
char s[8];

void f (char* num, int len, int len_r, int c, int c_r, int* c_s)
{
    int i;

    for (i=0; i<len-(c-1) && c>0; i++)
    {        
        f_p[2] = 1 + 0x30;
        printf (f_p, &num[i]);
        (*c_s)++;
        strncat (s, &num[i], 1);
        
        if (*c_s == c_r)
        {
            printf ("\n");
            (*c_s) = 0;

            if ((s[c_r-1] == (len_r+0x30)) && (c_r>1))
            {
                int i;
                for (i=c_r-1; i>0; i--)
                {
                    if (s[i-1]+1 == s[i])
                    {
                        continue;
                    }
                    else
                    {
                        break;
                    }
                }
                
                if (i==0)
                {
                    s[0] = 0;
                    return;
                }
                else
                {
                    int count;
                    s[i-1] = 0;
                    
                    count = (c_r-1) - i + 1;        
                    f_p[2] = c_r - (count + 1) + 0x30;
                    printf (f_p, s);
                    (*c_s) = c_r - (count+1);
                }
            }
            else        
            {
                s[c_r-1] = 0;

                f_p[2] = c_r-1 + 0x30;
                printf (f_p, s);
                (*c_s) = c_r-1;
            }
        }
        
        f (&num[i+1], len-1-i, len_r, c-1, c_r, c_s);
    }
}

 
int main (int argc, char** argv)
{
    char f_num[] = {"1234"};
    int len;
    int c_s;
    int i;

    c_s = 0;
    len = strlen (f_num);

    for (i=0; i<len; i++)
    {
        f (f_num, len, len, i, i, &c_s);
    }

    return 0;
}

思路的话,递归,分解成子问题哈
比如,从 4 个数中按一定顺序取 3 个,可以先定 1 个数,然后就变成从 3 个数中按一定顺序取 2 个...
不过这题也并不是完全由子问题堆积而成,子问题中需要父问题的协助...中间那一大段 if 就是为了解决这个问题...


莫问前尘有愧,但求今生无悔
2015-05-02 11:11
pycansi
Rank: 9Rank: 9Rank: 9
等 级:蜘蛛侠
威 望:5
帖 子:418
专家分:1060
注 册:2012-7-26
收藏
得分:0 
想看看 b版 的话会怎样解决这种问题


莫问前尘有愧,但求今生无悔
2015-05-02 11:19
BuilderZ
Rank: 3Rank: 3
等 级:论坛游侠
威 望:1
帖 子:82
专家分:123
注 册:2014-9-22
收藏
得分:0 
回复 5楼 pycansi
看样子是我搞错了, 当我没说, 不过这种问题我喜欢这样:
template <class T>
void combine(T set[], int n, int k, void(*cbk)(T set[])) {
    unsigned char *vec = new unsigned char[n];
    T * subset = new T[k];
    for (int i = 0; i < n; i++) {
        if (i < k) {
            vec[i] = 1;
        } else {
            vec[i] = 0;
        };
    };
    bool has_next = 1;
    while (has_next) {
        int j = 0;
        for (int i = 0; i < n; i++)    {
            if (vec[i] == 1) {
                subset[j++] = set[i];
            };
        };
        cbk(subset);
        has_next = 0;
        for (int i = 0; i < n - 1; i++) //1.从左到右扫描0/1列表,如果遇到“10”组合,就将它转换为”01”.2. 将上一步找出的“10”组合前面的所有1全部移到set的最左侧。3, 重复1.2.直到没有“10”组合出现
        {
            if (vec[i] == 1 && vec[i + 1] == 0) {
                vec[i] = 0;
                vec[i + 1] = 1;
                int count = 0;
                for (int j = 0; j < i; j++) {
                    if (vec[j] == 1)
                        count++;
                };
                if (count < i) {
                    for (int j = 0; j < count; j++) {
                        vec[j] = 1;
                    }
                    for (int j = count; j < i; j++) {
                        vec[j] = 0;
                    };
                };
                has_next = true;
                break;
            };
        };
    };
    delete[] vec;
    delete[] subset;
};

main函数就自己去编吧, 对0与1的控制来实现不会重复的组合,像[1 2 3 4 5 6 7],选出的元素是[1 2 3 4]那么列表就是[1 1 1 1 0 0 0]
2015-05-03 05:13
Icytxw
Rank: 1
等 级:新手上路
帖 子:3
专家分:0
注 册:2015-5-3
收藏
得分:0 
回复 4楼 pycansi
厉害
2015-05-03 10:24
wmf2014
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
等 级:贵宾
威 望:216
帖 子:2039
专家分:11273
注 册:2014-12-6
收藏
得分:0 
楼主给出的结果应该不全,还有134未列出。
这只是(4,1)...(4,4)排列组合,不是什么全排列,像12、21则会在全排列中出现,而组合中则不会有。

能编个毛线衣吗?
2015-05-03 12:25
beyondyf
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
等 级:贵宾
威 望:103
帖 子:3282
专家分:12654
注 册:2008-1-21
收藏
得分:0 
以下是引用pycansi在2015-5-2 11:19:04的发言:

想看看 b版 的话会怎样解决这种问题

输出所有的组合的话我也会选择分治处理。如果只输出部分(比如第i种组合)可以推导一下组合索引与元素索引之间的关系来处理。

送一段代码来和大家交流
程序代码:
#include <stdio.h>
#include <malloc.h>
#include <string.h>

void sub_show_comb(char * set, int n, char * stack, int count, int index)
{
    int i;
    if(index == count)
    {
        puts(stack);
        return;
    }
    for(i = 0; i <= n - count + index; i++)
    {
        stack[index] = set[i];
        sub_show_comb(set + i + 1, n - i - 1, stack, count, index + 1);
    }
}

void show_comb(char * set)
{
    char * stack;
    int n, i;
    n = strlen(set);
    stack = (char *)malloc(n + 1);
    for(i = 1; i <= n; i++)
    {
        stack[i] = '\0';
        sub_show_comb(set, n, stack, i, 0);
    }
    free(stack);
}

int main()
{
    char s[] = "1234";
    show_comb(s);
    return 0;
}

重剑无锋,大巧不工
2015-05-03 21:44
wmf2014
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
等 级:贵宾
威 望:216
帖 子:2039
专家分:11273
注 册:2014-12-6
收藏
得分:0 
无聊,凑一热闹。
程序代码:
#include <stdio.h>
void comb(char *s,char *d,int l,int p)
{
    int i,j;
    char a[10];
    for(i=0;d[i];i++)a[i]=d[i];
    a[i]=0;
    if(i==l)
        printf("%s,",a);
    else
    {
        for(j=p;s[j];j++)
        {
            a[i]=s[j];
            a[i+1]=0;
            comb(s,a,l,j+1);
        }
    }
}
void main()
{
    char a[10],b[]="1234";
    int i;
    a[0]=0;
    for(i=0;b[i];i++)comb(b,a,i+1,0);
    printf("\n");
}



运行结果:
1,2,3,4,12,13,14,23,24,34,123,124,134,234,1234,

[ 本帖最后由 wmf2014 于 2015-5-4 06:09 编辑 ]

能编个毛线衣吗?
2015-05-04 05:52
快速回复:公司一道面试题,求大神给思路!
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.017252 second(s), 7 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved