数学&位运算


常用知识点:

  • n&(n-1) 的性质:把 n 的二进制位中最低位的 1变为0
  • & 运算,通常用于将某一位置为 0
  • ^ 的特性:无进位加法

剑指 Offer 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

172. 阶乘后的零

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

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

# 数学观察

60. 排列序列

给出集合 [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

#康托展开,不懂

204. 计数质数

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的范围还是没懂

231.2的幂

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

class Solution:
    def isPowerOfTwo(self, n: int) -> bool:
        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

191. 位1的个数

返回一个无符号整数(以二进制串的形式)中数字位数为 ‘1’ 的个数。

class Solution:
    def hammingWeight(self, n: int) -> int:
        ans = 0
        while n:
            ans += 1
            n &= (n-1)
        return ans

记住:n&(n-1) 的性质:把 n 的二进制位中最低位的 1变为0

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

190. 颠倒二进制位

颠倒给定的 32 位无符号整数的二进制位。

1. 循环
class Solution:
    def reverseBits(self, n: int) -> int:
        ans = 0
        for i in range(32):
            ans <<= 1
            ans += (n & 1)
            n >>= 1
        return ans

483. 最小好进制

对于给定的整数 n, 如果n的k(k>=2)进制数的所有数位全为1,则称 k(k>=2)是 n 的一个好进制。

枚举k进制后的数位长度

class Solution:
    def smallestGoodBase(self, n: str) -> str:
        n = int(n)
        for m in range(n.bit_length(), 2, -1):
            k = int(n**(1/floor(m-1)))
            if (k**m-1)//(k-1) == n:
                return str(k)
        return str(n-1)

371. 两整数之和

给你两个整数 ab ,不使用 运算符 +- ​​​​​​​,计算并返回两整数之和。

提示:

1. 无进位加法使用 异或 计算得出
2. 进位结果使用 与运算和移位 计算得出
3. -1000 <= a, b <= 1000
class Solution:
    def getSum(self, a: int, b: int) -> int:
        while b != 0:
            carry = ((a&b)<<1)%2**32
            a = (a^b)%2**32
            b = carry
        if a&2**31:
            return ~((a^2**31)^(2**31-1))
        else:
            return a
# 由于python的int不是32位, 所以我们需要模拟32位, 方法就是把高于32位全部忽略, 我们通过0xFFFFFFFF作为mask, 相与来实现
# 再返回结果的时候, 由于后32位之前全是0, 负数可能会被识别为正数,  所以如果答案是负数, 需要把前面的0变成1, 后32位不变. 
class Solution:
    def getSum(self, a: int, b: int) -> int:
        mask = 0xFFFFFFFF
        a = a & mask 
        b = b & mask
        while (b != 0):
            carry =   (a & b) << 1
            carry = carry & mask
            a = a ^ b 
           
            b = carry 
        a = a & mask
        # a高于后32位全是0
        if a < 0x80000000:  # 后32位的最高位是0, 说明实际结果不是负数, 直接返回
            return a
        else: # 后32位的最高位是1, 说明实际结果是负数, 如果直接返回, 由于a高于32位全是0, 解释器会把a解释成一个大的正数, 所以必须把高位的0变成1,而低位不变解释器才能得到正确的答案
            return ~(a^mask)

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