当前位置: 首页> 教育> 培训 > 设计高端的国外网站_贸易公司取什么名字_近三天时政热点_上海网站seo诊断

设计高端的国外网站_贸易公司取什么名字_近三天时政热点_上海网站seo诊断

时间:2025/7/11 9:37:44来源:https://blog.csdn.net/he_zhidan/article/details/143091961 浏览次数:0次
设计高端的国外网站_贸易公司取什么名字_近三天时政热点_上海网站seo诊断

本文涉及知识点

C++图论

LeetCode1042. 不邻接植花

有 n 个花园,按从 1 到 n 标记。另有数组 paths ,其中 paths[i] = [xi, yi] 描述了花园 xi 到花园 yi 的双向路径。在每个花园中,你打算种下四种花之一。
另外,所有花园 最多 有 3 条路径可以进入或离开.
你需要为每个花园选择一种花,使得通过路径相连的任何两个花园中的花的种类互不相同。
以数组形式返回 任一 可行的方案作为答案 answer,其中 answer[i] 为在第 (i+1) 个花园中种植的花的种类。花的种类用 1、2、3、4 表示。保证存在答案。
示例 1:
输入:n = 3, paths = [[1,2],[2,3],[3,1]]
输出:[1,2,3]
解释:
花园 1 和 2 花的种类不同。
花园 2 和 3 花的种类不同。
花园 3 和 1 花的种类不同。
因此,[1,2,3] 是一个满足题意的答案。其他满足题意的答案有 [1,2,4]、[1,4,2] 和 [3,2,1]
示例 2:
输入:n = 4, paths = [[1,2],[3,4]]
输出:[1,2,1,2]
示例 3:
输入:n = 4, paths = [[1,2],[2,3],[3,4],[4,1],[1,3],[2,4]]
输出:[1,2,3,4]
提示:
1 <= n <= 104
0 <= paths.length <= 2 * 104
paths[i].length == 2
1 <= xi, yi <= n
xi != yi
每个花园 最多 有 3 条路径可以进入或离开

图论

以任意顺序处理节点都可以,因为最多三个临接点,所有1到4中最多3个数使用,使用未使用的那个数就可以了。
建立临接表的时候,将1到n,改成0到n-1。

代码

核心代码

class CNeiBo
{
public:	static vector<vector<int>> Two(int n, vector<vector<int>>& edges, bool bDirect, int iBase = 0) {vector<vector<int>>  vNeiBo(n);for (const auto& v : edges){vNeiBo[v[0] - iBase].emplace_back(v[1] - iBase);if (!bDirect){vNeiBo[v[1] - iBase].emplace_back(v[0] - iBase);}}return vNeiBo;}	static vector<vector<std::pair<int, int>>> Three(int n, vector<vector<int>>& edges, bool bDirect, int iBase = 0){vector<vector<std::pair<int, int>>> vNeiBo(n);for (const auto& v : edges){vNeiBo[v[0] - iBase].emplace_back(v[1] - iBase, v[2]);if (!bDirect){vNeiBo[v[1] - iBase].emplace_back(v[0] - iBase, v[2]);}}return vNeiBo;}	static vector<vector<int>> Mat(vector<vector<int>>& neiBoMat){vector<vector<int>> neiBo(neiBoMat.size());for (int i = 0; i < neiBoMat.size(); i++){for (int j = i + 1; j < neiBoMat.size(); j++){if (neiBoMat[i][j]){neiBo[i].emplace_back(j);neiBo[j].emplace_back(i);}}}return neiBo;}
};class Solution {public:vector<int> gardenNoAdj(int n, vector<vector<int>>& paths) {auto neiBo = CNeiBo::Two(n, paths, false, 1);vector<int> ans(n);for (int i = 0; i < n; i++) {bool use[5] = { false };for (const auto& next : neiBo[i]) {		use[ans[next]] = true;}for (int j = 1; j <= 4; j++) {if (!use[j]) { ans[i] = j; break; }}}return ans;}};

单元测试

int n;vector<vector<int>> paths;void Check(int n, vector<vector<int>>& paths,vector<int> ans) {auto neiBo = CNeiBo::Two(n, paths, false, 1);for (int i = 0; i < n; i++) {	for (const auto& next : neiBo[i]) {Assert::IsTrue(ans[i] != ans[next]);}			}}TEST_METHOD(TestMethod11){n = 3, paths = { {1,2},{2,3},{3,1} };auto res = Solution().gardenNoAdj(n, paths);Check(n, paths, res);}TEST_METHOD(TestMethod12){n = 4, paths = { {1,2},{3,4} };auto res = Solution().gardenNoAdj(n, paths);Check(n, paths, res);}TEST_METHOD(TestMethod13){n = 4, paths = { {1,2},{2,3},{3,4},{4,1},{1,3},{2,4} };auto res = Solution().gardenNoAdj(n, paths);Check(n, paths, res);}

扩展阅读

我想对大家说的话
工作中遇到的问题,可以按类别查阅鄙人的算法文章,请点击《算法与数据汇总》。
学习算法:按章节学习《喜缺全书算法册》,大量的题目和测试用例,打包下载。重视操作
有效学习:明确的目标 及时的反馈 拉伸区(难度合适) 专注
闻缺陷则喜(喜缺)是一个美好的愿望,早发现问题,早修改问题,给老板节约钱。
子墨子言之:事无终始,无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙,那算法就是他的是睛
失败+反思=成功 成功+反思=成功

视频课程

先学简单的课程,请移步CSDN学院,听白银讲师(也就是鄙人)的讲解。
https://edu.csdn.net/course/detail/38771
如何你想快速形成战斗了,为老板分忧,请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

测试环境

操作系统:win7 开发环境: VS2019 C++17
或者 操作系统:win10 开发环境: VS2022 C++17
如无特殊说明,本算法用**C++**实现。

关键字:设计高端的国外网站_贸易公司取什么名字_近三天时政热点_上海网站seo诊断

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: