Count of Smaller Number I && II

Count of Smaller Number I 

Give you an integer array (index from 0 to n-1, where n is the size of this array, value from 0 to 10000) and an query list. For each query, give you an integer, return the number of element in the array that are smaller that the given integer.

Example

For array [1,2,7,8,5], and queries [1,8,5], return [0,4,2]

Note

We suggest you finish problem Segment Tree Build and Segment Tree Query II first.

Challenge

Could you use three ways to do it.

  1. Just loop
  2. Sort and binary search
  3. Build Segment Tree and Search.

Solution:  Version 1. sort + binary search O(nlogn) Time
//Version 2. Segment Tree. not as efficient as version 1.
//check <Count of Smaller Number II>

public ArrayList<Integer> countOfSmallerNumber(int[] A, int[] queries) {
    //Version 1. sort + binary search
    //Version 2. Segment Tree. not as efficient as version 1.
    //check <Count of Smaller Number before itself>
    ArrayList<Integer> result = new ArrayList<>();
    if (A == null || queries == null) {
        return result;
    }
    if (A.length == 0) {
        for (int i = 0; i < queries.length; i++) {
            result.add(0);
        }
        return result;
    }
    Arrays.sort(A);
    for (int i = 0; i < queries.length; i++) {
        int target = queries[i];
        //find the last element A[i]<target, i+1 is the number
        int start = 0;
        int end = A.length - 1;
        while (start + 1 < end) {
            int mid = start + (end - start) / 2;
            if (A[mid] < target) {
                start = mid;
            } else {
                end = mid;
            }
        }
        if (A[end] < target) {
            result.add(end + 1);
        } else if (A[start] < target) {
            result.add(start + 1);
        } else {
            result.add(0);
        }
    }
    return result;
}

Count of Smaller Number II

Give you an integer array (index from 0 to n-1, where n is the size of this array, value from 0 to 10000) . For each elementAi in the array, count the number of element before this element Ai is smaller than it and return count number array.

Example

For array [1,2,7,8,5], return [0,1,2,3,2]

Note

We suggest you finish problem Segment Tree Build, Segment Tree Query II and Count of Smaller Number before itself I first.

Solution: Segment Tree. 这道题不能用sort+binary search的方法了因为顺序不能改变。

建一个0-10000的值型线段树。然后每个叶子节点代表这个值的count。所以在A[i]之前比它小的数的个数就是那个0~A[i]-1这个node 的count值。之后每次Query以后把A[i]那个leaf node count++, 相应回溯更新它所有父亲节点。

时间复杂度是O(m + nlogm) m是值的区间,n是query个数。

这个算法是否最优需要分情况,如果值特别分散且query数特别小,那还不如每次query用O(n)的时间count它之前的比她小的数。

public class SegmentTreeNode {
    int start, end;
    int count;
    SegmentTreeNode left;
    SegmentTreeNode right;
    public SegmentTreeNode(int start, int end) {
        this.start = start;
        this.end = end;
        this.count = 0;
    }
}

public ArrayList<Integer> countOfSmallerNumberII(int[] A) {
    ArrayList<Integer> result = new ArrayList<>();
    if (A == null || A.length == 0) {
        return result;
    }
    SegmentTreeNode node = buildSegmentTree(0, 10000);
    for (int i = 0; i < A.length; i++) {
        if (A[i] == 0) {
            result.add(0);
        } else {
            result.add(query(node, 0, A[i] - 1));
        }
        update(node, A[i]);
    }
    return result;
}

public SegmentTreeNode buildSegmentTree(int start, int end) {
    SegmentTreeNode node = new SegmentTreeNode(start, end);
    if (start < end) {
        int mid = start + (end - start) / 2;
        node.left = buildSegmentTree(start, mid);
        node.right = buildSegmentTree(mid + 1, end);
        node.count = node.left.count + node.right.count;
    }
    return node;
}

