Google面試問題指南：使用Python刪除重復出現的字符

junbaor 發布于2019-07-31 10:20 / 1167人閱讀

摘要：本文我們將討論一個可能出現在面試中的經典問題。問題給定一個字符串作為輸入，刪除任何重復出現的字符，并返回新字符串。為了解決這個問題，我們將使用一個名為的特定數據結構。空間復雜性最糟糕的情況是，我們得到一個包含所有唯一字符的字符串。

來源 | 愿碼(ChainDesk.CN)內容編輯

愿碼Slogan | 連接每個程序員的故事

網站 | http://chaindesk.cn

愿碼愿景 | 打造全學科IT系統免費課程，助力小白用戶、初級工程師0成本免費系統學習、低成本進階，幫助BAT一線資深工程師成長并利用自身優勢創造睡后收入。

官方公眾號 | 愿碼 | 愿碼服務號 | 區塊鏈部落

免費加入愿碼全思維工程師社群 | 任一公眾號回復“愿碼”兩個字獲取入群二維碼

本文閱讀時長：5min

當下，谷歌的面試時常被程序員提及。有時，面試能讓我們發揮最好的一面，從而獲得我們想要的職位。
本文我們將討論一個可能出現在Google面試中的經典問題。

愿碼提示：如果您是編碼老手，您可能已經知道如何解決這個問題！如果你經驗較淺，那么你一定會從本文中受益。

問題

給定一個字符串作為輸入，刪除任何重復出現的字符，并返回新字符串。

正如我們從上面的例子中看到的那樣，輸出是“abc”，因為我們刪除了第二個"a"，"b"和"c"。
首先，讓我們在Python 2.7中設置我們的功能。

def deleteReoccurringCharacters(string):

為了解決這個問題，我們將使用一個名為HashSet的特定數據結構。

您可以將集合視為與數組類似，但有兩個主要例外。

這是完全無序的

它不能包含重復項

因為它是無序的，我們還需要一個空字符串來存儲我們按順序添加到集合中的字符。這將是我們返回的字符串。
我們來設置一下

def deleteReoccurringCharacters(string):
    seenCharacters = set()
    outputString = ""

現在我們已經建立了我們需要的數據結構，讓我們再來談談我們的算法。
由于集合在內存中的工作方式，它的查找時間復雜度為0(1)。
這意味著我們可以用它來檢查我們是否已經訪問過一個角色！

我們的算法

遍歷初始字符串中的所有字符并執行以下操作：
第1步：檢查角色是否已經在我們的設置中
第2歩：如果它不在集合中，則將其添加到集合中并將其附加到字符串
讓我們看看代碼中的內容

for char in string:
    if char not in seenCharacters:
        seenCharacters.add(char)
        outputString += char

我們不必擔心“else”情況，因為我們不需要處理重復出現的字符本身。現在剩下要做的就是返回outputString。
這是完成的代碼的樣子：

def deleteReoccurringCharacters(string):
    seenCharacters = set()
    outputString = ""
    for char in string:
        if char not in seenCharacters:
            seenCharacters.add(char)
            outputString += char
    return outputString

如果這是一次面試，招聘人員會問你時間和空間的復雜性。我們來分析一下。

時間復雜性

迭代整個輸入字符串的時間復雜度為O(n)，因為字符串本身有n個字符。
但是，由于HashSet的查找時間為O(1)，所以不會影響時間復雜度。最后的時間復雜度為O(n)。

空間復雜性

最糟糕的情況是，我們得到一個包含所有唯一字符的字符串。例如，“abcdef”。
在這種情況下，我們將在字符串和集合中存儲所有n個元素。然而，我們也受到英語字母大小的限制。這是一個很好的機會來問我們的面試官什么類型的字符在字符串中是唯一的(大寫/小寫/數字/符號)。假設初始字符串將包含字母表中的小寫字母，因為字母表是有限的，所以集合和輸出字符串不能大于26個字符。留給我們最壞的情況空間復雜度為O(1)。

GPU云服務器云服務器刪除重復字符串 python字符串的使用詳解 cdn的出現問題云主機可能出現的問題

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/43649.html

Python面試問題指南：如何編碼鏈表

摘要：單身聯系與雙重聯系在鏈接列表方面，有兩種主要類型。代碼是如何工作的呢編碼鏈接列表可能是行問題或行問題。這將繼續，直到指向，在這種情況下循環停止。現在您已經掌握了處理鏈表面試問題所需的基本知識 showImg(https://segmentfault.com/img/remote/1460000019127546?w=1200&h=797); 什么是鏈表？鏈表是一種數據結構，由許多稱...

Cheriselalala 2019-07-31 10:23 評論0 收藏0
「真?全棧之路」Web前端開發的后端指南

前言在若干次前的一場面試，面試官看我做過python爬蟲/后端的工作，順帶問了我些后端相關的問題：你覺得什么是后端？送命題。當時腦瓦特了，答曰：邏輯處理和數據增刪改查。。。 showImg(https://user-gold-cdn.xitu.io/2019/4/24/16a4ed4fc8c18078); 當場被懟得體無完膚，羞愧難當。事后再反思這問題，結合資料總結了一下。發現自己學過的Re...

chuyao 2019-05-23 16:27 評論0 收藏0
Tools - 收藏集 - 掘金

摘要：個高級多線程面試題及回答后端掘金在任何面試當中多線程和并發方面的問題都是必不可少的一部分。默認為提供了年杭州面試經歷掘金想換個環境試試覺得做的不是自己想要的。源碼網站安居客項目架構演進掘金本文已授權微信公眾號獨家發布。 15 個高級 Java 多線程面試題及回答 - 后端 - 掘金在任何Java面試當中多線程和并發方面的問題都是必不可少的一部分。如果你想獲得任何股票投資銀行的前臺資訊職...

KitorinZero 2019-08-15 10:44 評論0 收藏0