為什么練習算法是關鍵?

別像我剛開始解決問題時那樣天真。盡管我認為時不時地破解幾個算法很有趣，但我從來沒有花太多時間去實踐，只為解決問題，其他什么都不顧，可能有時候馬馬虎虎解決了問題，但不明白為什么這樣。對于我自己，我一直在想，在一天結束時，整天求解算法有點太呆板了，它在實際的日常工作環境中并沒有實際的用途，從長遠來看，它也不會給我帶來多少好處。

“在求職過程中，了解如何求解算法會給你帶來競爭優勢”

但事實上，作為程序員，每天的工作中都會出現復雜的問題，大公司必須找到一個標準化的流程來收集求職者解決問題的洞察力和對細節技能的關注。這意味著，在求職過程中，了解如何求解算法將給你帶來競爭優勢，因為即使是不太出名的公司也傾向于采用類似的評估方法。

在我開始更一致地解決算法后不久，我發現有大量的資源可供實踐，學習解決這些問題的最有效策略，并為面試做好心理準備。(比如牛客網，力扣，領扣等)

除了練習面試問題外，這些網站通常按公司分組算法，嵌入活躍的博客，讓人們分享他們面試經驗的詳細總結，有時甚至提供模擬面試問題作為高級計劃的一部分。

如果你一開始真的很難解決問題，千萬不要失望，這是完全正常的。即使是非常有經驗的Python程序員也會發現，在沒有足夠培訓的情況下，許多算法很難在短時間內解決。

也不要失望，如果你的面試不像你預期的那樣，你剛剛開始解決算法。有些人每天都會準備好幾個月解決一些問題，并定期排練，然后才能敲定面試。

為了幫助您在培訓過程中，下面我選擇了10種算法(主要圍繞字符串操作和數組)，這些算法在電話編碼面試中一再出現。這些問題的程度主要是相對簡單的，但是很容易遇到的，所以請把它們作為一個好的起點。

字符串操作

數字顛倒

# 給定一個整數，返回顛倒之后的數字 
# 數字可能是負數也可能是整數 
 
def solution(x): 
    string = str(x) 
     
    if string[0] == '-': 
        return int('-'+string[:0:-1]) 
    else: 
        return int(string[::-1]) 
     
print(solution(-289)) 
print(solution(123)) 
 
Output: 
-132 
543 

平均單詞長度

# 對于給定的句子，返回平均單詞長度。 
# 請記住首先刪除標點符號。 
 
sentence1 = "Hi all, my name is Tom...I am originally from Australia." 
sentence2 = "I need to work very hard to learn more about algorithms in Python!" 
 
def solution(sentence): 
    for p in "!?',;.": 
        sentence = sentence.replace(p, '') 
    words = sentence.split() 
    return round(sum(len(word) for word in words)/len(words),2) 
     
print(solution(sentence1)) 
print(solution(sentence2)) 
 
Output: 
4.2 
4.08 

要求您使用字符串應用一些簡單計算的算法非常普遍，因此熟悉諸如.replace()和.split()之類的方法非常重要，在這種情況下，這些方法有助于我刪除不需要的字符并創建單詞列表，其長度很容易測量和求和。

添加字符串

# 給定兩個表示為字符串的非負整數num1和num2，返回num1和num2之和。 
# 您不得使用任何內置的BigInteger庫或將輸入直接轉換為整數。 
 
 
 
num1 = '364' 
num2 = '1836' 
 
# Approach 1:  
def solution(num1,num2): 
    eval(num1) + eval(num2) 
    return str(eval(num1) + eval(num2)) 
             
print(solution(num1,num2)) 
 
#Approach2  
# 給出一個長度為1的字符串，當參數是unicode對象時，ord（）函數返回一個表示字符 
# 的Unicode代碼點的整數，或者當參數是8位字符串時，返回字節的值。 
 