public int query(SegmentTreeNode node, int start, int end) {
    if (node.start == start && node.end == end) {
        return node.count;
    }
    int leftCount = 0, rightCount = 0;
    int mid = node.start + (node.end - node.start) / 2;
    if (start <= mid) {
        if (end <= mid) {
            leftCount = query(node.left, start, end);
        } else {
            leftCount = query(node.left, start, mid);
        }
    }
    if (end > mid) {
        if (start > mid) {
            rightCount = query(node.right, start, end);
        } else {
            rightCount = query(node.right, mid + 1, end);
        }
    }
    return leftCount + rightCount;
}

public void update(SegmentTreeNode node, int index) {
    if (node.start == index && node.end == index) {
        node.count = node.count + 1;
    } else {
        int mid = node.start + (node.end - node.start) / 2;
        if (node.start <= index && index <= mid) {
            update(node.left, index);
        } else if (mid < index && index <= node.end) {
            update(node.right, index);
        }
        node.count = node.left.count + node.right.count; //or node.count = node.count+1;
    }
}
FacebookTwitterGoogle+Share

Interval Sum I && II

Interval Sum I

Given an integer array (index from 0 to n-1, where n is the size of this array), and an query list. Each query has two integers [start, end]. For each query, calculate the sum number between index start and end in the given array, return the result list.

Example

For array [1,2,7,8,5], and queries [(0,4),(1,2),(2,4)], return [23,9,20]

Note

We suggest you finish problem Segment Tree Build, Segment Tree Query and Segment Tree Modify first.

Challenge

O(logN) time for each query

Solution: Version 1. prefix sum,
(Version 2. Segment tree: check Interval Sum II)

public ArrayList<Long> intervalSum(int[] A,
                                   ArrayList<Interval> queries) {
    //Version 1. prefix sum,
    //Version 2. Segment tree: check Interval Sum II
    ArrayList<Long> result = new ArrayList<>();
    if (A == null || queries == null || A.length == 0 || queries.size() == 0) {
        return result;
    }
    Long[] prefixSum = new Long[A.length];
    Long sum = 0L;
    for (int i = 0; i < A.length; i++) {
        sum += A[i];
        prefixSum[i] = sum;
    }
    for (Interval interval : queries) {
        if (interval.start == 0) {
            result.add(prefixSum[interval.end]);
        } else {
            result.add(prefixSum[interval.end] - prefixSum[interval.start - 1]);
        }

    }
    return result;
}

Interval Sum II

Given an integer array in the construct method, implement two methods query(start, end) andmodify(index, value):

  • For query(start, end), return the sum from index start to index end in the given array.
  • For modify(index, value), modify the number in the given index to value

Example

Given array A = [1,2,7,8,5].

  • query(0, 2), return 10.
  • modify(0, 4), change A[0] from 1 to 4.
  • query(0, 1), return 6.
  • modify(2, 1), change A[2] from 7 to 1.
  • query(2, 4), return 14.

Note

We suggest you finish problem Segment Tree Build, Segment Tree Query and Segment Tree Modify first.

Challenge

O(logN) time for query and modify.

Solution: Segment Tree.

建立:O(n) 时间

查询:O(logN) 时间

更改其中一个元素: O(logN)

public class Solution {
    SegmentTreeNode root;

    public class SegmentTreeNode {
        int start, end;
        int sum;
        SegmentTreeNode left;
        SegmentTreeNode right;
        public SegmentTreeNode(int start, int end) {
            this.start = start;
            this.end = end;
        }
    }
    public Solution(int[] A) {
        if (A == null || A.length == 0) {
            return;
        }
        this.root = buildSegmentTree(A, 0, A.length - 1);
    }

    private SegmentTreeNode buildSegmentTree(int[] A, int start, int end) {
        SegmentTreeNode node = new SegmentTreeNode(start, end);
        if (start == end) {
            node.sum = A[start];
        } else {
            int mid = start + (end - start) / 2;
            node.left = buildSegmentTree(A, start, mid);
            node.right = buildSegmentTree(A, mid + 1, end);
            node.sum = node.left.sum + node.right.sum;
        }
        return node;
    }

