顺义网站建设推广优化seo,企业宽带,怎么做有优惠券的网站,外包加工项目说在前面 #x1f388;不知道大家对于算法的学习是一个怎样的心态呢#xff1f;为了面试还是因为兴趣#xff1f;不管是出于什么原因#xff0c;算法学习需要持续保持。 题目描述
给你一个整数数组 nums 和一个整数 k #xff0c;请你统计并返回 nums 的子数组中元素的最…说在前面 不知道大家对于算法的学习是一个怎样的心态呢为了面试还是因为兴趣不管是出于什么原因算法学习需要持续保持。 题目描述
给你一个整数数组 nums 和一个整数 k 请你统计并返回 nums 的子数组中元素的最大公因数等于 k 的子数组数目。
子数组 是数组中一个连续的非空序列。
数组的最大公因数 是能整除数组中所有元素的最大整数。
示例 1
输入nums [9,3,1,2,6,3], k 3
输出4
解释nums 的子数组中以 3 作为最大公因数的子数组如下
- [9,3,1,2,6,3]
- [9,3,1,2,6,3]
- [9,3,1,2,6,3]
- [9,3,1,2,6,3]示例 2
输入nums [4], k 7
输出0
解释不存在以 7 作为最大公因数的子数组。提示
1 nums.length 10001 nums[i], k 10^9
思路分析
首先我们要先理解一下题目的意思题目会给我们一个整数数组 nums 和一个整数 k我们需要统计并返回 nums 的子数组中元素的最大公因数等于 k 的子数组数目。
一个序列中最大公因数等于k需要满足以下条件
1、所有元素均为k的倍数2、至少一个元素与其他所有元素的最大公因数都是k。
知道了这两个条件之后我们便可以开始编写代码了
1、记录每个位置前后连续元素为k的倍数的个数
因为一个序列中最大公因数等于k时序列中所有元素均为k的倍数所以我们可以先统计每个位置前后连续元素为k的倍数的个数。
const q1 new Array(nums.length).fill(0);
const q2 new Array(nums.length).fill(0);
for(let i 0; i q1.length; i){if(i 0){if(nums[i] % k 0) q1[i] 1;if(nums[q2.length - 1] % k 0) q2[q2.length - 1] 1;}else{if(nums[i] % k 0) q1[i] q1[i-1] 1;if(nums[q2.length - 1 - i] % k 0) q2[q2.length - 1 - i] q2[q2.length - i] 1;}
}2、遍历找到两个相邻元素之间的最大公因数为k的位置
如果一个序列中有两个元素的最大公因数为k,且其他元素均可以被k整除那么这个序列所有元素的最大公因数也为k,所以我们可以找到任意一组最大公因数为k的元素来进行计算。
for(let i 0; i nums.length; i){if(nums[i] k) res;if(i nums.length - 1 gcd(nums[i],nums[i 1]) k){……}
}3、计算当前位置可以组成满足条件的序列数。
如果找到一组相邻的元素他们的最大公因数为k,那么从当前位置向两边延伸找到连续为k的倍数的元素组成的序列都为满足条件的序列。
如nums [3,3,4,1,2],k 1
(1)、情况1左边序列数 * 右边序列数 总序列数
我们可以看到在下标i为1的时候gcd(nums[i],nums[i 1]) k此时从i往左看我们可以得到两个连续元素均为k的倍数[3,3]从i 1往右看我们可以得到三个连续元素均为k的倍数[4,1,2]。 我们只需计算两个数组的组合数即可这里的子序列需要是连续的所以我们可以得到的组合数应该是2 * 3 6;分别为[3,4],[3,4,1],[3,4,1,2],[3,3,4],[3,3,4,1],[3,3,4,1,2];
(2)、情况2左边序列数 - 上一次计算的左边序列数 * 右边序列数 总序列数
第二个满足条件的下标i为2此时从i往左看我们可以得到两个连续元素均为k的倍数[3,3,4]从i 1往右看我们可以得到三个连续元素均为k的倍数[1,2]。 我们只需计算两个数组的组合数即可这里的子序列需要是连续的所以我们可以得到的组合数应该是2 * 3 6;分别为[4,1],[4,1,2],[3,4,1],[3,4,1,2],[3,3,4,1],[3,3,4,1,2]这时我们会发现当前得出的结果与上一次得到的结果中有重复的子序列[3,4,1],[3,4,1,2],[3,3,4,1],[3,3,4,1,2],因为左边的序列中[3,3]在上一次计算中已经计算过了所以我们需要将这两个减去可以得到(3 - 2) * 2 2所以当前位置可以得到新的组合数为2;
(3)、子数组长度为1
题目中是这样定义的子数组子数组 是数组中一个连续的非空序列。所以在遇到nums[i] k时该元素可以单独成组。
let res 0;
let flag 0;
for(let i 0; i nums.length; i){if(nums[i] k) res;if(i nums.length - 1 gcd(nums[i],nums[i 1]) k){res (i 0 ? (q1[i] - flag) : 1) * (q2[i 1] || 1);flag q1[i];}if(nums[i] % k ! 0) flag 0;
}完整AC代码如下
AC代码
/*** param {number[]} nums* param {number} k* return {number}*/var subarrayGCD function(nums, k) {const gcd (a, b) {return a % b 0 ? b : gcd(b, a % b);}const q1 new Array(nums.length).fill(0);const q2 new Array(nums.length).fill(0);for(let i 0; i q1.length; i){if(i 0){if(nums[i] % k 0) q1[i] 1;if(nums[q2.length - 1] % k 0) q2[q2.length - 1] 1;}else{if(nums[i] % k 0) q1[i] q1[i-1] 1;if(nums[q2.length - 1 - i] % k 0) q2[q2.length - 1 - i] q2[q2.length - i] 1;}}let res 0;let flag 0;for(let i 0; i nums.length; i){if(nums[i] k) res;if(i nums.length - 1 gcd(nums[i],nums[i 1]) k){res (i 0 ? (q1[i] - flag) : 1) * (q2[i 1] || 1);flag q1[i];}if(nums[i] % k ! 0) flag 0;}return res;
};公众号
关注公众号『前端也能这么有趣』获取更多有趣内容。
说在后面 这里是 JYeontu现在是一名前端工程师有空会刷刷算法题平时喜欢打羽毛球 平时也喜欢写些东西既为自己记录 也希望可以对大家有那么一丢丢的帮助写的不好望多多谅解 写错的地方望指出定会认真改进 偶尔也会在自己的公众号『前端也能这么有趣』发一些比较有趣的文章有兴趣的也可以关注下。在此谢谢大家的支持我们下文再见 。
