Fork me on GitHub

Posted on

Description

https://leetcode.com/problems/clone-graph/description/

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
 * Definition for undirected graph.
 * struct UndirectedGraphNode {
 *     int label;
 *     vector<UndirectedGraphNode *> neighbors;
 *     UndirectedGraphNode(int x) : label(x) {};
 * };
 */
class Solution {
private:
    unordered_map<UndirectedGraphNode*, UndirectedGraphNode*> oldToNew;
public:
    UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) {
        if (!node) return NULL;
        if (oldToNew.find(node) == oldToNew.end()) {
            UndirectedGraphNode *newNode = new UndirectedGraphNode(node->label);
            oldToNew[node] = newNode;
            for (auto neighbor: node->neighbors)
                newNode->neighbors.push_back(cloneGraph(neighbor));
            
        }
        return oldToNew[node];
    }
};

Posted on

Description

https://leetcode.com/problems/copy-list-with-random-pointer/description/

Solution

The key point is to mantain a mapping from old node to copied node,

Step1: traverse the list to form the linked list

Step2: traverse the list to complete the random point relationship(using map)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
/**
 * Definition for singly-linked list with a random pointer.
 * class RandomListNode {
 *     int label;
 *     RandomListNode next, random;
 *     RandomListNode(int x) { this.label = x; }
 * };
 */
public class Solution {
    public RandomListNode copyRandomList(RandomListNode head) {
        if (head == null) return null;
        HashMap<RandomListNode, RandomListNode> oldToNew = new HashMap<>();
        RandomListNode ret = new RandomListNode(head.label);
        //traverse the list
        RandomListNode traverseOld = head, traverseNew = ret;
        while(traverseOld != null) {
            oldToNew.put(traverseOld, traverseNew);
            if(traverseOld.next != null) {
                traverseNew.next = new RandomListNode(traverseOld.next.label);
            }else {
                traverseNew.next = null;
            }
            traverseOld = traverseOld.next;
            traverseNew = traverseNew.next;
        }
        
        //Handle the random point
        traverseNew = ret;
        traverseOld = head;
        while(traverseNew != null) {
            traverseNew.random = oldToNew.get(traverseOld.random);
            traverseNew = traverseNew.next;
            traverseOld = traverseOld.next;
        }
        
        return ret;
    }
}

Posted on

Description

https://leetcode.com/problems/jump-game-ii/description/

Naive Solution(TLE)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int jump(int[] nums) {
        int size = nums.length;
        if (size == 1) return 0;
        LinkedList<Integer> queue = new LinkedList<Integer>();
        queue.add(0);
        int steps = 1;
        while (queue.isEmpty() == false) {
            LinkedList<Integer> tempQueue = new LinkedList<>(queue);
            queue = new LinkedList<Integer>();
            while(tempQueue.isEmpty() == false) {
                int pos = tempQueue.pop();
                int range = nums[pos];
                if (pos + range >= size - 1) return steps;
                for(int i = 1; i <= range; i++) queue.add(pos + i);
            }
            steps += 1;
        }
        return -1;
    }
}

Button Up

We maintain the range of each depth, using leftBound and rightBound.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public int jump(int[] nums) {
        if (nums == null) return 0;
        int size = nums.length;
        if (size == 0 || size == 1) return 0;

        int leftBound = 0, rightBound = 0;
        int currentStep = 0;
        int currentIndex = 0;
        while(rightBound < size - 1) {
            int oldRightBound = rightBound;
            currentIndex = leftBound;
            do {
                int range = nums[currentIndex];
                rightBound = Math.max(rightBound, currentIndex + range);
                currentIndex += 1;
            }while(currentIndex <= oldRightBound);
            if (rightBound <= oldRightBound) return -1; //Wrong answer
            leftBound = oldRightBound + 1;
            currentStep += 1;
        }
        return currentStep;
    }
}

Posted on

Description

https://leetcode.com/problems/jump-game/description/

Brutal Solution

