First non-repeating character in a stream

Given an input stream of n characters consisting only of small case alphabets the task is to find the first non repeating character each time a character is inserted to the stream.

Example

Flow in stream : a, a, b, c
a goes to stream : 1st non repeating element a (a)
a goes to stream : no non repeating element -1 (5, 15)
b goes to stream : 1st non repeating element is b (a, a, b)
c goes to stream : 1st non repeating element is b (a, a, b, c)

Input:
The first line of input contains an integer T denoting the no of test cases. Then T test cases follow. Each test case contains an integer N denoting the size of the stream. Then in the next line are x characters which are inserted to the stream.

Output:
For each test case in a new line print the first non repeating elements separated by spaces present in the stream at every instinct when a character is added to the stream, if no such element is present print -1.

Constraints:
1<=T<=200
1<=N<=500

Example:
Input:
2
4
a a b c
3
a a c
Output:
a -1 b b
a -1 c

如何处理重复是个难点,本题考察的是队列

纯字符串处理方法.

 1 #include <algorithm>
 2 #include <iostream>
 3 #include <string>
 4 
 5 using namespace std;
 6 
 7 int main() {//by guxuanqing@gmai.com
 8     int T,N;
 9     cin >> T;
10     //getchar();
11     string str;
12     string result;
13     string tmpch;
14     while(T--)
15     {
16         cin >> N;//debug(N);
17         //getchar();
18         str.clear();
19         result.clear();
20         tmpch.clear();
21         int hashs[128] = {0};
22         char ch;
23         int i = 0;
24         for(i = 0; i < N; i++)
25         {
26             cin >> ch;//debug(ch);
27             while (ch == ' ') {
28                 cin >> ch;
29             }
30             //getchar();
31             str.push_back(ch);//debug(str);
32             ++hashs[(int)str[i]]; //debug(hashs[str[i]]);
33             if(hashs[(int)str[i]] == 1)
34             {
35                 if(tmpch.empty())
36                 {
37                    result.push_back(str[i]);
38                 }else
39                 {
40                     result.push_back(tmpch[0]);
41                 }
42                 tmpch.push_back(str[i]);//the first time occurs,push it back to tmpch
43             }else
44             {
45                 // string::size_type n = tmpch.find(str[i]);debug(tmpch);
46                 // if(n != string::npos)
47                 // {
48                 //     tmpch.erase(n,n);debug(tmpch);
49                 // }
50                 auto n = std::find(tmpch.begin(), tmpch.end(), str[i]);
51                 if(n != tmpch.end()) tmpch.erase(n);
52                 if(tmpch.empty())
53                 {
54                     result.push_back('0');
55                 }else
56                 {
57                    result.push_back(tmpch[0]);
58                 }
59             }
60             //debug(result);
61         }
62         for(i = 0; i < N; i++)
63         {
64            if(result[i] == '0') cout << "-1 ";
65            else cout << result[i] << ' ';
66         }
67         cout << endl;
68     }
69 
70     return 0;
71 }

View Code

0.093s

栈处理的方法:

 1 //by Amit Negi 2
 2 #include <iostream>
 3 #include<queue>
 4 using namespace std;
 5 
 6 int main() {
 7     // your code goes here
 8     int t;
 9     cin>>t;
10     while(t--)
11     {
12       int n,i,j;
13       int arr[26];
14       queue<char> q;
15       cin>>n;
16       char s[n];
17       for(i=0;i<n;i++)
18         cin>>s[i];
19       for(i=0;i<26;i++)
20         arr[i]=0;
21       for(i=0;i<n;i++)
22       {
23           if(arr[s[i]-'a']==0)
24           {
25           q.push(s[i]);
26           arr[s[i]-'a']=1;
27           }
28           else
29             arr[s[i]-'a']+=1;
30 
31           while(!q.empty()&&arr[q.front()-'a']!=1)
32             q.pop();
33           if(q.empty())
34             cout<<-1<<" ";
35            else
36             cout<<q.front()<<" ";
37       }
38       cout<<endl;
39     }
40     return 0;
41 }

View Code

0.082s

 1 //by Ayush Bansal 9
 2 #include <bits/stdc++.h>
 3 #define FOR(i,a,b) for(int i=a;i<b;i++)
 4 using namespace std;
 5 
 6 int main() {
 7     //code
 8     int t,n;
 9     char c;
10     cin>>t;
11     while(t--)
12     {
13         vector<int> v(26,0);
14         queue<char> q;
15         cin>>n;
16         FOR(i,0,n)
17         {
18             cin>>c;
19             v[c-'a']++;
20             if(v[c-'a']<=1)
21             {
22                 q.push(c);
23             }
24             char ans;
25             while(!q.empty())
26             {
27                 if(v[q.front()-'a']<=1)
28                 {
29                     ans=q.front();
30                     break;
31                 }
32                 else
33                 {
34                     q.pop();
35                 }
36             }
37             if(q.empty())
38             {
39                 cout<<-1<<' ';
40             }
41             else
42             {
43                 cout<<ans<<' ';
44             }
45         }
46         cout<<endl;
47     }
48     
49     return 0;
50 }

View Code

0.115s