Leetcode 1436 - Destination City

題目

Problem#

給你一個字串陣列 path 其中 path[i] = [city_a, city_b] 代表從 A 城市到 B 城市存在路徑，問你回傳最後到達的城市名稱（即沒有通往其他城市的路徑之城市）

測資限制#

• $1 \le n \le 100$
• 保證測資一定構成一條直線，只有一個終點城市，沒有環

想法#

觀察輸入可以發現，有通往其他城市的城市其名稱一定是成對出現的，所有目標城市 (B_i) 除了終點之外，都一定出現在來源城市（A_i）中。

AC Code#

Copy

class Solution {
public:
    unordered_set<string> s;
    string destCity(vector<vector<string>>& paths)
    {
        int e = paths.size();
        for(int i = 0; i < e; i++)
        {
            s.insert(paths[i][1]);
        }
        for(int i = 0; i < e; i++)
        {
            s.erase(paths[i][0]);
        }
 
        return *s.begin();
    }
};

view raw leetcode/1436.cpp delivered with ❤ by emgithub

• 時間複雜度: $\mathcal{O}(n)$
• 空間複雜度: $\mathcal{O}(n)$

心得#

一開始直覺還去建圖，但其實沒必要去建，因為題目只要找最後的目標城市而已

Copy

class Solution2 {
public:
    unordered_map<string, int> m;
    unordered_map<int, string> rm;
    int id = 0;
    int GetID(string& s)
    {
        if(!m.count(s))
        {
            rm[id] = s;
            m[s] = id;
            id++;
        }
        return m[s];
    }
 
    vector<int> G[1005];
    string destCity(vector<vector<string>>& paths)
    {
        int e = paths.size();
        for(int i = 0; i < e; i++)
        {
            int a = GetID(paths[i][0]);
            int b = GetID(paths[i][1]);
            G[a].push_back(b);
        }
 
        for(int i = 0; i < m.size(); i++)
        {
            if(G[i].size() == 0)
            {
                return rm[i];
            }
        }
        return "";
    }
};

view raw leetcode/1436.cpp delivered with ❤ by emgithub