Leetcode 1203. 项目管理

小灰灰 2023-02-09 14:26 8阅读 0赞

### Leetcode 1203. 项目管理 ###

*  1、问题分析
 *  2、问题解决
 *  3、总结

# 1、问题分析 #

题目链接：[https://leetcode-cn.com/problems/sort-items-by-groups-respecting-dependencies/][https_leetcode-cn.com_problems_sort-items-by-groups-respecting-dependencies]  
   整体思路就是先建立 m+1 个分组集和，然后根据每个节点的分组，完成分组集和的初始化。包括 该分组有哪些节点、该分组的前置分组是什么。最后遍历该分组 ----> 遍历分组又分为遍历节点。代码我已经进行了详细的注释，理解应该没有问题，读者可以作为参考，如果看不懂(可以多看几遍)，欢迎留言哦！我看到会解答一下。  
   这是我花半天的时间才 `AC` 的。中途一直没有思路，一直想放弃，还好坚持了下来。愿各位小伙伴都能`持之以恒，取得理想的结果！`

# 2、问题解决 #

笔者以`C++`方式解决。

#include "iostream"
    
    using namespace std;
    
    #include "algorithm"
    #include "vector"
    #include "queue"
    #include "set"
    #include "map"
    #include "cstring"
    #include "stack"
    
    
    /** * 整体思路就是先建立 m+1 个分组集和，然后根据每个节点的分组，完成分组集和的初始化。 * 包括 该分组有哪些节点、该分组的前置分组是什么。 * 最后遍历该分组 ----> 遍历分组又分为遍历节点 */
    class Solution { 
    private:
    	// 定义分组结构体
    	struct GroupChen { 
    		// 分组id，编号
    		int belong_group = -1;
    		// 该分组有哪些数据 在示例 1 中 如分组 0 ，有 3,4,6 元素
    		// 这里使用 set 是为了防止数据重复
    		set<int> dataChens;
    		// 该分组的前置分组，即访问该分组时，必须访问所有的前置分组
    		// 示例1 中，0号分组的前置分组为 0 (包括自身)
    		set<GroupChen *> beforeGroupChens;
    	};
    
    	// 标记每个节点是否访问过 0 未访问 1 正在访问 2 已经访问
    	// 1 正在访问 的目的是防止图中有环 及时退出
    	vector<int> vis;
    	// 标记每个分组是否访问过 0 未访问 1 正在访问 2 已经访问
    	// 1 正在访问 的目的是防止图中有环 及时退出
    	vector<int> visGroup;
    
    	// 存储最终结果
    	vector<int> result;
    
    	// 剪枝 快速退出
    	int flag = 0;
    
    	// 共用节点数
    	int n_all;
    
    
    public:
    	vector<int> sortItems(int n, int m, vector<int> &group, vector<vector<int>> &beforeItems) { 
    		// 定义分组集和
    		vector<GroupChen *> groups;
    		// 动态初始化访问数组
    		vis.resize(n + 1);
    		visGroup.resize(m + 1);
    		//初始化节点数目
    		n_all = n;
    		// 初始化分组，注意这里 i <= m; 有个等于号，
    		// 在算法实现过程中，我们将没有分组的编号
    		// 即 group==-1的分组 放到 group=m 分组中
    		for (int i = 0; i <= m; ++i) { 
    			//新建一个节点
    			GroupChen *pChen = new GroupChen;
    			//设值节点编号
    			pChen->belong_group = i;
    			//将节点加入分组集和中
    			groups.push_back(pChen);
    		}
    
    		// 设置分组集和中 beforeGroupChens 和 dataChens 数据
    		for (int i = 0; i < n; ++i) { 
    			// 设置 dataChens 数据
    			// 这里注意分组是 -1 的情况，如果是 -1 则自动放入 m 号分组
    			if (group[i] != -1) { 
    				groups[group[i]]->dataChens.insert(i);
    			}
    			else { 
    				groups[m]->dataChens.insert(i);
    			}
    
    			// 设置 beforeGroupChens 数据
    			// 如果 beforeItems不为空才有设置的意义
    			if (!beforeItems[i].empty()) { 
    				// 遍历 beforeItems 前置节点 数组
    				for (int j = 0; j < beforeItems[i].size(); ++j) { 
    					// 这里仍然是对 group 为 -1 的情况进行处理
    					// 如果是 -1 则自动放入 m 号分组
    					// 否则仍然放在 group[?] 分组中
    					// beforeItems[i][j] 代表第 i 个节点， 第 j 个前驱
    					// group[beforeItems[i][j]] 代表该前驱的分组
    					int i1 = group[beforeItems[i][j]];
    					i1 = i1 == -1 ? m : i1;
    					// 这里仍然是对 group 为 -1 的情况进行处理
    					// 如果是 -1 则自动放入 m 号分组
    					if (group[i] != -1) { 
    						// 插入 group[i] 号分组的前驱分组
    						groups[group[i]]->beforeGroupChens.insert(groups[i1]);
    					}
    					else if (group[i] == -1) { 
    						groups[m]->beforeGroupChens.insert(groups[i1]);
    					}
    				}
    			}
    		}
    
    		// 遍历 m+1 个分组集和
    		for (int i = 0; i <= m; ++i) { 
    			// 没有解决方案，快速结束
    			if (flag == 1) { 
    				// 根据题目意思 返回空数组
    				result.clear();
    				return result;
    			}
    			// 如果某个 分组没有访问 则访问该 分组
    			// i 代表第 i 个分组
    			if (visGroup[i] == 0) { 
    				findAllGroups(groups, m, beforeItems, i);
    			}
    
    		}
    
    		// 没有解决方案，快速结束
    		if (flag == 1) { 
    			// 根据题目意思 返回空数组
    			result.clear();
    			return result;
    		}
    		return result;
    	}
    
    	/** * 访问 第 i 个分组 * @param groups 分组集和 * @param m 分组个数 * @param beforeItems * @param i 代表第 i 个分组 */
    	void findAllGroups(vector<GroupChen *> &groups, int m, vector<vector<int>> &beforeItems, int i) { 
    		// 说明有环，直接返回false
    		if (visGroup[i] == 1) { 
    			// 设置标志位
    			flag = 1;
    			return;
    		}
    		// 正在访问该节点
    		visGroup[i] = 1;
    		try { 
    			// 没有解决方案
    			if (flag == 1) { 
    				return;
    			}
    
    			// 如果该分组没有前驱分组 说明可以直接访问
    			if (groups[i]->beforeGroupChens.empty()) { 
    				for (auto it = groups[i]->dataChens.begin(); it != groups[i]->dataChens.end(); it++) { 
    					// 如果该分组中的 *it 节点没有被访问，则访问该节点，
    					if (vis[*it] == 0) { 
    						result.push_back(*it);
    						// 同时将访问状态设置成 2
    						vis[*it] = 2;
    						// 由于没有对重复元素，缺少元素等做判断，这里直接使用最简单直接的方式
    						// 只要结果数组中的值的个数大于 节点数量，说明肯定没有解决方案，提前结束
    						if (result.size() > n_all) { 
    							flag = 1;
    							return;
    						}
    					}
    				}
    			}
    			// 只有一个前驱分组状况
    			else if (groups[i]->beforeGroupChens.size() == 1) { 
    				for (auto it = groups[i]->beforeGroupChens.begin();
    					it != groups[i]->beforeGroupChens.end(); it++) { 
    					if ((*it)->belong_group == i) { 
    						// 如果正好是 自己本身 则遍历该分组
    						dfs(groups, i, beforeItems);
    					}
    					else { 
    						// 如果是其他分组，则先遍历该分组，即先遍历前置分组
    						findAllGroups(groups, m, beforeItems, (*it)->belong_group);
    						// 如果在遍历过程中，出现没有解决方案的情况，直接结束
    						if (flag == 1) { 
    							return;
    						}
    						// 注意访问完前置分组，一定要再次访问自身分组
    						dfs(groups, i, beforeItems);
    					}
    				}
    
    			}
    			// 如果前置分组有多个
    			else { 
    				for (auto it = groups[i]->beforeGroupChens.begin();
    					it != groups[i]->beforeGroupChens.end(); it++) { 
    					// 快速结束
    					if (flag == 1) { 
    						return;
    					}
    					// 因为上面我们定义前置分组里面会有自己分组，其实是不严格的
    					// 这里遇到是自身分组的时候 先跳过自身分组的遍历
    					if ((*it)->belong_group == i) { 
    						continue;
    					}
    					else { 
    						// 如果是其他分组，直接访问该分组
    						findAllGroups(groups, m, beforeItems, (*it)->belong_group);
    					}
    				}
    				// 注意访问完前置分组，一定要再次访问自身分组
    				dfs(groups, i, beforeItems);
    			}
    			//访问分组完成，访问状态变成2，即访问完成
    			visGroup[i] = 2;
    		}
    		catch (exception e) { 
    			// 出现异常直接 没有解决方案 退出
    			flag = 1;
    			return;
    		}
    	}
    
    	/** * 遍历第 index 个分组 * @param groups * @param index 第 index 个分组 * @param beforeItems */
    	void dfs(vector<GroupChen *> &groups, int index, vector<vector<int>> &beforeItems) { 
    		// 取出该分组
    		GroupChen *pChen = groups[index];
    
    		// 遍历该分组中的所有节点
    		for (auto it = pChen->dataChens.begin(); it != pChen->dataChens.end(); it++) { 
    			// 快速结束
    			if (flag == 1) { 
    				return;
    			}
    			// 访问该节点
    			dfs2(*it, beforeItems);
    		}
    	}
    
    	/** * 访问同一组内元素 * @param u 访问的是节点 u * @param beforeItems */
    	void dfs2(int u, vector<vector<int>> &beforeItems) { 
    		// 如果该节点已经访问过 或者该已经是 没有解决方案状态 直接退出
    		if (vis[u] == 2 || flag == 1) { 
    			return;
    		}
    
    		// 说明图有环 没有解决方案 直接退出
    		if (vis[u] == 1) { 
    			flag = 1;
    			return;
    		}
    
    		// 第一次访问，还没有结束
    		vis[u] = 1;
    
    		// 如果该节点没有前置节点，直接访问
    		if (beforeItems[u].empty()) { 
    			result.push_back(u);
    			//设置节点访问状态为完成
    			vis[u] = 2;
    			// 由于没有对重复元素，缺少元素等做判断，这里直接使用最简单直接的方式
    			// 只要结果数组中的值的个数大于 节点数量，说明肯定没有解决方案，提前结束
    			if (result.size() > n_all) { 
    				flag = 1;
    				return;
    			}
    		}
    		// 如果节点有前置节点
    		else { 
    			for (int i = 0; i < beforeItems[u].size(); ++i) { 
    				// 递归 先访问前置节点
    				dfs2(beforeItems[u][i], beforeItems);
    			}
    
    			// 由于没有对重复元素，缺少元素等做判断，这里直接使用最简单直接的方式
    			// 只要结果数组中的值的个数大于 节点数量，说明肯定没有解决方案，提前结束
    			if (result.size() > n_all) { 
    				flag = 1;
    				return;
    			}
    			// 访问完前置节点之后，再访问 u 号节点
    			else { 
    				result.push_back(u);
    				// 同时将节点访问状态设置成 2 ，即该节点访问完成
    				vis[u] = 2;
    				// 由于没有对重复元素，缺少元素等做判断，这里直接使用最简单直接的方式
    				// 只要结果数组中的值的个数大于 节点数量，说明肯定没有解决方案，提前结束
    				if (result.size() > n_all) { 
    					flag = 1;
    					return;
    				}
    			}
    		}
    	}
    };
    
    
    int main() { 
    	// int n = 8, m = 2;
    	int n = 5, m = 3;
    	// vector<int> group = { -1, -1, 1, 0, 0, 1, 0, -1 };
    	// vector<vector<int>> beforeItems = { {},
    	// { 6 },
    	// { 5 },
    	// { 6 },
    	// { 3, 6 },
    	// {},
    	// {},
    	// {} };
    
    	// vector<int> group = {-1, -1, 1, 0, 0, 1, 0, -1};
    	// vector<vector<int>> beforeItems = { {},
    	// {6},
    	// {5},
    	// {6},
    	// {3},
    	// {},
    	// {4},
    	// {}};
    
    
    	// vector<int> group = { -1, 0, 0, -1 };
    	// vector<vector<int>> beforeItems = { {},
    	// { 0 },
    	// { 1, 3 },
    	// { 2 } };
    
    	vector<int> group = {  0,
    		0,
    		2,
    		1,
    		0 };
    	vector<vector<int>> beforeItems = {  {  3 },
    	{ },
    	{ },
    	{ },
    	{  1, 3, 2 } };
    
    	Solution *pSolution = new Solution;
    	const vector<int> &vector1 = pSolution->sortItems(n, m, group, beforeItems);
    
    	for (int i = 0; i < vector1.size(); ++i) { 
    		cout << vector1[i] << " ";
    	}
    	cout << endl;
    
    	system("pause");
    	return 0;
    }

运行结果

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNTEwNTk3_size_16_color_FFFFFF_t_70]

有点菜，有时间再优化一下。

# 3、总结 #

书上的代码直接运行绝大部分是对的，但是总有一些软件的更新使得作者无能为力。之前的API是对的，但是之后就废弃了或修改了是常有的事。所以我们需要跟踪源代码。这只是一个小小的问题，如果没有前辈的无私奉献，很难想象我们自己一天能学到多少内容。感谢各位前辈的辛勤付出，让我们少走了很多的弯路！

点个赞再走呗！欢迎留言哦！

[https_leetcode-cn.com_problems_sort-items-by-groups-respecting-dependencies]: https://leetcode-cn.com/problems/sort-items-by-groups-respecting-dependencies/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNTEwNTk3_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200519154842823.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNTEwNTk3,size_16,color_FFFFFF,t_70