工控课堂

 找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

工控课堂 首页 工控文库 工控编程 查看内容

面试者必备面试题-10个常见的Python算法题

2020-10-8 08:54| 发布者: 198366809| 查看: 1| 评论: 1|原作者: 198366809

摘要: Python算法,Python面试,Python学习,Python面试技巧 1、整数反转 # Given an integer, return the integer with reversed ...
“Knowing how to solve algorithms will give you a competitive advantage during the job search process”  
如果你掌握算法,让你更占优势.



1、整数反转

# Given an integer, return the integer with reversed digits.# Note: The integer could be either positive or negative.
def solution(x):    string = str(x)
    if string[0] == '-':        return int('-'+string[:0:-1])    else:        return int(string[::-1])
print(solution(-231))print(solution(345))
Output:
-132
543

【解析】
一个热身的算法,主要熟悉一下字符串的切片;还有一点值得注意的是,需要考虑一下给定的整数是负数(带负号)。

2、单词平均长度

# For a given sentence, return the average word length. # Note: Remember to remove punctuation first.
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()等方法是很有必要的,在这个案例中它们帮助我们移除不需要的字符,然后创建一个新的单词列表,方便我们计算单词长度的测量与运算。
3、字符数字相加

# Given two non-negative integers num1 and num2 represented as string, return the sum of num1 and num2.# You must not use any built-in BigInteger library or convert the inputs to integer directly.
#Notes:#Both num1 and num2 contains only digits 0-9.#Both num1 and num2 does not contain any leading zero.
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 #Given a string of length one, the ord() function returns #an integer representing the Unicode code point of the character #when the argument is a unicode object, or the value of #the byte when the argument is an 8-bit string.
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( )都能够解决上面的问题,前一个方法比较简单快捷,但我们还是建议使用后一种方法,能够从底层去深入了解字符串的ASCII及相应的字符格式与整数的相互转换,而且能够掌握进位计数制的构成方法。

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 = 1else:            frequency +=1for i in range(len(s)):if frequency[s] == 1:return ireturn -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 indexfor 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

【解析】
我们给出了2种解决的算法,如果你是Python的新手,建议你使用第1种方案(先使用一个空字典,然后给键加上一个计数功能值);长远来说,第2种方法,我们只是简单使用了collection.Counter(s)来替换字符计数,enumerate(s)替换range(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’ 代入函数,当移除字符d时,得到的文本rakar就是回文格式,所以返回True.
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 <= nums[i + 1] for i in range(len(nums) - 1)) or             all(nums >= nums[i + 1] for i in range(len(nums) - 1)))
print(solution(A)) print(solution(B)) print(solution(C))
Output:
True
False
True

【解析】
这个问题也是很多人会问及的,解决办法也是相当简单,我们只要使用单行就可以解决问题.数组中元素的单调性(递增或者递减).我们使用all()函数来测试所有的枚举都成立(返回True),则函数返回True否则返回False.如果序列中没有元素,也返回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]

【解析】
当涉及到数组时,.remove()和.append()是一种好兄弟,在这个题目中,我们找到0元素并移除它,在这个序列的后面添加它,从而完成算法功能.

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 = ielse:            res.append(valid)return res
solution(array1)
Output:
[1, 1, 2, 3, 3, 3, 5, 5]

【解析】
这个题目在编写代码时要注意None元素的正确使用.

9、文字匹配问题

#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)
print(solution(sentence1, sentence2))
Output:
(['The','We','a','are','by','heavy','hit','in','meet','our',
    'pleased','storm','to','was','you'],
['city', 'really'])

【解析】
这个算法挺简单的,我们会使用常用的集合的方法,如set() , intersection() or &和 symmetric_difference()or ^.这些方法非常好用,如果您是第一次使用,务必做好记录工作.
10、打印素数序列

# Given k numbers which are less than n, return the set of # prime number among them# Note: The task is to write a program to print all Prime numbers # in an Interval.# Definition: A prime number is a natural number greater than 1 # that has no positive divisors other than 1 and itself.
n = 35def solution(n):    prime_nums = []for num in range(n):if num > 1: # all prime numbers are greater than 1for 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 itbreakelse:                prime_nums.append(num)return prime_numssolution(n)
Output:
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31]

【解析】
最后一个题目是比较经典的问题,大家只要熟悉素数的定义,结合Range函数求余操作,就会快速的推断出算法.



路过

雷人

握手

鲜花

鸡蛋

相关阅读

发表评论

最新评论

dyysn123 2020-10-8 08:53
激动人心,无法言表!

查看全部评论(1)

热门文章

QQ|免责声明|本站介绍|工控课堂 ( 沪ICP备20008691号-1 || 沪公网安备 31010602005455号 )|网站地图

GMT+8, 2020-10-8 08:54 , Processed in 0.077978 second(s), 45 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

返回顶部