Traverse from the start node, mark its range as true, then we can check the end of the list when traversion finished.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public boolean canJump(int[] nums) {
        int size = nums.length;
        boolean[] mark = new boolean[size];
        for(int index = 0; index < size; index++) mark[index] = false;
        mark[0] = true;
        for(int index = 0; index < size; index++) {
            if(mark[index] == true) {
                int range = nums[index];
                if (range > 0) {
                    for (int i = 1; i <= range && i + index < size; i++) 
                        mark[index + i] = true;
                }
            } 
        }
        return mark[size - 1];
    }
}

Mark-Free Solution

In the solution above, we found some redundant traversion in the nested loop, to improve it, we should skip the meaningless procedure. To clarify how it works, we should introduce a pre-rule discovered by the fact:

If the item A is reachable, then the item before A must be reachable.

Then we use a varialbe rightIndex to record the reachable boundary in the right. 

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public boolean canJump(int[] nums) {
        int size = nums.length;
        int rightIndex = 0;
        for(int index = 0; index < size; index++) {
            if(index <= rightIndex) {
                rightIndex = Math.max(rightIndex, nums[index] + index);
            } 
        }
        return rightIndex >= size - 1;
    }
}

Trimmed Solution

In the solution above, the procedure need to traverse all node regardless of the dataset. In fact we can terminate the result once we reached the end item of liste(success), or the current index is bigger than the rightIndex (fail)

1
2
3
4
5
6
7
8
9
10
11
class Solution {
    public boolean canJump(int[] nums) {
        int size = nums.length;
        int rightIndex = 0;
        for(int index = 0; index < size; index++) {
            if(index > rightIndex || rightIndex >= size - 1) break;
            rightIndex = Math.max(rightIndex, nums[index] + index); 
        }
        return rightIndex >= size - 1;
    }
}

Posted on

Description

https://leetcode.com/problems/task-scheduler/description/

Idea

The key of this problem is how to manipulate the order. First we should collect the count of each character.

Then we can image the box of n + 1 empty position which need to be filled by the given character. The solution chain should be contained of several box linked together(except for the last box).Each time when we are filling one box. We will fetch the character based on the count of the character in the priority queue.

In last iteration, there is no need to fill the n + 1 slots.

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
import java.util.PriorityQueue;
class Solution {
    
    public int leastInterval(char[] tasks, int n) {
        
        HashMap<Character, Integer> counter = new HashMap<>();
        for (char task : tasks) {
            Integer count = counter.get(task);
            if (count == null)
                counter.put(task, 1);
            else
                counter.put(task, count + 1);   
        }
        Queue<Integer> queue = new PriorityQueue<Integer>(
            new Comparator<Integer>() {
                public int compare(Integer a, Integer b) {
                    return b - a;
                }
            }
        );
        for ( Integer item : counter.values() ) {
            queue.add(item);
        }
        //Simulate the scenorio
        int length = 0;
        while( queue.isEmpty() == false) {
            int round = 0;
            LinkedList<Integer> remains = new LinkedList<>();
            for(int i = 0; !queue.isEmpty() && i < n + 1; i++){
                Integer remain = queue.remove();
                if(remain > 1) remains.add(remain-1);
                round += 1;
            }
            for (Integer remain : remains) {
                queue.add(remain);
            }
            length += queue.isEmpty() ? round : n + 1;
        }
        return length;
    }
    
}

Posted on

Description

https://leetcode.com/problems/gas-station/description/

Naive Solution — Traverse

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int length = gas.length;
        //traverse all the node on the circle.
        int start = 0;
        while(start < length) {
            if (validate(start, gas, cost) == true) return start;
            start += 1;
        }
        return -1;
    }
    
    public boolean validate(int start, int[] gas, int[] cost) {
        int length = gas.length;
        int remain = 0;
        int count = 0; 
        while(count <= length) {
            remain += gas[start];
            if (remain < cost[start]) return false; // Invalid position
            remain -= cost[start];
            start = (start + 1) % length;
            count += 1;
        }
        return true;  //The starter found;
        
    }
}

