首页 > 代码库 > 笔试算法题（10）：深度优先，广度优先以及层序遍历 & 第一个仅出现一次的字符
笔试算法题（10）：深度优先，广度优先以及层序遍历 & 第一个仅出现一次的字符
出题：要求实现层序遍历二元搜索树，并对比BFS与DFS的区别
分析：层序遍历也就是由上至下，从左到右的遍历每一层的节点，类似于BFS的策略，使用Queue可以实现，BFS不能用递归实现（由于每一层都需要存储所有节点，所以非常耗用内存）。这段代码主要用于反映BFS与DFS的联系；
解题：
1 class Node { 2 public: 3 int value; 4 Node *left; 5 Node *right; 6 }; 7 8 class MyStack { 9 private: 10 Node *array[]; 11 int capability; 12 int top; 13 public: 14 MyStack(int cap=5): array((Node**)malloc(sizeof(Node*)*cap)), capability(cap), top(0) {} 15 ~MyStack() { 16 for(int i=0;i<top;i++) 17 delete array[i]; 18 delete [] array; 19 } 20 21 bool isFull() { 22 return top == capability; 23 } 24 bool isEmpty() { 25 return top == 0; 26 } 27 int freeSlot() { 28 return capability - top; 29 } 30 31 /** 32 * top当前的位置就是下一个push元素所在的slot 33 * */ 34 bool push(Node *n) { 35 if(isFull()) return false; 36 array[top++]=n; 37 return true; 38 } 39 Node* pop() { 40 if(isEmpty()) return false; 41 return array[--top]; 42 } 43 void ShowStack() { 44 int temp=top-1; 45 printf("\n"); 46 for(int i=0;i<=temp;i++) 47 printf("%d, ",array[i]->value); 48 printf("\n"); 49 } 50 51 }; 52 53 class MyQueue { 54 private: 55 Node *array[]; 56 int capability; 57 int length; 58 int head; 59 int tail; 60 public: 61 MyQueue(int n=5): array((Node**)malloc(sizeof(Node*)*n)), head(0),tail(0),capability(n), length(0) {} 62 ~MyQueue() {delete [] array;} 63 64 bool isFull() { 65 if(length == capability) return true; 66 return false; 67 } 68 bool isEmpty() { 69 if(length == 0) return true; 70 return false; 71 } 72 int freeSlot() { 73 return capability-length; 74 } 75 void setBack() { 76 length=0; 77 } 78 /** 79 * head当前的指向位置是下一次将push的元素的 80 * */ 81 bool push(Node *n) { 82 if(isFull()) return false; 83 array[head]=n; 84 85 head=(head+1)%(capability); 86 length++; 87 return true; 88 } 89 /** 90 * tail当前指向的位置是下一次将pop的元素的 91 * */ 92 Node* pop() { 93 if(isEmpty()) return false; 94 int temp=tail; 95 tail=(tail+1)%(capability); 96 length--; 97 return array[tail]; 98 } 99 100 void showQueue() { 101 int i=tail; 102 int temp=length; 103 printf("\ncurrent stack elements: \n"); 104 while(temp>0) { 105 printf("%d, ",array[i++]->value); 106 temp--; 107 } 108 } 109 }; 110 /** 111 * 只要把MyQueue *queue=new MyQueue()换成 112 * MyStack *stack=new MyStack() 113 * 其他代码不变，就是dfs 114 * */ 115 void bfs(Node *root) { 116 MyQueue *queue=new MyQueue(); 117 Node *current; 118 printf("%d, ", root->value); 119 while(!queue->isEmpty()) { 120 current=queue->pop(); 121 if(current->left != NULL) { 122 printf("%d, ", current->left->value); 123 queue->push(current->left); 124 } 125 if(current->right != NULL) { 126 printf("%d, ", current->right->value); 127 queue->push(current->right); 128 } 129 } 130 delete queue; 131 }
出题：在一个字符串中找到第一个仅出现过一次的字符；
分析：
- 解法1：创建辅助链表顺序存储仅出现过一次字符；每当从字符串中扫描一个新字符都遍历辅助链表，如果有相同值则删除对应的链表节点，如果没有相同值则存储 在链表尾，直到扫描完所有字符；最终辅助链表头节点就是第一次仅出现过一次的字符；时间复杂度分析：最坏情况当所有字符都仅出现一次，O（n2），最好情 况O（n）；
- 解法2：一般涉及到大范围分布的有限字符，并且需要记录字符出现次数或者其他累加值的时候，哈希表（Hash Table）往往是第一选择；表宽度是所有可能出现的字符个数，256个，这样位置信息也就是字符编码；每一个slot记录的信息是对应位置的字符是否出 现超过1次，如果有严格的空间要求可以使用2bit的BitMap，简单起见可以直接使用int类型。当第一遍扫描字符串之后，字符信息就已经映射到 Hash Table中，第二遍再次扫描字符串，并在Hash Table中查找对应的出现次数，一旦遇到仅出现一次的字符，扫描结束，如果没有则扫描失败。如果不计Hash Function的时间，时间复杂度为O（n），Hash Function正好是解法1中顺序遍历放的优化，对于复杂的Hash Function，其时间复杂度有关键性影响；
解题：
1 char FindFirstChar(const char *target) { 2 const char *current=target; 3 int hashTable[256]; 4 5 /** 6 * 需要将Hash Table初始化，可以使用memset所有内存储都设置为0； 7 * 对于256大小的Table，其不能处理宽字符的情况 8 * */ 9 //memset(hashTable, 0, sizeof(int)*256); 10 for(int i=0;i<256;i++) { 11 hashTable[i]=0; 12 } 13 14 /** 15 * 这里可能出现的问题是当字符重复次数过多，int可能溢出，所以优化版本 16 * 使用2代表所有出现超过一次的情况 17 * */ 18 while(*current != ‘\0‘) { 19 if(hashTable[*current] == 2) { 20 current++; 21 } else { 22 hashTable[*current]++; 23 current++; 24 } 25 } 26 27 current=target; 28 while(*current != ‘\0‘) { 29 if(hashTable[*current] == 1) { 30 return *current; 31 } 32 current++; 33 } 34 /** 35 * 当从这里返回则说明所有字符都出现超过一次，所以返回-1，表示 36 * 没有任何可行字符，所以调用函数需要使用int类型，然后判断是否 37 * 为-1，如果不是才转换为char类型 38 * */ 39 return -1; 40 } 41 42 int main() { 43 const char *target="1234561234567"; 44 int temp=(int)FindFirstChar(target); 45 if(temp!=-1) { 46 printf("\nthe first char is : %c\n",(char)temp); 47 } else 48 printf("\nall chars are repeated more than once\n"); 49 50 return 0; 51 }
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。