h*******0
发帖数: 270 | 1 Find out the first non duplicate character in a string.
eg: "nasa" output: 'n'
只允许扫一遍字符串， 如果只是用hash，需要扫2遍。 我的想法是用double linked
list和hash。 第一次读到char， 就放到linkedlist结尾， 并插入（char， 对应node
pointer）到hash中。 如果第二次读到这个char， 把这个node删除， 将hash[char]
的value变成NULL。 如果删除的node为cur， 那么删除cur， 并让cur指向下一个。 最
后返回cur的data。
这个方法可以吗？ |
l*******b
发帖数: 2586 | |
c*u
发帖数: 22 | 3 hashset 一遍可以么
node
【在 h*******0 的大作中提到】
: Find out the first non duplicate character in a string.
: eg: "nasa" output: 'n'
: 只允许扫一遍字符串， 如果只是用hash，需要扫2遍。 我的想法是用double linked
: list和hash。 第一次读到char， 就放到linkedlist结尾， 并插入（char， 对应node
: pointer）到hash中。 如果第二次读到这个char， 把这个node删除， 将hash[char]
: 的value变成NULL。 如果删除的node为cur， 那么删除cur， 并让cur指向下一个。 最
: 后返回cur的data。
: 这个方法可以吗？
|
c*****a
发帖数: 808 | 4 linkedlist删除worst case是n吗? |
p*****p
发帖数: 379 | 5 有个问题，"abba"，你的描述好像会返回最后的a
我写了一个，看看有没有问题，想法差不多，就是循环的时候不删除到要返回的时候再
检查，这个最坏好像是n + (n - 1) / 2 + 1次（前面各出现两次最后一个出现一次）
char findFirstNonDuplicate(string str) {
int n = str.size();
if (!n) return '\0';
// assume string contains only ascii chars
int map[256] = {0};
list index_list;
for (int i = 0; i < n; ++i) {
if (!map[str[i]]) {
index_list.push_back(i);
}
++map[str[i]];
}
while (!index_list.empty()) {
if (map[str[index_list.front()]] > 1) index_list.pop_front();
else break;
}
if (!index_list.empty())
return str[index_list.front()];
else
return '\0';
}
node
【在 h*******0 的大作中提到】
: Find out the first non duplicate character in a string.
: eg: "nasa" output: 'n'
: 只允许扫一遍字符串， 如果只是用hash，需要扫2遍。 我的想法是用double linked
: list和hash。 第一次读到char， 就放到linkedlist结尾， 并插入（char， 对应node
: pointer）到hash中。 如果第二次读到这个char， 把这个node删除， 将hash[char]
: 的value变成NULL。 如果删除的node为cur， 那么删除cur， 并让cur指向下一个。 最
: 后返回cur的data。
: 这个方法可以吗？
|
s*****n
发帖数: 5488 | 6 256 char数组或者32个long搞定。
loop数组或者>>找 1.
node
【在 h*******0 的大作中提到】
: Find out the first non duplicate character in a string.
: eg: "nasa" output: 'n'
: 只允许扫一遍字符串， 如果只是用hash，需要扫2遍。 我的想法是用double linked
: list和hash。 第一次读到char， 就放到linkedlist结尾， 并插入（char， 对应node
: pointer）到hash中。 如果第二次读到这个char， 把这个node删除， 将hash[char]
: 的value变成NULL。 如果删除的node为cur， 那么删除cur， 并让cur指向下一个。 最
: 后返回cur的data。
: 这个方法可以吗？
|
s*****n
发帖数: 5488 | 7 bool findFirstNonDuplicate(string str, out firtchar) {
int n = str.size();
if (!n) return false;
// assume string contains only ascii chars
int map[256] = {0};
for(int i = 0 ; i < str.Length; i++)
map[str[i])++;
for (int j = 0; j < 256; j++)
if (map[j] == 1)
{
firstchar = map[j];
return true;
}
return false;
}
【在 p*****p 的大作中提到】
: 有个问题，"abba"，你的描述好像会返回最后的a
: 我写了一个，看看有没有问题，想法差不多，就是循环的时候不删除到要返回的时候再
: 检查，这个最坏好像是n + (n - 1) / 2 + 1次（前面各出现两次最后一个出现一次）
: char findFirstNonDuplicate(string str) {
: int n = str.size();
: if (!n) return '\0';
: // assume string contains only ascii chars
: int map[256] = {0};
: list index_list;
: for (int i = 0; i < n; ++i) {
|
B********t
发帖数: 147 | |
h*******0
发帖数: 270 | 9 hash里面存的是linkedlist的点， 所以你需要查找这个node， 遇到了直接删除就行
【在 c*****a 的大作中提到】
: linkedlist删除worst case是n吗?
|
h*******0
发帖数: 270 | 10 那面试官说只允许扫一遍，我也不知道为啥要这么要求。。 其实你的方法已经可以了
。。
【在 s*****n 的大作中提到】
: bool findFirstNonDuplicate(string str, out firtchar) {
: int n = str.size();
: if (!n) return false;
: // assume string contains only ascii chars
: int map[256] = {0};
: for(int i = 0 ; i < str.Length; i++)
: map[str[i])++;
: for (int j = 0; j < 256; j++)
: if (map[j] == 1)
: {
|
|
|
h*******0
发帖数: 270 | 11 可以设linkedlist pointer指向null， loop结束后检查pointer是否指向了null。 如
果指向null了，返回\0。 不过我觉得面试官考的有点无厘头。。。
【在 p*****p 的大作中提到】
: 有个问题，"abba"，你的描述好像会返回最后的a
: 我写了一个，看看有没有问题，想法差不多，就是循环的时候不删除到要返回的时候再
: 检查，这个最坏好像是n + (n - 1) / 2 + 1次（前面各出现两次最后一个出现一次）
: char findFirstNonDuplicate(string str) {
: int n = str.size();
: if (!n) return '\0';
: // assume string contains only ascii chars
: int map[256] = {0};
: list index_list;
: for (int i = 0; i < n; ++i) {
|
c*u
发帖数: 22 | 12 这样可以么
String str = "lacyrkaplcknb";
char[] cr = str.toCharArray();
LinkedHashSet set = new LinkedHashSet();
for (char val : cr) {
if (set.contains( val ))
set.remove( val );
else
set.add( val );
}
System.out.println( set.iterator().next() );
node
【在 h*******0 的大作中提到】
: Find out the first non duplicate character in a string.
: eg: "nasa" output: 'n'
: 只允许扫一遍字符串， 如果只是用hash，需要扫2遍。 我的想法是用double linked
: list和hash。 第一次读到char， 就放到linkedlist结尾， 并插入（char， 对应node
: pointer）到hash中。 如果第二次读到这个char， 把这个node删除， 将hash[char]
: 的value变成NULL。 如果删除的node为cur， 那么删除cur， 并让cur指向下一个。 最
: 后返回cur的data。
: 这个方法可以吗？
|
y****n
发帖数: 743 | 13 面试中，如果遇到字符，一定要问一句字符的范围。
如果你默认是[0-255]，甚至[32-127]。
万一你兴冲冲地写完算法后，对方告诉你，你的算法对中日韩文字出错，岂不晚矣了？ |
c******5
发帖数: 84 | 14 这样写应该有问题吧。。
输出肯定是一个字典顺序的非duplicate的结果
比如输入是ba 那输出就是a而不是b吧
【在 s*****n 的大作中提到】
: bool findFirstNonDuplicate(string str, out firtchar) {
: int n = str.size();
: if (!n) return false;
: // assume string contains only ascii chars
: int map[256] = {0};
: for(int i = 0 ; i < str.Length; i++)
: map[str[i])++;
: for (int j = 0; j < 256; j++)
: if (map[j] == 1)
: {
|
r********g
发帖数: 14 | 15 基于你的算法，我稍作改变：
建立一个hashset 和一个linkedlist， linkedlist 不需要double single即可 有
header和tail两个指针
对于string， 在遍历时，先检验是存在于hashset之中 如果存在 检验下一个char
如果不存在，放到linkedlist的tail后面 tail指向这个node 同时放到hashset中
这样遍历string一边后，
从linkedlist的header 开始查找 如果存在于hashset中 header指向下一个， 如果不
存在于hashset
return header的value 如果header指向null return 不dupliate的char 不存在。 |
h*******0
发帖数: 270 | 16 虽然俺不太懂java，但是我觉得好像有点问题。 这样的序列可以通过吗？ “bbba”
【在 c*u 的大作中提到】
: 这样可以么
: String str = "lacyrkaplcknb";
: char[] cr = str.toCharArray();
: LinkedHashSet set = new LinkedHashSet();
: for (char val : cr) {
: if (set.contains( val ))
: set.remove( val );
: else
: set.add( val );
: }
|
f***c
发帖数: 40 | 17 他那个答案只是返回字母顺序第一个 不是原来string 第一个，认同这句话
【在 c******5 的大作中提到】
: 这样写应该有问题吧。。
: 输出肯定是一个字典顺序的非duplicate的结果
: 比如输入是ba 那输出就是a而不是b吧
|
h*******0
发帖数: 270 | 18 要遍历linkedlist是吗？ 其实我觉得BB家的人题都是乱出的。。
【在 r********g 的大作中提到】
: 基于你的算法，我稍作改变：
: 建立一个hashset 和一个linkedlist， linkedlist 不需要double single即可 有
: header和tail两个指针
: 对于string， 在遍历时，先检验是存在于hashset之中 如果存在 检验下一个char
: 如果不存在，放到linkedlist的tail后面 tail指向这个node 同时放到hashset中
: 这样遍历string一边后，
: 从linkedlist的header 开始查找 如果存在于hashset中 header指向下一个， 如果不
: 存在于hashset
: return header的value 如果header指向null return 不dupliate的char 不存在。
|
r********g
发帖数: 14 | 19
string 遍历一遍即可
伪码：
for each char in string str
if char in hashtable
change the value of key char in hashtable( key char value 2)
next char
else
linkedlist.tail->next.value= char
tail = tail->next;
add char to hashtable( key char value 1)
end of loop for string // just one time
//now let us deal with the linkedlist
while( header != null){
if header value in hashtable is 2 ( hashtable.get(header)==2) // header is
duplicate
header = header->next;
else return header->value // first non-duplicate char
}
return "all char in string is duplicate"
// go through the linkedlist, can not find non-duplicate char , all char
could be found in hashtable with value 2
【在 h*******0 的大作中提到】
: 要遍历linkedlist是吗？ 其实我觉得BB家的人题都是乱出的。。
|
c*u
发帖数: 22 | 20 一、用 HashSet 和 LinkedHashSet
String str = "cbacbbbfa";
HashSet set = new HashSet();
LinkedHashSet linkSet = new LinkedHashSet();
int len = str.length();
for (int i=0;i
char ch = str.charAt( i );
if (set.contains( ch ))
linkSet.remove( ch );
else{
set.add( ch );
linkSet.add( ch );
}
}
System.out.println( linkSet.iterator().next() );
二、用 HashSet 和 LinkedList
String str = "cbacbbbfa";
HashSet set = new HashSet();
List list = new LinkedList();
for (int i=0;i
char ch = str.charAt( i );
if (set.contains( ch )){
if(list.contains( ch ))
list.remove( (Object)ch );
}
else{
set.add( ch );
list.add( ch );
}
}
System.out.println( list.get(0) );
【在 h*******0 的大作中提到】
: 虽然俺不太懂java，但是我觉得好像有点问题。 这样的序列可以通过吗？ “bbba”
|
|
|
p*****p
发帖数: 379 | 21 对于二：list contain方法应该是遍历的吧，这样变成O(n^2)了？
【在 c*u 的大作中提到】
: 一、用 HashSet 和 LinkedHashSet
: String str = "cbacbbbfa";
: HashSet set = new HashSet();
: LinkedHashSet linkSet = new LinkedHashSet();
: int len = str.length();
: for (int i=0;i: char ch = str.charAt( i );
: if (set.contains( ch ))
: linkSet.remove( ch );
: else{
|
p****e
发帖数: 3548 | 22 试了一下，合格不
// Type your C++ code and click the "Run Code" button!
// Your code output will be shown on the left.
// Click on the "Show input" button to enter input data to be read (from
stdin).
#include
using namespace std;
char getnonduplicate(string s)
{
int size = s.size();
if(size == 0) return '\0';
vector cc;
int lastnonduplicate = 0;
for(int i = 0; i < size; i++)
{
bool duplicate = false;
for(int j=0; j < cc.size(); j++)
{
if(cc[j] == s[i])
{
duplicate = true;
if(j < lastnonduplicate)
{
cc.erase(cc.begin() + j);
cc.push_back(s[i]);
lastnonduplicate--;
}
break;
}
}
if(! duplicate)
{
cc.insert(cc.begin() + lastnonduplicate, s[i]);
lastnonduplicate++;
}
}
if(lastnonduplicate != 0)
return cc[0];
else
return '\0';
}
int main() {
// Start typing your code here...
string s("nasasnmkkpppmegiil");
cout<
return 0;
} |
c********t
发帖数: 5706 | 23 大家为啥都用linkedlist呢？
linkedlist search and remove 都是O(n)啊，最终得到一个O（n^2)算法，还不如扫两
遍。
node
【在 h*******0 的大作中提到】
: Find out the first non duplicate character in a string.
: eg: "nasa" output: 'n'
: 只允许扫一遍字符串， 如果只是用hash，需要扫2遍。 我的想法是用double linked
: list和hash。 第一次读到char， 就放到linkedlist结尾， 并插入（char， 对应node
: pointer）到hash中。 如果第二次读到这个char， 把这个node删除， 将hash[char]
: 的value变成NULL。 如果删除的node为cur， 那么删除cur， 并让cur指向下一个。 最
: 后返回cur的data。
: 这个方法可以吗？
|
c*u
发帖数: 22 | 24 直接调 remove也行
if (set.contains( ch ))
linkSet.remove( ch );
【在 p*****p 的大作中提到】
: 对于二：list contain方法应该是遍历的吧，这样变成O(n^2)了？
|
c*u
发帖数: 22 | 25 linkedlist remove 是 O(1) 吧
【在 c********t 的大作中提到】
: 大家为啥都用linkedlist呢？
: linkedlist search and remove 都是O(n)啊，最终得到一个O（n^2)算法，还不如扫两
: 遍。
:
: node
|
w****a
发帖数: 710 | 26 可以获得string的大小么？可以的话从后往前扫，用hash辅助。 |