def solution(num1, num2): 
    n1, n2 = 0, 0 
    m1, m2 = 10**(len(num1)-1), 10**(len(num2)-1) 
 
    for i in num1: 
        n1 += (ord(i) - ord("0")) * m1  
        m1 = m1//10         
 
    for i in num2: 
        n2 += (ord(i) - ord("0")) * m2 
        m2 = m2//10 
 
    return str(n1 + n2) 
print(solution(num1, num2)) 
 
Output: 
2200 
2200 

我發現兩種方法都同樣出色：第一種方法簡潔明了，使用直覺式eval()方法動態評估基于字符串的輸入，第二種方法巧妙地使用ord()函數來重新構建兩種方法字符串作為實際數字通過其字符的Unicode代碼點。如果確實要在兩者之間進行選擇，則我可能會選擇第二種方法，因為它一開始看起來比較復雜，但在解決需要更高級的字符串操作算法時通常很方便。

找到第一個唯一的字符

#給定一個字符串，找到其中的第一個非重復字符并返回其索引。 
#如果不存在，則返回-1。＃注意：所有輸入字符串均已小寫。 
#Approach 1 
def solution(s): 
    frequency = {} 
    for i in s: 
        if i not in frequency: 
            frequency[i] = 1 
        else: 
            frequency[i] +=1 
    for i in range(len(s)): 
        if frequency[s[i]] == 1: 
            return i 
    return -1 
 
print(solution('alphabet')) 
print(solution('barbados')) 
print(solution('crunchy')) 
 
print('---') 
 
#Approach 2 
import collections 
 
def solution(s): 
    # build hash map : character and how often it appears 
    count = collections.Counter(s) # <-- gives back a dictionary with words occurrence count  
                                         #Counter({'l': 1, 'e': 3, 't': 1, 'c': 1, 'o': 1, 'd': 1}) 
    # find the index 
    for idx, ch in enumerate(s): 
        if count[ch] == 1: 
            return idx      
    return -1 
 
print(solution('alphabet')) 
print(solution('barbados')) 
print(solution('crunchy')) 
 
Output: 
1 
2 
1 
--- 
1 
2 
1 

同樣在這種情況下，提供了兩種可能的解決方案，我想如果您對算法還不熟悉，第一種方法看起來會更加熟悉，因為它是從空字典開始的簡單計數器。

但是，從長遠來看，理解第二種方法將對您有更多幫助，這是因為在此算法中，我僅使用collection.Counter而不是自己構建chars計數器，而是用enumerate代替了range(len(s)) ，可以幫助您更優雅地識別索引的功能。

有效回文

# 給定一個非空字符串s，您最多可以刪除一個字符。判斷是否可以使它回文。 
# 字符串僅包含小寫字母az。 
s = 'sadkas' 
def solution(s): 
    for i in range(len(s)): 
        t = s[:i] + s[i+1:] 
        if t == t[::-1]: return True 
 
    return s == s[::-1] 
   
solution(s) 
 
Output: 
True 

“有效回文”問題是一個真正的經典，您可能會在許多不同的情況下反復發現它。在這種情況下，任務是通過刪除最多一個字符來檢查天氣，該字符與其相反的字符匹配。當s ='sadkas'時，該函數通過排除'k'來返回True，我們得到的單詞“ sadas”是回文。

數組

單調數組

# 給定一個整數數組，請確定該數組是否為單調。 
A = [6, 5, 4, 4]  
B = [1,1,1,3,3,4,3,2,4,2] 
C = [1,1,2,3,7] 
 
def solution(nums):  
    return (all(nums[i] <= nums[i + 1] for i in range(len(nums) - 1)) or  
            all(nums[i] >= nums[i + 1] for i in range(len(nums) - 1)))  
   
print(solution(A))  
print(solution(B))  
print(solution(C))  
 
Output: 
True 
False 
True 

