Fork me on GitHub

Posted on

Linkage

https://leetcode.com/problems/longest-consecutive-sequence/description/

Code

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 longestConsecutive(int[] nums) {
        int lens = nums.length;
        if (lens == 0 || lens == 1) return lens;
        
        Set<Integer> number_set = new HashSet<Integer>();
        for (int item : nums) {
            number_set.add(item);
        }
        int index = 0;
        int max_lens = 0;
        while (!number_set.isEmpty() && index < lens) {
            int item = nums[index];
            index += 1;
            if (!number_set.contains(item)) continue;
            
            int smaller = item - 1, larger = item + 1;
            int current_lens = 1;
            number_set.remove(item);
            while(number_set.contains(smaller)) { number_set.remove(smaller); smaller -= 1; current_lens += 1; }
            while(number_set.contains(larger)) { number_set.remove(larger); larger += 1; current_lens += 1;}
            max_lens = Math.max(max_lens, current_lens);
        }
        return max_lens;
    }
    
}

Posted on

Description

https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree/description/

Code

This is a cliche question, we can use recursion to solve it, each time we will check the left child and right child, if each ancestor is not null, the current node must be the LCA, else return the non-null node.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) return null;
        if (root == p || root == q) return root;
        
        TreeNode left_ancestor = lowestCommonAncestor(root.left, p, q);
        TreeNode right_ancestor = lowestCommonAncestor(root.right, p, q);
        if (right_ancestor != null && left_ancestor != null) return root;
        
        return left_ancestor != null ? left_ancestor:right_ancestor;
    }
}

Posted on

Linkage

https://leetcode.com/problems/spiral-matrix/description/

Easy to implement the alogithm, but pay attention to the bounds.

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
class Solution {
    public enum Direction {  
        LEFT, RIGHT, UP, DOWN 
    }
    public List<Integer> spiralOrder(int[][] matrix) {
        int row_length = matrix.length;
        List<Integer> ret = new LinkedList<Integer>();
        if (row_length == 0)
            return ret;
        int column_length = matrix[0].length;
        
        Direction direction = Direction.RIGHT;
        int row = 0;
        int column = 0;
        int remain = row_length * column_length;
        int left_bound = 0;
        int right_bound = column_length - 1;
        int up_bound = 0;
        int down_bound = row_length - 1;
        
        while(remain > 0){
            switch (direction){
                case RIGHT:
                    for(; column <= right_bound && remain > 0; ++column){
                        remain -= 1;
                        ret.add(matrix[row][column]);
                    }
                    column -= 1;
                    row += 1;
                    up_bound += 1;
                    
                    direction = Direction.DOWN;
                    break;
                case DOWN:
                    for(; row <= down_bound && remain > 0; ++row){
                        remain -= 1;
                        ret.add(matrix[row][column]);
                    }
                    row -= 1;
                    column -= 1;
                    right_bound -= 1;
                    direction = Direction.LEFT;
                    break;
                case LEFT:
                    for(; column >= left_bound && remain > 0; --column){
                        remain -= 1;
                        ret.add(matrix[row][column]);
                    }
                    column += 1;
                    row -= 1;
                    down_bound -= 1;
                    direction = Direction.UP;
                    break;
                case UP:
                    for(; row >= up_bound && remain > 0; --row){
                        remain -= 1;
                        ret.add(matrix[row][column]);
                    }
                    row += 1;
                    column += 1;
                    left_bound += 1;
                    direction = Direction.RIGHT;
                    break;
            }
        }
        return ret;
    }
}

Follow up

https://leetcode.com/problems/spiral-matrix-ii/description/

Code

In this problem, we found the fact that the direction change is regular, namely, it follows right, down, left, up, right, down, left, up. So we can simplify the code from switch case to simple loop.This polishment also add the speed of calculation compared to the switch way.

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
class Solution {
    public int[][] generateMatrix(int n) {
        int[][] ret = new int[n][n];
        int row = 0, col = 0;
        
        int count = 1;
        int sum = n*n;
        int left_bound = 0, right_bound = n - 1, up_bound = 0, down_bound = n - 1;
        
        while (count <= sum) {
            while(col <= right_bound && count <= sum) {
                ret[row][col] = count++;
                col += 1;
            }
            col -= 1;
            up_bound += 1;
            row += 1;
            while(row <= down_bound && count <= sum) {
                ret[row][col] = count++;
                row += 1;
            }
            row -= 1;
            right_bound -= 1;
            col -= 1;
            while(col >= left_bound && count <= sum) {
                ret[row][col] = count++;
                col -= 1;
            }
            col += 1;
            down_bound -= 1;
            row -= 1;
            while(row >= up_bound && count <= sum) {
                ret[row][col] = count++;
                row -= 1;
            }
            row += 1;
            col += 1;
            left_bound += 1;
        }
    
        return ret;
    }
}

