Solution Idea

50051. Valid License Plates

題意

根據四個條件,判斷車牌是否合法:

  1. 車牌有兩種,第一種是 $x_1x_2$-$x_3x_4x_5x_6$ ,第二種是 $x_1x_2x_3$-$x_4x_5x_6$
  2. $x_1$ ~ $x_6$ 都必須是大小寫字母或數字
  3. $x_1$ ~ $x_6$ 至少要包含一個數字,且所有數字的和不能被 $7$ 整除
  4. $x_1$ ~ $x_6$ 不能包含同一種字元超過兩次
  5. $x_1$ ~ $x_6$ 不能有連續的兩個 $4$。第一種車牌中,$x_2$ 和 $x_3$ 不算連續;第二種車牌中,$x_3$ 和 $x_4$ 不算連續

把合法的車牌按照 ASCII 大小排序後輸出,先輸出第一種車牌,再輸出第二種車牌。

實作技巧

  1. 每個條件判斷盡量寫成 function ,增加程式的易讀性。

  2. 如果有需要用到字母的 ASCII 值,可以用單引號。例如 'A' <= ch , 而不是 65 <= ch。程式碼比較乾淨也不容易出錯。

  3. 善用 ctype.h 裡的 function。例如判斷 ch 是不是數字,可以用 isdigit(ch) ,不用自己寫成 '0' <= ch && ch <= '9'ctype.h 裡還有 isalpha(char)isalnum(char) 等 function。

  4. 比較字串大小時 (根據 ASCII 碼的值),可以用 string.h 裡的 strcmp(const char*, const char*) 幫助判斷。

實作注意事項

  1. 車牌都是七個字元,但是每個字串後面都會有 '\0' 字元代表結尾,所以陣列大小至少要是 $7 + 1 = 8$。如果拿 RE 可能是因為這個緣故。

  2. 關於strcmp(str1, str2): 若 str1str2 相同,會回傳 $0$;若 str1 < str2 ,則回傳一個負的值 (只保證是負的,不一定是 -1 !);若 str1 > str2,則回傳一個正的值 (只保證是正的,不一定是 1 !)。有同學判斷的時候寫 strcmp(str1, str2) == -1,這個寫法是錯的,應該改成 strcmp(str1, str2) < 0。 詳細的說明文件在這裡

  3. 關於isdigit(ch): 若 ch 是不是數字,會回傳 0;否則會回傳 非零的值(只保證不是零,不一定是 1)。其他類似的 function 包括 isalnum(ch), isalpha(ch) 等等也一樣。 詳細的說明文件在這裡

  4. 老師上課有提過課本裡的 bubble-sort 程式碼 index 有錯誤,p99. i = m - 1 應該為 i = m - 2。課本勘誤表連結

  5. 0 可以被 7 整除,所以 00-abcd 不是合法的車牌。

更多測資

提供同學另一筆容易錯的測資

Sample input

7
12-3456
44-ZejR
Gc4-4Oe
wJ--x20
3eM-nMM
K6-z-bB
00-abce

Sample output

Gc4-4Oe

程式碼

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
#include <stdio.h>
#include <assert.h>
#include <ctype.h>
#include <string.h>
#define MAXN 30
#define L 7
 
char license[MAXN][L+5];
 
int getHyphen(char *str){ // get the position of the hyphen (2 or 3, else return -1)
    if (str[2] == '-') return 2;
    return str[3] == '-' ? 3 : -1;
}
 
int multipleSameChar(char *str){ // check if an alpha or digit appears more than twice
    for(int i = 0; i < L; i++){
        int cnt = 1;
        for(int j = i + 1; j < L; j++)
            if (str[i] == str[j]) cnt++;
        if (cnt >= 3) return 1;
    }
    return 0;
}
 
int validSum(char *str){ // check if the sum of all digits cannot be divided by 7
    int sum = 0;
    for(int i = 0; i < L; i++)
        if (isdigit(str[i])) sum += str[i] - '0';
    return sum % 7 != 0; // no need to check if has at least one digit, since if there are no digits, sum remains 0 and it is invalid
}
 
int isValid(char *str){ // check if the string satisties all four constraints
    int sum = 0, haveNum = 0;
    int hyphen = getHyphen(str);
 
    if (hyphen == -1) return 0; // invalid (neither first nor second kind)
    if (!validSum(str)) return 0; // invalid (constraint 2.)
    if (multipleSameChar(str)) return 0; // invalid(constraint 3.)
 
    for(int i = 0; i < L; i++){
        char ch = str[i];
        if (i != hyphen && !isalnum(ch)) return 0; // invalid (constraint 1.)
        if (ch == '4' && str[i+1] == '4') return 0; // invalid (constraint 4.)
    }
 
    return 1;
}
 
 
int isSmaller(char *str1, char * str2){ // compare two strings
    int h1 = getHyphen(str1), h2 = getHyphen(str2);
    return h1 != h2 ? h1 < h2 : strcmp(str1, str2) < 0; // first check the type, if same type, check ASCII code using strcmp()
}
 
int sort(int *idx, int cnt){ // sort the index (selection sort)
    int tmp;
    for(int i = 0; i < cnt; i++){
        for(int j = i + 1; j < cnt; j++){
            if (isSmaller(license[idx[j]], license[idx[i]]))
                tmp = idx[i], idx[i] = idx[j], idx[j] = tmp;
        }
    }
}
 
int main(){
    int N, idx[MAXN], vcnt = 0;
 
    assert(scanf("%d", &N) == 1);
    for(int i = 0; i < N; i++){
        assert(scanf("%s", license[i]) == 1);
        if (isValid(license[i])) idx[vcnt++] = i; // safe the indices of all valid strings
    }
 
    sort(idx, vcnt);
 
    for(int i = 0; i < vcnt; i++)
        printf("%s\n", license[idx[i]]);
 
    return 0;
}

Discussion