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) ---- 贪心算法学习期的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!