105 The Skyline Problem

簡易翻譯和條件:

這題雖然是兩顆星但是其實沒有很難~
主要就是在輸入的兩行字中找到common characters 並排序輸出
為什麼我會把行這個字特別換紅色呢?

因為我在寫的時候一直拿到error
我才去研究 debug 網站中的公開測資
才發現原來字串也包含空字串阿!!!!!
傻眼XD

主要就是用迴圈找到相同的字串並且換掉換成標點符號(以免之後又被重複算到)
不換成空字串的原因是換空字串的話會影響到字串長度，也會因此跳過後面的字元
找到後就像上一篇提到的一樣利用 algorithm 裡的 sort function 來排列比較方便!

不過我的寫法其實是比較慢的

因為這樣寫就變成Ο(n²)了!

我有在這裡看到一個比較快的想法
主要就是自製一個簡易的map紀錄ascii的方式
最後就利用那個map陣列依序輸出兩邊皆不為0的 ascii 轉 char 的值!!
這樣就會是

Ο(n)

的時間複雜度了!
厲害!!!!

如果有任何問題或是你有更好的寫法歡迎再下面留言討論喔!
我們下一題見啦!

程式碼:

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

string s1="", s2="";
vector‹char› same;

bool compare(char x, char y){
    return x+1 < y+1;
}

int main()
{
    while(getline(cin, s1)&& getline(cin, s2)){

        for(size_t x=0; x<s1.size(); x++){
            for(size_t y=0; y<s2.size(); y++){
                if(s1[x]==s2[y] && s1[x]!='_'){
                    same.push_back(s1[x]);
                    s1.replace(x, 1, "_");
                    s2.replace(y, 1, "_");
                }
            }
        }

        sort(same.begin(), same.end(), compare);

        for(vector<char>::iterator i=same.begin(); i!=same.end(); i++){
            cout << *i;
        }

        cout << endl;
        same.clear();
    }
    return 0;
}