【栈 最小公倍数 最大公约数】2197. 替换数组中的非互质数

简介: 【栈 最小公倍数 最大公约数】2197. 替换数组中的非互质数

本文涉及知识点

最小公倍数 最大公约数

LeetCode2197. 替换数组中的非互质数

给你一个整数数组 nums 。请你对数组执行下述操作:

从 nums 中找出 任意 两个 相邻 的 非互质 数。

如果不存在这样的数,终止 这一过程。

否则,删除这两个数,并 替换 为它们的 最小公倍数(Least Common Multiple,LCM)。

只要还能找出两个相邻的非互质数就继续 重复 这一过程。

返回修改后得到的 最终 数组。可以证明的是,以 任意 顺序替换相邻的非互质数都可以得到相同的结果。

生成的测试用例可以保证最终数组中的值 小于或者等于 108 。

两个数字 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 <= 105

1 <= nums[i] <= 105

生成的测试用例可以保证最终数组中的值 小于或者等于 108

题解

用栈存放结果,因为返回值是向量,所以用向量模拟。

依次处理nums[i],

如果栈顶元素和当前数非互质,当前数替换为lcm(当前数,栈顶元素)。持续这个过程,直到条件不满足。

时间复杂度:O(n)

有两层循环,但第二层循环只出栈一次。所以总时间复杂度是O(n)。

代码

核心代码

class Solution {
public:
  vector<int> replaceNonCoprimes(vector<int>& nums) {
    vector<int> vRet;
    for (const auto& n : nums) {
      int tmp = n;
      while (vRet.size() && (gcd(vRet.back(), tmp) != 1)) {
        tmp = lcm(vRet.back(), tmp);
        vRet.pop_back();
      }
      vRet.emplace_back(tmp);
    }
    return vRet;
  }
};

测试用例

template<class T>
void Assert(const T& t1, const T& t2)
{
    assert(t1 == t2);
}
template<class T>
void Assert(const vector<T>& v1, const vector<T>& v2)
{
    if (v1.size() != v2.size())
    {
        assert(false);
        return;
    }
    for (int i = 0; i < v1.size(); i++)
    {
        Assert(v1[i], v2[i]);
    }
}
int main()
{
  vector<int> nums;
  {
    Solution sln;
    nums = { 6,4,3,2,7,6,2 };
    auto res = sln.replaceNonCoprimes(nums);
    Assert({ 12,7,6 }, res);
  }
  {
    Solution sln;
    nums = { 2,2,1,1,3,3,3 };
    auto res = sln.replaceNonCoprimes(nums);
    Assert({ 2,1,1,3 }, res);
  }
  {
    Solution sln;
    nums = { 287,41,49,287,899,23,23,20677,5,825 };
    auto res = sln.replaceNonCoprimes(nums);
    Assert({ 2009,20677,825 }, res);
  }
}


我想对大家说的话
闻缺陷则喜是一个美好的愿望,早发现问题,早修改问题,给老板节约钱。
子墨子言之:事无终始,无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙,那算法就是他的是睛

测试环境

操作系统:win7 开发环境: VS2019 C++17

或者 操作系统:win10 开发环境: VS2022 C++17

如无特殊说明,本算法用**C++**实现。

相关文章
|
27天前
|
C语言
【数据结构】栈和队列(c语言实现)(附源码)
本文介绍了栈和队列两种数据结构。栈是一种只能在一端进行插入和删除操作的线性表,遵循“先进后出”原则;队列则在一端插入、另一端删除,遵循“先进先出”原则。文章详细讲解了栈和队列的结构定义、方法声明及实现,并提供了完整的代码示例。栈和队列在实际应用中非常广泛,如二叉树的层序遍历和快速排序的非递归实现等。
123 9
|
18天前
|
存储 算法
非递归实现后序遍历时,如何避免栈溢出?
后序遍历的递归实现和非递归实现各有优缺点,在实际应用中需要根据具体的问题需求、二叉树的特点以及性能和空间的限制等因素来选择合适的实现方式。
23 1
|
5天前
|
存储 缓存 算法
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式,强调了合理选择数据结构的重要性,并通过案例分析展示了其在实际项目中的应用,旨在帮助读者提升编程能力。
26 5
|
21天前
|
存储 算法 Java
数据结构的栈
栈作为一种简单而高效的数据结构,在计算机科学和软件开发中有着广泛的应用。通过合理地使用栈,可以有效地解决许多与数据存储和操作相关的问题。
|
24天前
|
存储 JavaScript 前端开发
执行上下文和执行栈
执行上下文是JavaScript运行代码时的环境,每个执行上下文都有自己的变量对象、作用域链和this值。执行栈用于管理函数调用,每当调用一个函数,就会在栈中添加一个新的执行上下文。
|
26天前
|
存储
系统调用处理程序在内核栈中保存了哪些上下文信息?
【10月更文挑战第29天】系统调用处理程序在内核栈中保存的这些上下文信息对于保证系统调用的正确执行和用户程序的正常恢复至关重要。通过准确地保存和恢复这些信息,操作系统能够实现用户模式和内核模式之间的无缝切换,为用户程序提供稳定、可靠的系统服务。
47 4
|
1月前
|
算法 安全 NoSQL
2024重生之回溯数据结构与算法系列学习之栈和队列精题汇总(10)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构王道第3章之IKUN和I原达人之数据结构与算法系列学习栈与队列精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
|
2月前
数据结构(栈与列队)
数据结构(栈与列队)
20 1
|
2月前
|
存储 JavaScript 前端开发
为什么基础数据类型存放在栈中,而引用数据类型存放在堆中?
为什么基础数据类型存放在栈中,而引用数据类型存放在堆中?
72 1
|
2月前
【数据结构】-- 栈和队列
【数据结构】-- 栈和队列
17 0