VC驿站

 找回密码
 加入驿站

QQ登录

只需一步,快速开始

搜索
查看: 1905|回复: 19

【2011-5-19】有奖竞猜

  [复制链接]
56_avatar_middle
在线会员 发表于 2011-5-19 22:40:09 | 显示全部楼层 |阅读模式
20驿站币
本帖最后由 zhaoshengbo 于 2011-5-19 22:41 编辑

大家好:

来道小题大家思考下
求一个数组的最长递减子序列 比如{9,4,3,2,5,4,3,2}的最长递减子序列为{9,5,4,3,2}
有答案的捧个答案场,没答案的捧个思路场,来者有份!【2011-5-19】有奖竞猜





上一篇:请各位发布了悬赏帖子的会员看下!
下一篇:学历比例调查
97_avatar_middle
online_vip 发表于 2011-5-19 23:29:08 | 显示全部楼层
本帖最后由 dd131224 于 2011-5-19 23:29 编辑

呵呵, 捧个思路场吧, 那就

先把数组用插入排序法,又大到小进行排序..(这里代码我省略吧)

然后用一个循环对数组进行遍历输出
  1. int nSize = sizeof(ary) / sizeof(int);
  2. int nTemp = ary[0];

  3. printf("%d ", ary[0]);

  4. for(int i = 1; i < nSize; i++)
  5. {
  6.       if(nTemp != ary[i])
  7.      {
  8.           nTemp = ary[i];
  9.           printf("%d ", ary[i]);
  10.      }
  11.    
  12. }
复制代码

评分

参与人数 1驿站币 +5 收起 理由
56_avatar_small zhaoshengbo + 5

查看全部评分

02_avatar_middle
在线会员 发表于 2011-5-20 15:39:47 | 显示全部楼层
这道题首先可以看作两个部分:1,排序;2,求独。算法很多了,怎么做随自己意
我的想法是,能不能在排序过程中就过滤重复的数值。
一种思路是,如果可以改变原序列中数据,使用合并排序法。合并过程中,只有独一无二的元素才会被排列,重复的直接拷到序列末尾。加一个标识标注独一无二部分的末尾。
于是只有最长递减子序列出现在排序序列开头。。。。
等有时间了再把代码写出来看看行不行。。。现在不很方便【2011-5-19】有奖竞猜

评分

参与人数 1驿站币 +5 收起 理由
56_avatar_small zhaoshengbo + 5

查看全部评分

66_avatar_middle
在线会员 发表于 2011-5-20 16:49:50 | 显示全部楼层
【2011-5-19】有奖竞猜先剔除重复数字,再冒泡排序从大到小:
  int array[7] ,n_array[5];
  int n=7;  
  int temp;
for(int i=0;i<n;i++)
  scanf("%d",&array[i]);
  n_array[0]=array[0];
  int  t=1;

  for( i=1;i<=n-1;i++)
  {  int signf =1;   
     for(int j=0;j<=t-1;j++)
     {  
       if(array[i]==n_array[j])
       {
         signf=0;
         break;
       }
     }
     if(signf==1)
     {
       n_array[t]=array[i];
       t++;
      }
  }
  for(int i=0;i<=t;i++)
  {
    for(int j=0;j<=t-i;j++)
      {   
            if(n_array[j]>n_array[j-1])
            {   
                temp = n_array[j-1];
                n_array[j-1] = n_array[j];
                n_array[j] = temp;
            }
        }
   }
就是不知道行不行撒?

评分

参与人数 1驿站币 +5 收起 理由
56_avatar_small zhaoshengbo + 5

查看全部评分

