首页 新闻 论坛 群组 Blog 文档 下载 读书 Tag 网摘 搜索 .NET Java 游戏 视频 人才 外包 培训 数据库 书店 程序员
中国软件网
欢迎您:游客 | 登录 注册 帮助
    • ^_^ 算法比赛 -------------------- [无满意答案结帖,结帖人:zpcoder]
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • zpcoder
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    • 结帖率：
    发表于：2008-09-03 15:19:59 楼主
    一字符串A 由一个正整数+,(逗号)+另一个正整数组成。如同:  1234,56
    一字符串集合(数组)B,由多个A组成。列如：
    1234,57
    237,40
    3909,0
    ……

    求A,是否在B中存在 (或者说 A是否与B中的某一项相等,列 123,45 == 123,45)


    说明：

    ,号后面的数字如果是0,则可以表示其它的所有数也就是说若B中的一项是：12345,0 ; 可以包含以12345, 开头的任何一个A.同理,如果A的,后面是0的话.B中任何一项的开头与A相同则返回true

    提醒: ,后面的要是数字型的,也不是说没有 00、0000、0003……,这种写法。仅是一些数字。


    100  修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • worilo
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2008-09-03 15:21:281楼 得分:0
    sf
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • wdgphc
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2008-09-03 15:34:212楼 得分:0
    有没有 A为 0,123 之类的啊,或 0,0之类的啊?
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • HimeTale
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2008-09-03 15:42:503楼 得分:0
    先把b散列:
    1234,56->12345602  //02是逗号的位置
    3344,4->3344401
    0,2233->223304
    3909,0->390900
    0,0->00
    把散列到的数组位置值设为1.

    然后查找:
    如果a是123,456 则找00,12300,45603,12345603四个位置
    如果a是0,456 则找00,45603
    如果a是123,0 则找 12300
    如果a是0,0则找00


    按这个方式,查询复杂度O(1);

    ps:要是一点都看不懂我说的话说明你算法还没入门
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • HimeTale
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2008-09-03 15:44:564楼 得分:0
    如果a是123,0 则找 12300
    改成 如果a是123,0 则找 12300 ,00
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • juge001
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2008-09-03 15:45:525楼 得分:0
    C# code
                string strA = "1234,5";
            string strBList = new string[] { "1234,5", "121351,5" };

            string[] strATempList = strA.Split(",");

            //if (strATempList.Length != 2)
            //{
            //    return false;
            //}

            foreach(string strB in strBList)
            {
               
                string[] strBTempList = strB.Split(",");

                //if(strBTempList.Length != 2)
                //{
                //    continue;
                //}

                if ((int)strATempList[1] == 0 && (int)strATempList[0] == (int)strBTempList[0])
                {
                    return true;
                }
                else if ((int)strBTempList[1] == 0 && strATempList[0] == strBTempList[0])
                {
                    return true;
                }
                else if ((int)strBTempList[1] == (int)strATempList[1] && (int)strBTempList[0] == (int)strATempList[0])
                {
                    return true;
                }
            }
            return false;
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • gomoku
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2008-09-03 15:47:246楼 得分:0
    估计你很难衡量不同实现的效率差别。


    1、如果给定一个B，判断是否B中包含A，则顺序查找，O(n)。
    2、如果给定一个B，多次用不同的A来判断是否包含，则可以对B进行预处理（比如放到Hashtable或Dictionary中，O(n)）。以后每次判断约为O(1)。
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • wangkun9999
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2008-09-03 15:49:157楼 得分:0
    C# code
    