    public long query(int start, int end) {
        if (start < this.root.start || end > this.root.end) {
            return -1;
        }
        return query(this.root, start, end);
    }

    private long query(SegmentTreeNode root, int start, int end) {
        if (root.start == start && root.end == end) {
            return root.sum;
        }
        int mid = root.start + (root.end - root.start) / 2;
        long leftSum = 0L, rightSum = 0L;
        if (start <= mid) {
            if (end <= mid) {
                leftSum = query(root.left, start, end);
            } else {
                leftSum = query(root.left, start, mid);
            }
        }
        if (end > mid) {
            if (start > mid) {
                rightSum = query(root.right, start, end);
            } else {
                rightSum = query(root.right, mid + 1, end);
            }
        }
        return leftSum + rightSum;
    }

    public void modify(int index, int value) {
        modify(this.root, index, value);
    }

    public void modify(SegmentTreeNode root, int index, int value) {
        if (root.start == index && root.end == index) {
            root.sum = value;
        } else {
            int mid = root.start + (root.end - root.start) / 2;
            if (index <= mid) {
                modify(root.left, index, value);
            } else {
                modify(root.right, index, value);
            }
            root.sum = root.left.sum + root.right.sum;
        }
    }
}

Majority Number I & II & III

Majority Number I (找一个出现次数>1/2的数)

Given an array of integers, the majority number is the number that occurs more than half of the size of the array. Find it.

Example

Given [1, 1, 1, 1, 2, 2, 2], return 1

Challenge

O(n) time and O(1) extra space

Solution: 用的抵消的思想,如果两个数不一样大,就相互抵消,一样大就保留, 用count计数

public int majorityNumber(ArrayList<Integer> nums) {
    int candidate = -1;
    int count = 0;
    for (int i = 0; i < nums.size(); i++) {
        if (count == 0) {
            candidate = nums.get(i);
            count++;
        } else {
            if (candidate == nums.get(i)) {
                count++;
            } else {
                count--;
            }
        }
    }
    return candidate;
}

Majority Number II (找一个出现次数>1/3的数)

Given an array of integers, the majority number is the number that occurs more than 1/3 of the size of the array.

Find it.

Example

Given [1, 2, 1, 2, 1, 3, 3], return 1.

Note

There is only one majority number in the array.

Challenge

O(n) time and O(1) extra space.

Solution: 策略和I一样,只是现在有两个candidate,

public int majorityNumber(ArrayList<Integer> nums) {
    int candidate1 = -1;
    int candidate2 = -1;
    int count1 = 0;
    int count2 = 0;
    for (Integer num : nums) {
        if (candidate1 == num) {
            count1 ++;
        } else if (candidate2 == num) {
            count2 ++;
        } else if (count1 == 0) {
            candidate1 = num;
            count1 = 1;
        } else if (count2 == 0) {
            candidate2 = num;
            count2 = 1;
        } else {
            count1--;
            count2--;
        }
    }
    if (count1 == 0) {
        return candidate2;
    }
    if (count2 == 0) {
        return candidate1;
    }
    count1 = 0;
    count2 = 0;
    for (Integer num : nums) {
        if (num == candidate1) {
            count1++;
        }
        if (num == candidate2) {
            count2++;
        }
    }
    return count1 > count2 ? candidate1 : candidate2;
}

Majority Number III (找一个出现次数>1/k的数)

Given an array of integers and a number k, the majority number is the number that occurs more than 1/k of the size of the array.

Find it.

Example

Given [3,1,2,3,2,3,3,4,4,4] and k=3, return 3.

Note

There is only one majority number in the array.

Challenge

O(n) time and O(k) extra space

Solution: Similar approach as I & II

