為什么練習(xí)算法是關(guān)鍵?

別像我剛開始解決問題時(shí)那樣天真。盡管我認(rèn)為時(shí)不時(shí)地破解幾個(gè)算法很有趣，但我從來沒有花太多時(shí)間去實(shí)踐，只為解決問題，其他什么都不顧，可能有時(shí)候馬馬虎虎解決了問題，但不明白為什么這樣。對(duì)于我自己，我一直在想，在一天結(jié)束時(shí)，整天求解算法有點(diǎn)太呆板了，它在實(shí)際的日常工作環(huán)境中并沒有實(shí)際的用途，從長(zhǎng)遠(yuǎn)來看，它也不會(huì)給我?guī)矶嗌俸锰帯?/p>

“在求職過程中，了解如何求解算法會(huì)給你帶來競(jìng)爭(zhēng)優(yōu)勢(shì)”

但事實(shí)上，作為程序員，每天的工作中都會(huì)出現(xiàn)復(fù)雜的問題，大公司必須找到一個(gè)標(biāo)準(zhǔn)化的流程來收集求職者解決問題的洞察力和對(duì)細(xì)節(jié)技能的關(guān)注。這意味著，在求職過程中，了解如何求解算法將給你帶來競(jìng)爭(zhēng)優(yōu)勢(shì)，因?yàn)榧词故遣惶雒墓疽矁A向于采用類似的評(píng)估方法。

在我開始更一致地解決算法后不久，我發(fā)現(xiàn)有大量的資源可供實(shí)踐，學(xué)習(xí)解決這些問題的最有效策略，并為面試做好心理準(zhǔn)備。(比如?？途W(wǎng)，力扣，領(lǐng)扣等)

除了練習(xí)面試問題外，這些網(wǎng)站通常按公司分組算法，嵌入活躍的博客，讓人們分享他們面試經(jīng)驗(yàn)的詳細(xì)總結(jié)，有時(shí)甚至提供模擬面試問題作為高級(jí)計(jì)劃的一部分。

如果你一開始真的很難解決問題，千萬(wàn)不要失望，這是完全正常的。即使是非常有經(jīng)驗(yàn)的Python程序員也會(huì)發(fā)現(xiàn)，在沒有足夠培訓(xùn)的情況下，許多算法很難在短時(shí)間內(nèi)解決。

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

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

字符串操作

數(shù)字顛倒

# 給定一個(gè)整數(shù)，返回顛倒之后的數(shù)字 
# 數(shù)字可能是負(fù)數(shù)也可能是整數(shù) 
 
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 

平均單詞長(zhǎng)度

# 對(duì)于給定的句子，返回平均單詞長(zhǎng)度。 
# 請(qǐng)記住首先刪除標(biāo)點(diǎn)符號(hào)。 
 
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 

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

添加字符串

# 給定兩個(gè)表示為字符串的非負(fù)整數(shù)num1和num2，返回num1和num2之和。 
# 您不得使用任何內(nèi)置的BigInteger庫(kù)或?qū)⑤斎胫苯愚D(zhuǎn)換為整數(shù)。 
 
 
 
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  
# 給出一個(gè)長(zhǎng)度為1的字符串，當(dāng)參數(shù)是unicode對(duì)象時(shí)，ord（）函數(shù)返回一個(gè)表示字符 
# 的Unicode代碼點(diǎn)的整數(shù)，或者當(dāng)參數(shù)是8位字符串時(shí)，返回字節(jié)的值。 
 
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 

我發(fā)現(xiàn)兩種方法都同樣出色：第一種方法簡(jiǎn)潔明了，使用直覺式eval()方法動(dòng)態(tài)評(píng)估基于字符串的輸入，第二種方法巧妙地使用ord()函數(shù)來重新構(gòu)建兩種方法字符串作為實(shí)際數(shù)字通過其字符的Unicode代碼點(diǎn)。如果確實(shí)要在兩者之間進(jìn)行選擇，則我可能會(huì)選擇第二種方法，因?yàn)樗婚_始看起來比較復(fù)雜，但在解決需要更高級(jí)的字符串操作算法時(shí)通常很方便。

找到第一個(gè)唯一的字符

#給定一個(gè)字符串，找到其中的第一個(gè)非重復(fù)字符并返回其索引。 
#如果不存在，則返回-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 

同樣在這種情況下，提供了兩種可能的解決方案，我想如果您對(duì)算法還不熟悉，第一種方法看起來會(huì)更加熟悉，因?yàn)樗菑目兆值溟_始的簡(jiǎn)單計(jì)數(shù)器。

但是，從長(zhǎng)遠(yuǎn)來看，理解第二種方法將對(duì)您有更多幫助，這是因?yàn)樵诖怂惴ㄖ校覂H使用collection.Counter而不是自己構(gòu)建chars計(jì)數(shù)器，而是用enumerate代替了range(len(s)) ，可以幫助您更優(yōu)雅地識(shí)別索引的功能。

有效回文

# 給定一個(gè)非空字符串s，您最多可以刪除一個(gè)字符。判斷是否可以使它回文。 
# 字符串僅包含小寫字母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 

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

數(shù)組

單調(diào)數(shù)組

# 給定一個(gè)整數(shù)數(shù)組，請(qǐng)確定該數(shù)組是否為單調(diào)。 
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 

這是另一個(gè)非常常見的問題，并且上面提供的解決方案非常優(yōu)雅，因?yàn)樗梢詥涡芯帉憽．?dāng)且僅當(dāng)數(shù)組是單調(diào)遞增或單調(diào)遞減且為評(píng)估數(shù)組時(shí)，該數(shù)組才是單調(diào)的。上述算法利用all()函數(shù)的作用，如果iterable中的所有項(xiàng)目均為True，則返回True，否則返回False。如果可迭代對(duì)象為空，則all()函數(shù)還返回True。

移動(dòng)零

# 給出一個(gè)數(shù)組num，編寫一個(gè)函數(shù)以將所有零移動(dòng)到其末尾，同時(shí)保持 
# non-zero元素的相對(duì)順序。 
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] 

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

填空白

# 給定一個(gè)包含None值的數(shù)組，用該數(shù)組中的最新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] 

兩次解決方案都必須包含邊緣案例(為簡(jiǎn)單起見，在此省略)。從表面上看，這是一種易于構(gòu)建的算法，但是您需要牢記要使用for循環(huán)和if語(yǔ)句要實(shí)現(xiàn)的目標(biāo)，并應(yīng)習(xí)慣使用None值。

匹配詞和不匹配詞

# 給出兩個(gè)句子，返回一個(gè)數(shù)組，該數(shù)組的單詞出現(xiàn)在一個(gè)句子中，而不是 
# 另一個(gè)單詞；返回一個(gè)數(shù)組，這些單詞具有共同的單詞。 
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']) 

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

質(zhì)數(shù)數(shù)組

# 給定k個(gè)小于n的數(shù)字，返回其中的素?cái)?shù)集 
# 注意：任務(wù)是編寫一個(gè)程序來打印一個(gè)間隔中的所有素?cái)?shù)。 
# 定義：質(zhì)數(shù)是大于1的自然數(shù)，除1及其本身外，沒有除數(shù)。 
 
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] 

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

結(jié)論

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