C/C++教程

Leetcode 1743. 从相邻元素对还原数组（DAY 122） ---- 贪心算法学习期

本文主要是介绍Leetcode 1743. 从相邻元素对还原数组（DAY 122） ---- 贪心算法学习期，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

原题题目

在这里插入图片描述

代码实现（首刷自解）

class Solution {
public:
    vector<int> restoreArray(vector<vector<int>>& adjacentPairs) {
        unordered_map<int,vector<int>> map;
        unordered_set<int> temp;
        vector<int> ret(adjacentPairs.size()+1,INT_MAX);
        int nums = adjacentPairs.size()+1;
        for(const auto& pair:adjacentPairs)
        {
            for(int i=0;i<=1;++i)
            {
                map[pair[i]].emplace_back(pair[i^1]);
                if(map[pair[i]].size() == 2)    temp.erase(temp.find(pair[i]));
                else    temp.emplace(pair[i]);
            }
        }

        for(const auto& num:temp)
            if(ret[0] == INT_MAX)   ret[0] = num;
            
        for(int i=1;i<nums;++i)
        {
            for(const auto& num:map[ret[i-1]])
            {
                if(i>=2 &&num == ret[i-2]) continue;
                ret[i] = num;
            }
        }
        return ret;
    }
};
这篇关于Leetcode 1743. 从相邻元素对还原数组（DAY 122） ---- 贪心算法学习期的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
您可能喜欢
栏目导航