Fork me on GitHub

Posted on

Description

Given an integer n, return all distinct solutions to the n-queens puzzle.

Each solution contains a distinct board configuration of the n-queens’ placement, where 'Q' and '.' both indicate a queen and an empty space respectively.

Example:

1
2
3
4
5
6
7
8
9
10
11
12
13
Input: 4
Output: [
 [".Q..",  // Solution 1
  "...Q",
  "Q...",
  "..Q."],

 ["..Q.",  // Solution 2
  "Q...",
  "...Q",
  ".Q.."]
]
Explanation: There exist two distinct solutions to the 4-queens puzzle as shown above.

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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
class Solution(object):
    def solveNQueens(self, n):
        """
        :type n: int
        :rtype: List[List[str]]
        """
        matrix = [ ["." for j in range(n)] for i in range(n)]
        self.solution_list = []
        self.solve(matrix, 0)
        
        return self.solution_list
                        
    def solve(self, matrix, row):
        n = len(matrix)
        if row == n:
            ## Deep copy
            new_matrix = [ "" for i in range(n)]
            
            for i in range(n):
                for j in range(n):
                    new_matrix[i] += matrix[i][j]
            self.solution_list.append(new_matrix)
            return
        
        for col in range(n):
            if self.validate(matrix, row, col):
                matrix[row][col] = "Q"
                self.solve(matrix, row+1)
                matrix[row][col] = '.'

    
    def validate(self, matrix, row, col):
        lens = len(matrix)
        for i in range(lens):
            if matrix[row][i] == "Q":
                return False
            if matrix[i][col] == "Q":
                return False
        
        index = 1
        while row - index >= 0 and col - index >= 0:
            if matrix[row-index][col-index] == "Q":
                return False
            index += 1
            
        index = 1
        while row + index < lens and col + index < lens:
            if matrix[row+index][col+index] == "Q":
                return False
            index += 1
        
        index = 1
        while row + index < lens and col - index >= 0:
            if matrix[row+index][col-index] == "Q":
                return False
            index += 1
            
        index = 1
        while row - index < lens and col + index < lens:
            if matrix[row-index][col+index] == "Q":
                return False
            index += 1
        
        
        return True

Posted on

Description

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

Example:

1
2
3
Input: [-2,1,-3,4,-1,2,1,-5,4],
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.

Follow up:

If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution(object):
    def maxSubArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        yet_max = nums[0]
        lens = len(nums)
        ret = nums[0]
        for i in range(1, lens):
            yet_max = max(nums[i], nums[i] + yet_max)
            if yet_max > ret:
                ret = yet_max
        
        return ret

Extension

Given an integer array nums, find the contiguous subarray within an array (containing at least one number) which has the largest product.

Example 1:

1
2
3
Input: [2,3,-2,4]
Output: 6
Explanation: [2,3] has the largest product 6.

Example 2:

1
2
3
Input: [-2,0,-1]
Output: 0
Explanation: The result cannot be 2, because [-2,-1] is not a subarray.

