化州网站建设公司,小游戏网站欣赏,网站首页图片轮转,wordpress商品采集插件文章目录1. 题目2. 解题1. 题目
给你一个整数数组 nums 。请你对数组执行下述操作#xff1a;
从 nums 中找出 任意 两个 相邻 的 非互质 数。如果不存在这样的数#xff0c;终止 这一过程。否则#xff0c;删除这两个数#xff0c;并 替换 为它们的 最小公倍数#xff…
文章目录1. 题目2. 解题1. 题目
给你一个整数数组 nums 。请你对数组执行下述操作
从 nums 中找出 任意 两个 相邻 的 非互质 数。如果不存在这样的数终止 这一过程。否则删除这两个数并 替换 为它们的 最小公倍数Least Common MultipleLCM。只要还能找出两个相邻的非互质数就继续 重复 这一过程。
返回修改后得到的 最终 数组。 可以证明的是以 任意 顺序替换相邻的非互质数都可以得到相同的结果。
生成的测试用例可以保证最终数组中的值 小于或者等于 10^8 。
两个数字 x 和 y 满足 非互质数 的条件是GCD(x, y) 1 其中 GCD(x, y) 是 x 和 y 的 最大公约数 。
示例 1
输入nums [6,4,3,2,7,6,2]
输出[12,7,6]
解释
- (6, 4) 是一组非互质数且 LCM(6, 4) 12 。得到 nums [12,3,2,7,6,2] 。
- (12, 3) 是一组非互质数且 LCM(12, 3) 12 。得到 nums [12,2,7,6,2] 。
- (12, 2) 是一组非互质数且 LCM(12, 2) 12 。得到 nums [12,7,6,2] 。
- (6, 2) 是一组非互质数且 LCM(6, 2) 6 。得到 nums [12,7,6] 。
现在nums 中不存在相邻的非互质数。
因此修改后得到的最终数组是 [12,7,6] 。
注意存在其他方法可以获得相同的最终数组。示例 2
输入nums [2,2,1,1,3,3,3]
输出[2,1,1,3]
解释
- (3, 3) 是一组非互质数且 LCM(3, 3) 3 。得到 nums [2,2,1,1,3,3] 。
- (3, 3) 是一组非互质数且 LCM(3, 3) 3 。得到 nums [2,2,1,1,3] 。
- (2, 2) 是一组非互质数且 LCM(2, 2) 2 。得到 nums [2,1,1,3] 。
现在nums 中不存在相邻的非互质数。
因此修改后得到的最终数组是 [2,1,1,3] 。
注意存在其他方法可以获得相同的最终数组。提示
1 nums.length 10^5
1 nums[i] 10^5
生成的测试用例可以保证最终数组中的值 小于或者等于 10^8 。来源力扣LeetCode 链接https://leetcode-cn.com/problems/replace-non-coprime-numbers-in-array 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。 2. 解题
题目说了 以 任意 顺序替换相邻的非互质数都可以得到相同的结果使用 栈 放入至少两个数字从栈顶开始检查是否是 非互质数如果是删除栈顶2个数push LCM 到栈顶重复该过程直到不满足退出再加入下一个数到栈顶
class Solution {
public:vectorint replaceNonCoprimes(vectorint nums) {stackint s;for(int i int(nums.size())-1; i0; --i){s.push(nums[i]);while(s.size() 2){int a s.top();s.pop();int b s.top();s.pop();int g __gcd(a, b);if(g 1){s.push(1LL*a*b/g);}else{s.push(b);s.push(a);break;}}}vectorint ans;while(!s.empty()){ans.push_back(s.top());s.pop();}return ans;}
};212 ms 129.1 MB C 我的CSDN博客地址 https://michael.blog.csdn.net/
长按或扫码关注我的公众号Michael阿明一起加油、一起学习进步