public int majorityNumber(ArrayList<Integer> nums, int k) {
    Map<Integer, Integer> majorityCounts = new HashMap<>();
    for (Integer num : nums) {
        if (majorityCounts.containsKey(num)) {
            majorityCounts.put(num, majorityCounts.get(num) + 1);
        } else {
            if (majorityCounts.size() < k - 1) {
                majorityCounts.put(num, 1);
            } else {
                List<Integer> toBeRemoved = new ArrayList<>();
                for (Integer key : majorityCounts.keySet()) {
                    if (majorityCounts.get(key) > 1) {
                        majorityCounts.put(key, majorityCounts.get(key) - 1);
                    } else {
                        toBeRemoved.add(key);
                    }
                }
                //important here: can not remove the element while iterating the set
                //which will cause ConcurrentModificationException
                for (Integer key : toBeRemoved) {
                    majorityCounts.remove(key);
                }
            }
        }
    }
    Set<Integer> results = majorityCounts.keySet();
    int maxCount = 0;
    int candidate = 0;
    for (Integer key : majorityCounts.keySet()) {
        majorityCounts.put(key, 0);
    }
    for (Integer num : nums) {
        if (majorityCounts.containsKey(num)) {
            int count = majorityCounts.get(num) + 1;
            majorityCounts.put(num, count);
            if (count > maxCount) {
                maxCount = count;
                candidate = num;
            }
        }
    }
    return candidate;
}

Lintcode: Data Stream Median

Data Stream Median

Numbers keep coming, return the median of numbers at every time a new number added.

 

Example

For numbers coming list: [1, 2, 3, 4, 5], return [1, 1, 2, 2, 3].

For numbers coming list: [4, 5, 1, 3, 2, 6, 0], return [4, 4, 4, 3, 3, 3, 3].

For numbers coming list: [2, 20, 100], return [2, 2, 20].

Challenge

Total run time in O(nlogn).

Clarification

What’s the definition of Median? – Median is the number that in the middle of a sorted array. If there are n numbers in a sorted array A, the median is A[(n - 1) / 2]. For example, if A=[1,2,3], median is 2. If A=[1,19], median is 1.

Solution: 维护两个堆 左边是max heap右边是min heap。当有新的数进来时先比较两个heap的数量 永远让left和right的size一样或者left比right多1, 这样的话median永远是left.poll()。然后确定好应该加到哪个heap之后,要比较当前数和两个堆顶数的大小,来决定是直接把该数放到那个heap中还是应该把另外一个heap的root放过来然后把这个数放到另外那个堆里。

O(NlogN) time.

public int[] medianII(int[] nums) {
	if (nums == null || nums.length == 0) {
		return nums;
	}
	int initialSize = 20;
	int[] median = new int[nums.length];
	Queue < Integer > leftHeap = new PriorityQueue < > (initialSize,
	new Comparator < Integer > () {
		public int compare(Integer a, Integer b) {
			return b - a;
		}
	});
	Queue < Integer > rightHeap = new PriorityQueue < > ();

	for (int i = 0; i < nums.length; i++) {
		if (leftHeap.size() > rightHeap.size()) {
			//need to put this one to rightHeap
			if (nums[i] >= leftHeap.peek()) {
				rightHeap.offer(nums[i]);
			} else {
				rightHeap.offer(leftHeap.poll());
				leftHeap.offer(nums[i]);
			}
		} else {
			//need to put this one to leftHeap
			if (leftHeap.isEmpty() && rightHeap.isEmpty()) {
				leftHeap.offer(nums[i]);
			} else {
				if (nums[i] <= rightHeap.peek()) {
					leftHeap.offer(nums[i]);
				} else {
					leftHeap.offer(rightHeap.poll());
					rightHeap.offer(nums[i]);
				}
			}
		}
		median[i] = leftHeap.peek();
	}
	return median;
}

LRU Cache

LRU Cache

Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and set.

get(key) – Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
set(key, value) – Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.

Solution: Use a doubly linked list, with a head and tail node pointers, as well as a hashMap with all the key and node pairs.

1. When get(), it first checks if the key is in the map, if it is, remove that node from its original position and move to the tail (right before the tail node). if it doesn’t exists, return -1.