Posted on

Linkage

https://leetcode.com/problems/set-matrix-zeroes/description/

Solution

A traverse of will help us to mark which column or row should be marked as all zero. In this implementation, we will use O(m+n) space.

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 void setZeroes(int[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;
        boolean[] row_index = new boolean[m];
        boolean[] column_index = new boolean[n];
        for (int i = 0; i < m; i++){
            for (int j = 0; j < n; j++){
                if (matrix[i][j] == 0) {
                    row_index[i] = true;
                    column_index[j] = true;
                }
            }
        }
        for (int i = 0; i < m; ++i){
            if (row_index[i] == true){
                for (int k = 0; k < n; k++){
                    matrix[i][k] = 0;
                }
            }
        }
        
        for (int j = 0; j < n; ++j) {
            if (column_index[j] == true) {
                for (int k = 0; k < m; ++k) {
                    matrix[k][j] = 0;
                }
            }
        }
        
    }
}

Posted on

Preface

Recently, I learned the shared_pointer in C++11, but things is much complicated then I expected before, in this article, I will go through the an “easy” implementation of binary seach tree, then I will throw out a new concept- weak pointer.

Example

First Case

First, let me implement a tree node using shared pointer 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>x
#include <memory>

class Node {
    int value;
public:
    std::shared_ptr<Node> left_ptr;
    std::shared_ptr<Node> right_ptr;
    Node(int val) : value(val) {
        std::cout<<"Contructor"<<std::endl;
    }
    ~Node() {
        std::cout<<"Destructor"<<std::endl;
    }
};

int main () {
    std::shared_ptr<Node> ptr = std::make_shared<Node>(4);
    ptr->left_ptr = std::make_shared<Node>(2);
    ptr->right_ptr = std::make_shared<Node>(5);
}

You can see the nodes are deleted safely.

Circle Reference Case

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
//
// Created by 佘国榛 on 2018/6/27.
//
#include <iostream>
#include <memory>

class Node {
    int value;
public:
    std::shared_ptr<Node> left_ptr;
    std::shared_ptr<Node> right_ptr;
    std::shared_ptr<Node> parent_ptr;
    Node(int val) : value(val) {
        std::cout<<"Contructor"<<std::endl;
    }
    ~Node() {
        std::cout<<"Destructor"<<std::endl;
    }
};

int main () {
    std::shared_ptr<Node> ptr = std::make_shared<Node>(4);
    ptr->left_ptr = std::make_shared<Node>(2);
    ptr->left_ptr->parent_ptr = ptr;
    ptr->right_ptr = std::make_shared<Node>(5);
    ptr->right_ptr->parent_ptr = ptr;

    std::cout<<"ptr reference count = "<<ptr.use_count()<<std::endl;
    std::cout<<"ptr->leftPtr reference count = "<<ptr->left_ptr.use_count()<<std::endl;
    std::cout<<"ptr->rightPtr reference count = "<<ptr->right_ptr.use_count()<<std::endl;
    return 0;
}

Result:

1
2
3
4
5
6
Contructor
Contructor
Contructor
ptr reference count = 3
ptr->leftPtr reference count = 1
ptr->rightPtr reference count = 1

You can see through output that the three node is not properly deallocated;

Why?????

