Thursday, October 17, 2013

Copy List with random pointer@leetcode

刷题必备书籍Cracking the Coding Interview: 150 Programming Questions and Solutions 

简历:The Google Resume: How to Prepare for a Career and Land a Job at Apple, Microsoft, Google, or any Top Tech Company
算法学习书籍:Introduction to Algorithms
编程珠玑:Programming Pearls (2nd Edition)
C++ 学习:The C++ Programming Language, 4th Edition
经典操作系统书籍,龙书:Operating System Concepts
创业:The Start-up of You: Adapt to the Future, Invest in Yourself, and Transform Your Career

Copy List with Random Pointer


AC Rate: 1399/7131
My Submissions
A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null.
Return a deep copy of the list.
利用一个hashtable,在一边查找random和next的时候一边建立。

/**
* Definition for singly-linked list with a random pointer.
* struct RandomListNode {
* int label;
* RandomListNode *next, *random;
* RandomListNode(int x) : label(x), next(NULL), random(NULL) {}
* };
*/
class Solution {
public:
RandomListNode *copyRandomList(RandomListNode *head) {
if (!head) return NULL;
unordered_map<RandomListNode*, RandomListNode*> hm;
RandomListNode *pre = head, *tmp = head;
while(tmp) {
if (hm.count(tmp)) {
if(tmp!=head) hm[pre]->next = hm[tmp];
}else{
RandomListNode * t = new RandomListNode(tmp->label);
hm[tmp] = t;
if(tmp!=head) hm[pre]->next = hm[tmp];
}
if (tmp->random == NULL || hm.count(tmp->random)) {
hm[tmp]->random = hm[tmp->random];
}else{
RandomListNode * t = new RandomListNode(tmp->random->label);
hm[tmp->random] = t;
hm[tmp]->random = hm[tmp->random];
}
pre = tmp;
tmp = tmp->next;
}
return hm[head];
}
};

No comments:

Post a Comment

Leetcode 316. Remove Duplicate Letters

 这道题表面问的是如何删除重复,实际在问如何从多个字符选取一个保留,从而让整个字符串按升序排列。那么策略就是对于高顺位的字符比如‘a',就要选靠前位置的保留,而低顺位字符如’z'则应该尽量选取靠后位置保留。 算法大概思路:每看到一个字符,我们要决定是否保留 1. ...