資訊專欄INFORMATION COLUMN
摘要：本文我們將討論一個(gè)可能出現(xiàn)在面試中的經(jīng)典問(wèn)題。問(wèn)題給定一個(gè)字符串作為輸入，刪除任何重復(fù)出現(xiàn)的字符，并返回新字符串。為了解決這個(gè)問(wèn)題，我們將使用一個(gè)名為的特定數(shù)據(jù)結(jié)構(gòu)?？臻g復(fù)雜性最糟糕的情況是，我們得到一個(gè)包含所有唯一字符的字符串。
來(lái)源 | 愿碼(ChainDesk.CN)內(nèi)容編輯
愿碼Slogan | 連接每個(gè)程序員的故事
網(wǎng)站 | http://chaindesk.cn
愿碼愿景 | 打造全學(xué)科IT系統(tǒng)免費(fèi)課程，助力小白用戶、初級(jí)工程師0成本免費(fèi)系統(tǒng)學(xué)習(xí)、低成本進(jìn)階，幫助BAT一線資深工程師成長(zhǎng)并利用自身優(yōu)勢(shì)創(chuàng)造睡后收入。
官方公眾號(hào) | 愿碼 | 愿碼服務(wù)號(hào) | 區(qū)塊鏈部落
免費(fèi)加入愿碼全思維工程師社群 | 任一公眾號(hào)回復(fù)“愿碼”兩個(gè)字獲取入群二維碼
本文閱讀時(shí)長(zhǎng)：5min
當(dāng)下，谷歌的面試時(shí)常被程序員提及。有時(shí)，面試能讓我們發(fā)揮最好的一面，從而獲得我們想要的職位。
本文我們將討論一個(gè)可能出現(xiàn)在Google面試中的經(jīng)典問(wèn)題。
愿碼提示：如果您是編碼老手，您可能已經(jīng)知道如何解決這個(gè)問(wèn)題！如果你經(jīng)驗(yàn)較淺，那么你一定會(huì)從本文中受益。
問(wèn)題給定一個(gè)字符串作為輸入，刪除任何重復(fù)出現(xiàn)的字符，并返回新字符串。
正如我們從上面的例子中看到的那樣，輸出是“abc”，因?yàn)槲覀儎h除了第二個(gè)"a"，"b"和"c"。
首先，讓我們?cè)赑ython 2.7中設(shè)置我們的功能。
def deleteReoccurringCharacters(string):
為了解決這個(gè)問(wèn)題，我們將使用一個(gè)名為HashSet的特定數(shù)據(jù)結(jié)構(gòu)。
您可以將集合視為與數(shù)組類似，但有兩個(gè)主要例外。
這是完全無(wú)序的
它不能包含重復(fù)項(xiàng)
因?yàn)樗菬o(wú)序的，我們還需要一個(gè)空字符串來(lái)存儲(chǔ)我們按順序添加到集合中的字符。這將是我們返回的字符串。
我們來(lái)設(shè)置一下
def deleteReoccurringCharacters(string):
seenCharacters = set()
outputString = ""
現(xiàn)在我們已經(jīng)建立了我們需要的數(shù)據(jù)結(jié)構(gòu)，讓我們?cè)賮?lái)談?wù)勎覀兊乃惴ā?br>由于集合在內(nèi)存中的工作方式，它的查找時(shí)間復(fù)雜度為0(1)。
這意味著我們可以用它來(lái)檢查我們是否已經(jīng)訪問(wèn)過(guò)一個(gè)角色！
遍歷初始字符串中的所有字符并執(zhí)行以下操作：
第1步：檢查角色是否已經(jīng)在我們的設(shè)置中
第2歩：如果它不在集合中，則將其添加到集合中并將其附加到字符串
讓我們看看代碼中的內(nèi)容
for char in string:
if char not in seenCharacters:
seenCharacters.add(char)
outputString += char
我們不必?fù)?dān)心“else”情況，因?yàn)槲覀儾恍枰幚碇貜?fù)出現(xiàn)的字符本身。現(xiàn)在剩下要做的就是返回outputString。
這是完成的代碼的樣子：
def deleteReoccurringCharacters(string):
seenCharacters = set()
outputString = ""
for char in string:
if char not in seenCharacters:
seenCharacters.add(char)
outputString += char
return outputString
如果這是一次面試，招聘人員會(huì)問(wèn)你時(shí)間和空間的復(fù)雜性。我們來(lái)分析一下。
時(shí)間復(fù)雜性迭代整個(gè)輸入字符串的時(shí)間復(fù)雜度為O(n)，因?yàn)樽址旧碛衝個(gè)字符。
但是，由于HashSet的查找時(shí)間為O(1)，所以不會(huì)影響時(shí)間復(fù)雜度。最后的時(shí)間復(fù)雜度為O(n)。
最糟糕的情況是，我們得到一個(gè)包含所有唯一字符的字符串。例如，“abcdef”。
在這種情況下，我們將在字符串和集合中存儲(chǔ)所有n個(gè)元素。然而，我們也受到英語(yǔ)字母大小的限制。這是一個(gè)很好的機(jī)會(huì)來(lái)問(wèn)我們的面試官什么類型的字符在字符串中是唯一的(大寫/小寫/數(shù)字/符號(hào))。假設(shè)初始字符串將包含字母表中的小寫字母，因?yàn)樽帜副硎怯邢薜?，所以集合和輸出字符串不能大?6個(gè)字符。留給我們最壞的情況空間復(fù)雜度為O(1)。
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/43649.html
摘要：?jiǎn)紊砺?lián)系與雙重聯(lián)系在鏈接列表方面，有兩種主要類型。代碼是如何工作的呢編碼鏈接列表可能是行問(wèn)題或行問(wèn)題。這將繼續(xù)，直到指向，在這種情況下循環(huán)停止?，F(xiàn)在您已經(jīng)掌握了處理鏈表面試問(wèn)題所需的基本知識(shí) showImg(https://segmentfault.com/img/remote/1460000019127546?w=1200&h=797); 什么是鏈表？ 鏈表是一種數(shù)據(jù)結(jié)構(gòu)，由許多稱...
前言 在若干次前的一場(chǎng)面試，面試官看我做過(guò)python爬蟲/后端 的工作，順帶問(wèn)了我些后端相關(guān)的問(wèn)題：你覺(jué)得什么是后端？ 送命題。當(dāng)時(shí)腦瓦特了，答曰：邏輯處理和數(shù)據(jù)增刪改查。。。 showImg(https://user-gold-cdn.xitu.io/2019/4/24/16a4ed4fc8c18078); 當(dāng)場(chǎng)被懟得體無(wú)完膚，羞愧難當(dāng)。事后再反思這問(wèn)題，結(jié)合資料總結(jié)了一下。發(fā)現(xiàn)自己學(xué)過(guò)的Re...
摘要：個(gè)高級(jí)多線程面試題及回答后端掘金在任何面試當(dāng)中多線程和并發(fā)方面的問(wèn)題都是必不可少的一部分。默認(rèn)為提供了年杭州面試經(jīng)歷掘金想換個(gè)環(huán)境試試覺(jué)得做的不是自己想要的。源碼網(wǎng)站安居客項(xiàng)目架構(gòu)演進(jìn)掘金本文已授權(quán)微信公眾號(hào)獨(dú)家發(fā)布。 15 個(gè)高級(jí) Java 多線程面試題及回答 - 后端 - 掘金在任何Java面試當(dāng)中多線程和并發(fā)方面的問(wèn)題都是必不可少的一部分。如果你想獲得任何股票投資銀行的前臺(tái)資訊職...
閱讀 1649·2023-04-25 18:19
閱讀 2093·2021-10-26 09:48
閱讀 1100·2021-10-09 09:44
閱讀 1748·2021-09-09 11:35
閱讀 3041·2019-08-30 15:54
閱讀 2039·2019-08-30 11:26
閱讀 2299·2019-08-29 17:06
閱讀 895·2019-08-29 16:38
