设s和t是表示成单链表的两个串,试编写一个找出s中第1个不在t中出现的字符(假定每个结点只存放一个字符)的算法。
时间: 2024-01-22 12:21:15 浏览: 179
单链表的应用,多项式的合并
4星 · 用户满意度95%
可以使用哈希表来实现这个算法。
具体步骤如下:
1. 对于字符串t,将其中的每个字符都插入到哈希表中。
2. 遍历字符串s,对于其中的每个字符,查找其是否在哈希表中出现过。如果没有出现过,则找到了第1个不在t中出现的字符。如果遍历完s后仍然没有找到这样的字符,则说明s中的所有字符都在t中出现过。
代码实现如下:
```
char findFirstUniqueChar(ListNode* s, ListNode* t) {
unordered_set<char> hash;
ListNode* p = t;
while (p != nullptr) {
hash.insert(p->val);
p = p->next;
}
p = s;
while (p != nullptr) {
if (hash.find(p->val) == hash.end()) {
return p->val;
}
p = p->next;
}
return '\0';
}
```
其中,ListNode表示单链表结点,val表示结点存储的字符值。
阅读全文