leetcode賬戶合并的方法是什么

本篇內(nèi)容介紹了“l(fā)eetcode賬戶合并的方法是什么”的有關(guān)知識(shí)，在實(shí)際案例的操作過(guò)程中，不少人都會(huì)遇到這樣的困境，接下來(lái)就讓小編帶領(lǐng)大家學(xué)習(xí)一下如何處理這些情況吧！希望大家仔細(xì)閱讀，能夠?qū)W有所成！

一、題目?jī)?nèi)容

給定一個(gè)列表 accounts，每個(gè)元素 accounts[i] 是一個(gè)字符串列表，其中第一個(gè)元素 accounts[i][0] 是 名稱 (name)，其余元素是 emails 表示該賬戶的郵箱地址。

現(xiàn)在，我們想合并這些賬戶。如果兩個(gè)賬戶都有一些共同的郵箱地址，則兩個(gè)賬戶必定屬于同一個(gè)人。請(qǐng)注意，即使兩個(gè)賬戶具有相同的名稱，它們也可能屬于不同的人，因?yàn)槿藗兛赡芫哂邢嗤拿Q。一個(gè)人最初可以擁有任意數(shù)量的賬戶，但其所有賬戶都具有相同的名稱。

合并賬戶后，按以下格式返回賬戶：每個(gè)賬戶的第一個(gè)元素是名稱，其余元素是按順序排列的郵箱地址。賬戶本身可以以任意順序返回。

示例 1：

輸入：
accounts = [["John", "johnsmith@mail.com", "john00@mail.com"], ["John", "johnnybravo@mail.com"], ["John", "johnsmith@mail.com", "john_newyork@mail.com"], ["Mary", "mary@mail.com"]]
輸出：
[["John", 'john00@mail.com', 'john_newyork@mail.com', 'johnsmith@mail.com'],  ["John", "johnnybravo@mail.com"], ["Mary", "mary@mail.com"]]
解釋：
第一個(gè)和第三個(gè) John 是同一個(gè)人，因?yàn)樗麄冇泄餐泥]箱地址 "johnsmith@mail.com"。 
第二個(gè) John 和 Mary 是不同的人，因?yàn)樗麄兊泥]箱地址沒(méi)有被其他帳戶使用。
可以以任何順序返回這些列表，例如答案 [['Mary'，'mary@mail.com']，['John'，'johnnybravo@mail.com']，
['John'，'john00@mail.com'，'john_newyork@mail.com'，'johnsmith@mail.com']] 也是正確的。

提示：

accounts的長(zhǎng)度將在[1，1000]的范圍內(nèi)。
accounts[i]的長(zhǎng)度將在[1，10]的范圍內(nèi)。
accounts[i][j]的長(zhǎng)度將在[1，30]的范圍內(nèi)。

二、解題思路

首先，建立一個(gè)圖graph和字典email_dict，email_dict里存儲(chǔ)郵箱對(duì)應(yīng)的名字name作為結(jié)果集res每個(gè)列表的第一個(gè)元素，graph里存儲(chǔ)郵箱間的兩兩對(duì)應(yīng)關(guān)系。

其次，DFS，對(duì)graph的郵箱兩兩判斷，存在則添加至tmp，visited集合加入對(duì)應(yīng)的郵箱，之后則不在查看該郵箱。

最后對(duì)加入的郵箱排序，放在name后面即可。

三、代碼

from collections import defaultdict


class Solution:
    def accountsMerge(self, accounts: list) -> list:
        graph = defaultdict(set)
        email_dict = defaultdict()
        for account in accounts:
            name = account[0]
            emails = account[1:]
            first_email = emails[0]
            for email in emails:
                email_dict[email] = name
                graph[first_email].add(email)
                graph[email].add(first_email)
        visited = set()
        res = []

        def dfs(email, tmp):
            tmp.append(email)
            for email2 in graph[email]:
                if email2 not in visited:
                    visited.add(email2)
                    tmp = dfs(email2, tmp)
            return tmp

        for email in graph:
            if email not in visited:
                visited.add(email)
                tmp = dfs(email, [])
                res.append([email_dict[email]] + sorted(tmp))

        return res


if __name__ == '__main__':
    s = Solution()
    accounts = [["John", "johnsmith@mail.com", "john00@mail.com"],
                ["John", "johnnybravo@mail.com"],
                ["John", "johnsmith@mail.com", "john_newyork@mail.com"],
                ["Mary", "mary@mail.com"]]
    ans = s.accountsMerge(accounts)
    print(ans)

“l(fā)eetcode賬戶合并的方法是什么”的內(nèi)容就介紹到這里了，感謝大家的閱讀。如果想了解更多行業(yè)相關(guān)的知識(shí)可以關(guān)注億速云網(wǎng)站，小編將為大家輸出更多高質(zhì)量的實(shí)用文章！