剑指 Offer 2022/7/5

剑指 Offer 14- II. 剪绳子 II

给你一根长度为 n 的绳子，请把绳子剪成整数长度的 m 段（m、n都是整数，n>1并且m>1），每段绳子的长度记为 k[0],k[1]…k[m - 1] 。请问 k[0]k[1]…*k[m - 1] 可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。

答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。

示例 1：
输入: 2
输出: 1
解释: 2 = 1 + 1, 1 × 1 = 1

示例 2:
输入: 10
输出: 36
解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36

代码思路

1. 动态规划
   多了一步取余，但这个方法好像只在python中行得通，在别的代码中不行

class Solution:
    def cuttingRope(self, n: int) -> int:
        dp=[1]*(n+1)
        for i in range(2,n+1):
            dp[i]=max([max(dp[i-j]*j,j*(i-j))for j in range(1,i)])
        return dp[n]%1000000007
1
2
3
4
5
6

2. 贪心
   官方题解
   推论二： 尽可能将绳子以长度 33 等分为多段时，乘积最大。
   切分规则：
   最优： 3 。把绳子尽可能切为多个长度为 3 的片段，留下的最后一段绳子的长度可能为 0,1,20,1,2 三种情况。
   次优： 2 。若最后一段绳子长度为 2 ；则保留，不再拆为 1+1 。
   最差： 11 。若最后一段绳子长度为 11 ；则应把一份 3 + 1 替换为 2 + 2，因为 $2\times 2>3\times 1$

class Solution:
    def cuttingRope(self, n: int) -> int:
        if n <= 3: return n - 1
        a, b, p = n // 3, n % 3, 1000000007
        if b == 0: return 3 ** a % p
        if b == 1: return 3 ** (a - 1) * 4 % p
        return 3 ** a * 2 % p
1
2
3
4
5
6
7

快速幂

class Solution:
    def cuttingRope(self, n: int) -> int:
        def remainder(x, a, p):
            rem = 1
            while a > 0:
                if a % 2: rem = (rem * x) % p
                x = x ** 2 % p
                a //= 2
            return rem
        if n <= 3: return n - 1
        a, b, p = n // 3, n % 3, 1000000007
        if b == 0: return remainder(3,a,p)
        if b == 1: return remainder(3,a-1,p) * 4 % p
        return remainder(3,a,p) * 2 % p
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

剑指 Offer 15. 二进制中1的个数

编写一个函数，输入是一个无符号整数（以二进制串的形式），返回其二进制表达式中数字位数为 ‘1’ 的个数（也被称为 汉明重量).）。
提示：
请注意，在某些语言（如 Java）中，没有无符号整数类型。在这种情况下，输入和输出都将被指定为有符号整数类型，并且不应影响您的实现，因为无论整数是有符号的还是无符号的，其内部的二进制表示形式都是相同的。
在 Java 中，编译器使用 二进制补码 记法来表示有符号整数。因此，在上面的 示例 3 中，输入表示有符号整数 -3。

示例 1：
输入：n = 11 (控制台输入 00000000000000000000000000001011)
输出：3
解释：输入的二进制串 00000000000000000000000000001011 中，共有三位为 ‘1’。

示例 2：
输入：n = 128 (控制台输入 00000000000000000000000010000000)
输出：1
解释：输入的二进制串 00000000000000000000000010000000 中，共有一位为 ‘1’。

示例 3：
输入：n = 4294967293 (控制台输入 11111111111111111111111111111101，部分语言中 n = -3）
输出：31
解释：输入的二进制串 11111111111111111111111111111101 中，共有 31 位为 ‘1’。

代码思路

1. n右移，每一步判读最后一位是否为一，为一就总数加一

class Solution:
    def hammingWeight(self, n: int) -> int:
        num=0
        while n:
            if n&1:num+=1
            n>>=1
        return num
1
2
3
4
5
6
7

2. 1左移，然后与n做与运算，判断每一位是否为一，为一总数加一

class Solution:
    def hammingWeight(self, n: int) -> int:
        num=0
        for i in range(32):
            if n & (1 << i):num+=1
        return num
1
2
3
4
5
6

3. 使用$n\&(n-1)$
   $n\&(n-1)$，其预算结果恰为把 n 的二进制位中的最低位的 1 变为 0 之后的结果。

class Solution:
    def hammingWeight(self, n: int) -> int:
        num=0
        while n:
            n &= n - 1
            num += 1
        return num
1
2
3
4
5
6
7