2. When set(key, value), it first call get function, to see if it exists, them update the value, otherwise, check if the queue is full, then remove the first element (the one right after head node) and add the new node to the tail.

Set(), Get() O(1) Time.

public class Solution {
    public class Node {
        int key;
        int value;
        Node prev;
        Node next;
        public Node(int key, int value) {
            this.key = key;
            this.value = value;
            this.prev = null;
            this.next = null;
        }
    }

    Map<Integer, Node> cache;
    int capacity;
    Node head;
    Node tail;

    public Solution(int capacity) {
        cache = new HashMap<>();
        this.capacity = capacity;
        head = new Node(0, 0);
        tail = new Node(0, 0);
        head.next = tail;
        tail.prev = head;
    }

    public int get(int key) {
        if (cache.containsKey(key)) {
            //remove it from its original place
            //put to the tail the queue
            Node node = cache.get(key);
            removeNode(node);
            addToTail(node);
            return node.value;
        }
        return -1;
    }

    public void set(int key, int value) {
        if (get(key) != -1) {
            cache.get(key).value = value;
            return;
        }
        Node newNode = new Node(key, value);
        if (cache.size() < capacity) {
            addToTail(newNode);
        } else {
            cache.remove(head.next.key);
            removeNode(head.next);
            addToTail(newNode);
        }
        cache.put(newNode.key, newNode);
    }

    public void addToTail(Node node) {
        node.prev = tail.prev;
        node.prev.next = node;
        node.next = tail;
        tail.prev = node;
    }

    public void removeNode(Node node) {
        if (node.prev != null) {
            node.prev.next = node.next;
        }
        if (node.next != null) {
            node.next.prev = node.prev;
        }
        node.next = null;
        node.prev = null;
    }
}

 

Rehashing

The size of the hash table is not determinate at the very beginning. If the total size of keys is too large (e.g. size >= capacity / 10), we should double the size of the hash table and rehash every keys. Say you have a hash table looks like below:

size=3, capacity=4

<code>[null, 21, 14, null]
       ↓    ↓
       9   null
       ↓
      null
</code>

The hash function is:

<code>int hashcode(int key, int capacity) {
    return key % capacity;
}
</code>

here we have three numbers, 9, 14 and 21, where 21 and 9 share the same position as they all have the same hashcode 1 (21 % 4 = 9 % 4 = 1). We store them in the hash table by linked list.

rehashing this hash table, double the capacity, you will get:

size=3, capacity=8

<code>index:   0    1    2    3     4    5    6   7
hash : [null, 9, null, null, null, 21, 14, null]
</code>

Given the original hash table, return the new hash table after rehashing .

Example

Given [null, 21->9->null, 14->null, null],

return [null, 9->null, null, null, null, 21->null, 14->null, null]

Note

For negative integer in hash table, the position can be calculated as follow:

  • C++/Java: if you directly calculate -4 % 3 you will get -1. You can use function: a % b = (a % b + b) % b to make it is a non negative integer.
  • Python: you can directly use -1 % 3, you will get 2 automatically.

Solution:

Note: For negative integer in hash table, the position can be calculated as follow:
if you directly calculate -4 % 3 you will get -1.
You can use function: a % b = (a % b + b) % b to make it is a non negative integer.

public ListNode[] rehashing(ListNode[] hashTable) {
    if (hashTable == null) {
        return null;
    }
    ListNode[] newHash = new ListNode[hashTable.length * 2];
    int capacity = newHash.length;
    for (int i = 0; i < hashTable.length; i++) {
        ListNode node = hashTable[i];
        while (node != null) {
            int index = mod(node.val, capacity);
            ListNode next = node.next; //need to remove the next pointer
            node.next = null;
            //if it is the first one
            if (newHash[index] == null) {
                newHash[index] = node;
            } else {
                ListNode runner = newHash[index];
                while (runner.next != null) {
                    runner = runner.next;
                }
                runner.next = node;
            }
            hashTable[i] = next; //set to its next node
            node = next;
        }
    }
    return newHash;
}

