目录
内容编译自 Donne Martin 的开源项目，侵权速删
070生成质数列表
挑战介绍
实现一个算法生成质数列表。介绍如下：
- 质数是指在大于 1 的自然数中，除了 1 和它本身以外不再有其他因数的自然数。
- 给定数字
n，对于从0至n-1的数字，需要判断这个数字是不是质数，如果是，则返回True，否则返回False。最终得到由布尔值构成的列表。 - 例如给定数字
5，则需要返回[False, False, True, True, False]。
挑战内容
本次挑战中，你需要在 primes.py 文件中补充类 PrimeGenerator 的空缺部分。
PrimeGenerator中的generate_primes方法用于生成素数列表。generate_primes函数的参数max_num用于指定传入的最大值。generate_primes函数需要返回一个数组，数组的元素为从0至max_num-1的数字是否为质数的布尔值，即True或者False。- 如果传入的
max_num为None，需要使用raise语句显示TypeError。 - 如果传入的
max_num不是自然数，也需要使用raise语句显示TypeError。
代码：指定一个排除标志数prime（范围从2到最大数的算术平方根），以prime为步长，排除范围内所有的prime*k。
import math
from numpy import array
class PrimeGenerator(object):
def generate_primes(self, max_num):
if max_num is None:
raise TypeError
array=[True]*max_num
array[0]=False
array[1]=False
prime=2
while prime<=math.sqrt(max_num):
self._cross_off(array,prime)
prime=self._next_prime(array,prime)
return array
def _cross_off(self,array,prime)://用于排除prime和它的倍数，因为从二开始，所以range的起点为prime的平方（往后的3也直接从3*3开始，因为之前的6必然被排除过）
for index in range(prime*prime,len(array),prime):
array[index]=False
def _next_prime(self,array,prime)://用于确定下一个标志数，功能是排除4,6,8,12这类被排除的数
next=prime+1
while next<len(array) and not array[next]:
next+=1
return next 071求一个数字的树根
挑战介绍
实现一个算法求一个数字的树根。介绍如下：
- 将一正整数的各个位数相加(即横向相加)后，若加完后的值大于等于 10 的话，则继续将各位数进行横向相加直到其值小于 10 为止所得到的数，即为数根。
- 例如对于数字
138，有1+3+8=12，1+2=3，则138的数根为3。
挑战内容
本次挑战中，你需要在 digits.py 文件中补充类 Solution 的空缺部分。
Solution中的add_digits方法用于求一个数字的数根。add_digits函数的参数val用于指定传入的数字。add_digits函数需要返回找到的数根。- 如果传入的
val为None，需要使用raise语句显示TypeError。 - 如果传入的
val为负数，需要使用raise语句显示ValueError。
代码：
class Solution(object):
def add_digits(self, val):
if val is None:
raise TypeError
if val<0:
raise ValueError
digits=[]
while val!=0:
digits.append(val%10)
val//=10
digits_sum=sum(digits)
if digits_sum>=10:
return self.add_digits(digits_sum)
else:
return digits_sum072查找列表的最大值
挑战介绍
实现一个包含插入方法的类，插入的数字存放在数组中。这个类支持计算最大值，最小值，均值和众数，并且计算的复杂度为 O(1)O(1)。
挑战内容
本次挑战中，你需要在 math_ops.py 文件中补充类 Solution 的空缺部分。
Solution中的__init__方法用于初始化，它的参数upper_limit用来表示数组长度的最大值。Solution类需要包含的属性为表示最大值的max，表示最小值的min，表示均值的mean，表示众数的mode。其他属性可根据需要自行添加。Solution中的insert方法用于插入数字。insert函数的参数val用于指定需要插入的数字。insert函数没有返回值。它需要在插入数字时以 O(1)O(1) 的计算复杂度得到最大值，最小值，均值和众数并存储在对应的属性中。- 如果传入的
val为None，需要使用raise语句显示TypeError。
代码
class Solution(object):
def __init__(self, upper_limit=100):
self.max=None
self.min=None
#Mean
self.num_items=0
self.running_sum=0
self.mean=None
#Mode
self.array=[0]*(upper_limit+1)
self.mode_occurrences=0
self.mode=None
def insert(self, val):
if val is None:
raise TypeError
if self.max is None or val>self.max:
self.max=val
if self.min is None or val<self.min:
self.min =val
self.num_items+=1
self.running_sum+=val
self.mean=self.running_sum/self.num_items
self.array[val]+=1
if self.array[val]>self.mode_occurrences:
self.mode_occurrences=self.array[val]
self.mode=val073确定一个数字是否为 2 的幂
挑战介绍
实现一个算法确定一个数字是否为 2 的幂。
挑战内容
本次挑战中，你需要在 power_of_two.py 文件中补充类 Solution 的空缺部分。
Solution中的is_power_of_two方法用于确定一个数字是否为 2 的幂。is_power_of_two函数的参数val用于指定传入的数字。is_power_of_two函数需要返回一个布尔值，即True或者False。- 如果传入的
val <= 0，则返回False。 - 如果传入的
val为None，需要使用raise语句显示TypeError。
代码：2的二进制形式为1000...000，减一有按位取反的效果。把2的幂与2的幂减一按位相与，结果为零即可验证是2的幂。
class Solution(object):
def is_power_of_two(self, val):
if val is None:
raise TypeError
if val<=0:
return False
return (val&(val-1))==0074求两个数字的和
挑战介绍
实现一个算法求两个数字的和，但不能在代码中使用 + 号和 - 号。
挑战内容
本次挑战中，你需要在 sum.py 文件中补充类 Solution 的空缺部分。
Solution中的sum_two方法用于求两个数字的和。sum_two函数的参数a和b用于指定传入的两个数字。sum_two函数需要返回一个数字。- 如果传入的
a和b中有None，需要使用raise语句显示TypeError。
代码：
相与：
11 1
10 01 00 0
异或：
11 00 0
01 10 1
显然相与运算可以记录进位，异或运算是朴素的按位加减（无法向前进位）
class Solution(object):
def sum_two(self, a, b):
if a is None or b is None:
raise TypeError
result=a^b//单纯加减，没有进位
carry=(a&b)<<1//记录进位
if carry!=0:
return self.sum_two(result,carry)
return result075求两个数字的差
挑战介绍
实现一个算法求两个数字的差，但不能在代码中使用 + 号和 - 号。
挑战内容
本次挑战中，你需要在 sub.py 文件中补充类 Solution 的空缺部分。
Solution中的sub_two方法用于求两个数字的和差。sub_two函数的参数a和b用于指定传入的两个数字，需要求a减去b的值。sub_two函数需要返回一个数字。- 如果传入的
a和b中有None，需要使用raise语句显示TypeError。
代码：对a按位取反再相与，把0-1变成1-1，得到借位
class Solution(object):
def sub_two(self, a, b):
if a is None or b is None:
raise TypeError
result=a^b
borrow=(~a&b)<<1
if borrow!=0:
return self.sub_two(result,borrow)
return result