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

这篇具有很好参考价值的文章主要介绍了leetcode 1743. 从相邻元素对还原数组。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

题目链接:leetcode 1743

1.题目

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

给你一个二维整数数组 adjacentPairs ,大小为 n - 1 ,其中每个 adjacentPairs[i] = [ui, vi] 表示元素 ui 和 vi 在 nums 中相邻。

题目数据保证所有由元素 nums[i] 和 nums[i+1] 组成的相邻元素对都存在于 adjacentPairs 中,存在形式可能是 [nums[i], nums[i+1]] ,也可能是 [nums[i+1], nums[i]] 。这些相邻元素对可以 按任意顺序 出现。

返回 原始数组 nums 。如果存在多种解答,返回 其中任意一个 即可。

2.示例

1)示例 1:
输入:adjacentPairs = [[2,1],[3,4],[3,2]]
输出:[1,2,3,4]
解释:数组的所有相邻元素对都在 adjacentPairs 中。
特别要注意的是,adjacentPairs[i] 只表示两个元素相邻,并不保证其 左-右 顺序。

2)示例 2:
输入:adjacentPairs = [[4,-2],[1,4],[-3,1]]
输出:[-2,4,1,-3]
解释:数组中可能存在负数。
另一种解答是 [-3,1,4,-2] ,也会被视作正确答案。

3)示例 3:
输入:adjacentPairs = [[100000,-100000]]
输出:[100000,-100000]

4)提示:
nums.length == n
adjacentPairs.length == n - 1
adjacentPairs[i].length == 2
2 <= n <= 105
-105 <= nums[i], ui, vi <= 105
题目数据保证存在一些以 adjacentPairs 作为元素对的数组 nums

3.分析

分析,相邻节点之间建边,找到一个度为1的点,它就是起点,挨个循着边找下一个节点即可文章来源地址https://www.toymoban.com/news/detail-491627.html

4.代码

class Solution {
public:
    bool flag=false;
    vector<int> ans,test;
    map<int,vector<int>> map1;
    vector<int> nums;
    map<int,bool> vis;
    void dfs(int x,int num,int n){
        vis[x]=true;
        test.push_back(x);
        if(num==n-1){
            flag=true;
            ans=test;
            return;
        }
        for(int i=0;i<map1[x].size();i++)
            if(vis[map1[x][i]]==false)
                dfs(map1[x][i],num+1,n);
        test.pop_back();
        vis[x]=false;
    }
    vector<int> restoreArray(vector<vector<int>>& adjacentPairs) {
        int n=adjacentPairs.size()+1;
        for(int i=0;i<adjacentPairs.size();i++){
            int a=adjacentPairs[i][0],b=adjacentPairs[i][1];
            if(map1.count(a)==0) nums.push_back(a);
            if(map1.count(b)==0) nums.push_back(b);
            map1[a].push_back(b);
            map1[b].push_back(a);
            vis[a]=false;vis[b]=false;
        }
        int st=0;
        for(int i=0;i<nums.size();i++)
            if(map1[nums[i]].size()==1){
                st=nums[i];
                break;
            }
        dfs(st,0,n);
        return ans;
    }   
};      