//For negative integer in hash table, the position can be calculated as follow:
//if you directly calculate -4 % 3 you will get -1.
//You can use function: a % b = (a % b + b) % b to make it is a non negative integer.
public int mod(int A, int module) {
    return (A % module + module) % module;
}

Heapify

Heapify

Given an integer array, heapify it into a min-heap array.

For a heap array A, A[0] is the root of heap, and for each A[i], A[i * 2 + 1] is the left child of A[i] and A[i * 2 + 2] is the right child of A[i].

Example

Given [3,2,1,4,5], return [1,2,3,4,5] or any legal heap array.

Challenge

O(n) time complexity

Clarification

What is heap?

  • Heap is a data structure, which usually have three methods: push, pop and top. where “push” add a new element the heap, “pop” delete the minimum/maximum element in the heap, “top” return the minimum/maximum element.
What is heapify?
  • Convert an unordered integer array into a heap array. If it is min-heap, for each element A[i], we will get A[i * 2 + 1] >= A[i] and A[i * 2 + 2] >= A[i].
What if there is a lot of solutions?
  • Return any of them.

Solution 1: For each of the node in the heap array, use siftup method once.

public void heapify(int[] A) {
    if (A == null || A.length <= 1) {
        return;
    }
    for (int i = 0; i < A.length; i++) {
        siftUp(A, );
    }
}

public void siftUp(int[] A, int index) {
    int parentIndex = (index - 1) / 2;
    while (parentIndex >= 0 && A[index] < A[parentIndex]) {
        swap(A, index, parentIndex);
        index = parentIndex;
        parentIndex = (index - 1) / 2;
    }
}

public void swap(int[] A, int a, int b) {
    int tmp = A[a];
    A[a] = A[b];
    A[b] = tmp;
}

Solution 2. for A[0, …, n/2-1] non leaf nodes, call siftDown method, O(n) time complexity.

比solution1时间上更优因为可以节省最下行叶子节点的时间, 叶子节点不需要siftdown.

public void heapify(int[] A) {
    if (A == null || A.length <= 1) {
        return;
    }
    for (int i = A.length / 2 - 1; i >= 0; i--) {
        siftDown(A, i);
    }
}

public void siftDown(int[] A, int index) {
    while (index < A.length) {
        int smallest = index;
        if (index * 2 + 1 < A.length && A[index * 2 + 1] < A[smallest]) {
            smallest = index * 2 + 1;
        }
        if (index * 2 + 2 < A.length && A[index * 2 + 2] < A[smallest]) {
            smallest = index * 2 + 2;
        }
        if (smallest == index) {
            break;
        }
        swap(A, smallest, index);
        index = smallest;
    }
}

public void swap(int[] A, int a, int b) {
    int tmp = A[a];
    A[a] = A[b];
    A[b] = tmp;
}

Hash Function

Hash Function

In data structure Hash, hash function is used to convert a string(or any other type) into an integer smaller than hash size and bigger or equal to zero. The objective of designing a hash function is to “hash” the key as unreasonable as possible. A good hash function can avoid collision as less as possible. A widely used hash function algorithm is using a magic number 33, consider any string as a 33 based big integer like follow:

hashcode(“abcd”) = (ascii(a) * 333 + ascii(b) * 332 + ascii(c) *33 + ascii(d)) % HASH_SIZE

= (97* 333 + 98 * 332 + 99 * 33 +100) % HASH_SIZE

= 3595978 % HASH_SIZE

here HASH_SIZE is the capacity of the hash table (you can assume a hash table is like an array with index 0 ~ HASH_SIZE-1).

Given a string as a key and the size of hash table, return the hash value of this key.f

Example

For key=”abcd” and size=100, return 78

Clarification

For this problem, you are not necessary to design your own hash algorithm or consider any collision issue, you just need to implement the algorithm as described.