57_avatar_middle
在线会员 发表于 2011-5-20 17:50:10 | 显示全部楼层
我的思路是这样的.
利用vector<int > array; //用来保存数组中以每个值最长的序列数,例如你上面举的例子中array为:5,3,2,4,3,2,1
并分别把最长序列利用vector数组保存起来
vector<vector<int>> map;
并且保存的顺序要与上面array的顺序一致.(这样是为了方便以后查找到某个序列最长后,从map里面得到序列.
再进行比较array里面那个值最大.在根据对应关系,取出序列值

评分

参与人数 1驿站币 +5 收起 理由
56_avatar_small zhaoshengbo + 5

查看全部评分

56_avatar_middle
ico_lz  楼主| 发表于 2011-5-20 20:52:52 | 显示全部楼层
本帖最后由 zhaoshengbo 于 2011-5-20 21:00 编辑

请大家认真审题【2011-5-19】有奖竞猜

10 4 3 2 1 0 9 8 7 6 5
两个答案:
①10 4 3 2 1 0
②10 9 8 7 6 5
如果按楼上的各位的说法答案是10~0并不是正确答案


补充一句这是创新工厂的笔试题

我给出的数组就是个例子,数组的值并不做限制

02_avatar_middle
在线会员 发表于 2011-5-21 00:32:37 | 显示全部楼层
本帖最后由 cheerup 于 2011-5-21 14:43 编辑

晕死。彻底被雷到。原来如此。
那么假设不但要找出最长的,还要能把最长的递减序列都能打出来
如此,我的思路是,第一步改造数据结构
list<struct* >, 其中struct包含数字和指向另一个list<struct*>的指针(引用也行)
对于任何一个list<struct*>,它都是递增的,找到比当前的元素更小的数值的时候,就向下一层传递,
比如7 8 5 6 12 11 2 3 4最后变成
7                      8                    12         
5          6          5          6         11
2 3 4    2 3 4     2 3 4    2 3 4     2 3 4
最后再对这个数据结构找最长的单链
这个例子一共有15个答案
当然,这个解法太暴力了……
代码来了。。。。用VC#写的主要是习惯问题……
int[] arrIn=null;
        Entry top;

        class Entry
        {
            public int num;
            public int currentMax = int.MinValue;
            public Entry parentEntry = null;
            public List<Entry> le = new List<Entry>();

            public Entry()
            {
                num = int.MinValue;
            }

            public Entry(int num)
            {
                this.num = num;
            }

            public Entry(int num, Entry parentEntry)
            {
                this.num = num;
                this.parentEntry = parentEntry;
            }

            public void Add(int num)
           {
                if (num == currentMax)
                {
                    return;
                }
                else if (num > currentMax)
                {
                    currentMax = num;
                    le.Add(new Entry(num, this));
                }
                else
                {
                    for (int i = 0; i < le.Count; i++)
                        if(num<le.num)
                            le.Add(num);
                }
           }

           //下面两个函数只是测试打印用
            public string PrintLane(string strIn)
            {
                if (parentEntry == null)
                    return strIn;
                else if (parentEntry.parentEntry == null)
                    return num.ToString() + " " + strIn;
                else
                    return parentEntry.PrintLane(num.ToString() + " " + strIn);
            }

            public void Print(List<string> ls)
            {
                for (int i = 0; i < le.Count; i++)
                {
                    if (le.le.Count == 0)
                        ls.Add(le.PrintLane(string.Empty));
                    else
                        le.Print(ls);
                }
            }
        }

        //这个函数呼叫创建数据结构
        private void MaxDecSeries()
        {
            ConstructData();
            PrintData();
        }

       //这个函数用来打印
        private void PrintData()
        {
            List<string> ls = new List<string>();
            top.Print(ls);
            textBoxOutput.Text = string.Empty;
            for (int i = 0; i < ls.Count; i++)
                textBoxOutput.Text += ls + Environment.NewLine;
        }

        //这个创建数据结构
        private void ConstructData()
        {
            string[] tmp = textBoxInput.Text.Split(' ');
            arrIn = new int[tmp.Length];
            for (int i = 0; i < tmp.Length; i++)
                arrIn = int.Parse(tmp);
            top = new Entry();
            if(arrIn[0]==int.MinValue)
                top.le.Add(new Entry(arrIn[0], top));

            for(int i=0; i<tmp.Length; i++)
            {
                top.Add(arrIn);
            }
        }

上面的代码是完成拷贝我说的数据结构后面只要把最长的找出来就好。就不贴了。太长

评分

参与人数 1驿站币 +5 收起 理由
56_avatar_small zhaoshengbo + 5

查看全部评分

03_avatar_middle
在线会员 发表于 2011-5-22 23:51:27 | 显示全部楼层
路过,瞅瞅啊000000【2011-5-19】有奖竞猜
54_avatar_middle
在线会员 发表于 2011-6-11 12:56:11 | 显示全部楼层
不懂 来捧个场
27_avatar_middle
在线会员 发表于 2011-6-12 12:56:59 | 显示全部楼层
本帖最后由 lizuolong 于 2011-6-12 12:59 编辑

提供下思路,
看楼主题目半天才明白,其实楼主的例子不恰当,都包含4,3,2.
我提供思路:
先把数组中的递减序列提取出来,然后比较提取出来的序列数组的长度进行比较,输出>=的数组
例子:
10 5 2 9 7 3 1 3 5 8 7 6 2 1
递减序列为
10 5 2
9 7 3 1
3
5
8 7 6 2 1
长度分别3 4 1 1 5取最后一组数组
当然也可以才把一个元素的数组不列出来

手机上回复的,排版应该不会有问题
50_avatar_middle
在线会员 发表于 2011-6-16 11:41:55 | 显示全部楼层
这个问题,比较难,我得好好想一下,想好了,在答复你了
43_avatar_middle
在线会员 发表于 2011-7-5 21:49:34 | 显示全部楼层
本帖最后由 jialu 于 2011-7-5 22:15 编辑

思路:
nPos=0;
nCounter=1;
nMaxPos=0;
nMaxCounter=1;
for( i=1;i<n;i++)
{
     if( *(pData+i) - *(pData+i-1) <0 )
      {
         nCounter++;
     }
     else
      {
          if(nCounter>nMaxCouter)
          {
             nMaxPos=nPos;
             nMaxCouter=nCouter;
             nPos=i;
             nCounter=1;
           }
       }
}

根据nMaxPos和nMaxCouter输出子序列,不过只输出一个最长递减子序列。
有相同长度的子序列要复杂点,可以用数组保存位置和长度,然后求长度最大值。
88_avatar_middle
在线会员 发表于 2011-7-27 11:24:05 | 显示全部楼层
比如 数组 10,7,2,5,3,8,6,4,1(数组array)  求他的递减序列。
可以分几步,
第一步求出连续递减序列,
//求出第NUM开始array的连续递减排列,返回有ii个数。
int array[9] = {10,7,2,5,3,8,6,4,1};
int LongArray(int Num,int arrayT[9])
{
        int ii=0;
        arrayT[0] = array [Num];
        for(int i = Num; i<9;i++)
        {
                if(arrayT[ii]>array[i+1])
                {       
                        ii++;
                        arrayT[ii] = array [i+1];
                        printf("%d  \n",arrayT[ii-1]);
                }
        }
        return ii;
}
得到array的连续递减排列为 10 7 2 1

第2步比较 连续数组排列的每一个数其后是否有大于其本身的代码
//compare two Num.
int Equal(int arr)
{
        for(int i=0;i<9;i++)
        {
                if(arr<array[i])
                        return i;
        }
        return 0;
}

第3步  如有,替换后,求其最长的连续递减排列(可用递归,我没想好怎么用。)
时间关系,我就没写伪代码了;
比如array的连续递减排列为 10 7 2 1 ;比较第一个数10有没比他大的? 没有,放弃。第2个7,发现有比他大的8,得到连续排列为 8 6 4 1
加上前面的10 。得到排列10,8,6,4,1 长于前面的排列10 7 2 1 ;
所以取10,8,6,4,1的每个数字与其后面的数字进行比较。
最后可得最长递减子序列为10,8,6,4,1。。






78_avatar_middle
在线会员 发表于 2011-8-3 09:14:32 | 显示全部楼层
我也来看看各种解法,,
79_avatar_middle
在线会员 发表于 2011-8-14 09:58:48 | 显示全部楼层
顶一下楼主哦!。。。。。
80_avatar_middle
在线会员 发表于 2011-10-25 15:34:53 | 显示全部楼层
路过,进来看看,学习一下
64_avatar_middle
在线会员 发表于 2011-11-4 14:53:49 | 显示全部楼层
呵呵 最近看stl 感觉用list很好解决。直接上代码了。
list<int> list1;
list1.push_back(9);
list1.push_back(4);
......                        //input other elements
list1.sort();             //sort the elements
list1.unique();        //delete the element appeared twice or more
64_avatar_middle
在线会员 发表于 2011-11-4 14:57:44 | 显示全部楼层
啊 题目没看清楚。晕死。。。。
53_avatar_middle
在线会员 发表于 2011-11-11 01:31:04 | 显示全部楼层
我的思路会用链表 先用头插法插入数据  然后在建立另外一个链表 初始值为先前的链表的第一个 然后就是比较了  然后有相等的就跳出比下一个
15_avatar_middle
在线会员 发表于 2011-11-16 19:22:11 | 显示全部楼层
本帖最后由 小疯风流 于 2011-11-16 19:24 编辑

是不是保持后面的数字都是递减并且小于第一个数?且后面的数字总和最大?
原数组a[n],建个新数组b[n],初始化都为0,
把后面的数与第一个数比较,大于则继续,小于则b[j]++,j是位置,再比较a[i-1]和a,是递减则j不变,b[j]++,要不是递减则j=i,b[j]++。最后比较数组b的元素,找出最大值,根据数组b的位置j,从数组a的j位置开始输出b[j]个元素。
您需要登录后才可以回帖 登录 | 加入驿站 qq_login

本版积分规则

关闭

站长提醒上一条 /2 下一条

QQ|小黑屋|手机版|VC驿站 ( 辽ICP备09019393号tongdun|网站地图wx_jqr

GMT+8, 2019-3-25 23:26

Powered by Discuz! X3.4

© 2009-2019 cctry.com

快速回复 返回顶部 返回列表