APCS 實作題 10610 第2題交錯字串參考解法

若您覺得文章寫得不錯，請點選文章上的廣告，來支持小編，謝謝。

此題在高中生程式解題系統的題號為：c462: apcs 交錯字串 (Alternating Strings)。

============底下文字取自官方的試題文件============
問題描述 
一個字串如果全由大寫英文字母組成，我們稱為大寫字串；如果全由小寫字母組成則稱為小寫字串。字串的長度是它所包含字母的個數，在本題中，字串均由大小寫英文字母組成。假設 k 是一個自然數，一個字串被稱為「k-交錯字串｣，如果它是由長度為 k 的大寫字串與長度為 k 的小寫字串交錯串接組成。

舉例來說，「StRiNg｣是一個 1-交錯字串，因為它是一個大寫一個小寫交替出現；而「heLLow｣是一個 2-交錯字串，因為它是兩個小寫接兩個大寫再接兩個小寫。但不管 k 是多少，「aBBaaa｣、「BaBaBB｣、「aaaAAbbCCCC｣都不是 k-交錯字串。

本題的目標是對於給定 k 值，在一個輸入字串找出最長一段連續子字串滿足 k-交錯字串的要求。例如 k=2 且輸入「aBBaaa｣，最長的 k-交錯字串是「BBaa｣，長度為 4。又如 k=1 且輸入「BaBaBB｣，最長的 k-交錯字串是「BaBaB｣，長度為 5。
============以上文字取自官方的試題文件============

解法如下：
變數 cg 記錄目前交錯字串長度。
變數 g 紀錄最大交錯字串長度。
變數 ck 紀錄目前字母case累積次數。
變數 preL 紀錄上一個字母的case是大寫u、小寫 l、未知n。
變數 curL 紀錄目前字母的case是大寫u、小寫 l、未知n。

將題目輸入的 k 值分成兩種情況來處理，這是因為筆者的解法在處理 k = 1 與 k > 1 這兩種情況時，剛好是相反的。

k = 1 時，當發生大小寫轉換(preL != curL)時，cg 就加 1；否則  cg 設為 1。 g 設為 max(g, cg)。


k > 1 時，請參考底下圖片：
當發生大小寫轉換(preL != curL)時，目前字母case累積次數 ck 會有三種情況：
ck < k，將 cg = 0。
ck == k，將 cg + k，cg = max(g, cg)。
ck > k，cg = k。

請注意到上圖右邊是個？號，這是因為在字串到尾端時，若沒有發生大小寫轉換，會少考慮到右邊的？號中ck次數的情況。

所以改為當沒發生大小寫轉換(preL == curL) 時，判斷底下兩件事：
ck == k，將 cg + k，cg = max(g, cg)。
ck > k，cg = k。
而在發生大小寫轉換(preL != curL)時，將 cg = 0，ck = 1。 

以 k = 2 為例，g, cg, ck 值的變化如下表：
最大交錯字串長度(g)的改變會發生在紅色或橘色字母上。
目前交錯字串長度(cg)的改變會發生在橘色字母上。

C 程式碼：
 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
#include <stdio.h>
#include <string.h>
#include <ctype.h>

// 回傳兩個整數的最大值
int max(int x,int y) {
    return (x >= y? x: y);
}

// 取得字母大小寫
char letterCase(char c)
{
    if(islower(c)) return 'l';
    if(isupper(c)) return 'u';
    return 'n';
}

int main(void) {
    int k;
    char str[100000];

    while(scanf("%d", &k) == 1)
    {
        int g = 0;      // 交錯字串最大長度
        int cg = 0;     // 目前交錯字串長度
        scanf("%s", str);
        int len = strlen(str);

        char preL = 'n';    // 上一個字母是大寫u、小寫 l、未知n。
        char curL;          // 目前字母是大寫u、小寫 l、未知n。
        int ck = 0;         // 目前字母case累積次數

        //  k 為 1 時要另外處理
        if(k == 1)
        {
            for(int i = 0; i < len; i++)
            {
                curL = letterCase(str[i]);      // 取得字母大小寫
                if(preL != curL)    // 轉換大小寫時
                    cg++;
                else                // 沒轉換大小寫時
                    cg = 1;

                g = max(cg, g);     // g 和 cg 誰是最大交錯字串長度
                preL = curL;        // 上一個字母case為目前字母case
            }
        }
        else
        {
            for(int i = 0; i < len; i++)
            {
                curL = letterCase(str[i]);

                if(preL == curL)
                {
                    ck++;
                    if(ck == k)             // 累積到 k 次
                    {
                        cg += k;            // 加到目前交錯字串長度
                        g = max(cg, g);     // g 和 cg 誰是最大交錯字串長度
                    }

                    if(ck > k)              // 目前case次數超過 k 次
                        cg = k;             // 目前交錯字串長度也只能等於 k
                }
                else if(preL != curL)       // 轉換大小寫時
                {
                    if(ck < k) cg = 0;      // 目前case次數小於 k 次，目前交錯字串長度歸零
                    ck = 1;                 // case次數從 1 開始
                }
                preL = curL;                // 上一個字母case為目前字母case
            }
        }

        printf("%d\n", g);
    }
    return 0;
}


