day24 题目：剑指 Offer 14- I. 剪绳子、剑指 Offer 57 - II. 和为 s 的连续正数序列、剑指 Offer 62. 圆圈中最后剩下的数字

知识点：数学、双指针，难度为中等、简单、简单

学习计划链接：「剑指 Offer」 - 学习计划

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

注意：本题与主站 343 题相同：https://leetcode-cn.com/problems/integer-break/

# 思路及代码

数学题，没做出来，看了题解的推导 面试题 14- I. 剪绳子，主要有以下几点

• 将绳子以相等长度切分为多段时，所得乘积最大。
• 尽可能将绳子以 长度3等分 为多段时，乘积最大
  • 若最后一段为 2 保留，不在拆分为 1+1
  • 若最后一段为 1 应将一份 3+1 换为 2+2
    则有以下算法流程：

/**

 * @param {number} n

 * @return {number}

 */

var cuttingRope = function(n) {

    if(n <= 3) return n-1

    let [a, b] = [Math.floor(n/3), n%3]

    if(b === 0) return Math.pow(3, a)

    if(b === 1) return Math.pow(3, a-1) * 4

    return Math.pow(3, a) * 2

};

# 剑指 Offer 57 - II. 和为 s 的连续正数序列

输入一个正整数  target  ，输出所有和为  target  的连续正整数序列（至少含有两个数）。

序列内的数字由小到大排列，不同序列按照首个数字从小到大排列。

示例 1：

输入： target = 9
输出： [[2,3,4],[4,5]]

示例 2：

输入： target = 15
输出： [[1,2,3,4,5],[4,5,6],[7,8]]

限制：

• 1 <= target <= 10^5

# 思路及代码

双指针。

/**

 * @param {number} target

 * @return {number[][]}

 */

var findContinuousSequence = function(target) {

    let res = []

    let [l, r] = [1, 2]

    while(l < r) {

        let sum = (l+r) * (r-l+1) / 2

        if(sum === target) { 

            let temp = []

            for(let i = l; i <= r; i++)

                temp.push(i)

            res.push(temp)

            ++l

        } else if(sum < target) ++r

        else ++l

    }

    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。

示例 1：

输入: n = 5, m = 3
输出: 3

示例 2：

输入: n = 10, m = 17
输出: 2

限制：

• 1 <= n <= 10^5
• 1 <= m <= 10^6

# 思路及代码

约瑟夫环。

/**

 * @param {number} n

 * @param {number} m

 * @return {number}

 */

var lastRemaining = function(n, m) {

   let res = 0

   for(let i = 2; i <= n; i++) {

       res = (res + m) % i

   }

   return res

};