Henry ’Blog
0%

<剑指offer> 剑指offer 14-1、14-2、15

发表于 更新于 分类于 Valine：

摘要：
14-1 剪绳子
14-2 剪绳子||
15 二进制中的一个数

面试题14-1剪绳子

题目：

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

解法：

思路一：

暴力遍历+备忘录法减少运算量

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// 暴力解法+备忘录减少运算量
class Solution {
    public int cuttingRope(int n) {
        int[] f=new int[n+1];
        return mem(f,n);
        
    }
    public int mem(int[] f,int n){
        if(f[n]!=0){
            return f[n];
        }
        if (n == 2) return 1;
        int res = -1;
        for (int i = 1; i <= n - 1; i++) {
            res = Math.max(res, Math.max(i * (n - i), i * mem(f,n - i)));
        }
        f[n]=res;
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# 使用辅助函数
class Solution:
    def cuttingRope(self, n: int) -> int:
        def memoize(n):
            if n == 2: return 1
            if f[n] != 0: # 如果f[n]已经计算过，直接返回避免重复计算
                return f[n]
            res = -1
            for i in range(1, n):
                res = max(res, max(i * (n - i),i * memoize(n - i)))
            f[n] = res
            return res

        f = [0 for _ in range(n + 1)]
        return memoize(n)

思路二：

贪心算法+数学推导：
① 当所有绳段长度相等时，乘积最大。② 最优的绳段长度为 3。
在这里插入图片描述

1
2
3
4
5
6
7
8
9
class Solution {
    public int cuttingRope(int n) {
        if(n<=3) return n-1;
        int i=n%3,j=n/3;
        if(i==0) return (int)Math.pow(3,j);
        else if(i==1) return (int)Math.pow(3,j-1)*4;
        return (int)Math.pow(3,j)*2;
    }
}
1
2
3
4
5
6
7
8
class Solution:
    def cuttingRope(self, n: int) -> int:
        if n<=3: return n-1
        i=n%3
        j=n//3
        if i==0: return int(math.pow(3,j))
        elif i==1: return int(math.pow(3,j-1)*4)
        return int(math.pow(3,j)*2)

面试题14-2 剪绳子||

题目：

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

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

解法：

添加大数求余：循环求余||快速幂求余算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
//循环求余
class Solution {
    public int cuttingRope(int n) {
        if(n <= 3) return n - 1;
        int b = n % 3, p = 1000000007,a=n/3;
        long rem = 1, x = 3;
        // 循环求余数
        for(int i=1; i<a; i++) {
            rem = (rem * x) % p;
        }
        if(b == 0) return (int)(rem * 3%p);
        if(b == 1) return (int)(rem * 4%p );
        return (int)(rem * 6%p );
    }
}
//快速幂求余
class Solution {
    public int cuttingRope(int n) {
        if(n <= 3) return n - 1;
        int b = n % 3, p = 1000000007;
        long rem = 1, x = 3;

        for(int a = n / 3 - 1; a > 0; a /= 2) {
            if(a % 2 == 1) rem = (rem * x) % p;
            x = (x * x) % p;
        }
        if(b == 0) return (int)(rem * 3 % p);
        if(b == 1) return (int)(rem * 4 % p);
        return (int)(rem * 6 % p);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def cuttingRope(self, n: int) -> int:
        if n <= 3: return n - 1
        a, b, p, x, rem = n // 3 - 1, n % 3, 1000000007, 3 , 1
        while a > 0:
            if a % 2: rem = (rem * x) % p
            x = x ** 2 % p
            a //= 2
        if b == 0: return (rem * 3) % p # = 3^(a+1) % p
        if b == 1: return (rem * 4) % p # = 3^a * 4 % p
        return (rem * 6) % p # = 3^(a+1) * 2  % p
# 由于语言特性，Python 可以不考虑大数越界问题
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

面试题15 二进制中的一个数

题目：

请实现一个函数，输入一个整数，输出该数二进制表示中 1 的个数。例如，把 9 表示成二进制是 1001，有 2 位是 1。因此，如果输入 9，则该函数输出 2。

解法：

思路一：

依次从右向左遍历二进制位，统计出一的个数；

1
2
3
4
5
6
7
8
9
10
11
12
public class Solution {
    // you need to treat n as an unsigned value
    public int hammingWeight(int n) {
       // 普通遍历法
        int res=0;
        while(n!=0){
            res+=n&1;
            n>>>=1;
        }
        return res;
        }
}
1
2
3
4
5
6
7
8
class Solution:
    def hammingWeight(self, n: int) -> int:
		#普通遍历法
        res=0
        while n:
            res+=n&1
            n>>=1
        return res

思路二：

利用n-1二进制位与n之间的不同，依次统计1的个数
在这里插入图片描述

1
2
3
4
5
6
7
8
9
10
11
public class Solution {
    // you need to treat n as an unsigned value
    public int hammingWeight(int n) {
        int res=0;
        while(n!=0){
            res++;
            n=n&(n-1);
        }
        return res;
    }
}
1
2
3
4
5
6
7
8
class Solution:
    def hammingWeight(self, n: int) -> int:
        # 借助n-1
        res=0
        while n:
            res+=1
            n=n&(n-1)
        return res