剪绳子
程序员文章站
2023-10-28 13:29:52
题目描述:给你一根长度为 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。链接:https://leetcode-cn.com/problems/jian-sheng-zi-lcof......
1. 无大数情况下
题目描述:
给你一根长度为 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。
链接:https://leetcode-cn.com/problems/jian-sheng-zi-lcof
1.1 dfs + 回溯
思路分析:在无大数情况下,可以考虑采用dfs,但要注意合理剪枝,否则代码还是运行不通过。
代码:
class Solution {
public:
int sum = 0;
int mul = 1;
int maxVal = 0;
int t;
int cuttingRope(int n) {
t = n;
_cuttingRope(1);
return maxVal;
}
private:
void _cuttingRope(int pos)
{
if(sum == t)
{
maxVal = max(maxVal, mul);
return;
}
for(int i = pos; i < t; ++i)
{
if(sum + i > t)//在这里就开始剪枝,超过了直接返回
return;
sum += i;
mul *= i;
_cuttingRope(i);
sum -= i;
mul /= i;
}
}
};
2. 有大数情况下
此时使用dfs是行不通的。
在这里可以学习一下Krahets的解析。
2.1 循环取余法
代码:
class Solution {
public:
int cuttingRope(int n) {
if(n < 4)
return n - 1;
long long ret = 1;
while(n > 4)
{
ret = (ret * 3) % 1000000007;
n -= 3;
}
//n 可能是 4 , 3 , 2
//4 可以不用剪了 3 * 3 * 1 一定小于 3 * (1 + 3)
//2 是在n - 3 = 2 时,需要考虑最后一段绳子的情况
return ret * n % 1000000007;
}
};
2.2 快速幂
代码:
class Solution {
public:
int cuttingRope(int n) {
if(n < 4)
return n - 1;
//除3是因为,3的绳子长度最后的幂一定是最长的,优先级最高
int divisor = n / 3 - 1;//减1是因为需要考虑,最后一段绳子为4 2 的情况,后续需要特别考虑
int mod = n % 3;//余数 0 1 2
long long mul = 3;//快速幂时的初始底数
long long ret = 1;//返回值
while(divisor > 0)
{
//比如:0011 & 1 此时为1了,则可以将该数进行相乘了
//比如:0010 & 1 此时就就不能进行相乘
if(divisor & 1)
ret = (ret * mul) % 1000000007;
//该数继续向后走
mul = (mul * mul) % 1000000007;
//右移一位
divisor >>= 1;
}
if(mod == 0)//最后一段绳子为3
return ret * 3 % 1000000007;
if(mod == 1)//最后一段绳子为4
return ret * 4 % 1000000007;
return ret * 6 % 1000000007;//最后一段绳子为5,则为3 * 2
}
};
本文地址:https://blog.csdn.net/w903414/article/details/111655910
上一篇: 《海湾花园——厦门》周沙尘