「剑指Offer」Day24：数学（中等）
剑指 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。
输入: 10 输出: 36 解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36
思路
动态规划，创建数组 dp，其中 dp[i] 表示将正整数 i 拆分成至少两个正整数的和之后，这些正整数的最大乘积。
特别地，0 不是正整数，1 是最小的正整数，0 和 1 都不能拆分，因此
。
特别地，0 不是正整数，1 是最小的正整数，0 和 1 都不能拆分，因此
当 
时，假设对正整数 
拆分出的第一个正整数是
，则有以下两种方案：
-
将
和
的和，且
；
-
将
因此，当 固定时，有 %2Cj%C3%97dp%5Bi%E2%88%92j%5D))
。由于 j 的取值范围是 1 到 i−1，需要遍历所有的 j 得到 dp[i] 的最大值，因此可以得到状态转移方程如下：
最终得到 dp[n] 的值即为将正整数 n 拆分成至少两个正整数的和之后，这些正整数的最大乘积。
🔗参考题解：https://leetcode-cn.com/problems/integer-break/solution/zheng-shu-chai-fen-by-leetcode-solution/
🔗参考题解：https://leetcode-cn.com/problems/integer-break/solution/zheng-shu-chai-fen-by-leetcode-solution/
代码实现
如当n=3时，dp[0]=dp[1]=0，dp[2]=1，则当i=3时，先对3剪一刀分为1和2，此时分为剪和不剪两种情况：剪：继续对2进行相同的操作，可知最大乘积为dp[2]，不剪：为2，则dp[3]=max(1*dp[2], 1*2)=2
class Solution {
public int cuttingRope(int n) {
int[] dp = new int[n+1];
for(int i = 2; i <= n; i++) {
int curMax = 0;
for(int j = 1; j < i; j++){
curMax = Math.max(curMax, Math.max(j * (i - j), j * dp[i-j]));
}
dp[i] = curMax;
}
return dp[n];
}
}
剑指 Offer 57 - II. 和为s的连续正数序列
题目描述
输入一个正整数 target ，输出所有和为 target 的连续正整数序列（至少含有两个数）。序列内的数字由小到大排列，不同序列按照首个数字从小到大排列。
输入：target = 15 输出：[[1,2,3,4,5],[4,5,6],[7,8]]🔗题目链接：https://leetcode-cn.com/problems/he-wei-sde-lian-xu-zheng-shu-xu-lie-lcof
思路
和为目标值target的连续正整数序列的数值范围为[1 , target/2 + 1]，可将它们该范围内的数字存入一个数组中，运用滑动窗口求和为目标值的连续序列，调用函数Arrays.copyOfRange()进行截取
代码实现
class Solution {
public int[][] findContinuousSequence(int target) {
List<int[]> list = new ArrayList<>();
//和为target的连续正整数序列的数值范围为1 ~ target/2 + 1
int length = target / 2 + 1;
int[] nums = new int[length];
for(int i = 0; i < length; i++){
nums[i] = i + 1;
}
int left = 0;
int right = 0;
int sum = 1;
while(left < length - 1){ //滑动窗口
if(sum > target){
sum -= nums[left];
left++;
continue;
}else if(sum == target){
list.add(Arrays.copyOfRange(nums, left, right + 1));
}
if(right < length - 1){
sum += nums[++right];
}else{
sum -= nums[left++];
}
}
int[][] res = new int[list.size()][];
for(int i = 0; i < list.size(); i++){
res[i] = list.get(i);
}
return res;
}
}
剑指 Offer 62. 圆圈中最后剩下的数字
题目描述
0,1,···,n-1这n个数字排成一个圆圈，从数字0开始，每次从这个圆圈里删除第m个数字（删除后从下一个数字开始计数）。求出这个圆圈里剩下的最后一个数字。
例如，0、1、2、3、4这5个数字组成一个圆圈，从数字0开始每次删除第3个数字，则删除的前4个数字依次是2、0、4、1，因此最后剩下的数字是3。
🔗题目链接：https://leetcode-cn.com/problems/yuan-quan-zhong-zui-hou-sheng-xia-de-shu-zi-lcof
例如，0、1、2、3、4这5个数字组成一个圆圈，从数字0开始每次删除第3个数字，则删除的前4个数字依次是2、0、4、1，因此最后剩下的数字是3。
🔗题目链接：https://leetcode-cn.com/problems/yuan-quan-zhong-zui-hou-sheng-xia-de-shu-zi-lcof
方法一：模拟
将数字0~n-1存入一个ArrayList集合中，找到要删除的位置，移除集合中的元素，直到只剩下一个元素，但这种方法的时间复杂度)
class Solution {
public int lastRemaining(int n, int m) {
List<Integer> list = new ArrayList<>();
for(int i = 0; i < n; i++){
list.add(i);
}
int index = 0;
while(n > 1){
index = (index + m - 1) % n; //确定要删除的数字的下标
list.remove(index);
n--;
}
return list.get(0);
}
}
方法二：数学方法
这是著名的著名的约瑟夫环问题，可使用数学解法，时间复杂度为class Solution {
public int lastRemaining(int n, int m) {
int ans = 0;
// 最后一轮剩下2个人，所以从2开始反推
for (int i = 2; i <= n; i++) {
ans = (ans + m) % i;
}
return ans;
}
}
投递阿里云等公司10个岗位 >
查看16道真题和解析