2. 有两个已递增有序的单链表pLinkList和qLinkList，将这两个链表合并成一个递增有序的链表，请自己定义单链表的结构。 解答：同样很经典，不用多说，直接上我自己的code（不是最好的）：  #include <iostream> using namespace std; struct LinkList { int data; LinkList *next; }; LinkList* createList() { LinkList *head = NULL, *p, *q; int data; cin >> data; while(data) { p = new LinkList; p->data = data; p->next = NULL; if(head == NULL) { head = p; q = head; } else { q->next = p; q = p; } cin >> data; } return head; } // 合并后的链表放在pLinkList中 void merge(LinkList *&pLinkList, LinkList *qLinkList) { LinkList *pre, *p, *q; pre = NULL; p = pLinkList; q = qLinkList; while(p != NULL && q != NULL) { if(p->data < q->data) { pre = p; p = p->next; } else { // 如果p第一个结点大于q，则改变合并后头结点为q if(pre == NULL) { pLinkList = q; } else { pre->next = q; } pre = q; q=q->next; pre->next = p; } } // 最后不要忘了qLinkList剩余的大结点 if(q != NULL) { pre->next = q; } } void print(LinkList *l) { LinkList *p = l; while(p != NULL) { if(p->next == NULL) { cout << p->data; break; } cout << p->data << " -> "; p = p->next; } cout << endl; } int main() { cout << "Please enter pLinkList: "; LinkList *pLinkList = createList(); print(pLinkList); cout << "\nPlease enter pLinkList: "; LinkList *qLinkList = createList(); print(qLinkList); merge(pLinkList, qLinkList); cout << "\nThe merge LinkList is: \n"; print(pLinkList); return 0; }
3. 具体题目不记得，大概意思就是：从N个数中随机抽取出M个数（M < N），为了使抽取比较均匀，请自己定义抽取函数使得抽取的数既均匀又尽量随机。 解答：当时时间太急了，没来得及多想，做法很傻：从1 ~ M*N中随机抽取一个数字，然后mod (N + 1)，求得的值为N个数中的下标，再根据此下标去N个数中取，重复M次即可。假如这N个数存在数组nArray[]中，抽取的M个数存在数组mArray[]中，伪代码描述如下： for(int i = 0; i < M; i++) { int index = Random(M * N) % N; mArray[i] = nArray[index]; } 由于觉得这个算法实在是不好，就懒得测试了，大家有好想法的赶紧提出来吧。 四、扩展题具体题目也记不清了，一大堆描述，大概意思是：有一个海量日志库，里面的每条日志记录都有相应的关键词和访问次数，但记录是无序的，为了挖掘客户偏好，需要找出前N个最高访问次数的日志记录，请设计算法尽量使时间复杂度和空间复杂度最低。 解答：典型的Top K问题，我用的算法也是大家都知道的，大致描述下思路：假如关键词和访问次数成一个记录结构体，维护一个有N个该结构体的小根堆，初始化为N个日志记录的关键词和访问次数（建堆算法），每次有新的记录时，将该记录的访问次数与小根堆的堆顶元素进行比较，如果大于堆顶元素则与堆顶元素交换记录，然后调整堆结构使其重新为一个小根堆，否则置之不理。当所有记录遍历完后，所有的堆元素就是所要求的前N个最高访问次数的日志记录。时间复杂度为O(MlgN)，不知道自己分析的对不对，完全是自以为是的想法，如果大家有更好的算法欢迎提出！
|
