1743. 从相邻元素对还原数组-哈希表法

1743. 从相邻元素对还原数组-哈希表法,第1张

1743. 从相邻元素对还原数组-哈希表法

存在一个由 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 。如果存在多种解答,返回 其中任意一个 即可。

示例 1:

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

示例 2:

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

示例 3:

输入:adjacentPairs = [[100000,-100000]]
输出:[100000,-100000]

个人感觉这题如果真的用c语言去做的话,确实比较复杂,解题代码如下:

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
#define size 15675
struct hash{
    int count;
    int adj;
 
     int val;
 struct hash *next;
};
void hash_add(int val,int adj,struct hash *h,int count){
    struct hash *p=(struct hash*)malloc(sizeof(struct hash));
    p->val=val;
    p->next=h->next;
    p->adj=adj;
    p->count=count;
    h->next=p;
}
int find_hash(int val,int adj,struct hash *h){
    h=h->next;
    while(h){
        if(h->val==val){
              h->count++;
              return 1;

        }
        
          h=h->next;
    }
    return 0;
}

int find_hash_adj(int val,struct hash *h,int pre){
    h=h->next;
    while(h){
        if(h->val==val&&h->adj!=pre){
            return h->adj;
        }
          h=h->next;
    }
    return 0;
}




int* restoreArray(int** adjacentPairs, int adjacentPairsSize, int* adjacentPairsColSize, int* returnSize){
    int *num=(int *)malloc(sizeof(int)*adjacentPairsSize*2);
    
     struct hash *h=(struct hash *)malloc(sizeof(struct hash)*size);
    int i;
    int *a=(int *)malloc(sizeof(int)*2);
    for(i=0;i<size;i++){
        (h+i)->next=NULL;
    }
    int pz=0;

    for(int i=0;i<adjacentPairsSize;i++){
        int a=adjacentPairs[i][0];
        int b=adjacentPairs[i][1];
        
       if(find_hash(a,b,h+abs(a)%size)==0){

            hash_add(a,b,h+abs(a)%size,1);
             }
             else{
                  hash_add(a,b,h+abs(a)%size,2);

             }
      

         if(find_hash(b,a,h+abs(b)%size)==0){
              hash_add(b,a,h+abs(b)%size,1);

         }
         else{

            hash_add(b,a,h+abs(b)%size,2);

         }
         

        
        
    }
    int val_start;
    int val_end;
    int end=0;
   

    for(int i=0;i<size;i++){
        struct hash *p=(h+i)->next;
       
        while(p){
           
             if(p->count==1&&end==1){
                val_end=p->val;
               end++;
              
            }
            if(p->count==1&&end==0){
                val_start=p->val;
               end++;
              
            }
            
            p=p->next;
        }
        if(end==2){
            break;
        }

    }
 
    num[pz++]=val_start;
    int now=val_start;
    int pre=-1;
    int adj=0;

    while(true){
       
       if(now==val_start){
          
         adj=find_hash_adj(now,h+abs(now)%size,pre);
          pre=now;
         now=adj;
          }
          else{
              
               adj=find_hash_adj(now,h+abs(now)%size,pre);
               pre=now;
               now=adj;


          }


         num[pz++]=adj;
         if(adj==val_end){break;}

    }


   
  *returnSize=pz;
    return num;
   
    

}

欢迎分享,转载请注明来源:内存溢出

原文地址: https://outofmemory.cn/langs/2991812.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2022-09-23
下一篇 2022-09-23

随机推荐

  • 鸿蒙负一屏怎么设置

    演示机型:华为Mate 40系统版本:HarmonyOS 2.0 鸿蒙负一屏怎么设置共有3步。以下是华为Mate 40中设置鸿蒙负一屏的具体操作步骤: 操作步骤 1 两指捏合进主屏幕状态在手机桌

    2022-09-30
    0 0 0
  • 风信子怎么水培

    1、选种:选择健康的,表皮没有破损的种球,剥去外皮。2、容器:可选择大口径的透明玻璃瓶或者带有水培篮的专业水培容器,使用前需进行消毒。3、水质:最好使用纯净水,自来水的话需要先1、选种:选择健康的,表

    2022-09-30
    0 0 0
  • 清河县美食

    清河县美食有武氏烧饼、清河八大碗、曲家牛肉、清河菜豆腐、清河小米、武大郎粉皮等。1、武氏烧饼:武氏烧饼武氏烧饼始源于北宋景佑年间,始称“炊饼”后改称“武大郎烧饼”。清河县美食有武氏烧饼、清河八大碗、曲

    2022-09-30
    0 0 0
  • 芋头隔水蒸多久能熟

    芋头隔水一般需要中大火蒸20-30分钟才能熟,具体需要看芋头的大小、用什么锅具等,比如使用高压锅蒸个头较小的芋头,一般10-15分钟左右就可以了。用普通锅的话,中途可以开盖用筷子芋头隔水一般需要中大火

    2022-09-30
    0 0 0
  • 紫茉莉播种时间和方法

      1、时间:紫茉莉的播种时间可以在春夏秋三个季节进行,但最好是在春季的3~5月播种。2、选种:选择健康、饱满的紫茉莉花种子,将种子和新高脂膜混合搅拌,增加种子的发芽率。3、选  1、时间:紫茉莉的播

    2022-09-30
    0 0 0
  • pin初始密码是多少

    适用环境:产品型号:iPhone11系统版本:iOS14.2.0操作步骤方法方法1第1步。PIN码一般为四位密码,默认为&ldquo;0000&rdquo;或&ldquo;1234&rdquo;PI

    2022-09-30
    0 0 0
  • 平安桐乡日是每月的几日

    平安桐乡日是每月的26日,桐乡位于浙江省北部杭嘉湖平原腹地,属于嘉兴五县市之一。2019年6月起,每逢26日被定为平安日,全市各地均开展了形式多样的平安建设活动。国安才能家安,家平安桐乡日是每月的26

  • 朋友圈文案富含哲理 朋友圈文案人生哲理

    1、咳嗽还吃薯片,感冒还穿短袖,头晕还玩手机,发烧了还熬夜,不能吃辣的,还硬要吃,没错,这就是我。2、你没必要活成所有人喜欢的样子,也永远活不成所有人喜欢的样子。最舒服的关系,是不1、咳嗽还吃薯片,感

    2022-09-30
    0 0 0
  • 皮衣脏了怎么办

    用湿毛巾反复将皮衣擦干净、晾干,在晾晒时,还可以用竹棒敲打,把一些脏污拍打掉。到超市去买一瓶专门涂在皮衣上的油,涂上即可。还有一个小妙招就是用香蕉皮擦洗,而且皮衣会显得更用湿毛巾反复将皮衣擦干净、晾干

    2022-09-30
    0 0 0

发表评论

登录后才能评论

评论列表(0条)

保存