问题一
Prime number (质 数)
Given a positive integer number n. Determine whether n is a prime number or not. (You may implement your program in any programming language.)
(给定一个正整数n。判断n是否是素数(你可以用任何编程语言来实现你的程序)
我当时给出的解答: 发现如果使用 111111111111529 这个大数;直接就卡死了;
def is_prime(number): count = 0 if number<= 1: print('不是') else: for i in range(1, number+1): if number%i==0: count+=1 if count > 2: print(False) else: print(True) if __name__ == "__main__": # is_prime(6) is_prime(111111111111529)
于是我给优化了一下;
def isPrime(n): start_time = time.time() import math if n <= 1: return False for i in range(2,int(math.sqrt(n))+1,6): if n % i == 0 or n % i+2 ==0:return '不是质数' consume_time = time.time() - start_time return ['是质数',consume_time] if __name__ == "__main__": print(isPrime(2))
上面两种方法的时间复杂度都是为 O(n); 但是面试官和我说 可以改成 O(1);我也是一脸懵逼;难道是用递归来弄么;如果有人可以用O(1)的时间复杂度来解决 请评论一下;让我涨涨见识;
问题二
2.Largest number
# // 2.1 Given a list of non negative integers, arrange them such that they form the largest number. (You may implement your program in pseudocode or any programming language.)
(给定一个非负整数列表,将它们排列成最大的数(您可以用伪代码或任何编程语言实现您的程序。)
def sum_number1(numList): ''' ****给定的是一个list ****做一个非整数判断 ''' auxiliary = [str(i) for i in numList if str(i).isdigit()] if not auxiliary: return '' length = len(auxiliary) for index1 in range(length): for index2 in range(length - index1 - 1): if auxiliary[index2] + auxiliary[index2 + 1] < auxiliary[index2 + 1] + auxiliary[index2]: auxiliary[index2], auxiliary[index2 + 1] = auxiliary[index2 + 1], auxiliary[index2] result = '' for index3 in range(length): result = result + auxiliary[index3] print(result) if __name__ == "__main__": # sum_number([1,29,'4123',59,'a']) sum_number1([19, 49, '3123', 59, 'a'])
第二题的时间复杂度O(n^2);