iT邦幫忙

2021 iThome 鐵人賽

DAY 23
0
自我挑戰組

用 C & C++ 帶你手把手解 UVa 一顆星選集系列 第 23

Day 0x17 UVa10252 Common Permutation

題意

  • 輸入 ab 兩字串,輸出皆為兩者的子字串
  • 需要注意的有:
    1. 重複輸入兩字串 (各一行)
    2. 字串皆小寫字母
    3. 輸出的字串要同時為兩字串的子字串 (可順序不同)
    4. 承上點,有多組符合輸出字母由小到大

解法

  • 換句話說,確定兩字串的字母各有多少個,由小到大輸出即可,和 Day 0x5 UVa10062 Tell me the frequencies! & Day 0x6 UVa10008 What's Cryptanalysis? 這兩題小類似
  • 重複讀入兩字串直到 EOF,並用兩次迴圈分別計算兩字串各字母的出現次數
    char a[1001] = {0};
    char b[1001] = {0};
    int i, j;
    
    while(gets(a) && gets(b)){
    
        int tableA[26] = {0};
        int tableB[26] = {0};
    
        for(i = 0; i < strlen(a); i++){
            tableA[a[i] - 'a']++;
        }
        for(i = 0; i < strlen(b); i++){
            tableB[b[i] - 'a']++;
        }
        ...
    }
    
  • for 迴圈由小到大遍歷字母表,透過 if 比較兩字串該字母出現的次數誰比較少,再用 for 輸出較少刺數的字母
    for(i = 0; i < 26; i++){
        if(tableA[i] != 0 && tableB[i] != 0){
            if(tableA[i] <= tableB[i]){
                min = tableA[i];
            }
            else{
                min = tableB[i];
            }
            for(j = 0; j < min; j++){
                printf("%c", i + 97);
            }
        }
    }
    
  • C code
    #include<stdio.h>
    #include<string.h>
    
    int main(){
    
        char a[1001] = {0};
        char b[1001] = {0};
        int i, j;
        int length;
        int min;
    
        while(gets(a) && gets(b)){
    
            int tableA[26] = {0};
            int tableB[26] = {0};
    
            for(i = 0; i < strlen(a); i++){
                tableA[a[i] - 'a']++;
            }
            for(i = 0; i < strlen(b); i++){
                tableB[b[i] - 'a']++;
            }
    
            for(i = 0; i < 26; i++){
                if(tableA[i] && tableB[i]){
                    if(tableA[i] <= tableB[i]){
                        min = tableA[i];
                    }
                    else{
                        min = tableB[i];
                    }
                    for(j = 0; j < min; j++){
                        printf("%c", i + 97);
                    }
                }
            }
    
            printf("\n");
    
        }
    
        return 0;
    }
    

上一篇
Day 0x16 UVa10235 Simply Emirp
下一篇
Day 0x18 UVa10415 Eb Alto Saxophone Player
系列文
用 C & C++ 帶你手把手解 UVa 一顆星選集30

尚未有邦友留言

立即登入留言