之前的一个面试题

cs8121319

0到9所有数的正则表达式：[0-9]
0的99所有数的正则表达式：[0-9] | [1-9][0-9]
0的999所有数的正则表达式：[0-9] | [1-9][0-9] | [1-9][0-9][0-9]
........
给定unsigned int n，求0到n的所有数的正则表达式。

1. 
   
2. char * func(int x)
   
3. {
   
4.     char *re_result=(char *)malloc(MAX_LEN);
   
5.     int y=x;
   
6. 
   
7.     int round=0;
   
8.     //int 对于的10进制数最多15位
   
9.     char a[15];
   
10.     while(y>1)
    
11.     {
    
12.         y=(int)(y/10);
    
13.         round++;
    
14.     }
    
15.     itoa(x,a,10);
    
16.     a[round]='\0';
    
17.     //cout<<"a len : "<<strlen(a)<<"and int array: "<<a<<endl;
    
18. 
    
19.     char b09[6]="[0-9]";
    
20.     char b19[6]="[1-9]";
    
21. 
    
22. 
    
23.     //这个是对比本数小一位的所有数的正则
    
24.     // 65536  对应 0-9999
    
25.     char re_temp_low[MAX_LEN]={0};
    
26. 
    
27.     //这个和本数位数相同、最高位相同的所有数的正则
    
28.     // 65536  对应 60000 - 65536
    
29.     char re_temp_high[MAX_LEN]={0};
    
30. 
    
31.     //这个是与本数相同位数，但是最高位小一些的数的正则，前提是本数最高位大于1
    
32.     //65536  对应 10000 - 59999
    
33.     char re_start[MAX_LEN]={0};
    
34. 
    
35.     int len=round;
    
36.     for(;len>=1;len--)
    
37.     {
    
38.         //计算re_temp_low
    
39.         int len_1=len - 2;
    
40.         if(len_1>=0)
    
41.         {
    
42.             if(len_1==0)
    
43.             {
    
44.                 sprintf (re_temp_low,"%s%s",re_temp_low,b09);
    
45. 
    
46.             }
    
47.             if(len_1>0)
    
48.             {
    
49.                 int len_2=len_1;
    
50.                 sprintf(re_temp_low,"%s%s",re_temp_low,b19);
    
51.                 while(len_1>0)
    
52.                 {
    
53.                     sprintf(re_temp_low,"%s%s",re_temp_low,b09);
    
54.                     len_1--;
    
55.                 }
    
56.             }
    
57.             sprintf(re_temp_low,"%s | ",re_temp_low);
    
58. 
    
59.             //计算 re_temp_high
    
60. 
    
61.             int len_high=len - 2;
    
62.             //第len_num这个数要单独打印，前面的数直接输出，后面为[0-9]
    
63.             int len_num=(round-1)-len_high;
    
64.             //cout<<"len_num : "<<len_num<<endl;
    
65. 
    
66.             for(int i=0;i<len_num;i++)
    
67.             {
    
68.                 sprintf(re_temp_high,"%s%c",re_temp_high,a[i]);
    
69. 
    
70.             }
    
71. 
    
72.             char temp[6]="[0-9]";
    
73.             //之前a为int数组，用的下面的
    
74.             //temp[3]='0'+(a[i]-0);
    
75. 
    
76.             temp[3]=a[len_num]-1;
    
77.             if(len_num != round-1)
    
78.                 temp[3]=a[len_num]-1;
    
79.             if(len_num == round-1)
    
80.                 temp[3]=a[len_num];
    
81.             sprintf(re_temp_high,"%s%s",re_temp_high,temp);
    
82. 
    
83.             while(len_high>0)
    
84.             {
    
85.                 sprintf(re_temp_high,"%s%s",re_temp_high,b09);
    
86.                 len_high--;
    
87. 
    
88.             }
    
89.             sprintf(re_temp_high,"%s | ",re_temp_high);
    
90. 
    
91.         }
    
92.         else break;
    
93.     }
    
94. 
    
95.     //计算re_start
    
96.     if(a[0]>'1')
    
97.     {
    
98. 
    
99.         char temp[6]="[1-9]";
    
100.         char temp2[6]="[0-9]";
     
101.         temp[3]=a[0]-1;
     
102.         if(a[0] >'2')
     
103.             sprintf (re_start,"%s",temp);
     
104.         else
     
105.             sprintf (re_start,"%s","1");
     
106.         for(int i=round;i>0;i--)
     
107.             sprintf (re_start,"%s%s",re_start,temp2);
     
108.         //cout<<re_start<<endl;
     
109.         sprintf (re_result,"%s|%s|%s",re_start,re_temp_high,re_temp_low);
     
110.         return re_result;
     
111.     }
     
112. 
     
113.     sprintf (re_result,"%s|%s",re_temp_high,re_temp_low);
     
114.     return re_result;
     
115. }
     

复制代码

hellioncu

感觉应该用递归代码会比较简单

walleeee

0到9所有数的正则表达式：[0-9]
0的99所有数的正则表达式：[0-9] | [1-9][0-9]
0的999所有数的正则表达式：[0-9] | [1-9][0-9] | [1-9][0-9][0-9]

0到9所有数的正则表达式：[0-9]{1} = a1
0的99所有数的正则表达式：[0-9]{1} | [1-9][0-9]{1} = a2
0的999所有数的正则表达式：[0-9]{1} | [1-9][0-9]{1,2} = a3

可以递归

cs8121319

n不一定是9999一类的啊，可能是65536之类的

dengxiayehu

xuexi