^_^ 算法比赛 --------------------

Question

一字符串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……,这种写法。仅是一些数字。

Answer 1

先把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:要是一点都看不懂我说的话说明你算法还没入门

Answer 2

            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;

Answer 3

估计你很难衡量不同实现的效率差别。
1、如果给定一个B，判断是否B中包含A，则顺序查找，O(n)。
2、如果给定一个B，多次用不同的A来判断是否包含，则可以对B进行预处理（比如放到Hashtable或Dictionary中，O(n)）。以后每次判断约为O(1)。

Answer 4

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;
}

Answer 5

            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;晕死,编译都通不过,修改了一下,不好意思....

Answer 6

题目补充说明: , 号之前没有0 全是大于0的正整数;  , 之后才有可能是0
以下是自己最早写的        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;

Answer 7

//更正：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;

Answer 8

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中列出来。

Answer 9

的确崩溃还是散列md5值吧！！不过md5的化，复杂度比较高了点

Answer 10

很难衡量不同实现的效率差别。 
1、如果给定一个B，判断是否B中包含A，则顺序查找，O(n)。 
2、如果给定一个B，多次用不同的A来判断是否包含，则可以对B进行预处理（比如放到Hashtable或Dictionary中，O(n)）。以后每次判断约为O(1)。