day24 subject ： The finger of the sword Offer 14- I. Cut the rope 、 The finger of the sword Offer 57 - II. And for s Continuous positive sequence of 、 The finger of the sword Offer 62. The last number in the circle

Knowledge point ： mathematics 、 Double pointer , The difficulty is medium 、 Simple 、 Simple

Learning plan link ：「 The finger of the sword Offer」 - Study plan

subject	Knowledge point	difficulty
The finger of the sword Offer 14- I. Cut the rope	mathematics 、 Dynamic programming	secondary
The finger of the sword Offer 57 - II. And for s Continuous positive sequence of	mathematics 、 Double pointer 、 enumeration	Simple
The finger of the sword Offer 62. The last number in the circle	recursive 、 mathematics	Simple

The finger of the sword Offer 14- I. Cut the rope

I'll give you a length of n The rope of , Please cut the rope to the whole length m paragraph （m、n Are integers. ,n>1 also m>1）, The length of each rope is recorded as k[0],k[1]...k[m-1] . Excuse me, k[0]*k[1]*...*k[m-1] What's the maximum possible product ？ for example , When the length of the rope is 8 when , We cut it into lengths of 2、3、3 Three paragraphs of , The maximum product we get here is 18.

Example 1：

 Input : 2
 Output : 1
 explain : 2 = 1 + 1, 1 × 1 = 1

Example 2:

 Input : 10
 Output : 36
 explain : 10 = 3 + 3 + 4, 3 × 3 × 4 = 36

Tips ：

• 2 <= n <= 58

Be careful ： This topic and the main station 343 The question is the same ：https://leetcode-cn.com/problems/integer-break/

Ideas and code

mathematical problem , Didn't do it , Read the derivation of the problem solution Interview questions 14- I. Cut the rope , There are mainly the following points

• When the rope is cut into segments of equal length , The product is the largest .
• Put the rope as far as possible in length 3 Equal division For multi segment , Product maximum
  • If the last paragraph is 2 Retain , No longer split into 1+1
  • If the last paragraph is 1 One copy shall be 3+1 Replace with 2+2
    Then there is the following algorithm flow ：

/** * @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
};

The finger of the sword Offer 57 - II. And for s Continuous positive sequence of

Enter a positive integer target , Output all and as target A sequence of continuous positive integers （ Contains at least two numbers ）.

The numbers in the sequence are arranged from small to large , The different sequences are arranged in descending order according to the first number .

Example 1：

 Input ： target = 9
 Output ： [[2,3,4],[4,5]]

Example 2：

 Input ： target = 15
 Output ： [[1,2,3,4,5],[4,5,6],[7,8]]

Limit ：

• 1 <= target <= 10^5

Ideas and code

Double pointer .

/** * @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
};

The finger of the sword Offer 62. The last number in the circle

0,1,···,n-1 this n Number in a circle , From numbers 0 Start , Delete the... From this circle every time m A digital （ Delete and count from the next number ）. Find the last number left in the circle .

for example ,0、1、2、3、4 this 5 Numbers make a circle , From numbers 0 Start deleting the 3 A digital , Before deleting 4 The numbers in turn are 2、0、4、1, So the last remaining number is 3.

Example 1：

 Input : n = 5, m = 3
 Output : 3

Example 2：

 Input : n = 10, m = 17
 Output : 2

Limit ：

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

Ideas and code

Joseph ring .

/** * @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
};