设s和t是表示成单链表的两个串,试编写一个找出s中第1个不在t中出现的字符(假定每个结点只存放一个字符)的算法。
时间: 2024-01-22 10:21:15 浏览: 26
可以使用哈希表来实现这个算法。
具体步骤如下:
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表示结点存储的字符值。
相关问题
设s和t是表示成单链表的两个串,试编写一个找出s中第1个不在t中出现的字符(假设每一个结点只存放一个字符)的的算法。
### 回答1:
算法思路:
1. 遍历s串,对于每个字符,都在t串中查找是否存在。
2. 如果不存在,则说明该字符是s中第一个不在t中出现的字符,直接返回该字符即可。
3. 如果遍历完s串都没有找到不在t中出现的字符,则返回空。
算法实现:
```
char findFirstCharNotInT(ListNode* s, ListNode* t) {
unordered_set<char> charSet;
while (t != nullptr) {
charSet.insert(t->val);
t = t->next;
}
while (s != nullptr) {
if (charSet.find(s->val) == charSet.end()) {
return s->val;
}
s = s->next;
}
return '\0';
}
```
算法分析:
时间复杂度:O(m+n),其中m和n分别为s和t的长度。
空间复杂度:O(n),其中n为t的长度,用一个哈希表存储t中的字符。
### 回答2:
这道题目是一道关于链表操作的算法题,我们可以通过两个指针来完成查找。算法思路如下:
1.先遍历链表t,将其中出现过的字符标记一下。这可以使用一个大小为256的数组来实现,数组下标为字符的ASCII码,数组值为1表示该字符出现过。
2.遍历链表s,对于每个字符,查看是否已经在t中出现过。这可以使用第一步中的数组进行查询,如果该字符的值为0,则说明该字符是s中的第1个不在t中出现的字符,输出该字符并结束程序。
3.如果在遍历完链表s之前未能找到目标字符,则说明s中所有的字符都出现过,输出提示信息并结束程序。
代码实现如下:
```
char find_first_not_in_t(List* s, List* t) {
int char_set[256] = { 0 };
Node* t_ptr = t->head;
while (t_ptr != NULL) {
char_set[t_ptr->data] = 1;
t_ptr = t_ptr->next;
}
Node* s_ptr = s->head;
while (s_ptr != NULL) {
if (char_set[s_ptr->data] == 0) {
return s_ptr->data;
}
s_ptr = s_ptr->next;
}
printf("所有字符都在t中出现过");
exit(1);
}
```
### 回答3:
我们可以使用哈希表来解决这个问题。具体步骤如下:
1. 将串t中的所有字符都存入哈希表中,其中哈希表的key为字符,value为该字符在串t中出现的次数。
2. 从串s的头结点开始遍历,逐个检查每个节点中存储的字符是否出现在哈希表中。
3. 若该节点中的字符不在哈希表中,说明该字符是s中第一个不在t中出现的字符,直接返回该字符即可。
4. 若遍历到链表结尾,仍未找到该字符,则返回空字符,表示串s中所有字符都在串t中出现过。
时间复杂度分析:整个算法需要遍历两个链表,时间复杂度为O(n),其中n为链表长度。由于哈希表的插入和查找操作时间复杂度均为O(1),所以不会增加总体时间复杂度。因此,本算法的时间复杂度为O(n)。
用C语言设计:设s和t是表示成单链表的两个串,试编写一个找出s中第1个不在t中出现的字符(假定每个结点只存放一个字符)的算法。
以下是一种基于哈希表的实现方法:
1. 新建一个哈希表,用于存储t中出现的字符;
2. 遍历s中的每个字符,如果该字符不在哈希表中,则返回该字符,否则继续遍历;
3. 如果遍历完s后仍未找到符合条件的字符,则返回空字符。
下面是代码实现:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 1000
typedef struct Node {
char data;
struct Node *next;
} ListNode, *LinkedList;
LinkedList createList(char *s) {
LinkedList L = (LinkedList) malloc(sizeof(ListNode));
L->next = NULL;
ListNode *p = L;
while (*s) {
ListNode *node = (ListNode *) malloc(sizeof(ListNode));
node->data = *s++;
node->next = NULL;
p->next = node;
p = node;
}
return L;
}
char findFirstChar(LinkedList s, LinkedList t) {
int hash[MAXSIZE] = {0}; // 哈希表
ListNode *p = t->next;
while (p) { // 将t中的字符加入哈希表
hash[p->data]++;
p = p->next;
}
p = s->next;
while (p) { // 在s中查找第一个不在t中出现的字符
if (!hash[p->data]) {
return p->data;
}
p = p->next;
}
return '\0';
}
int main() {
char *s = "hello world";
char *t = "world";
LinkedList Ls = createList(s);
LinkedList Lt = createList(t);
char c = findFirstChar(Ls, Lt);
if (c != '\0') {
printf("The first character in s that does not appear in t is: %c\n", c);
} else {
printf("No such character found.\n");
}
return 0;
}
```
注意:该实现方法假定字符集大小不超过哈希表的最大容量 MAXSIZE,如果字符集过大,需要考虑使用其他数据结构或算法。
相关推荐
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)