Interesting quiz [modified]
-
Hi all, I came across this quiz the other day. It goes something like: you have a string "aabbccddeffghijk" and you should find the foremost occurrence of an unique character in the string, so in this case letter 'e' should be the answer, and this should be done in just one traversing. The tip is that array index should be of interest. I only came up with a single traversing that can only sorts out all the letters that occurred only once in the string, but how can I tell the sequence of those single occurrence of letters within single traversing, or is this possible practically:
int ar\[26\] = {0}; TCHAR\* ptsz = "aabbccddeffghijk"; int nIndex = 0; while (\*(ptsz++)) { nIndex = int(\*ptsz) - 'a'; ar\[nIndex\]++; }Thanks,
modified on Tuesday, July 1, 2008 10:54 PM
-
Hi all, I came across this quiz the other day. It goes something like: you have a string "aabbccddeffghijk" and you should find the foremost occurrence of an unique character in the string, so in this case letter 'e' should be the answer, and this should be done in just one traversing. The tip is that array index should be of interest. I only came up with a single traversing that can only sorts out all the letters that occurred only once in the string, but how can I tell the sequence of those single occurrence of letters within single traversing, or is this possible practically:
int ar\[26\] = {0}; TCHAR\* ptsz = "aabbccddeffghijk"; int nIndex = 0; while (\*(ptsz++)) { nIndex = int(\*ptsz) - 'a'; ar\[nIndex\]++; }Thanks,
modified on Tuesday, July 1, 2008 10:54 PM
LiYS wrote:
you should find the first occurrence of a character that also appeared foremost in the string
This is a confusing statement. I assume you mean you need to find the first unique character in the string?
Steve
-
Hi all, I came across this quiz the other day. It goes something like: you have a string "aabbccddeffghijk" and you should find the foremost occurrence of an unique character in the string, so in this case letter 'e' should be the answer, and this should be done in just one traversing. The tip is that array index should be of interest. I only came up with a single traversing that can only sorts out all the letters that occurred only once in the string, but how can I tell the sequence of those single occurrence of letters within single traversing, or is this possible practically:
int ar\[26\] = {0}; TCHAR\* ptsz = "aabbccddeffghijk"; int nIndex = 0; while (\*(ptsz++)) { nIndex = int(\*ptsz) - 'a'; ar\[nIndex\]++; }Thanks,
modified on Tuesday, July 1, 2008 10:54 PM
Hi, why store the occurence count in an array, instead store the first position using two special values, say -1 for never seen yet, and -2 for seen multiple times. you would have to traverse your array to initialize it, traverse the string once, then traverse the array again to find the lowest value >=0. BTW IMO this belongs in the algo forum, not the C++ one. :)
Luc Pattyn [Forum Guidelines] [My Articles]
Voting for dummies? No thanks. X|
-
LiYS wrote:
you should find the first occurrence of a character that also appeared foremost in the string
This is a confusing statement. I assume you mean you need to find the first unique character in the string?
Steve
-
Hi all, I came across this quiz the other day. It goes something like: you have a string "aabbccddeffghijk" and you should find the foremost occurrence of an unique character in the string, so in this case letter 'e' should be the answer, and this should be done in just one traversing. The tip is that array index should be of interest. I only came up with a single traversing that can only sorts out all the letters that occurred only once in the string, but how can I tell the sequence of those single occurrence of letters within single traversing, or is this possible practically:
int ar\[26\] = {0}; TCHAR\* ptsz = "aabbccddeffghijk"; int nIndex = 0; while (\*(ptsz++)) { nIndex = int(\*ptsz) - 'a'; ar\[nIndex\]++; }Thanks,
modified on Tuesday, July 1, 2008 10:54 PM
I notice that the string is sorted. Is the algorithm permitted to assume this? If so the the following will do the trick:
// VanillaConsole.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include <iostream>
using namespace std;
int main()
{
const char *pstr = "aabbccddeffghijk";
for (unsigned int i=1; pstr[i]!=0; ++i)
{
if (pstr[i]!=pstr[i-1] && pstr[i]!=pstr[i+1])
{
cout << "First unique character: " << pstr[i] << endl;
return 0;
}
}
cout << "No unique characters." << endl;
return 0;
}Steve
-
Hi all, I came across this quiz the other day. It goes something like: you have a string "aabbccddeffghijk" and you should find the foremost occurrence of an unique character in the string, so in this case letter 'e' should be the answer, and this should be done in just one traversing. The tip is that array index should be of interest. I only came up with a single traversing that can only sorts out all the letters that occurred only once in the string, but how can I tell the sequence of those single occurrence of letters within single traversing, or is this possible practically:
int ar\[26\] = {0}; TCHAR\* ptsz = "aabbccddeffghijk"; int nIndex = 0; while (\*(ptsz++)) { nIndex = int(\*ptsz) - 'a'; ar\[nIndex\]++; }Thanks,
modified on Tuesday, July 1, 2008 10:54 PM
The only thing I see wrong with your approach is that you are incrementing
ptszprematurely."Love people and use things, not love things and use people." - Unknown
"To have a respect for ourselves guides our morals; to have deference for others governs our manners." - Laurence Sterne
-
Hi all, I came across this quiz the other day. It goes something like: you have a string "aabbccddeffghijk" and you should find the foremost occurrence of an unique character in the string, so in this case letter 'e' should be the answer, and this should be done in just one traversing. The tip is that array index should be of interest. I only came up with a single traversing that can only sorts out all the letters that occurred only once in the string, but how can I tell the sequence of those single occurrence of letters within single traversing, or is this possible practically:
int ar\[26\] = {0}; TCHAR\* ptsz = "aabbccddeffghijk"; int nIndex = 0; while (\*(ptsz++)) { nIndex = int(\*ptsz) - 'a'; ar\[nIndex\]++; }Thanks,
modified on Tuesday, July 1, 2008 10:54 PM
As has been pointed out, the array is sorted. If that's true, and not just a coincidence... (This assumes a /0 terminated string)
TCHAR findfirstuniquechar_sorted (TCHAR *sz)
{
if (!sz) return 0;// loop through while safe for (int n = 0; sz \[n\]; n++) { if (sz \[n\] == sz \[n+1\]) // we're the same as the one after continue; if ( (n > 0) && (sz \[n\] == sz \[n-1\])) // we're the same as the one before! continue; // found one that's different from either side. return sz \[n\]; } return 0; // none found.}
If the string is not sorted, the problem becomes harder. As you use TCHAR, I'm assuming unicode, so you can't just have a 26 array for placement...
TCHAR findfirstuniquechar_unsorted (TCHAR *sz)
{
if (!sz)
return 0;; This line posts badly - it should be CMap less than TCHAR, TCHAR and, int, int and greater-then CharMap; hope that made sense... pre bug reported.
CMap<TCHAR, TCHAR &, int, int &> CharMap;
int nPos;
int nCharPos;// One pass through string. for (nPos = 0; sz \[nPos\]; nPos++) { if (CharMap.Lookup (sz \[nPos\], nCharPos)) { // char already used, so signal is as not-counting-anymore CharMap \[sz\[nPos\]\] = -1; } else { // New one! CharMap \[sz\[nPos\]\] = nPos; } } // Now all chars are account for, look for the char with the lowest <= 0 position. POSITION pos = CharMap.GetStartPosition (); nPos = -1; TCHAR c, cFirst = 0; while (pos) { CharMap.GetNextAssoc (pos, c, nCharPos); if (nCharPos < 0) // not a unique char. continue; if ( (nPos == -1) || (nCharPos < nPos)) // is this the earliest, or the first unique one we've mapped? { cFirst = c; nPos = nCharPos; } } return cFirst; // either first unique, or 0;}
OK, I've just spent FAR too much time on that. I hope it wasn't homework! Iain.
Plz sir... CPallini CPallini abuz drugz, plz plz help urgent.