无法与网站建立安全连接,贵州省住房和城乡建设厅官方网站首页,单职业传奇网站,做搜狗网站点击赚钱目录
题目#xff1a;
示例#xff1a;
分析#xff1a;
代码#xff1a; 题目#xff1a; 示例#xff1a; 分析#xff1a;
这是一道程序设计类的题目#xff0c;题目比较长#xff0c;我稍微概括一下。
构造函数中给我们一个数组#xff0c;第i个元素表示第…目录
题目
示例
分析
代码 题目 示例 分析
这是一道程序设计类的题目题目比较长我稍微概括一下。
构造函数中给我们一个数组第i个元素表示第i个节点的父节点让我们以此数组来构造一棵树不是二叉树。
类中有三个成员函数第一个是上锁函数给我们一个节点值以及一个用户ID让我们对节点以用户的名义上锁前提是这个节点没上锁。
第二个是解锁函数给我们一个节点值和一个用户ID让我们把这个节点解锁前提是这个节点之前已经上锁并且是同一个用户ID上锁的。
第三个是升级函数给我们节点值和用户ID要我们把这个节点上锁并且把这个节点的所有子孙节点都解锁。前提是这个节点的祖先节点没有一个上锁的并且这个节点的子孙节点至少有一个上锁的。 我们来逐个击破首先是上锁函数我们只需要拿一个数组来存放上锁关系即可这个数组的第i个元素表示给节点i上锁的用户如果是-1则表示这个节点没有上锁。
解锁函数也类似我们只需要查看给节点上锁的用户是不是当前用户即可。
最后剩下升级函数一共是三个条件。
第一个是当前节点未上锁这个好办我们查询上诉关系数组就行。
第二个是查询子孙节点要求子孙节点至少有一个上锁要用到节点的父子关系了所以我们在构造函数的时候就构建出节点的父子关系拿一个map来存放每个节点的子节点就行。
寻找子孙节点的时候我们使用递归函数去查询我使用的是DFS找哪怕一个上锁的节点我们都返回true表示子孙节点有上锁的但是我们不是立即返回因为这个升级函数还要我们把上锁的子孙节点都解锁因此我们还需要接着往下寻找子孙节点遇到上锁的我们就解锁。
第三个条件是祖先节点没有上锁的由于每个节点只会有一个父节点因此我们不断向上去寻找祖先节点即可遇到上锁的就返回false。
最后三个条件都满足了我们再将这个节点以当前用户的名义上锁。
代码
class LockingTree {
public:unordered_mapint,vectorintsons; //记录每个节点的子节点vectorintparent; //记录每个节点的父亲vectorintwhoLock; //记录每个节点的上锁情况LockingTree(vectorint parent):parent(parent),whoLock(vectorint(parent.size(),-1)) {//构建子节点的关系for(int i0;iparent.size();i){if(sons.find(parent[i])sons.end()) sons[parent[i]]vectorint(0);sons[parent[i]].push_back(i);}}bool lock(int num, int user) {//如果该节点已经上过锁那么不能上锁,反之可以并且修改上锁人if(whoLock[num]!-1) return false;whoLock[num]user;return true;}bool unlock(int num, int user) {//如果该节点没有被该用户上锁,那么不能解锁,反之解锁if(whoLock[num]!user) return false;whoLock[num]-1;return true;}//寻找某节点的父节点是否上锁bool find(int num){if(num-1) return true;if(whoLock[num]!-1) return false;return find(parent[num]);}//寻找子节点是否上锁,如果上锁,那么解锁bool unlockSon(int num){bool flagfalse;if(whoLock[num]!-1){flagtrue;whoLock[num]-1;} for(auto son:sons[num]){if(unlockSon(son)) flagtrue;}return flag;}bool upgrade(int num, int user) {//如果该节点已经锁上了那么不能上锁if(whoLock[num]!-1) return false;//如果有上锁的祖先节点那么不能上锁 if(!find(parent[num])) return false;//如果子孙节点没有一个上锁的,那么不能上锁if(!unlockSon(num)) return false;//一切没问题上锁whoLock[num]user;return true;}
};