In this context, we need to maitain two arrays to record the local max product and local min product which end with the char before the current one.

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution(object):
    def maxProduct(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        
        yet_min = nums[0]
        yet_max = nums[0]
        ret = nums[0]
        lens = len(nums)
        
        for index in range(1, lens):
            raw_yet_max = yet_max
            yet_max = max(nums[index], nums[index]*yet_max, nums[index]*yet_min)
            yet_min = min(nums[index], nums[index]*raw_yet_max, nums[index]*yet_min)
            
            if yet_max > ret:
                ret = yet_max
            
        return ret

Posted on

Description

https://leetcode.com/problems/counting-bits/description/

Given a non negative integer number num. For every numbers i in the range 0 ≤ i ≤ num calculate the number of 1’s in their binary representation and return them as an array.

Example:
For num = 5 you should return [0,1,1,2,1,2].

Follow up:

  • It is very easy to come up with a solution with run time O(n*sizeof(integer)). But can you do it in linear time O(n) /possibly in a single pass?

  • Space complexity should be O(n).

  • Can you do it like a boss? Do it without using any builtin function like __builtin_popcount in c++ or in any other language.

    ​

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution(object):
    def countBits(self, num):
        """
        :type num: int
        :rtype: List[int]
        """
        ret = [1]
        stack = [1]
        index = 0
        while index <= num:
            new_stack = []
            for count in stack:
                ret.append(count)
                ret.append(count+1)
                new_stack.append(count)
                new_stack.append(count+1)
                index += 1
            stack = new_stack
            
        return [0] + ret[0:num]

Posted on

Description

Given an unsorted array of integers, find the length of longest increasing subsequence.

Example:

1
2
3
Input: [10,9,2,5,3,7,101,18]
Output: 4 
Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4.

Note:

  • There may be more than one LIS combination, it is only necessary for you to return the length.
  • Your algorithm should run in O(n2) complexity.

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
class Solution(object):
    def lengthOfLIS(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        lens = len(nums)
        if not lens:
            return 0
        
        end_array = [0 for i in range(lens)]
        end_array[0] = 1
        max_length = 1
        for end in range(1, lens):
            local_max_length = 1
            for start in range(0, end):
                if nums[start] < nums[end]:
                    if end_array[start] + 1 > local_max_length:
                        local_max_length = end_array[start] + 1
            
            end_array[end] = local_max_length
            if max_length < local_max_length:
                max_length = local_max_length
            
        return max_length

Posted on

Sudoku Solver

Description

https://leetcode.com/problems/sudoku-solver/description/

Write a program to solve a Sudoku puzzle by filling the empty cells.

A sudoku solution must satisfy all of the following rules:

  1. Each of the digits 1-9 must occur exactly once in each row.
  2. Each of the digits 1-9 must occur exactly once in each column.
  3. Each of the the digits 1-9 must occur exactly once in each of the 9 3x3 sub-boxes of the grid.

Empty cells are indicated by the character '.'.

Solution

This is a brutal-force implementation of Sudoku algorithm, The solution ism quite straightforward, we choose each empty cell, try values from 1 to 9, once validated, then we recursively call the solver function, until there is no other empty cell.

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
29
30
31
32
33
34
35
36
37
38
39
40
41
class Solution(object):
    def solveSudoku(self, board):
        """
        :type board: List[List[str]]
        :rtype: void Do not return anything, modify board in-place instead.
        """
        self.numbers = ["1", "2", "3", "4", "5", "6", "7", "8", "9"]
        self.solveSu(board)
     
    def solveSu(self, board):
        for i in range(9):
            for j in range(9):
                if board[i][j] == '.':
                    for k in self.numbers:
                        if self.validateSudoku(board, k, i, j):
                            board[i][j] = k
                            if self.solveSu(board):
                                return True
                            else:
                                board[i][j] = '.'
                    return False
        
        return True
        
    def validateSudoku(self, board, k, i, j):
        for index in range(9):
            if board[i][index] == k:
                return False
            
        for index in range(9):
            if board[index][j] == k:
                return False
        
        start_row = int(i/3)*3
        start_col = int(j/3)*3
        for index_row in range(start_row, start_row+3):
            for index_col in range(start_col, start_col+3):
                if board[index_row][index_col] == k:
                    return False
        
        return True

Improvement

A little trick to make the backtracing faster is accelerate the validation process, by using hash table in each row, each column, each block.

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
class Solution(object):
    def solveSudoku(self, board):
        """
        :type board: List[List[str]]
        :rtype: void Do not return anything, modify board in-place instead.
        """
        self.numbers = ["1", "2", "3", "4", "5", "6", "7", "8", "9"]
        self.row_hash = [{} for j in range(9)]
        self.col_hash = [{} for j in range(9)]
        self.block_hash = [{} for j in range(9)]
        
        for i in range(9):
            for j in range(9):
                if board[i][j] != '.':
                    value = board[i][j]
                    self.row_hash[i][value] = True
                    self.col_hash[j][value] = True
                    self.block_hash[int(i/3)*3+(int(j/3))][value] = True
        self.solveSu(board)
        
     
    def solveSu(self, board):
        for i in range(9):
            for j in range(9):
                if board[i][j] == '.':
                    for k in self.numbers:
                        if self.validateSudoku(board, k, i, j):
                            board[i][j] = k
                            self.row_hash[i][k] = True
                            self.col_hash[j][k] = True
                            self.block_hash[int(i/3)*3+(int(j/3))][k] = True
                            if self.solveSu(board):
                                return True
                            else:
                                board[i][j] = '.'
                                self.row_hash[i][k] = False
                                self.col_hash[j][k] = False
                                self.block_hash[int(i/3)*3+(int(j/3))][k] = False
                    return False
        
        return True
        
    def validateSudoku(self, board, k, i, j):
        if self.row_hash[i].get(k) or self.col_hash[j].get(k) or self.block_hash[int(i/3)*3+(int(j/3))].get(k):
            return False
        
        
        return True

Experiment

Posted on

This is an easy parser that can support nested list, link:https://leetcode.com/problems/mini-parser/description/

Description

Given a nested list of integers represented as a string, implement a parser to deserialize it.

Each element is either an integer, or a list – whose elements may also be integers or other lists.

Note: You may assume that the string is well-formed:

  • String is non-empty.
  • String does not contain white spaces.
  • String contains only digits 0-9, [, - ,, ].

Example 1:

1
2
3
Given s = "324",

You should return a NestedInteger object which contains a single integer 324.

Example 2:

1
2
3
4
5
6
7
8
9
Given s = "[123,[456,[789]]]",

Return a NestedInteger object containing a nested list with 2 elements:

1. An integer containing value 123.
2. A nested list containing two elements:
    i.  An integer containing value 456.
    ii. A nested list with one element:
         a. An integer containing value 789.

Implementation

We use devide and conquer to parse it.

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
# """
# This is the interface that allows for creating nested lists.
# You should not implement it, or speculate about its implementation
# """
#class NestedInteger(object):
#    def __init__(self, value=None):
#        """
#        If value is not specified, initializes an empty list.
#        Otherwise initializes a single integer equal to value.
#        """
#
#    def isInteger(self):
#        """
#        @return True if this NestedInteger holds a single integer, rather than a nested list.
#        :rtype bool
#        """
#
#    def add(self, elem):
#        """
#        Set this NestedInteger to hold a nested list and adds a nested integer elem to it.
#        :rtype void
#        """
#
#    def setInteger(self, value):
#        """
#        Set this NestedInteger to hold a single integer equal to value.
#        :rtype void
#        """
#
#    def getInteger(self):
#        """
#        @return the single integer that this NestedInteger holds, if it holds a single integer
#        Return None if this NestedInteger holds a nested list
#        :rtype int
#        """
#
#    def getList(self):
#        """
#        @return the nested list that this NestedInteger holds, if it holds a nested list
#        Return None if this NestedInteger holds a single integer
#        :rtype List[NestedInteger]
#        """

class Solution(object):
    def deserialize(self, s):
        """
        :type s: str
        :rtype: NestedInteger
        """
        if s[0] != '[':
            return int(s)
        else:
            ret = self.parseArray(s, 0)
            return ret[0]
        
        
    def parseArray(self, s, index):
        cursor = index + 1
        length = len(s)
        ret_array = NestedInteger()
        number_str = ''
        while cursor < length:
            
            if s[cursor] == '[':
                sub_array, cursor = self.parseArray(s, cursor)
                ret_array.add(sub_array)
                
                continue
            if s[cursor] == ',':
                cursor += 1
                if number_str:
                    ret_array.add(NestedInteger(int(number_str)))
                    number_str = ''
                continue
            if s[cursor] == ']':
                if number_str:
                    ret_array.add(NestedInteger(int(number_str)))
                cursor += 1
                return ret_array, cursor
            
            ##number
            number_str += s[cursor]
            cursor += 1
        
        return ret_array, cursor
0 i1 n2 t3 e4 N5
e 1 2 3 3 4
x 2 2 3 4 4
e 3 3 3 3 4
c 4 4 4 4 4
u 5 5 5 5 5

Posted on

In this question, we need to implement a naive caculator, but thing will never be easu for the rookie like me, so lets go through it.

Description

Given a nested list of integers represented as a string, implement a parser to deserialize it.

Each element is either an integer, or a list – whose elements may also be integers or other lists.

Note: You may assume that the string is well-formed:

  • String is non-empty.
  • String does not contain white spaces.
  • String contains only digits 0-9, [, - ,, ].

Discuss

From the textbook we learn that the data structure Stack will be of great help to get the value from expression. The following code just implement it with the given rules.

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
import pdb
class Solution(object):
    
    def calculate(self, s):
        """
        :type s: str
        :rtype: int
        """
        def add(a, b):
            return a+b
        def sub(a, b):
            return a-b
        def dot(a, b):
            return a*b
        def divide(a, b):
            return int(a/b)
        
        self.s = s
        self.length = len(s)
        self.index = 0
        self.operator_dict = {
            " ": 0,
            "+": (1, add),
            "-": (1, sub),
            "*": (2, dot),
            "/": (2, divide)
        }
        self.expression_stack = []
        self.number_stack = []
        while self.index < self.length:
            self.escape_space()
            self.processNumber()
            self.escape_space()
            self.processOperator()

        while self.expression_stack:
            self.doCaculate()
            
        return self.number_stack[0]
    
    def doCaculate(self):
        right = self.number_stack.pop()
        left = self.number_stack.pop()
        func = self.expression_stack.pop()[1]
        result = func(left, right)
        self.number_stack.append(result)
    
    def escape_space(self):
        while self.index < self.length and self.s[self.index] == ' ':
            self.index += 1
        return 
    
    def processOperator(self):
        if self.index >= self.length:
            return
        operator = self.s[self.index]
        self.index += 1
        tup = self.operator_dict[operator]
        
        ##In case the first element of the expression stack
        while self.expression_stack and tup[0] <= self.expression_stack[-1][0]:
                self.doCaculate()
        
        self.expression_stack.append(tup)
        
    
    def processNumber(self):
        if self.index >= self.length:
            return 
        number_stack = []
        while self.index < self.length and self.isdigit():
            number_stack.append(int(self.s[self.index]))
            self.index += 1
        
        ret_num = 0
        bit = 1
        while number_stack:
            current = number_stack.pop()
            ret_num += current*bit
            bit *= 10
            
        self.number_stack.append(ret_num)

if __name__ == '__main__':
    s = Solution()
    print(s.calculate("1*2-3/4+5*6-7*8+9/10"))

Detail

In fact , this implementation can extended to support more operators, life exponential, and the another question on leetcode Basic Caculator IV is more considering the parentheses.

Posted on

Preface

Before you read, I hope you should have some hand-on experience of the Promise mechenism in javascript. And you should also bear in mind that Promise is not mysterious at all, which is just a trick invented by some functional programming enthusiast. In the following part, I will unmask the magic of this magic Promise

Anatomy

Recap

Let’s coin a simple promise example first

1
2
3
4
5
6
7
8
9
10
11
function getUserId() {
    return new Promise(function(resolve){
        http.get(url, function(results){
            resolve(results.id);
        })
    });
}

getUserId().then(function(id){
   //Processing given id from resolve; 
});

Prototype for Promise

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
function Promise(fn) {
    var state = 'pending';
    var value = null;
    var callbacks = [];
    
    //'then' is a register for callbacks function 
    this.then = function (onFulfilled, onRejected){
        return new Promise(function(resolve, reject){
            handle({
                onFulfilled: onFulfilled || null,
                onRejected: onRejected || null,
                resolve: resolve,
                reject: reject
            });
        });
    };
    
    function handle(callback){
        if (state == 'pending'){
            callbacks.push(callback);
            return;
        }
        
        var cb = (state === 'fulfilled' ? callback.onFulfilled: callback.onRejected);
        
        if (cb === null) {
            cb = (state === 'fulfilled' ? callback.resolve : callback.reject);
            cb(value);
            return;
        }
        
        try {
        	var ret = cb(value);
        	callback.resolve(ret);
    	} catch (e) {
        	callback.reject(e);
    	} 

                                       r
    }
    
    
    function resolve(newValue){
        if (newValue && (typeof newValue === 'object' || typeof newValue === 'function')) {
            var then = newValue.then;
            if (typeof then === 'function') {
                then.call(newValue, resolve);
                return;
            }
        }
        value = newValue;
        state = 'fulfilled';
        execute();
    };
    
    function reject(reason) {
        state = 'rejected';
        value = reason;
        execute();
    }
    
    
    function execute(){
        setTimeout(function() {
            callbacks.forEach(function (callback){
            	callback(value);
        	});
        }, 0);
    }
    
    //Start the real function call
    fn(resolve, reject);
}

​
​
​
​
​
​
​
​
​

​
​
​
​
​
​
​
​
​
​

​
​
​
​

Posted on

Definition and Goal

The dynamic proxy can be divided into two parts: “proxy” and “dynamic”——the “proxy(pattern)” is one kind of design pattern in GoF, and the “dynamic” means the proxy pattern can be polished with the help of reflection mechanism in JVM. The ability to decoupling the routine tasks and business tasks is the reason why dynamic proxy is widely used in many Java Web Framework(Like Spring).

Overview

In this article, we will elaborate on the evolution of proxy during the example Database transaction, to illustrate the idea of this magic proxy, and at the end we will demystify the implementation of how this amazing mechanism implemented behind JDK.

Background

The task of own design is modeling how to manipulate the database transaction, we have only one table named User, providing two method: add, delelete for outsider. Pay attention the fact that we need to use start and end routine before and after the normal operation on database to gurantee the atomic of our transaction.

First, we define the interface ingerated with our functions

1
2
3
4
interface UserService {
    public void addUser();
    public void deleteUser();
}

Evolution

Naive

The naive way is to implement the interface of the UserService brutally, 

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 UserServiceNoProxy implements UserService {

    @Override
    public void addUser() {
        System.out.println("Start a database connection");
        System.out.println("Add the user information");
        System.out.println("Close a database connection");
    }

    @Override
    public void deleteUser() {
        System.out.println("Start a database connection");
        System.out.println("Delete the user information");
        System.out.println("Close a database connection");
    }   
}

public class TestNoProxy {
    public static void main(String[] args) {
        UserServiceNoProxy userServiceNoProxy = new UserServiceNoProxy();
        userServiceNoProxy.addUser();
        userServiceNoProxy.deleteUser();
    }
}

The shortcoming of this implementation is the mixture the code of routine operation(Start Close DB connection) and the one of the variable operation(Add or Delete user). So our next improvement is to sepearate these two kinds of code.

Static Proxy

We generate two classes to decouple the routine code and the normal code.

UserServiceImpl: Contains the normal functions to manipulate database

1
2
3
4
5
6
7
8
9
10
11
12
13
class UserServiceImpl implements UserService {

    @Override
    public void addUser() {
        System.out.println("Add the user information");
    }

    @Override
    public void deleteUser() {
        System.out.println("Delete the user information");
    }
    
}

UserServiceStaticProxy: The wrapper of UserServiceImpl, attached with routine functions

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 UserServiceStaticProxy implements UserService {

    private UserService userService;

    public UserServiceStaticProxy(UserService userService){
        super();
        this.userService = userService;
    }

    public void open(){
        System.out.println("Start a database connection");
    }

    public void close(){
        System.out.println("Close a database connection");
    }

    @Override
    public void deleteUser() {
        this.open();
        userService.deleteUser();
        this.close();
    }

    @Override
    public void addUser() {
        this.open();
        userService.addUser();
        this.close();
    }

}

By the proxy pattern, we can seperate the operation into two classes. But one thing is still disturbing, let’s say, the addUser and deleteUser both contains the open and close , which are redundant. So we need to introduce the dynamic proxy to sublime.

Dynamic Proxy

Before coding, we have to say that the code below is a little bold to your intuition, and you should just follow the rules to generate the code, we will demysify it in the next part.

We need a few package related to Reflect to create a Dynamic proxy.

1
2
3
import java.lang.reflect.InvocationHandler;
import java.lang.reflect.Method;
import java.lang.reflect.Proxy;

The key idea is to create a dynamic proxy is by implementing InvocationHandler, then override the getProxy and invoke, in the invoke method we wrap the operation logic with routine

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class ServiceProxy implements InvocationHandler{

    private Object target = null;

    public Object getProxy(Object obj){
        this.target = obj;  //Save the object
        return Proxy.newProxyInstance(obj.getClass().getClassLoader(), obj.getClass().getInterfaces(), this);
    }

    @Override
    public Object invoke(Object proxy, Method method, Object[] args) throws Throwable {
        System.out.println("Start a database connection");
        Object result = method.invoke(target, args);
        System.out.println("Close a database connection");
        return result;
    }
}

Once we create ServiceProxy class, the next part is to use it to manipulate data, the test code is shown below:

1
2
3
4
5
6
7
public class TestDynamicProxy {
    public static void main(String[] args) {
        UserService service = (UserService) new ServiceProxy().getProxy(new UserServiceImpl());
        service.addUser();
        service.deleteUser();
    }
}

The result should be consistent with the static proxy, but with tiny code. In the next part, I will explore the InvocationHandler in the JDK.

Demystify the magic behind the dynamic Proxy

There are not only one way to implement dynamic proxy in java, the way mentioned about is one of them called JDK Dynamic Proxy, we will focus on it in the part below:

JDK Dynamic Proxy

First we need to recap the procedure of create a dynamic Proxy:

a.Use a proxy class A Implements the InvocationHandler with a implemented class C, finish the invoke and getProxy method, we use the newProxyInstance function to return the real proxy B in getProxy method

b.Instantiaze the proxy B as b

c.Use b as the proxy of C to call function declared in the interface.

By analysis, we can know the fact that proxy class B is generated by the extant code, as for how to create a new class in JVM, we just need to generate the corresponding java file and compile it into binary .class file ,then use the class loader to load the file into corresponding position in JVM memory. We will not talk about the detailed code of it due to the limitation of time.

CGLIB

This is an open-source library to generate the class on low level, which means it skip the copiling time spent in JDK Proxy. We will talk about it later.

Posted on

Preface

This is the first time to record my leetcode journey on the blog, in memory of the suffering of the disease.

Description:

Given an array nums of n integers, are there elements a, b, c in nums such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Example

1
2
3
4
5
6
7
Given array nums = [-1, 0, 1, 2, -1, -4],

A solution set is:
[
  [-1, 0, 1],
  [-1, -1, 2]
]

Analysis

Base: TwoSum

Background

Two Sum problem is simple, just need find all the pair in the array which satisify the sum is equal to a certain number. Here are 2 main solutions(except the bi-loop brutal way):

  1. Use a boolean map to record whether the certain number is in the given array(O(n)), then travserse the given array(O(n))
  2. Sort the given array, then use two pointer initialized at the start and the end of the array, to detect the proper pair of items by moving.

Extension: Three Sum

Two ways to solve the 3sum problem, and all needs to downgrade the 3sum to 2sum problem,

Tricky and Dirty

Getting familiar with Java do require me some time to read the reference API in Java. Als in my initial implementation, I ignore the duplication case, so I just use the set in java brutally. But the efficiency of the algo is really low, and because of it, I encountered the TLE in the second to last case.

My ugly implementation:(It do work)

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
class Solution {
    public List<List<Integer>> threeSum(int[] nums){
        List<List<Integer>> ret = new LinkedList<>();
        Arrays.sort(nums);
        if (nums.length<3){
            return ret;
        }
        for (int i = 0; i < nums.length-2; i++){
            if(nums[i] > 0)
                break;
            else if(nums[i] == 0 && nums[i+1] == 0 && nums[i+2] == 0){
                List<Integer> triple = new LinkedList<Integer>();
                triple.add(0);
                triple.add(0);
                triple.add(0);
                ret.add(triple);
                break;
            }
            Integer two_sum = nums[i];
            two_sum = -two_sum;
            int start = i + 1;
            int end = nums.length-1;
            while(start < end){
                while(nums[start)
                if(nums[start] + nums[end] == two_sum){
                    List<Integer> triple = new LinkedList<Integer>();
                    triple.add(nums[i]);
                    triple.add(nums[start]);
                    triple.add(nums[end]);
                    ret.add(triple);
                    ++start;
                    --end;
                }else if(nums[start] + nums[end] < two_sum){
                    ++start;
                }else {
                    --end;
                }
            }
        }
        Set set = new HashSet();
        set.addAll(ret);
        List<List<Integer>> new_ret = new LinkedList<>();
        new_ret.addAll(set);
        return new_ret;
    }
}

After understanding the tricky of ignoring duplicated item by traversing the pointer(since the array has been sorted), the new code is much cleaner and faster:

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
class Solution {
    public List<List<Integer>> threeSum(int[] nums){
        List<List<Integer>> ret = new LinkedList<>();
        Arrays.sort(nums);
        if (nums.length<3){
            return ret;
        }
        for (int i = 0; i < nums.length-2; i++){
            if(nums[i] > 0)
                break;
            if(i > 0 && nums[i] == nums[i-1]) continue;
            int two_sum = -nums[i];
            // two_sum = -two_sum;
            int start = i + 1;
            int end = nums.length-1;
            while(start < end){
                if(nums[start] + nums[end] == two_sum){
                    List<Integer> triple = new LinkedList<Integer>();
                    triple.add(nums[i]);
                    triple.add(nums[start]);
                    triple.add(nums[end]);
                    ret.add(triple);
                    while(end > start && nums[end-1]==nums[end]) --end;
                    while(start < end && nums[start]==nums[start+1]) ++start;
                    ++start;
                    --end;
                }else if(nums[start] + nums[end] < two_sum){
                    ++start;
                }else {
                    --end;
                }
            }
        }
        return ret;
    }
}

Result

Reference

https://leetcode.com/problems/3sum/description/