leetcode Question: Clone Graph

Clone Graph

     Clone an undirected graph. Each node in the graph contains a label and a list of its neighbors.

OJ's undirected graph serialization:
Nodes are labeled uniquely.
We use # as a separator for each node, and , as a separator for node label and each neighbor of the node.
As an example, consider the serialized graph {0,1,2#1,2#2,2}.
The graph has a total of three nodes, and therefore contains three parts as separated by #.
  1. First node is labeled as 0. Connect node 0 to both nodes 1 and 2.
  2. Second node is labeled as 1. Connect node 1 to node 2.
  3. Third node is labeled as 2. Connect node 2 to node 2 (itself), thus forming a self-cycle.
Visually, the graph looks like the following:
       1
      / \
     /   \
    0 --- 2
         / \
         \_/

Analysis:

At the first look, this problem seems wired. Remind the Copy Constructor of a class object, when the class member contains pointers, the direct copy is shadow, we need deep copy. For this problem, there are two major tasks:
(1)  Traverse the graph
(2)  Construct the new graph at the same time.

Traverse the graph is similar to the tree traversal, both DFS and  BFS can be used. Slight difference  is to consider the loop in the graph (e.g., the 2-->2 in the above figure), thus we need store the visited vertex information. If the neighbor of current node has not been visited, then search that node.

Only one point should be noticed for constructing the new graph, in the code below, I used a map< int, node*> to store the visited information, so that if the node has been visited, just add the map[int] to the current node's neighbor list. Be careful the current node is the node you "newed", but not the node in the original graph (line 12 and 13 in the code below. If you set visited[v->label] = v, it is not correct.).

Code:

/**
 * Definition for undirected graph.
 * struct UndirectedGraphNode {
 *     int label;
 *     vector<UndirectedGraphNode *> neighbors;
 *     UndirectedGraphNode(int x) : label(x) {};
 * };
 */
class Solution {
public:
    UndirectedGraphNode* dfs(UndirectedGraphNode *v, map<int, UndirectedGraphNode*> &visited){
        UndirectedGraphNode* res = new UndirectedGraphNode(v->label);
        visited[v->label]=res;
        for (int i=0;i<v->neighbors.size();i++){
            if (!visited[v->neighbors[i]->label]){
                res->neighbors.push_back(dfs(v->neighbors[i],visited));
            }else{
                res->neighbors.push_back(visited[v->neighbors[i]->label]);
            }
        }
        return res;
    }
    UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) {
        // IMPORTANT: Please reset any member data you declared, as
        // the same Solution instance will be reused for each test case.
        if (node==NULL){
            return NULL;
        }else{
            map<int, UndirectedGraphNode*> visited;
            UndirectedGraphNode* res = dfs(node, visited);
            return res;
        }
           
    }
};

leetcode Question: Linked List Cycle

Linked List Cycle

Given a linked list, determine if it has a cycle in it.
Follow up:
Can you solve it without using extra space?

Analysis:

Currently the best way I can figure out is the classic two pointers.
One pointer is slow (1 step a time)
One pointer is fast (2 steps a time)
If there is a cycle, the two pointers will eventually meet (equal).


Code:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    bool hasCycle(ListNode *head) {
        // IMPORTANT: Please reset any member data you declared, as
        // the same Solution instance will be reused for each test case.
        if (!head){return false;}
        ListNode* p=head;
        ListNode* q=head;
        while(q->next && q->next->next){
            p=p->next;
            q=q->next->next;
            if (p==q){return true;}
        }
        return false;
    }
};

leetcode Question: Single Number I

Single Number

Given an array of integers, every element appears twice except for one. Find that single one.
Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

Analysis:


The requirement is O(n) time and O(1) space.
Thus, the  "first sort and then find " way is not working.
Also the "hash map" way is not working.

Since we can not sort the array, we shall find a cumulative way, which is not about the ordering.

XOR is a good way, we can use the property that A XOR A = 0, and A XOR B XOR A = B.

So, the code becomes extremely easy.

Code(C++):


class Solution {
public:
    int singleNumber(int A[], int n) {
        // IMPORTANT: Please reset any member data you declared, as
        // the same Solution instance will be reused for each test case.
        int res = A[0];
        for (int i=1;i<n;i++){
            res = res ^ A[i];
        }
        return res;
    }
};

Code (Python):


class Solution:
    # @param A, a list of integer
    # @return an integer
    def singleNumber(self, A):
        res = 0
        for a in A:
            res = res ^ a
        return res