這是另一個非常常見的問題，并且上面提供的解決方案非常優雅，因為它可以單行編寫。當且僅當數組是單調遞增或單調遞減且為評估數組時，該數組才是單調的。上述算法利用all()函數的作用，如果iterable中的所有項目均為True，則返回True，否則返回False。如果可迭代對象為空，則all()函數還返回True。

移動零

# 給出一個數組num，編寫一個函數以將所有零移動到其末尾，同時保持 
# non-zero元素的相對順序。 
array1 = [0,1,0,3,12] 
array2 = [1,7,0,0,8,0,10,12,0,4] 
 
def solution(nums): 
    for i in nums: 
        if 0 in nums: 
            nums.remove(0) 
            nums.append(0) 
    return nums 
 
solution(array1) 
solution(array2) 
 
Output: 
[1, 3, 12, 0, 0] 
[1, 7, 8, 10, 12, 4, 0, 0, 0, 0] 

當您使用數組時，.remove()和.append()方法是寶貴的盟友。在此問題中，我使用它們首先刪除屬于原始數組的每個零，然后將其附加到同一數組的末尾。

填空白

# 給定一個包含None值的數組，用該數組中的最新non None值填充None值 
array1 = [1,None,2,3,None,None,5,None] 
 
def solution(array): 
    valid = 0             
    res = []                  
    for i in nums:  
        if i is not None:     
            res.append(i) 
            valid = i 
        else: 
            res.append(valid) 
    return res 
 
solution(array1)  
 
Output: 
[1, 1, 2, 3, 3, 3, 5, 5] 

兩次解決方案都必須包含邊緣案例(為簡單起見，在此省略)。從表面上看，這是一種易于構建的算法，但是您需要牢記要使用for循環和if語句要實現的目標，并應習慣使用None值。

匹配詞和不匹配詞

# 給出兩個句子，返回一個數組，該數組的單詞出現在一個句子中，而不是 
# 另一個單詞；返回一個數組，這些單詞具有共同的單詞。 
sentence1 = 'We are really pleased to meet you in our city' 
sentence2 = 'The city was hit by a really heavy storm' 
 
def solution(sentence1, sentence2): 
    set1 = set(sentence1.split()) 
    set2 = set(sentence2.split()) 
     
    return sorted(list(set1^set2)), sorted(list(set1&set2))  
 
print(solution(sentence1, sentence2)) 
 
Output: 
(['The','We','a','are','by','heavy','hit','in','meet','our', 
    'pleased','storm','to','was','you'], 
 ['city', 'really']) 

這個問題很直觀，但是算法利用了一些非常常見的集合操作，例如set()，intersection()或&和symmetric_difference()或^，它們對于使您的解決方案更加優雅非常有用。

質數數組

# 給定k個小于n的數字，返回其中的素數集 
# 注意：任務是編寫一個程序來打印一個間隔中的所有素數。 
# 定義：質數是大于1的自然數，除1及其本身外，沒有除數。 
 
n = 35 
def solution(n): 
    prime_nums = [] 
    for num in range(n): 
        if num > 1: # all prime numbers are greater than 1 
            for i in range(2, num): 
                if (num % i) == 0: # if the modulus == 0 is means that the number can be divided by a number preceding it 
                    break 
            else: 
                prime_nums.append(num) 
    return prime_nums 
solution(n) 
 
Output: 
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31] 

我想用另一個經典問題來結束本篇文章。如果您既熟悉質數定義又知道模數運算，那么可以很容易地找到一個解決方案，即通過谷值范圍(n)(modulus operation)。

結論

在本文中，我分享了10種Python算法的解決方案，這些解決方案是面試時經常遇到的問題。如果您正在準備與知名技術公司的面試，那么本文是您熟悉常見算法模式然后轉向更復雜問題的一個很好的起點。還要注意，本文中介紹的練習(及其解決方案)是對力扣和領扣上存在的問題的部分重新解釋。我遠不是該領域的專家，因此我提供的解決方案僅是指示性的解決方案。