Let me take a look at what happens during the process. When we reach the end of main function, we will delete the local variable, namely, ptr, but when we check the reference count of the ptr, it is 2,(The reason is that the current ptr is being pointed by the Node(2) and Node(5), so the deconstructor of the Node will not be implemented. This is how things work.

How to tackle it ——>weak_pointer

All we need to do is to hand set the type pf parent_ptr as weak_ptr

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
#include <iostream>
#include <memory>

class Node {
    int value;
public:
    std::shared_ptr<Node> left_ptr;
    std::shared_ptr<Node> right_ptr;
    std::weak_ptr<Node> parent_ptr;
    Node(int val) : value(val) {
        std::cout<<"Contructor"<<std::endl;
    }
    ~Node() {
        std::cout<<"Destructor"<<std::endl;
    }
};

int main () {
    std::shared_ptr<Node> ptr = std::make_shared<Node>(4);
    ptr->left_ptr = std::make_shared<Node>(2);
    ptr->left_ptr->parent_ptr = ptr;
    ptr->right_ptr = std::make_shared<Node>(5);
    ptr->right_ptr->parent_ptr = ptr;

    std::cout<<"ptr reference count = "<<ptr.use_count()<<std::endl;
    std::cout<<"ptr->leftPtr reference count = "<<ptr->left_ptr.use_count()<<std::endl;
    std::cout<<"ptr->rightPtr reference count = "<<ptr->right_ptr.use_count()<<std::endl;
    std::cout<<"ptr->rightPtr->parentPtr reference count = "<<ptr->right_ptr->parent_ptr.lock().use_count()<<std::endl;
    std::cout<<"ptr->leftPtr->parentPtr reference count = "<<ptr->left_ptr->parent_ptr.lock().use_count()<<std::endl;
    return 0;
}

Posted on

Linkage

https://leetcode.com/problems/word-ladder-ii/description/

Idea

The idea of this problem is to combine the BFS(forward) and the DFS(backward) to traverse the visited node. To be more specific, when we are searching the endWord, we should use BFS, which can trim a lot of branch compared to DFS.For reforming the ladder in backward from endWord, we need to maintain a reverse adjacent table, which will record the parent nodes of a child nodes in the BFS process.

TLE Code in Java

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
public class Solution {
    public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
        Queue<String> queue = new LinkedList();
        HashMap<String, Integer> dic = new HashMap();
        HashMap<String, Set<String>> pre = new HashMap();
        List<List<String>> ret = new LinkedList();
        int min_depth = -1;
        for (String word : wordList) {
            dic.put(word, 0);
        }
        dic.put(beginWord, 1);
        
        queue.offer(beginWord);
        
        while(queue.isEmpty() == false) {
            String currentWord = queue.poll();
            
            Integer currentDepth = dic.get(currentWord);
            if (currentDepth == null) currentDepth = 0;
            if (min_depth >= 0 && currentDepth > min_depth) {
                break;   
            }
            for(int position = 0; position < currentWord.length(); position += 1) {
                for (int index = 0; index < 26; index++){
                    char replace = (char) ('a' + index);
                    String newWord = currentWord.substring(0, position) + replace + currentWord.substring(position+1, beginWord.length());
                    if ( newWord.equals(currentWord) ) continue;
                    Integer wordDepth = dic.get(newWord);
        
                    if (wordDepth != null && ( wordDepth == 0 || ( currentDepth < wordDepth ) ) ) {
                        dic.put(newWord,  currentDepth + 1);
                        Set<String> set = pre.get(newWord);
                        if (set == null) {
                            set = new HashSet();
                        }
                        set.add(currentWord);
                        pre.put(newWord, set);
                        
                        if ( newWord.equals(endWord) ) {
                            min_depth = currentDepth;
                        }else {
                            queue.offer(newWord);
                        }
                    }
                }
            }
        }
        
        if(min_depth > 0) {
            List<String> arrayList = new LinkedList<String>();
            arrayList.add(endWord);
            gatherResult(ret, beginWord, endWord, dic, pre, arrayList);
            for (List<String> ret_item : ret) {
                Collections.reverse(ret_item);
            }
        }
        
        return ret;
    }
    
    public void gatherResult(List<List<String>> ret, String startWord, String endWord, HashMap<String, Integer> dic, HashMap<String, Set<String>> pre, List<String> ret_item){
        if (endWord.equals(startWord)) {
            ret.add(ret_item);
            return;
        }
        Set<String> nextWordList = pre.get(endWord);
        for (String word : nextWordList) {
            List<String> new_item = new LinkedList(ret_item);
            new_item.add(word);
            gatherResult( ret, startWord, word, dic, pre, new_item);
        }
    }
}