Faster Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int length = gas.length;
        //traverse all the node on the circle.
        int start = 0;
        while(start < length) {
            int pos = validate(start, gas, cost);
            if (pos == -1) return start;
            if (pos > start) 
                start = pos;
            else
                //The inteval between start to end has no feasible position
                return -1;
        }
        return -1;
    }
    
    public int validate(int start, int[] gas, int[] cost) {
        int length = gas.length;
        int remain = 0;
        int count = 0; 
        while(count <= length) {
            remain += gas[start];
            if (remain < cost[start]) return (start + 1) % length; // Invalid position
            remain -= cost[start];
            start = (start + 1) % length;
            count += 1;
        }
        return -1;  //The starter found;
        
    }
}

Posted on

Description

https://leetcode.com/problems/odd-even-linked-list/description/

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode oddEvenList(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode odd = head;
        ListNode even = head.next;
        ListNode traverseOdd = odd;
        ListNode endTraverseOdd = null;
        ListNode traverseEven = even;
        
        while(traverseOdd != null && traverseEven != null) {
            traverseOdd.next = traverseEven.next;
            if(traverseOdd.next == null) break; //break at the end of odd node
            traverseOdd = traverseOdd.next;
            traverseEven.next = traverseOdd.next;
            traverseEven = traverseEven.next;
        }
        
        traverseOdd.next = even;
        
        return odd;
    }
}

Posted on

Description

https://leetcode.com/problems/longest-increasing-path-in-a-matrix/description/

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
class Solution {
    public int height;
    public int width;
    public int longestIncreasingPath(int[][] matrix) {
        height = matrix.length;
        if (height == 0) return 0;
        width = matrix[0].length;
        
        
        //Using restore[i][j], means the length of increasing count of coordinate (i, j)
        int[][] restore = new int[height][width];
        
        //Mark each item as clean(-1)
        for(int i = 0; i < height; i++)
            for(int j = 0; j < width; j++)
                restore[i][j] = -1;
        
        int retLength = -1;
        
        for (int i = 0; i < height; i++)
            for(int j = 0; j < width; j++)
                retLength = Math.max(retLength, startFromIJ(matrix, i, j, restore));  
        
        return retLength;
    }
    
    public int startFromIJ(int[][] matrix, int i, int j, int[][] restore) {
        if (restore[i][j] != -1) return restore[i][j];
        // if (i < 0 || i >= height || j < 0 || j >= width) return 0;
        int[][] directions = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}};
        int ret = 1;
        for (int index = 0; index <= 3; index += 1) {
            int newRow = i + directions[index][0];
            int newCol = j + directions[index][1];
            if (newRow >= 0 && newRow < height && newCol >= 0 && newCol < width && matrix[newRow][newCol] > matrix[i][j]){
                ret = Math.max(ret, startFromIJ(matrix, newRow, newCol, restore) + 1);
            }
        }
        restore[i][j] = ret;
        return ret;
    }
}

Posted on

Linkage

https://leetcode.com/problems/find-peak-element/description/

Naive Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public int findPeakElement(int[] nums) {
        int length = nums.length;
        if (length == 0) return -1;
        if (length == 1) return 0;
        
        int left = 0, right = length-1;
        int middle = (left + right) / 2;
        long leftItem, rightItem, currentItem;
        while (left <= right) {
            currentItem = nums[middle];
            leftItem = middle - 1 < 0 ? (long) Double.NEGATIVE_INFINITY : nums[middle - 1];
            rightItem = middle + 1 > length-1 ? (long) Double.NEGATIVE_INFINITY : nums[middle + 1];
            if (currentItem > leftItem && currentItem > rightItem) return middle;
            if (currentItem <= leftItem) 
                right = middle - 1;
            else
                left = middle + 1;
            middle = (left + right) / 2;
        }
        return -1;
    }
}

