江苏龙网

  1. 主页 > 生活百科 > >

编程面试前需要解决的10个算法( 二 )

算法


Output:
2200
2200
我发现这两种方法同样有效: 第一种方法简洁，直观地使用 eval ()方法动态评估基于字符串的输入; 第二种方法聪明地使用 ord ()函数通过字符的 Unicode 代码点将两个字符串重新构建为实际数字 。如果我真的必须在两者之间做出选择，我可能会选择第二种方法，因为它起初看起来更复杂，但在解决需要更高级的字符串处理和计算的“中等”和“硬”算法时，这种方法通常很方便 。
4. 第一个独特的角色# Given a string, find the first non-repeating character in it and return its index. # If it doesn't exist, return -1. # Note: all the input strings are already lowercase. #Approach 1def 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 2import 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
在这种情况下，还提供了两种可能的解决方案，我猜想，如果您对算法还很陌生，那么第一种方法看起来有点熟悉，因为它从一个空字典开始构建为简单的计数器 。
然而，从长远来看，理解第二种方法将对您有更大的帮助，这是因为在这个算法中，我只是使用了集合 。计数器不是自己构建一个字符计数器，而是用枚举值替换范围(len (s)) ，这个函数可以帮助您更好地识别索引 。
5. 有效回文# Given a non-empty string s, you may delete at most one character. Judge whether you can make it a palindrome.# The string will only contain lowercase characters a-z. s = 'radkar'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 = ‘ radkar’函数通过排除‘ k’返回 Trueas 时，我们得到了单词‘ radar’ ，这是一个回文 。
数组6. 单调数组# Given an array of integers, determine whether the array is monotonic or not.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
这是另一个经常被问到的问题，上面提供的解决方案非常优雅，因为它可以写成一行程序 。一个数组是单调的当且仅当它是单调增加的或单调减少的，为了对它进行评估，上面的算法利用了返回 Trueif 一个迭代中的所有项都为真的 all ()函数，否则返回 False 。如果可迭代对象为空，则 all ()函数也返回 True 。
7. 把零移开#Given an array nums, write a function to move all zeroes to the end of it while maintaining the relative order of #the non-zero elements. 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]
当您使用数组时, 。移走()及 。Append ()方法是宝贵的盟友 。在这个问题中，我使用它们首先删除属于原始数组的每个零，然后将它们附加到同一个数组的末尾 。
8. 填补空白# Given an array containing None values fill in the None values with most recent # non None value in the array 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 值 。
. 匹配和不匹配的单词#Given two sentences, return an array that has the words that appear in one sentence and not#the other and an array with the words in common. 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)) # ^ A.symmetric_difference(B), & A.intersection(B)


推荐阅读


上一篇：红枣姜茶早上空腹喝吗,桂圆枸杞红枣茶经期能喝吗

下一篇：降压茶有哪些,普洱有哪些功效