Accept Code In C++

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
class Solution {
public:
    vector<vector<string> > findLadders(string beginWord, string endWord, vector<string> &wordList) {
        vector<std::vector<string> > ret;
        queue<string> node_queue;
        unordered_map<string, int> word_dic;
        unordered_map<string, unordered_set<string> > reverse_adjacent_table;
        int min_depth = -1;


        for (vector<string>::iterator iter = wordList.begin(); iter != wordList.end(); iter++) {
            word_dic[*iter] = 0;
        }
        word_dic[beginWord] = 1;

        node_queue.push(beginWord);

        while (node_queue.empty() == false) {
            string currentWord = node_queue.front();
            node_queue.pop();
            int currentDepth = word_dic.find(currentWord)->second;
            if (min_depth >= 0 && currentDepth > min_depth) break;

            for (int position = 0; position < currentWord.size(); position++) {

                string newWord = currentWord;
                for (char ch = 'a'; ch <= 'z'; ch++) {
                    newWord[position] = ch;
                    if (newWord == currentWord) continue;
                    auto iter = word_dic.find(newWord);
                    if (iter == word_dic.end()) continue;
                    int wordDepth = iter->second;
                    if (wordDepth == 0 || currentDepth < wordDepth) {
                        word_dic[newWord] = currentDepth + 1;
                        auto iter = reverse_adjacent_table.find(newWord);
                        unordered_set<string> *set;
                        if (iter == reverse_adjacent_table.end()) {
                            set = new unordered_set<string>();
                        } else {
                            set = &iter->second;
                        }
                        set->insert(currentWord);
                        pair<string, unordered_set<string> > string2set(newWord, *set);
                        reverse_adjacent_table[newWord] = *set;

                        if (newWord == endWord) {
                            min_depth = currentDepth;
                        } else {
                            node_queue.push(newWord);
                        }
                    }
                }
            }
        }

        vector<string> ret_item;
        if (min_depth > 0) {
            ret_item.push_back(endWord);
            this->gatherResult(beginWord, endWord, ret, ret_item, reverse_adjacent_table);
        }

        for(auto iter = ret.begin(); iter != ret.end(); iter++) {
            reverse(iter->begin(), iter->end());
        }

        return ret;
    }

    void gatherResult(const string &startWord, const string &endWord, vector<std::vector<string> >& ret, vector<string>& ret_item, unordered_map<string, unordered_set<string> >& reverse_adjacent_table) {
        if (endWord == startWord) {
            ret.push_back(ret_item);
            return;
        }

        unordered_set<string> nextWordList = reverse_adjacent_table[endWord];

        for (unordered_set<string>::iterator iter = nextWordList.begin(); iter != nextWordList.end(); iter++) {
            vector<string> *new_item = new vector<string>(ret_item);
            new_item->push_back(*iter);
            gatherResult(startWord, *iter, ret, *new_item, reverse_adjacent_table);
        }
    }

};

Posted on

The example is showing below.

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
#include <iostream>
#include <memory>
#include <vector>

template <class T>
class TrackingAllocator{
    public:
        using value_type = T;
    
        using pointer = T *;
        using const_pointer = const T *;

        using void_pointer = void *;
        using const_void_pointer = const void*;

        using size_type = size_t;

        using difference_type = std::ptrdiff_t;

        TrackingAllocator() = default;
        ~TrackingAllocator() = default;

        size_type get_allocations() {
            return mAllocations;
        }

        pointer allocate(size_type num_objects) {
            return static_cast<pointer>(operator new(sizeof(value_type)*num_objects));
        }

        void deallocate(pointer p, size_type num_objects) {
            operator delete(p);
        }

        size_type max_size() const{
            return std::numeric_limits<size_type>::max();
        }
private:
    static size_type mAllocations;
};

template <class T>
typename TrackingAllocator<T>::size_type TrackingAllocator<T>::mAllocations = 0;

int main () {
    std::vector<int, TrackingAllocator<int> > v(5);
    return 0;
}

Posted on

Linkage

https://leetcode.com/problems/word-ladder/description/

Naive Code

In the naive implementation, we will consider all words as the node in graph, then using BFS to record the shortest depth. Once we visit endWord, then we return the current depth.

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
import java.util.Queue;

