网站建设 中企动力宜昌,织梦网站优化怎么做,烟台做网站找哪家好,wordpress主题语言包目录
找规律
构建乘积数组
原题链接
解析
核心思想
答案
剪绳子
原题链接
解析
核心思想
答案
圆圈中最后剩下的数字
原题链接
解析
核心思想
答案 找规律
需要通过列举多个示例#xff0c;从多个示例的输入到输出中得到规律去普遍化。
构建乘积数组
给定…目录
找规律
构建乘积数组
原题链接
解析
核心思想
答案
剪绳子
原题链接
解析
核心思想
答案
圆圈中最后剩下的数字
原题链接
解析
核心思想
答案 找规律
需要通过列举多个示例从多个示例的输入到输出中得到规律去普遍化。
构建乘积数组
给定一个数组 A[0,1,…,n-1]请构建一个数组 B[0,1,…,n-1]其中 B[i] 的值是数组 A 中除了下标 i 以外的元素的积, 即 B[i]A[0]×A[1]×…×A[i-1]×A[i1]×…×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都是整数n1并且m1每段绳子的长度记为 k[0],k[1]...k[m - 1] 。请问 k[0]*k[1]*...*k[m - 1] 可能的最大乘积是多少例如当绳子的长度是8时我们把它剪成长度分别为2、3、3的三段此时得到的最大乘积是18。
答案需要取模 1e971000000007如计算初始结果为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(n2){return 1}if(n3){return 2}let max 1while(n4){max*3n-3}return max*n;
}; 方法二动态规范
var cuttingRope function (n) {let res new Array(n 1)res[0] 1res[1] 1for (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 0let j 1while(arr.length!1){if(mj){arr.splice(index,1)i --j0}ijif(iarr.length){i0}}return arr[0]
};方法二找规律递归
var lastRemaining function (n, m) {if (n 1) return 0; //只有一个数的时候那就是下标为0的地方return (lastRemaining(n - 1, m) m) % n;
};
