当前位置：首页 > news >正文

如何在工商局网站上做网登互联网项目

news 2025/7/23 6:07:58

如何在工商局网站上做网登,互联网项目,莱芜网吧恢复营业,做全屏轮播的网站有哪些本文涉及知识点最大公约数并集查找调和级数 LeetCode1998. 数组的最大公因数排序给你一个整数数组 nums ，你可以在 nums 上执行下述操作任意次 ： 如果 gcd(nums[i], nums[j]) > 1 ，交换 nums[i] 和 nums[j] 的位置。其中 gcd(nums…

本文涉及知识点

最大公约数并集查找调和级数

LeetCode1998. 数组的最大公因数排序

给你一个整数数组 nums ，你可以在 nums 上执行下述操作任意次：
如果 gcd(nums[i], nums[j]) > 1 ，交换 nums[i] 和 nums[j] 的位置。其中 gcd(nums[i], nums[j]) 是 nums[i] 和 nums[j] 的最大公因数。
如果能使用上述交换方式将 nums 按非递减顺序排列，返回 true ；否则，返回 false 。
示例 1：
输入：nums = [7,21,3]
输出：true
解释：可以执行下述操作完成对 [7,21,3] 的排序：

交换 7 和 21 因为 gcd(7,21) = 7 。nums = [21,7,3]
交换 21 和 3 因为 gcd(21,3) = 3 。nums = [3,7,21]
示例 2：
输入：nums = [5,2,6,2]
输出：false
解释：无法完成排序，因为 5 不能与其他元素交换。
示例 3：
输入：nums = [10,5,9,3,15]
输出：true
解释：
可以执行下述操作完成对 [10,5,9,3,15] 的排序：
交换 10 和 15 因为 gcd(10,15) = 5 。nums = [15,5,9,3,10]
交换 15 和 3 因为 gcd(15,3) = 3 。nums = [3,5,9,15,10]
交换 10 和 15 因为 gcd(10,15) = 5 。nums = [3,5,9,10,15]

提示：
1 <= nums.length <= 3 * 10⁴
2 <= nums[i] <= 10⁵

并集查找（并查集）

vIndexs[x] 记录 x的最大下标。
一，值相同的连通。只需要和前一个下标连通，不需要连通所有下标。比如：i1,i2,i3。只需要： $i1\leftarrow i2,i2 \leftarrow i3$ ,不需要 $\leftarrow i1$ 。
二，从2开始枚举x，x不必在nums中存在。连通x的倍数。
三，各连通区域的数放在向量中。
四，个向量排序，逆序。
五，根据nums[i]所处的连通区域从向量尾取数据。
六，检查取出的数据是否非降序。

代码

核心代码

class CUnionFind
{
public:CUnionFind(int iSize) :m_vNodeToRegion(iSize){for (int i = 0; i < iSize; i++){m_vNodeToRegion[i] = i;}m_iConnetRegionCount = iSize;}	CUnionFind(vector<vector<int>>& vNeiBo):CUnionFind(vNeiBo.size()){for (int i = 0; i < vNeiBo.size(); i++) {for (const auto& n : vNeiBo[i]) {Union(i, n);}}}int GetConnectRegionIndex(int iNode){int& iConnectNO = m_vNodeToRegion[iNode];if (iNode == iConnectNO){return iNode;}return iConnectNO = GetConnectRegionIndex(iConnectNO);}void Union(int iNode1, int iNode2){const int iConnectNO1 = GetConnectRegionIndex(iNode1);const int iConnectNO2 = GetConnectRegionIndex(iNode2);if (iConnectNO1 == iConnectNO2){return;}m_iConnetRegionCount--;if (iConnectNO1 > iConnectNO2){UnionConnect(iConnectNO1, iConnectNO2);}else{UnionConnect(iConnectNO2, iConnectNO1);}}bool IsConnect(int iNode1, int iNode2){return GetConnectRegionIndex(iNode1) == GetConnectRegionIndex(iNode2);}int GetConnetRegionCount()const{return m_iConnetRegionCount;}vector<int> GetNodeCountOfRegion()//各联通区域的节点数量{const int iNodeSize = m_vNodeToRegion.size();vector<int> vRet(iNodeSize);for (int i = 0; i < iNodeSize; i++){vRet[GetConnectRegionIndex(i)]++;}return vRet;}std::unordered_map<int, vector<int>> GetNodeOfRegion(){std::unordered_map<int, vector<int>> ret;const int iNodeSize = m_vNodeToRegion.size();for (int i = 0; i < iNodeSize; i++){ret[GetConnectRegionIndex(i)].emplace_back(i);}return ret;}
private:void UnionConnect(int iFrom, int iTo){m_vNodeToRegion[iFrom] = iTo;}vector<int> m_vNodeToRegion;//各点所在联通区域的索引,本联通区域任意一点的索引，为了增加可理解性，用最小索引int m_iConnetRegionCount;
};class Solution {
public:bool gcdSort(vector<int>& nums) {m_c = nums.size();const int iMax = *std::max_element(nums.begin(), nums.end());vector<int> vIndexs(iMax + 1, -1);CUnionFind uf(m_c);for (int i = 0; i < nums.size(); i++) {int& index = vIndexs[nums[i]];if (-1 != index) {uf.Union(i, index);}index = i;}for (int x = 2; x <= iMax; x++) {int iPre = vIndexs[x];for (int y =x*2; y <= iMax; y += x) {if (-1 == vIndexs[y]) { continue; }if( -1 != iPre ){ uf.Union(iPre, vIndexs[y]); }iPre = vIndexs[y];}}unordered_map<int, vector<int>> mNodes;for (int i = 0; i < m_c; i++) {mNodes[uf.GetConnectRegionIndex(i)].emplace_back(nums[i]);}for (auto& [tmp, v] : mNodes) {sort(v.begin(), v.end(), std::greater<>());}vector<int> vRet;for (int i = 0; i < m_c; i++) {auto& v = mNodes[uf.GetConnectRegionIndex(i)];vRet.emplace_back(v.back());v.pop_back();}for (int i = 1; i < m_c; i++) {if (vRet[i] < vRet[i - 1]) { return false; }}return true;}int m_c;
};

测试用例

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]);}
}template<class T>
void Assert(const T& t1, const T& t2)
{assert(t1 == t2);
}int main()
{vector<int> nums;{Solution slu;nums = { 5,2,6,2 };auto res = slu.gcdSort(nums);Assert(false, res);}{Solution slu;nums = { 10, 3, 9, 6, 8 };auto res = slu.gcdSort(nums);Assert(true, res);}{Solution slu;nums = { 7,21,3 };auto res = slu.gcdSort(nums);Assert(true, res);}{Solution slu;nums = { 10,5,9,3,15 };auto res = slu.gcdSort(nums);Assert(true, res);}
}

扩展阅读

视频课程

有效学习：明确的目标及时的反馈拉伸区（难度合适），可以先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771

如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

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