python 刪除重復字符

by Anthony Sistilli

安東尼·西斯蒂里(Anthony Sistilli)

Google面試問題指南：使用Python刪除重復出現的字符 (Google Interview Question Guide: Delete Reoccurring Characters with Python)

Nowadays, Google interviews are all the rage. But sometimes, interviews can get the best of us. Especially if it’s for a position we really want.

如今，Google面試風靡一時。 但是有時候，采訪可以使我們受益匪淺。 尤其是在我們真正想要的職位上。

I’ve had the pleasure of interviewing at multiple top companies as a student, and landing a job in Silicon Valley as a Software Engineer.

我很高興能在學生中接受多家頂級公司的采訪，并以軟件工程師的身份在硅谷找到一份工作。

My goal is to help you get that dream job you’ve always wanted!

我的目標是幫助您獲得夢always以求的工作！

We’re going to go over a classic question that could show up on your next Google Interview.

我們將討論一個經典問題，該問題可能會在您的下一次Google采訪中出現。

Warning: if you’re a coding veteran, you probably already know how to solve this question!

警告：如果您是編碼方面的資深人士，您可能已經知道如何解決此問題！

If you’re trying to get an Internship or a Full-Time job next year, then you’ll definitely benefit from this article. ???

如果您想在明年獲得實習或全職工作，那么您一定會從本文中受益。 ???

問題：給定字符串作為輸入，刪除所有重復出現的字符，然后返回新字符串。 (QUESTION: Given a string as your input, delete any reoccurring character, and return the new string.)

If you would prefer a video to explain the question, I made one here.

如果您希望使用視頻來解釋這個問題， 我在這里做了一個 。

As we can see from the example above, the output is “abc” because we delete the second ‘a’, ‘b’, and ‘c’.

從上面的示例可以看到，輸出為“ abc”，因為我們刪除了第二個“ a”，“ b”和“ c”。

First things first, let’s set up our function in Python 2.7.

首先，讓我們在Python 2.7中設置函數。

def deleteReoccurringCharacters(string):

To tackle this question, we’re going to use a specific data structure called a HashSet.

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

You can think of a set as being similar to an array, with two main exceptions.

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

1. It’s completely unordered

   完全沒有秩序

2. It can’t contain duplicates

   它不能包含重復項

Because it’s unordered, we’ll also need an empty string to store the characters we’ve added to the set in order. This will be the string we return.

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

Let’s set both of those things up.

讓我們同時設置這兩件事。

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

Now that we’ve set up the data structures we need, let’s talk about our algorithm.

現在我們已經建立了所需的數據結構，下面我們來談談我們的算法。

Because of the way a set works in memory, it has a lookup time complexity of 0(1).

由于集合在內存中的工作方式，其查找時間復雜度為0(1)。

This means we can use it to check whether or not we’ve already visited a character!

這意味著我們可以使用它來檢查我們是否已經訪問過角色！

我們的算法 (Our algorithm)

Loop through all the characters in the initial string and do the following:

循環遍歷初始字符串中的所有字符，然后執行以下操作：

Step 1: Check if the character is in our set already

步驟1：檢查角色是否已經在我們的集合中

Step 2: If it’s not in the set, add it to the set and append it to the string

步驟2：如果不在集合中，請將其添加到集合中并將其附加到字符串中

Let’s see what that would look like in code ???

讓我們看一下代碼中的樣子嗎？

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

We don’t have to worry about an “else” case, because we don’t do anything with the reoccurring character itself.

我們不必擔心“其他”情況，因為我們無需對重復出現的角色本身做任何事情。

Now all that’s left to do is return the outputString.

現在剩下要做的就是返回outputString了。

Here’s what the finished code looks like:

這是完成的代碼，如下所示：

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

And there you have it!

在那里，您擁有了！

Now if this was an interview, your recruiter would ask you about the time and space complexity.

現在，如果這是一次面試，您的招聘人員會問您時間和空間的復雜性。

Let’s do a little analysis.

讓我們做一點分析。

時間復雜度 (Time Complexity)

Iterating through the entire input string has a time complexity of O(n), since there are n characters in the string itself.

遍歷整個輸入字符串的時間復雜度為O(n)，因為字符串本身包含n個字符。

For each of those characters, we have to check whether or not we’ve seen the… However, since a HashSet has a lookup time of O(1), our time complexity isn’t impacted.

對于每個這些字符，我們都必須檢查是否已看到……。但是，由于HashSet的查找時間為O(1)，因此，時間復雜度不會受到影響。

Leaving us with a final time complexity of O(n).

使我們的最終時間復雜度為O(n)。

空間復雜度 (Space Complexity)

Worst case scenario, we get a string with all unique characters. For example, “abcdef”.

最壞的情況是，我們得到一個包含所有唯一字符的字符串。 例如，“ abcdef”。

In that case, we would store all n elements in our string and our set.

在這種情況下，我們將所有n個元素存儲在字符串和集合中。

However, we’re also limited to size of the english alphabet.

但是，我們還限于英文字母的大小。

This is a good chance to ask our interviewer what type of characters count as unique in the string (uppercase / lowercase / numbers / symbols).

這是一個很好的機會，可以詢問我們的面試官字符串中哪種字符算作唯一字符(大寫/小寫/數字/符號)。

Assuming that the initial string will contain lowercase letters from the alphabet, since the alphabet is finite, our set and output string can never be bigger than 26 characters.

假設初始字符串將包含字母表中的小寫字母，由于字母表是有限的，因此我們的set和輸出字符串不得大于26個字符。

Leaving us with a worst case scenario space complexity of O(1).

最糟糕的情況是，我們的空間復雜度為O(1)。

您現在知道了如何解決Google面試問題！ (You now know how to solve a Google interview question!)

This question is likely to come up in the early stages of the interview due to it’s straightforwardness… Like the online test, or the first phone call.

這個問題很容易在面試的初期出現，因為它很簡單……就像在線考試或第一次打來的電話一樣。

If you’re a visual learner like I am, check out this video I made explaining the solution further. I create a new tutorial video everyday revolving around starting your career in software.

如果您像我一樣是視覺學習者， 請觀看我進一步解釋該解決方案的視頻。 我每天都會制作一個新的教學視頻，圍繞著您在軟件領域的職業發展展開。

I’ve also posted the finished code on Github here.

我也貼在完成的代碼在Github 這里 。

Thanks for watching, and good luck!

感謝收看，祝您好運！

.a #33

.a＃33

翻譯自: https://www.freecodecamp.org/news/solving-a-google-interview-question-python-2-code-included-eddefcaeffb2/

python 刪除重復字符