【亂序版 ● 劍指offer】每日算法題打卡題解——數學 （題号14,57）

打卡day18

啊，這次發晚了已經不是28号了，(T＿T)

目 錄

• • 第一題：劍指 Offer 14- I. 剪繩子
  • 第二題：劍指 Offer 57 - II. 和為s的連續正數序列

第一題：劍指 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

來源：力扣（LeetCode）

連結：https://leetcode-cn.com/problems/jian-sheng-zi-lcof

解題思路：

數學推導總體分為兩步：① 當所有繩段長度相等時，乘積最大。② 最優的繩段長度為 3 。

具體推導過程見大佬解析：https://leetcode-cn.com/problems/jian-sheng-zi-lcof/solution/mian-shi-ti-14-i-jian-sheng-zi-tan-xin-si-xiang-by/

java代碼：

class Solution {
    public int cuttingRope(int n) {
        if (n==1 || n==2)
            return 1;
        if (n==3)
            return 2;
        int sum=1;
        while (n>4){
            sum*=3;
            n-=3;
        }
        return sum*n;
    }
}
           

第二題：劍指 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

來源：力扣（LeetCode）

連結：添加連結描述

解題思路：

可以用求和公式，或滑動視窗（雙指針）

java代碼：

//求和公式
class Solution {
    public int[][] findContinuousSequence(int target) {
        int i = 1;
        double j = 2.0;
        List<int[]> res = new ArrayList<>();
        while(i < j) {
            //求根公式
            j = (-1 + Math.sqrt(1 + 4 * (2 * target + (long) i * i - i))) / 2;
            if(i < j && j == (int)j) {
                int[] ans = new int[(int)j - i + 1];
                for(int k = i; k <= (int)j; k++)
                    ans[k - i] = k;
                res.add(ans);
            }
            i++;
        }
        return res.toArray(new int[0][]);
    }
}


//雙指針的
class Solution {
    public int[][] findContinuousSequence(int target) {
        int r = 1, l = 2, sum = 3;//定義左右指針
        List<int[]> res = new ArrayList<>();
        while(r < l) {
            if(sum == target) {//sum剛好等于目标值是
                int[] ans = new int[l - r + 1];
                for(int i = r; i <= l; i++){
                    ans[i - r] = i;
                }
                res.add(ans);
            }
            if(sum >= target) {
                sum -= r;
                r++;
            } 
            else {
                l++;
                sum += l;
            }
        }
        return res.toArray(new int[0][]);
    }
}