到了这里,关于leetcode 1743. 从相邻元素对还原数组的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【LeetCode题目详解】 203. 移除链表元素707. 设计链表206. 反转链表 day3(补)

    题意:删除链表中等于给定值 val 的所有节点。 示例 1: 输入:head = [1,2,6,3,4,5,6], val = 6 输出:[1,2,3,4,5] 示例 2: 输入:head = [], val = 1 输出:[] 示例 3: 输入:head = [7,7,7,7], val = 7 输出:[] 看到这道题就想到了链表 这道题有两种写法,涉及如下链表操作的两种方式: 直接使用

    2024年02月16日
    浏览(42)
  • ( 数组) 27. 移除元素 ——【Leetcode每日一题】

    难度:简单 给你一个数组 nums 和一个值 val ,你需要 原地 移除所有数值等于 val 的元素,并返回移除后数组的新长度。 不要使用额外的数组空间,你必须仅使用 O(1) 额外空间并 原地 修改输入数组。 元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。 说明

    2024年02月08日
    浏览(441)
  • 【LeetCode刷题(数组and排序)】:存在重复元素

    给你一个整数数组 nums 。如果任一值在数组中出现 至少两次 ,返回 true ;如果数组中每个元素互不相同,返回 false 示例 1: 输入:nums = [1,2,3,1] 输出:true 示例 2: 输入:nums = [1,2,3,4] 输出:false 示例 3: 输入:nums = [1,1,1,3,3,4,3,2,4,2] 输出:true 在对数字从小到大排序之后,数

    2024年02月07日
    浏览(51)
  • 【LeetCode】2619. 数组原型对象的最后一个元素

    请你编写一段代码实现一个数组方法,使任何数组都可以调用 array.last() 方法,这个方法将返回数组最后一个元素。如果数组中没有元素,则返回 -1 。 你可以假设数组是 JSON.parse 的输出结果。 示例 1 : 输入: nums = [null, {}, 3] 输出: 3 解释:调用 nums.last() 后返回最后一个元

    2024年01月21日
    浏览(44)
  • leetcode: 2789. 合并数组中的最大元素

    给你一个下标从 0 开始、由正整数组成的数组  nums  。 你可以在数组上执行下述操作 任意 次: 选中一个同时满足  0 = i nums.length - 1  和  nums[i] = nums[i + 1]  的整数  i  。将元素  nums[i + 1]  替换为  nums[i] + nums[i + 1]  ,并从数组中删除元素  nums[i]  。 返回你可以从最

    2024年03月14日
    浏览(39)
  • 【LeetCode题目详解】 977.有序数组的平方 209.长度最小的子数组59.螺旋矩阵II day2

    看完这个题目第一想法就是直接暴力解决,直接将全部平方然后进行排序。比如快排。 代码如下: 时间复杂度是 O(nlogn)或者说【O(n + nlogn)】,括号里面这个是为了比较接下来的方法。 然后看了代码随想录的视频学习了用双指针来写这道题的方法(说实话不看视频真没想到可

    2024年02月13日
    浏览(43)
  • leetcode 215.数组中第k大的元素

    🌟 leetcode链接:数组中第k大的元素 思路: 使用堆数据结构,大堆的堆顶是堆内最大的元素,也就是把当前堆 pop k - 1 次,第 k 次 top 出来的元素就是第 k 大的数。 代码:

    2024年02月09日
    浏览(54)
  • 【LeetCode】移除元素、删除有序数组中的重复项、合并两个有序数组

    🧑‍💻作者: @情话0.0 📝专栏:《LeetCode》 🔖题目链接:移除元素、删除有序数组中的重复项、合并两个有序数组 给你一个数组 nums 和一个值 val,你需要 原地移除所有数值等于 val 的元素,并返回移除后数组的新长度。 不要使用额外的数组空间,你必须仅使用 O(1) 额外空

    2023年04月09日
    浏览(77)
  • Leetcode24-找到两个数组中的公共元素(2956)

    给你两个下标从 0 开始的整数数组 nums1 和 nums2 ,它们分别含有 n 和 m 个元素。 请你计算以下两个数值: 统计 0 = i n 中的下标 i ,满足 nums1[i] 在 nums2 中 至少 出现了一次。 统计 0 = i m 中的下标 i ,满足 nums2[i] 在 nums1 中 至少 出现了一次。 请你返回一个长度为 2 的整数数组

    2024年01月20日
    浏览(44)
  • 【leetcode合集】如何知道自己是否掌握了数组与链表?试试这几道题目吧!

      目录 1.数组题目合集 1.1 leetcode.27 移除元素 1.2 leetcode.26 删除有序数组中的重复项 1.3 leetcode.88 合并两个有数数组 2.链表题目合集 2.1 leetcode.203 移除链表元素 2.2 leetcode.206 反转链表 2.3 leetcode.876 链表的中间结点 2.4 牛客 链表中倒数第k个结点 2.5 leetcode.21 合并两个有序链表 2.

    2024年01月25日
    浏览(43)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包