算法求解

wonderall01

回复 7# folklore
hash怎么实现呢，给个思路，谢谢

cdtits

1. int detect(char *pnum)
   
2. {
   
3.         int num;
   
4.         int tmp[10] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
   
5.         while (num = *pnum++) {
   
6.                 if (++tmp[num - '0'] > 1)
   
7.                         return 0;
   
8.         }
   
9.         return 1;
   
10. }

复制代码

cdtits

1. int detect(char *pnum)
   
2. {
   
3.         int num;
   
4.         int tmp[10] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
   
5.         while (num = *pnum++) {
   
6.                 if (++tmp[num - '0'] > 1)
   
7.                         return 0;
   
8.         }
   
9.         return 1;
   
10. }

复制代码

fenghw8088

我觉得是10个数的全排列问题，是先取1个数放第1个盒子，再取1个数放第2个盒子，直到取完10个数。
一次循环处理一个数，怎么也要10次循环。
如果要少于10次循环完成，是不是无解呀？

folklore

回复 10# wonderall01


    jsut access the numbers as strings, so

1.create a hash table
2.for each number do
  2.1 read the number
  2.2 trim out the prefix 0
  2.3 check if the number in hash table
      2.3.1 the specified number allready exists in hash table --> duplicated detected
      2.3.2 other ways: push the number to hash table.
3. clear the above hash table
4. destory the hash table

perhaps you can use STL(hash<> or map<>) to make it easy.

file3

1. int isRepeat(long num)
   
2. {
   
3.     char str[32] = { 0 };
   
4.     int i = 0;
   
5. 
   
6.     int ret = -1;
   
7.     sprintf(str, "%d", num);
   
8. 
   
9.     for (i = 0; str[i] != '\0' & i < 32; i++)
   
10.     {
    
11.         for(j = i + 1; str[j] != '\0' && j <= strlen(str); j++)
    
12.         {
    
13.             if (str[i] == str[j])
    
14.             {
    
15.                 return -1;
    
16.             }
    
17.         }
    
18.     }
    
19.     return 0;
    
20. }
    
21. 
    
22. int main()
    
23. {
    
24.     long  num = 0;
    
25. 
    
26.     for (num = 0; num < 10000000000; num++)
    
27.     {
    
28.        if ( isRepeat(num) == 0)
    
29.          printf("not repeat num: %ld \n", num);
    
30.     }
    
31.     return 0;
    
32. }

复制代码

_Rayx

计算了一下，数并不多，可能就1000万左右，所以最好就是广度优先搜索了。
这个效果应该是最好的，而且保证了不重复。

_Rayx

如果只是想找到这样的数的个数，应该使用位DP。

sacry

Algorithms to generate permutations‎?

不会抽烟

是不是说每个数字的每个位上的数都只能出现一次？ 比如说 101, 220 ， 12355 就不行。如果是这样的话，看下面的程序。 做个了测试，0~999之间的，可以搞定。

1. 
   
2. int i=0, j=0, k=0;
   
3. int * idx = (int*)calloc(1, 11*sizeof(int));;
   
4. char str[11] = "0000000000";
   
5. for(i=0; i<999; i++){
   
6.    sprintf(str, "%d", i);
   
7.    for(j=0; ; j++){
   
8.       if(str[j] == '\0'){
   
9.         fprintf(stdout, " %d", i);
   
10.         break;
    
11.       }
    
12.       k=(str[j]-'0');
    
13.       idx[k]++;
    
14.       if(idx[k] >1)
    
15.         break;
    
16.    }
    
17.   memset(idx, 0, 11*sizeof(int));
    
18. }
    
19. 
    
20.                                  

复制代码