public bool TestNumber(string A,ArrayList B)
{
   string[] C=A.Split(',');
   if (B.Contains(A)||B.Contains("0,"+C[1])||B.Contains(C[0]+",0"))
     return true;
  else
     return false;
}
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • zfc1978
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2008-09-03 15:50:328楼 得分:0
    路过，关注中。
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • juge001
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2008-09-03 15:50:409楼 得分:0
    C# code
                string strA = "1234,5";
            string[] strBList = new string[2] { "1234,5", "121351,5" };

            string[] strATempList = strA.Split(',');

            foreach(string strB in strBList)
            {
               
                string[] strBTempList = strB.Split(',');

                if (Convert.ToInt32(strATempList[1]) == 0 && Convert.ToInt32(strATempList[0]) == Convert.ToInt32(strBTempList[0]))
                {
                    return true;
                }
                else if (Convert.ToInt32(strBTempList[1]) == 0 && Convert.ToInt32(strATempList[0]) == Convert.ToInt32(strBTempList[0]))
                {
                    return true;
                }
                else if (Convert.ToInt32(strBTempList[1]) == Convert.ToInt32(strATempList[1]) && Convert.ToInt32(strBTempList[0]) == Convert.ToInt32(strATempList[0]))
                {
                    return true;
                }
            }
            return false;


    晕死,编译都通不过,修改了一下,不好意思....
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • zpcoder
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2008-09-03 15:53:5110楼 得分:0
    题目补充说明: , 号之前没有0 全是大于0的正整数;  , 之后才有可能是0
    以下是自己最早写的

    C# code
            string[] input = txtProduct.Text.Trim().Split(','); //A
        foreach (string li in B)
        {
            string[] colle = li.Text.Split(',');
            if (input[0] == colle[0])
            {
                if (int.Parse(input[1]) == 0 || int.Parse(colle[1]) == 0 || input[1] == colle[1]) return true;
            }
        }
        return false;
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • zpcoder
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2008-09-03 15:56:5311楼 得分:0
    C# code
    //更正：10楼

        string[] input = A.Split(','); 
        foreach (string str in B)
        {
            string[] colle = str.Split(',');
            if (input[0] == colle[0])
            {
                if (int.Parse(input[1]) == 0 || int.Parse(colle[1]) == 0 || input[1] == colle[1]) return true;
            }
        }
        return false;
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • Nantty
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2008-09-03 16:50:4912楼 得分:0
    string A = "123,10";
    string[] Aa= new string[2];
    int a0;
    double a1;
    Aa = A.Split(',');
    a0 = System.Convert.ToInt32(Aa[0]);
    a1 = System.Convert.ToDouble("0."+Aa[1]);

    string[] B ={"0123,10","25,56","56,45","123,100","123,"};
    string[] Bb=new string[2];
    int i;
               
    for (i = 0; i < 5; i++)
    {
      int b0;
      double b1;
      Bb = B[i].Split(',');

      b0 = System.Convert.ToInt32(Bb[0]);
      b1 = System.Convert.ToDouble("0."+Bb[1]);

      if (a0==b0 && a1==b1) listBox1.Items.Add(B[i].ToString());
    }

    按你的要求，符合条件的就会在listBox1中列出来。
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • wanghui0380
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2008-09-04 12:50:3313楼 得分:0
    嗯哼，和3楼一样的想法，散列出特征值即可
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • zswang
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：

    • 2

      7
    发表于：2008-09-04 12:55:4614楼 得分:0
    12340000000000000,57
    23700000000000000,40
    39090000000000000000000000000000000000000000000000,0
    图崩溃。
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • hflkl1314
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2008-09-04 12:56:1915楼 得分:0
    学别人算法比赛
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • wanghui0380
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2008-09-04 13:03:3916楼 得分:0
    的确崩溃

    还是散列md5值吧！！不过md5的化，复杂度比较高了点
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • QQmeiren
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2008-09-04 13:06:5517楼 得分:0
    很难衡量不同实现的效率差别。


    1、如果给定一个B，判断是否B中包含A，则顺序查找，O(n)。
    2、如果给定一个B，多次用不同的A来判断是否包含，则可以对B进行预处理（比如放到Hashtable或Dictionary中，O(n)）。以后每次判断约为O(1)。
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • HimeTale
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2008-09-04 13:45:3018楼 得分:0
    引用 14 楼 zswang 的回复:
    12340000000000000,57
    23700000000000000,40
    39090000000000000000000000000000000000000000000000,0
    崩溃。

    前提当然是范围,
    不给范围的话我算个加法都有可能崩溃.
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • berlin8600
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2008-09-04 13:59:3319楼 得分:0
    也不知道，
    这个A最多有多少位，
    B最多有多少个元素哈？
    就是，先给个范围啊。
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • zpcoder
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2008-09-08 16:05:2620楼 得分:0

    18楼 说的对, 肯定有的社~~

    我们只是就这个事聊聊，那有你们说的那么牛角尖。
    修改 删除 举报 引用 回复
    网站简介－广告服务－网站地图－帮助－联系方式－诚聘英才－English－ 问题报告
    北京创新乐知广告有限公司 版权所有 京 ICP 证 070598 号
    世纪乐知(北京)网络技术有限公司 提供技术支持
    Copyright © 2000-2008, CSDN.NET, All Rights Reserved