算法题--找规律（构建乘积数组、剪绳子、圆圈中最后剩下的数字）
目录
找规律
需要通过列举多个示例，从多个示例的输入到输出中得到规律去普遍化。
构建乘积数组
给定一个数组 A[0,1,…,n-1]，请构建一个数组 B[0,1,…,n-1]，其中 B[i] 的值是数组 A 中除了下标 i 以外的元素的积, 即 B[i]=A[0]×A[1]×…×A[i-1]×A[i+1]×…×A[n-1]。不能使用除法。
示例:
输入: [1,2,3,4,5] 输出: [120,60,40,30,24]
var constructArr = function(a) {
};原题链接
解析
注意for循环的第一步中mul*=a[i]，第一次执行循环体的时候不会执行，第二次循环前会先执行再i++。
核心思想
以示例为例构建5位数组arr每位等于i-1的累乘[1,1,2,6,24]，此时最后一位即对应答案，前一位需要乘5，再前一位需要乘5*4，再前一位需要乘5*4*3，再前一位需要乘5*4*3*2。
答案
var constructArr = function(a) {
const res = []
for (let i = 0, mul = 1; i < a.length; mul *= a[i], i++) {
res[i] = mul
}
for (let i = a.length - 1, mul = 1; i >= 0; mul *= a[i], i--) {
res[i] = res[i] *mul
}
return res
};剪绳子
给你一根长度为 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。
答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。
示例 1：
输入: 2 输出: 1 解释: 2 = 1 + 1, 1 × 1 = 1
示例 2:
输入: 10 输出: 36 解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36
var cuttingRope = function(n) {
};原题链接
解析
找规律通过下图可发现规律为拆分为尽可能多的3相乘，其次为2相乘。
核心思想
方法一（找规律）
前3个为特殊的值直接返回，后面每个值大于4即减一次3并将最大值乘一次3，跳出循环后将最后剩余的值乘以最大值即可
方法二（动态规划）
首先确定动态规划的数组代表什么，res[n]表示绳长为n时剪的乘积的最大值。
然后设定初始值res[0]=res[1]=1，再找到上下层级的关系。当长度大于2时，每次剪长度为j，分为两种情况
1.(n-j)*j 此时为最大值的话不在往下拆分。
2.res[n-j]*j，剪去长度为j时继续往下剪。
由于5米绳子，剪2和剪3是一样的，所以除以2，只用循环一半，所以j从1~n/2即可
结论：res[n]=Math.max((n-j)*j,res[n-j]*j) ，j从1~n/2。
答案
方法一（找规律）
var cuttingRope = function (n) {
if(n<=2){
return 1
}
if(n===3){
return 2
}
let max = 1
while(n>4){
max*=3
n-=3
}
return max*n;
};方法二（动态规范）
var cuttingRope = function (n) {
let res = new Array(n + 1)
res[0] = 1
res[1] = 1
for (let i = 2; i <= n; i++) {
let curMax = 0;
for (let j = 1; j <= i/2; j++) {
curMax = Math.max(curMax, Math.max(j * (i - j), j * res[i - j]));
}
res[i] = curMax;
}
return res[n];
};圆圈中最后剩下的数字
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
var lastRemaining = function (n, m) {
};原题链接
解析
通过列举m为定值，n为多值的的示例，找示例结果中的规律。
f(1,3)=0
f(2,3)=1
f(3,3)=1
f(4,3)=0
f(5,3)=3
核心思想
方法一：
按题目意思设置2个序号一个用于表示当前遍历的数组位置，一个用来表示循环到第几个，循环删除数组中的元素只到数组中只剩余1个元素。
方法二：通过列举当m为定值，n为多个值的示例得到循环递归的关系
f(x,y)=(f(x-1,y)+y)%x
理解为f(x,y)删除第y位的元素后，相当于x-1个元素时向右偏移y位，例如f(5,3)删除第一位元素后从
01234=》0134，此时以3为第一位，相当于3401的四位依次删除的结果，然后由于可能大于数组所以需要%x。
答案
方法一：根据题意循环删除（时间复杂度过不了）
var lastRemaining = function(n, m) {
let arr = new Array(n).fill(0).map((v,i)=>i)
let i = 0
let j = 1
while(arr.length!==1){
if(m===j){
arr.splice(index,1)
i --
j=0
}
i++
j++
if(i===arr.length){
i=0
}
}
return arr[0]
};
方法二：找规律递归
var lastRemaining = function (n, m) {
if (n === 1) return 0; //只有一个数的时候那就是下标为0的地方
return (lastRemaining(n - 1, m) + m) % n;
};