Log N Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public int findPeakElement(int[] nums) {
        int length = nums.length;
        if (length == 0) return -1;
        if (length == 1) return 0;
        
        int left = 0, right = length-1;
        int middle = (left + right) / 2;
        long leftItem, rightItem, currentItem;
        while (left <= right) {
            currentItem = nums[middle];
            leftItem = middle - 1 < 0 ? (long) Double.NEGATIVE_INFINITY : nums[middle - 1];
            rightItem = middle + 1 > length-1 ? (long) Double.NEGATIVE_INFINITY : nums[middle + 1];
            if (currentItem > leftItem && currentItem > rightItem) return middle;
            if (currentItem <= leftItem) 
                right = middle - 1;
            else
                left = middle + 1;
            middle = (left + right) / 2;
        }
        return -1;
    }
}

Posted on

Description

https://leetcode.com/problems/fraction-to-recurring-decimal/description/

Solution

Pay attention to the fact that the pair of quote plus redundant in each divide iteration is the feature to judge whether the loop happened. Based on which, We ssing a list to record the order of the pair list, and maintain a set to judge whether the pair is occupied in each iteration. Once it was in the set, we stop it. Then we traverse the pair list to find the loop part and the unloop part.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
class Pair {
    private long quote;
    private long remain;
    public Pair(long quote, long remain) {
        this.quote = quote;
        this.remain = remain;
    }
    
    public long getQuote() {
        return this.quote;
    }
    
    public long getRemain() {
        return this.remain;
    }
    @Override
    public int hashCode(){
        return (int) (this.quote * this.remain);
    }
    
    @Override
    public boolean equals(Object obj) {
        if (this == obj) {
            return true;
        }
        if(obj instanceof Pair) {
            return ( (Pair)obj ).remain == this.remain && (( (Pair)obj ).getQuote() == this.quote);
        }
        return false;
    }
}


public class Solution {
    public String fractionToDecimal(int numerator, int denominator) {
        StringBuilder ret = new StringBuilder();
        ArrayList<Character> integerList = new ArrayList();
        HashSet<Pair> remainQuoteSet = new HashSet<>();
        ArrayList<Pair> remainQuoteList = new ArrayList<>();
        
        long longNumerator = (long) numerator;
        long longDenominator = (long) denominator;
        if (longNumerator*longDenominator < 0) ret.append('-');
        longNumerator = Math.abs(longNumerator);
        longDenominator = Math.abs(longDenominator);
        long quote = longNumerator / longDenominator;
        long remain = longNumerator % longDenominator;

        //Process Integer
        do{
            integerList.add( (char) (quote % 10 + '0') );
            quote /= 10;
        }while(quote > 0);
        for (int index = integerList.size()-1; index >= 0; index -= 1){
            ret.append(integerList.get(index));
        }
        
        if (remain == 0) {
            return ret.toString();
        }
        
        ret.append(".");
        
        //Process Decimal
        quote = remain * 10 / longDenominator;
        remain = remain * 10 % longDenominator;
        Pair pair = new Pair(quote, remain);
        while(remainQuoteSet.contains(pair) == false) {
            remainQuoteSet.add(pair);
            remainQuoteList.add(pair);
            quote = remain * 10 / longDenominator;
            remain = remain * 10 % longDenominator;
            pair = new Pair(quote, remain);
        }
        
        int beginIndexOfLoop = remainQuoteList.indexOf(pair);
        //Find the unloop section
        for (int index = 0; index < beginIndexOfLoop; index += 1) {
            ret.append( (char) (remainQuoteList.get(index).getQuote() + '0') );
        }
        
        //Find the loop section
        if (remain != 0) {
            ret.append('(');
            for (int index = beginIndexOfLoop; index < remainQuoteList.size(); index += 1) {
                ret.append( (char) (remainQuoteList.get(index).getQuote() + '0') );
            }
            ret.append(')');
        } 
        
        System.out.println(remainQuoteList);
        return ret.toString();
    }
}

Attention

  1. In java, you can use the class as the key word in the map(set), but to make them work functionally, you need some extra effort——override the hashCode and equals methods in the class.
  2. The corner case of big int can reduce to some awkward situation, so my suggestion is convert the parmeter to long type.