2017/10/18 交錯字串

2023.1.24 PM 11:00 by CBJ

來源 : https://zerojudge.tw/ShowProblem?problemid=c462
出題者 : 字元判斷
標籤 : 2017年10月APCS
難易度 : 2

解題想法 : 
此題的做法不只一種，此處使用的是先將字串化為一個數列，數列中每個值就是連續大寫(小寫)的個數，得到這個數列後就可以得出答案。(例如aaaBBBccDDDDe -> 33241)

另一種作法則是，直接遍歷陣列，並同時維護當前位在大寫還是小寫，以及當前的長度。

此題實作不難，建議各位能夠使用自己的風格實作。

//C++ language

#include<iostream>
#include<vector> //vector 
#include<algorithm> //max() 
using namespace std;
int main(){
    int k; cin>>k;
    string s; cin>>s;
    vector<int>times;
    bool last_is_lower=false,
         last_is_upper=false;
    int cnt=0;
    for(char c:s){
        if(last_is_upper){
            if(isupper(c)) cnt++;
            else{
                times.push_back(cnt);
                cnt=1;
                last_is_upper=false;
                last_is_lower=true;
            }
        }
        else if(last_is_lower){
            if(islower(c)) cnt++;
            else{
                times.push_back(cnt);
                cnt=1;
                last_is_lower=false;
                last_is_upper=true;
            }
        }
        else{
            if(isupper(c)) last_is_upper=true;
            else last_is_lower=true;
            cnt++;
        }
    }
    if(cnt) times.push_back(cnt);
    
    int max_length=0,cur_length=0;
    for(int i:times){
        if(i==k) cur_length+=k;
        else if(i<k){
            max_length=max(max_length,cur_length);
            cur_length=0;
        }
        else{
            cur_length+=k;
            max_length=max(max_length,cur_length);
            cur_length=k;
        }
    }
    max_length=max(max_length,cur_length);
    
    cout<<max_length<<"\n";
    return 0;
}

## Python language

k=int(input())
s=input()
times=[]
def init():
    u=l=0
    last_is_upper=last_is_lower=False
    if s[0].isupper():
        last_is_upper=True
        u+=1
    else:
        last_is_lower=True
        l+=1
    for i in s[1:]:
        if last_is_upper:
            if i.isupper():
                u+=1
                last_is_upper=True
            else:
                times.append(u)
                u=0
                l+=1
                last_is_upper=False
                last_is_lower=True
        elif last_is_lower:
            if i.islower():
                l+=1
                last_is_lower=True
            else:
                times.append(l)
                l=0
                u+=1
                last_is_lower=False
                last_is_upper=True
    if l>0: times.append(l)
    elif u>0: times.append(u)
def find_max_length():
    max_length=cur_length=0
    for i in times:
        if i==k:
            cur_length+=k
        elif i<k:
            max_length=max(max_length,cur_length)
            cur_length=0
        elif i>k:
            cur_length+=k
            max_length=max(max_length,cur_length)
            cur_length=k
    max_length=max(max_length,cur_length)
    return max_length
init()
print(find_max_length())

相關文章

分享此文：