L2-002. 链表去重（模拟）-白红宇

L2-002. 链表去重（模拟）

阅读量：5257 次

发布时间：2019-06-14

本文共 2184 字，大约阅读时间需要 7 分钟。

题意：

给定一个带整数键值的单链表L，本题要求你编写程序，删除那些键值的绝对值有重复的结点。即对任意键值K，只有键值或其绝对值等于K的第一个结点可以被保留。同时，所有被删除的结点必须被保存在另外一个链表中。例如：另L为21→-15→-15→-7→15，则你必须输出去重后的链表21→-15→-7、以及被删除的链表-15→15。

输入格式：

输入第一行包含链表第一个结点的地址、以及结点个数N（<= 10⁵ 的正整数）。结点地址是一个非负的5位整数，NULL指针用-1表示。

随后N行，每行按下列格式给出一个结点的信息：

Address Key Next

其中Address是结点的地址，Key是绝对值不超过10⁴的整数，Next是下一个结点的地址。

输出格式：

首先输出去重后的链表，然后输出被删除结点组成的链表。每个结点占一行，按输入的格式输出。

分析：string超时，地址用int存，输出%05d。

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include
               
                #include
                
                 #include
                 #include
                  
                   #include
                   
                    #include
                    
                     #include
                     
                      #define lowbit(x) (x & (-x))const double eps = 1e-8;inline int dcmp(double a, double b){ if(fabs(a - b) < eps) return 0; return a > b ? 1 : -1;}typedef long long LL;typedef unsigned long long ULL;const int INT_INF = 0x3f3f3f3f;const int INT_M_INF = 0x7f7f7f7f;const LL LL_INF = 0x3f3f3f3f3f3f3f3f;const LL LL_M_INF = 0x7f7f7f7f7f7f7f7f;const int dr[] = {0, 0, -1, 1, -1, -1, 1, 1};const int dc[] = {-1, 1, 0, 0, -1, 1, -1, 1};const int MOD = 1e9 + 7;const double pi = acos(-1.0);const int MAXN = 100000 + 10;const int MAXT = 10000 + 10;using namespace std;int nex[MAXN];int zhi[MAXN];int shu[MAXN];int pos[MAXN];map
                      
                        mp;vector
                       
                        
                          > v1;vector
                         
                          
                            > v2;int main(){ int st; int N; cin >> st >> N; int a, b; int x; for(int i = 0; i < N; ++i){ cin >> a >> x >> b; nex[a] = b; zhi[a] = x; } int tmp = st; int cnt = 0; while(1){ ++cnt; pos[cnt] = tmp; shu[cnt] = zhi[tmp]; if(nex[tmp] == -1) break; tmp = nex[tmp]; } for(int i = 1; i <= cnt; ++i){ int t = abs(shu[i]); if(!mp.count(t)){ mp[t] = 1; v1.push_back(pair
                           
                            (pos[i], shu[i])); } else{ v2.push_back(pair
                            
                             (pos[i], shu[i])); } } int len = v1.size(); for(int i = 0; i < len; ++i){ printf("%05d %d ", v1[i].first, v1[i].second); if(i == len - 1){ cout << "-1" << endl; } else{ printf("%05d\n", v1[i + 1].first); } } len = v2.size(); for(int i = 0; i < len; ++i){ printf("%05d %d ", v2[i].first, v2[i].second); if(i == len - 1){ cout << "-1" << endl; } else{ printf("%05d\n", v2[i + 1].first); } } return 0;}

转载于:https://www.cnblogs.com/tyty-Somnuspoppy/p/8654107.html

你可能感兴趣的文章