[剑指Offer]13~16

2024-04-09 23:00:07 阅读数 278

学习使用工具

剑指Offer http://itmyhome.com/sword-means-offer/sword-means-offer.pdf

LeetCode的剑指Offer题库 https://leetcode.cn/problemset/all/

剑指 Offer 14- I. 剪绳子

给你一根长度为 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。

示例 1：

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

示例 2:

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

提示：

2 <= n <= 58

解法：

首先有数学推论：将绳子以相等的长度等分为多段，得到的乘积最大；尽可能将绳子以长度 3 等分为多段时，乘积最大。由此有思路：

当 n ≤ 3 时，返回 n−1。
当 n > 3 时，
- 当 n % 3 = 0 时，直接返回 $3^{n \over 3}$
- 当 n % 3 = 1 时，将余数1与其中一个3组合转换为两个2的乘积更大，因此返回 $4 * 3^{n-1 \over 3}$
- 当 n % 3 = 2 时，返回 $2 * 3^{n \over 3}$

def cuttingRope(self, n: int) -> int:
        if n <= 3:
            return n - 1
        else:
            if n % 3 == 0:
                return pow(3, n // 3)
            elif n % 3 == 1:
                return pow(3, n // 3 - 1) * 4
            else:
                return pow(3, n // 3) * 2

即使不知道3等分的情况下乘积最大，只知道第一条推论，也可以通过枚举切割段数来进行解答。

不使用数学推论而用动态规划思想来看的话，这是一个类似完全背包的问题，摘录一下官方的题解：

令 x 是拆分出的第一个正整数，则剩下的部分是 n−x，n−x可以不继续拆分，或者继续拆分成至少两个正整数的和。

创建数组 dp，其中 dp[i]表示将正整数 i 拆分成至少两个正整数的和，且 dp[0]=dp[1]=0。

当 i≥2 时，假设对正整数 i 拆分出的第一个正整数是 j（1≤j<i）：

将 i 拆分成 j 和 i−j 的和，且 i−j不再拆分成多个正整数，此时的乘积是 j×(i−j)
将 i 拆分成 j 和 i−j的和，且 i−j 继续拆分成多个正整数，此时的乘积是 j×dp[i−j]

因此，当 j 固定时，有 dp[i]=max⁡(j×(i−j),j×dp[i−j])。

为了得到 dp[i] 的最大值，需要遍历所有的 j 。状态转移方程： $dp[i] = max⁡_{1≤j<i}\{max⁡(j×(i−j),j×dp[i−j])\}$

def cuttingRope(self, n: int) -> int:
    dp = [0] * (n + 1)
    dp[0] = 0
    dp[1] = 1
    for i in range(2, n + 1):
        for j in range(i):
            a = j * (i - j)
            b = j * dp[i - j]
            dp[i] = max(dp[i], a, b)
    return dp[n]

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

提示：

2 <= n <= 1000

解法：

这题和上面那题有什么本质的区别吗，加个取模不就好了？

def cuttingRope(self, n: int) -> int:
        if n <= 3:
            return n - 1
        else:
            if n % 3 == 0:
                return pow(3, n // 3) % 1000000007
            elif n % 3 == 1:
                return pow(3, n // 3 - 1) * 4 % 1000000007
            else:
                return pow(3, n // 3) * 2 % 1000000007

翻了下评论区，主要是对动态规划的影响。

说法是扩大了n的范围，导致了大数越界情况的出现。而动态规划的过程中不能取余，不然就没法通过max进行大小比较了。但因为Python的int类型底层使用了变长数组来实现大整数，不管多大都不会超，所以动态规划不会溢出，一样计算最后再取余就好了……

如果使用的非Python语言，还使用动态规划的话，就不得不面对大数问题的解决方法了。而且解决之后性价比也不高，还是用数学方法来做比较合适（个人认为这题出的并不好）。

剑指 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'。

提示：

输入必须是长度为 32 的 二进制串 。

解法：

从原数开始，记录模2的值，然后除以2，再记录模2的值，再除以2……直到数已经为0为止。从二进制来看，相当于每次记录最低位，然后右移一位，直到移空为止。

def hammingWeight(self, n: int) -> int:
        ans = 0
        while(n > 0):
            ans += n % 2
            n = n // 2
        return ans

另外，新的一天，新的Offer消失术：

def hammingWeight(self, n: int) -> int:
    return bin(n).count('1')

剑指 Offer 16. 数值的整数次方

实现 pow(x, n) ，即计算 x 的 n 次幂函数（即， $x^n$ ）。不得使用库函数，同时不需要考虑大数问题。

示例 1：

输入：x = 2.00000, n = 10
输出：1024.00000

示例 2：

输入：x = 2.10000, n = 3
输出：9.26100

示例 3：

输入：x = 2.00000, n = -2
输出：0.25000
解释：2-2 = 1/22 = 1/4 = 0.25

提示：

-100.0 < x < 100.0
-231 <= n <= 231-1
-104 <= xn <= 104

解法：

实现幂函数很简单，连乘就行了，不过必然超时，尝试缩短计算幂的次数（又递归）。

当n为奇数时，Pow(x, n) = Pow(x, n - 1) * x
当n为偶数时，Pow(x, n) = Pow(x, n / 2) * Pow(x, n / 2)
Pow(x, 1) = x, Pow(x, 0) = 1

def myPow(self, x: float, n: int) -> float:
        if n == 1:
            return x
        if n == 0:
            return 1
        if n == -1:
            return 1/x
        
        if n % 2 == 0:
            return self.myPow(x, n / 2) * self.myPow(x, n / 2)
        else:
            return self.myPow(x, n - 1) * x

然后还是超时，x = 0.00001, n = 2147483647哪个大聪明想的这个测试用例？检查了一下发现self.myPow(x, n / 2)递归了两次，我不超时谁超时？遂改。

def myPow(self, x: float, n: int) -> float:
        if n == 1:
            return x
        if n == 0:
            return 1
        if n == -1:
            return 1/x
        
        if n % 2 == 0:
            ans = self.myPow(x, n / 2)
            return ans * ans
        else:
            return self.myPow(x, n - 1) * x

通过之后又逛了下讨论区，发现一个更好的写法，不用判断n是否是奇数，放在这里进行学习。

def myPow(self, x: float, n: int) -> float:
        if n == 1:
            return x
        if n == 0:
            return 1
        if n == -1:
            return 1/x
        
        half = self.myPow(x, n / 2)
        mod = self.myPow(x, n % 2)
        
        return half * half * mod