Python编程面试前要解决的10个算法
scuyxi 2020-08-16
为什么练习算法是关键?
别像我刚开始解决问题时那样天真。尽管我认为时不时地破解几个算法很有趣，但我从来没有花太多时间去实践，只为解决问题，其他什么都不顾，可能有时候马马虎虎解决了问题，但不明白为什么这样。对于我自己，我一直在想，在一天结束时，整天求解算法有点太呆板了，它在实际的日常工作环境中并没有实际的用途，从长远来看，它也不会给我带来多少好处。
“在求职过程中，了解如何求解算法会给你带来竞争优势”
但事实上，作为程序员，每天的工作中都会出现复杂的问题，大公司必须找到一个标准化的流程来收集求职者解决问题的洞察力和对细节技能的关注。这意味着，在求职过程中，了解如何求解算法将给你带来竞争优势，因为即使是不太出名的公司也倾向于采用类似的评估方法。
在我开始更一致地解决算法后不久，我发现有大量的资源可供实践，学习解决这些问题的最有效策略，并为面试做好心理准备。(比如牛客网，力扣，领扣等)
除了练习面试问题外，这些网站通常按公司分组算法，嵌入活跃的博客，让人们分享他们面试经验的详细总结，有时甚至提供模拟面试问题作为高级计划的一部分。
如果你一开始真的很难解决问题，千万不要失望，这是完全正常的。即使是非常有经验的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)。