C++ 程式碼：
 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
#include <iostream>
#include <string>

using namespace std;

// 取得字母大小寫
char letterCase(char c)
{
    if(islower(c)) return 'l';
    if(isupper(c)) return 'u';
    return 'n';
}

int main(void) {
    int k;
    string str;

    while(cin >> k)
    {
        int g = 0;      // 交錯字串最大長度
        int cg = 0;     // 目前交錯字串長度
        cin >> str;
        int len = str.length();

        char preL = 'n';    // 上一個字母是大寫u、小寫 l、未知n。
        char curL;          // 目前字母是大寫u、小寫 l、未知n。
        int ck = 0;         // 目前字母case累積次數

        //  k 為 1 時要另外處理
        if(k == 1)
        {
            for(int i = 0; i < len; i++)
            {
                curL = letterCase(str[i]);      // 取得字母大小寫
                if(preL != curL)    // 轉換大小寫時
                    cg++;
                else                // 沒轉換大小寫時
                    cg = 1;
                
                g = max(cg, g);     // g 和 cg 誰是最大交錯字串長度
                preL = curL;        // 上一個字母case為目前字母case
            }
        }
        else
        {
            for(int i = 0; i < len; i++)
            {
                curL = letterCase(str[i]);

                if(preL == curL)
                {
                    ck++;
                    if(ck == k)             // 累積到 k 次
                    {
                        cg += k;            // 加到目前交錯字串長度
                        g = max(cg, g);     // g 和 cg 誰是最大交錯字串長度
                    }

                    if(ck > k)              // 目前case次數超過 k 次
                        cg = k;             // 目前交錯字串長度也只能等於 k
                }
                else if(preL != curL)       // 轉換大小寫時
                {
                    if(ck < k) cg = 0;      // 目前case次數小於 k 次，目前交錯字串長度歸零
                    ck = 1;                 // case次數從 1 開始
                }
                preL = curL;                // 上一個字母case為目前字母case
            }
        }

        cout << g << endl;
    }
    return 0;
}

Python 程式碼：
 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
def letterCase(c):
    if c.isupper():
        return 'u'
    if c.islower():
        return 'l'
    return 'n'

while True:
    try:
        k = int(input())
        g = 0      # 交錯字串最大長度
        cg = 0     # 目前交錯字串長度
        s = input()
        l = len(s)

        preL = 'n'    # 上一個字母是大寫u、小寫 l、未知n。
        curL = 'n'     # 目前字母是大寫u、小寫 l、未知n。
        ck = 0         # 目前字母case累積次數

        #  k 為 1 時要另外處理
        if(k == 1):
            for i in range(l):
                curL = letterCase(s[i])      # 取得字母大小寫
                if(preL != curL):    # 轉換大小寫時
                    cg = cg + 1
                else:                # 沒轉換大小寫時    
                    cg = 1
                g = max(cg, g)     # g 和 cg 誰是最大交錯字串長度
                preL = curL        # 上一個字母case為目前字母case
        else:
            for i in range(l):
                curL = letterCase(s[i])
                if preL == curL:
                    ck = ck + 1
                    if(ck == k):             # 累積到 k 次    
                        cg += k            # 加到目前交錯字串長度
                        g = max(cg, g)     # g 和 cg 誰是最大交錯字串長度

                    if(ck > k):              # 目前case次數超過 k 次
                            cg = k             # 目前交錯字串長度也只能等於 k
                    
                elif preL != curL:       # 轉換大小寫時
                    if ck < k:
                        cg = 0      # 目前case次數小於 k 次，目前交錯字串長度歸零
                    ck = 1                 # case次數從 1 開始
                preL = curL                # 上一個字母case為目前字母case

        print(g)
    except EOFError:
        break
Labels: , , ,