204. Count Primes
时间 O(NloglogN) 空间 O(N)
如果一个数是另一个数的倍数,那这个数肯定不是素数。利用这个性质,我们可以建立一个素数数组,从2开始将素数的倍数都标注为不是素数。第一轮将4、6、8等表为非素数,然后遍历到3,发现3没有被标记为非素数,则将6、9、12等标记为非素数,一直到N为止,再数一遍素数数组中有多少素数。
由于1和0都不是质数,所以初始化完数组后,要res[0] = False, res[1] = False
需要注意数组的越界问题。双层循环,外层循环从2到int((n-1)**0.5)+1
, 内层循环也是从2开始,到(n-1)/j + 1
,n都要-1才行,不然就会越界,可以用4做例子代入就明白了
数组里存放的是true和false,最后用sum(res)
统计数组中有多少个true就是证明有多少个质数
202. Happy Number
结果要么最终为1,要么最终陷入循环。所以用res = set()
来存放结果,因为set()中不包含重复元素,每次得出结果后可以坚持结果是否存在set中,若存在,则返回false。
如何对数字位进行平方和再相加?将数字转换为str后就可以进行for循环。
for i in str(n): sum += int(i)**2
每次得到一个新的n, 若他既不等于1,又不存在set中,就将他添加进去res.add(n)
60. Permutation Sequence
给出数字n,一共存在n!个全排列。具有同样起始数字的排列就有(n-1)!个,因为n中每个数字都会作为起始数字。
先将n存进数组中
while n>=1: group = k / factorial(n-1)
......k = k%factorial(n-1)
(如果K大于0:我们想要找的第k个排列在有序的全排列中属于第group+1组。因为数组从0开始计数,所以直接以group为下标去nums里找相应的起始数字就可以。
如果K小于0: 当前数字是第group个排列的最后一个数字,it's the last element of (group)th group, 此时group要减1)
.....if k >0: res.append(str(nums[group])) nums.remove(nums[group]) else: res.append(str(nums[group-1])) nums.remove(nums[group]) n -= 1
return ''.join(res)
remove 是为了防止之后又访问到这个元素