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

🔗题目链接：https://leetcode-cn.com/problems/jian-sheng-zi-lcof

思路

动态规划，创建数组 dp，其中 dp[i] 表示将正整数 i 拆分成至少两个正整数的和之后，这些正整数的最大乘积。
特别地，0 不是正整数，1 是最小的正整数，0 和 1 都不能拆分，因此 $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])$ 。由于 j 的取值范围是 1 到 i−1，需要遍历所有的 j 得到 dp[i] 的最大值，因此可以得到状态转移方程如下：

$dp[i]=max\left\{ max(j×(i−j),j×dp[i−j]) \right\}, (i\leq j < i)$

最终得到 dp[n] 的值即为将正整数 n 拆分成至少两个正整数的和之后，这些正整数的最大乘积。

🔗参考题解：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~n-1存入一个ArrayList集合中，找到要删除的位置，移除集合中的元素，直到只剩下一个元素，但这种方法的时间复杂度 $O(n^2)$

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);
    }
}

方法二：数学方法

这是著名的著名的约瑟夫环问题，可使用数学解法，时间复杂度为 $O(n)$ .

参考题解：https://leetcode-cn.com/problems/yuan-quan-zhong-zui-hou-sheng-xia-de-shu-zi-lcof/solution/javajie-jue-yue-se-fu-huan-wen-ti-gao-su-ni-wei-sh/

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;
    }
}