class Solution {
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        
        Queue<String> queue = new LinkedList<String>();
        int[] depth_array = new int[ wordList.size() ]; //The last in depth_array is beginWord
        for (int i = 0; i < wordList.size(); i++) {
            depth_array[i] = 0;
        }
        List<String> targetWordList = findNext(beginWord, wordList, depth_array, 0);
        for (String nextWord : targetWordList) {
            if ( nextWord.equals(endWord) ) {
                return 2;
            }else {
                queue.offer(nextWord);
            }
        }
        
        while(queue.isEmpty() == false) {
            String currentWord = queue.poll();
            int currentDepth = depth_array[ wordList.indexOf(currentWord) ];
            System.out.println(currentDepth);
            targetWordList = findNext(currentWord, wordList, depth_array, currentDepth);
            for (String nextWord : targetWordList) {
                if ( nextWord.equals(endWord) ) {
                    return currentDepth + 2;
                }else {
                    queue.offer(nextWord);
                }
            }
        }
        return 0;
        
    }
    
    public boolean isNext(String beginWord, String endWord) {
        int countOfDifferentChar = 0;
        for(int i = 0; i < beginWord.length(); i++) {
            if( beginWord.charAt(i) != endWord.charAt(i) ) {
                countOfDifferentChar += 1;
            }
        }
        return countOfDifferentChar == 1 ? true : false;
    }
    
    public List<String> findNext(String beginWord, List<String> wordList, int [] depth_array, int depth) {
        List<String> retWordList = new ArrayList<String>();
        for (int i = 0; i < wordList.size(); i++){
            if ( depth_array[i] == 0 && isNext(beginWord, wordList.get(i) ) == true ) {
                retWordList.add( wordList.get(i) );
                depth_array[i] = depth + 1;
            }
        }
        return retWordList;
    }
    

}

Improve Code

In the naive implementation. each time to find the next word on the chain ,we need to traverse all the node in the all graph, which is time-consuming(The test cases improve this). The wiser way is to dectect new node by substitute each letter in the current word,(The consumed time is word_length*26)

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
import java.util.Queue;
import java.util.HashMap;
class Solution {
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        
        Queue<String> queue = new LinkedList<String>();
        HashMap<String, Integer> map = new HashMap();
        
        for (String word : wordList) {
            map.put(word, 0);
        }
        
        List<String> targetWordList = findNext(beginWord, wordList, map, 0);
        for (String nextWord : targetWordList) {
            if ( nextWord.equals(endWord) ) {
                return 2;
            }else {
                queue.offer(nextWord);
            }
        }
        
        while(queue.isEmpty() == false) {
            String currentWord = queue.poll();
            int currentDepth = map.get(currentWord);
            targetWordList = findNext(currentWord, wordList, map, currentDepth);
            for (String nextWord : targetWordList) {
                if ( nextWord.equals(endWord) ) {
                    return currentDepth + 2;
                }else {
                    queue.offer(nextWord);
                }
            }
        }
        return 0;
        
    }
    
    public List<String> findNext(String beginWord, List<String> wordList, HashMap<String, Integer> map, int depth) {
        List<String> retWordList = new ArrayList<String>();
        for(int position = 0; position < beginWord.length(); position += 1) {
            for (int index = 0; index < 26; index++){
                char replace = (char) ('a' + index);
                String newWord = beginWord.substring(0, position) + replace + beginWord.substring(position+1, beginWord.length()); 
                Integer word_distance = map.get(newWord);
                if (word_distance != null && word_distance == 0) {
                    retWordList.add(newWord);
                    map.put(newWord,  depth + 1);
                }
            }
        }
        
        return retWordList;
    }
    

}

Posted on

Linkage

https://leetcode.com/problems/sort-colors/description/

Idea

0……0 1……1 x1 x2 …. xm 2…..2

​ | | |

​ left i right

Code

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
class Solution {
    public void sortColors(int[] nums) {
        //[left, right] is 1
        
        int left=0, right=nums.length - 1;
        int i = 0;
        while(i <= right) {
            if(nums[i]==0) {
                swap(nums, i++, left++);
                continue;
            }if(nums[i]==1) {
                i++;
                continue;
            } 
            if(nums[i]==2) {
                swap(nums, i, right--);
                continue;
            }
                
        }
    }
    
    public void swap(int[] array, int left, int right) {
        int temp = array[left];
        array[left] = array[right];
        array[right] = temp;
    }
}