数学


面试题64. 求1+2+…+n

1+2+...+n ,要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句(A?B:C)。

class Solution:
    def sumNums(self, n: int) -> int:
        return n and n+self.sumNums(n-1)
# 学会了and的特性
# a and b 返回 b, a and 0 返回 a

136.只出现一次的数字

给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只出现了一次的元素。

说明:

你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗?

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        return reduce(lambda x, y: x ^ y, nums)
#reduce(function, iterable[, initializer])内置函数
#异或(在二进制基础上)的特性:a^a=0,a^0=a

172.阶乘后的零

给定一个整数 n,返回 n! 结果尾数中零的数量。

class Solution:
    def trailingZeroes(self, n: int) -> int:
        cnt = 0
        while n > 0:
            n //= 5
            cnt += n
        return cnt
# 数学观察

231.2的幂

给定一个整数,编写一个函数来判断它是否是 2 的幂次方。

return n>0 and n&(n-1)==0

说明:

num n n-1 n&(n-1)
2**0 0001 0000 0000
2**1 0010 0001 0000
2**2 0100 0011 0000

60.第k个排列

给出集合 [1,2,3,…,n],其所有元素共有 n! 种排列。

按大小顺序列出所有排列情况,并一一标记,当 n = 3 时, 所有排列如下:
“123”,”132”,”213”,”231”,”312”,”321”

给定 nk,返回第 k 个排列。

class Solution:
    def getPermutation(self, n: int, k: int) -> str:
        ans=""
        factroial=[1]
        for i in range(1,n):
            factroial.append(i*factroial[-1])
        valid=[1]*(n+1)

        k-=1
        for i in range(1,n+1):
            order=k//factroial[n-i]+1
            for j in range(1,n+1):
                order-=valid[j]
                if order==0:
                    ans+=str(j)
                    valid[j]=0
                    break
            k %= factroial[n-i]

        return ans

#康托展开,不懂

计数质数

class Solution:
    def countPrimes(self, n: int) -> int:
        if n<3: return 0
        ans=[1]*n
        for i in range(2,int(n**0.5)+1):
            ans[2*i::i]=[0]*len(ans[2*i::i])
        return sum(ans)-2

#埃氏筛
#那个i的范围还是没懂

文章作者: ╯晓~
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 ╯晓~ !
评论
  目录