Solution: Use a helper to avoid overflow.  To calculate a*33%HASH_SIZE, instead of multiply by 33, we add a to itself 33 times. if(result+num>mod) we only add num-mod it to the result, otherwise, just need to add num to result. In this case, we are either adding or removing HASH_SIZE from the final result so it won’t overflow.

public int hashCode(char[] key, int HASH_SIZE) {
    int result = 0;
    for (int i = 0; i < key.length; i++) {
        result = helper(result, 33, HASH_SIZE);
        result += key[i];
        result %= HASH_SIZE;
    }
    return result;
}

int helper(int num, int base, int mod) {
    int result = 0;
    for (int i = 0; i < base; i++) {
        if (result + num > mod) {
            result += num - mod;
        } else {
            result += num;
        }
    }
    return result;
}

Topological Sorting

Topological Sorting

Given an directed graph, a topological order of the graph nodes is defined as follow:

  • For each directed edge A -> B in graph, A must before B in the order list.
  • The first node in the order can be any node in the graph with no nodes direct to it.

Find any topological order for the given graph.

Example

For graph as follow:

picture

The topological order can be:

<code>[0, 1, 2, 3, 4, 5]
[0, 2, 3, 1, 5, 4]
...
</code>
Note

You can assume that there is at least one topological order in the graph.

Challenge

Can you do it in both BFS and DFS?

Solution 1. BFS

1. first create a map which contains all the nodes and its indegrees

2. only add node with 0 indegree to the list and once the node is select, remove 1 indegree from all its neighbors

public ArrayList<DirectedGraphNode> topSort(ArrayList<DirectedGraphNode> graph) {
    //BFS
    ArrayList<DirectedGraphNode> result = new ArrayList<>();
    if (graph == null || graph.size() <= 1) {
        return graph;
    }
    HashMap<DirectedGraphNode, Integer> inDegreeMap = new HashMap<>();
    for (DirectedGraphNode node : graph) {
        if (!inDegreeMap.containsKey(node)) {
            inDegreeMap.put(node, 0);
        }
        for (DirectedGraphNode neighbor : node.neighbors) {
            if (inDegreeMap.containsKey(neighbor)) {
                inDegreeMap.put(neighbor, inDegreeMap.get(neighbor) + 1);
            } else {
                inDegreeMap.put(neighbor, 1);
            }
        }
    }
    while (!inDegreeMap.isEmpty()) {
        for (DirectedGraphNode node : inDegreeMap.keySet()) {
            if (inDegreeMap.get(node) == 0) {
                result.add(node);
                inDegreeMap.remove(node);
                for (DirectedGraphNode neighbor : node.neighbors) {
                    inDegreeMap.put(neighbor, inDegreeMap.get(neighbor) - 1);
                }
                break;
            }
        }
    }
    return result;
}

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
         / \
         \_/

Solution: BFS遍历图 用Hash表存储Original Node-》 Copy Node 映射
O(n) time complexity, O(n) space

public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
    if (node == null) {
        return null;
    }
    Queue<UndirectedGraphNode> queue = new LinkedList<>();
    Map<UndirectedGraphNode, UndirectedGraphNode> map = new HashMap<>();
    queue.offer(node);
    UndirectedGraphNode copyRoot = new UndirectedGraphNode(node.label);
    map.put(node, copyRoot);
    while (!queue.isEmpty()) {
        int count = queue.size();
        for (int i = 0; i < count; i++) {
            UndirectedGraphNode curr = queue.poll();
            for (UndirectedGraphNode neighbor : curr.neighbors) {
                if (!map.containsKey(neighbor)) {
                    queue.offer(neighbor);
                    UndirectedGraphNode currCopy = new UndirectedGraphNode(neighbor.label);
                    map.put(neighbor, currCopy);
                }
            }
        }
    }
    for (UndirectedGraphNode originalNode : map.keySet()) {
        for (UndirectedGraphNode neighbor : originalNode.neighbors) {
            map.get(originalNode).neighbors.add(map.get(neighbor));
        }
    }
    return map.get(node);
}