Restore the Array From Adjacent Pairs（C++从相邻元素对还原数组）

比眉伴天荒 2022-11-07 13:21 160阅读 0赞

解题思路：

(1)dfs

class Solution {
    public:
        vector<int> restoreArray(vector<vector<int>>& adjacentPairs) {
            unordered_map<int,int> mp;
            unordered_map<int,vector<int>>mt;
            for(int i=0;i<adjacentPairs.size();i++) {
                mp[adjacentPairs[i][0]]++;
                mp[adjacentPairs[i][1]]++;
                mt[adjacentPairs[i][0]].push_back(adjacentPairs[i][1]);
                mt[adjacentPairs[i][1]].push_back(adjacentPairs[i][0]);
            }
            
            int start=0;
            for(auto it=mp.begin();it!=mp.end();it++) {
                if(it->second==1) start=it->first;
                it->second=0;
            }
            
            vector<int> v(1,start);
            mp[start]=1;
            
            while((mt[start].size()==1 && mp[mt[start][0]]==0) || (mp[mt[start][0]]==0 || mp[mt[start][0]]==1)) {
                if(mp[mt[start][0]]==0) {
                    v.push_back(mt[start][0]);
                    mp[mt[start][0]]=1;
                    start=mt[start][0];
                } else if(mt[start].size()==1) return v;
                else {
                    v.push_back(mt[start][1]);
                    mp[mt[start][1]]=1;
                    start=mt[start][1];
                }
            }
            return v;
        }
    };

发表评论取消回复

表情：

评论列表（有 0 条评论，160人围观）

还没有评论，来说两句吧...

相关阅读

相关 Array数组ES6方法Array.isArray、Array.of、Array.from；find、findIndex方法

Array构造函数上的三个方法 Array.isArray Array.isArray() 用于确定传递的值是否是一个数组。如果是数组，则返回true，否则为false

偏执的太偏执、/ 2023年01月17日 04:58/ 0 赞/ 208 阅读

相关 C#相邻两数组元素同步长交换

using System; using System.Collections; using System.Collections.Generic;

痛定思痛。/ 2022年12月05日 12:10/ 0 赞/ 136 阅读

相关 Restore the Array From Adjacent Pairs（C++从相邻元素对还原数组）

解题思路： (1)dfs class Solution { public: vector<int> restoreArray(vector<

比眉伴天荒/ 2022年11月07日 13:21/ 0 赞/ 161 阅读

相关 1743. 从相邻元素对还原数组2021-07-25

存在一个由 n 个不同元素组成的整数数组 nums ，但你已经记不清具体内容。好在你还记得 nums 中的每一对相邻元素。给你一个二维整数数组 adjacentPairs

╰半橙微兮°/ 2022年08月31日 13:24/ 0 赞/ 133 阅读

相关 1743. 从相邻元素对还原数组

存在一个由 n 个不同元素组成的整数数组 nums ，但你已经记不清具体内容。好在你还记得 nums 中的每一对相邻元素。给你一个二维整数数组 adjacentPairs

曾经终败给现在/ 2022年08月31日 13:18/ 0 赞/ 156 阅读

相关数组中不相邻元素的最大和

原题链接: [Maximum sum such that no two elements are adjacent][] 题目给定一个只含正数的数组，找到数组满足条件的

今天药忘吃喽~/ 2022年08月09日 11:46/ 0 赞/ 129 阅读

相关 Facebook面试题 Remove duplicates from array where all duplicate numbers are located adjacently

> Given an integer array which has the property that all the elements haveing same value

た入场券/ 2022年07月13日 08:50/ 0 赞/ 105 阅读

相关对数组（包括json数组）中相邻元素查重，并记录每个元素的重复个数

先看效果： ![70][] ![70 1][] 代码如下： //定义 function getMergeArr(oldArr,jsonN

冷不防/ 2022年05月11日 05:10/ 0 赞/ 140 阅读

相关 RESTORE DATABASE命令还原SQLServer 2005 数据库

今天在sqlServer20005 的management studio里使用bak文件还原数据库的时候,总是失败! ![BACKERROR.GIF][] Restor

快来打我*/ 2022年04月24日 06:28/ 0 赞/ 258 阅读

相关往数组Array中添加元素

\[html\] [view plain][] [copy][view plain] 1. unshift：将参数添加到原数组开头，并返回数组的长度 \[ht

缺乏、安全感/ 2021年10月08日 06:34/ 0 赞/ 396 阅读