LeetCode - Algorithms - 98. Validate Binary Search Tree

The solution of wikipedia is the elegant answer to this question. It finally passed on LeetCode after I modified and submited six times.

Sometimes we already have a binary tree, and we need to determine whether it is a BST. This problem has a simple recursive solution.

Essentially we keep creating a valid range (starting from [MIN_VALUE, MAX_VALUE]) and keep shrinking it down for each node as we go down recursively.

Problem

Given a binary tree, determine if it is a valid binary search tree (BST).

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isValidBST(TreeNode root) {
        return isValidBST(root,Long.MIN_VALUE,Long.MAX_VALUE);
    }

    public boolean isValidBST(TreeNode root, long minKey, long maxKey) {
    	if (root==null) return true;
    	if (root.val<=minKey || root.val>=maxKey) return false;
    	return isValidBST(root.left,minKey,root.val) && isValidBST(root.right,root.val,maxKey);
    }   
}

Submission Detail

  • 75 / 75 test cases passed.
  • Runtime: 0 ms
  • Your runtime beats 100.00 % of java submissions.

ref

LeetCode - Algorithms - 145. Binary Tree Postorder Traversal

2007年学习数据结构曾经把北大《数据结构与算法》(张铭、赵海燕、王腾蛟)教材书上的c++实现翻译为Java语言，后序周游是最难理解的，现在拿来在LeetCode上跑跑。

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
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
    	List<Integer> list = new ArrayList<Integer>();

		if (root!=null) {
			StackElement element = null;
			TreeNode ptr = root;
			Stack<StackElement> stk = new Stack<StackElement>();
			while(true) {
				while(ptr!=null) {
					element = new StackElement();
					element.setTreenode(ptr);
					element.setTag(Tags.Left);;
					stk.push(element);
					ptr = ptr.left;
				}
				element = (StackElement) stk.peek();
				stk.pop();
				ptr = element.getTreenode();
				while( element.getTag()==Tags.Right ) {
					list.add(element.getTreenode().val);		
					if (stk.isEmpty())
						return list;
					else {
						element = (StackElement) stk.peek();
						stk.pop();
						ptr = element.getTreenode();
					}
				}
				element.setTag(Tags.Right);;
				stk.push(element);
				ptr = ptr.right;
			}			
		}    	

        return list;        
    }
}

enum Tags {Left,Right};

final class StackElement {
	private TreeNode treenode = null;
	private Tags tag;

	public Tags getTag() {
		return tag;
	}
	public void setTag(Tags tag) {
		this.tag = tag;
	}
	public TreeNode getTreenode() {
		return treenode;
	}
	public void setTreenode(TreeNode treenode) {
		this.treenode = treenode;
	}

	public StackElement() {
		super();
	}

}

Submission Detail

  • 68 / 68 test cases passed.
  • Runtime: 4 ms
  • Your runtime beats 0.68 % of java submissions.

LeetCode - Algorithms - 144. Binary Tree Preorder Traversal

2007年学习数据结构曾经把北大《数据结构与算法》(张铭、赵海燕、王腾蛟)教材书上的c++实现翻译为Java语言，现在拿来在LeetCode上跑跑，不是很理解。

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
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
    	List<Integer> list = new ArrayList<Integer>();
		if (root!=null) {
			TreeNode ptr = root;
			Stack<TreeNode> stk = new Stack<TreeNode>();
			while(!stk.isEmpty() || ptr != null) {
				if (ptr!=null) {
					list.add(ptr.val);
					stk.push(ptr);
					ptr = ptr.left;
				}
				else {
					ptr = (TreeNode) stk.peek();
					ptr = ptr.right;
					stk.pop();
				}
			}			
		}    	
    	return list;        
    }
}

Submission Detail

  • 68 / 68 test cases passed.
  • Runtime: 1 ms
  • Your runtime beats 61.91 % of java submissions.

LeetCode - Algorithms - 102. Binary Tree Level Order Traversal

Although its performance is not good, solution of Binary Tree Level Order Traversal is clear.

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
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
    	List<List<Integer>> result = new ArrayList<List<Integer>>();
    	if (root==null) return result;
    	Map<Integer,List<Integer>> map = new TreeMap<Integer,List<Integer>>();
		updateMap(root,0,map);

    	for(Map.Entry<Integer, List<Integer>> entry : map.entrySet()) {
    		result.add(entry.getValue());
    	}
    	return result;        
    }

    private void updateMap(TreeNode root, int level, Map<Integer,List<Integer>> map) {
    	if (root == null) return;
    	++level;
    	if (map.containsKey(level)) {
    		map.get(level).add(root.val);
    	}
    	else {
    		List<Integer> list = new ArrayList<Integer>();
    		list.add(root.val);
    		map.put(level, list);
    	}
    	updateMap(root.left,level,map);
    	updateMap(root.right,level,map);
    	return;
    }    
}

Submission Detail

  • 34 / 34 test cases passed.
  • Runtime: 6 ms
  • Your runtime beats 3.09 % of java submissions.

LeetCode - Algorithms - 94. Binary Tree Inorder Traversal

2007年学习数据结构曾经用Java实现过，虽然还是知其然而不知其所以然，北大那本《数据结构与算法》(张铭、赵海燕、王腾蛟)教材上是用C++实现的。

非递归深度优先周游二叉树

  • 栈是实现递归的最常用的结构
  • 深度优先二叉树周游是递归定义的
  • 利用一个栈来记下尚待周游的结点或子树，以备以后访问。

非递归中序周游二叉树

  • 遇到一个结点，就把它推入栈中，并去周游它的左子树
  • 周游完左子树后，从栈顶托出这个结点并访问之，然后按照它的右链接指示的地址再去周游该结点的右子树。

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
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
    	List<Integer> list = new ArrayList<Integer>();
		if (root!=null) {
			TreeNode ptr = root;
			Stack<TreeNode> stk = new Stack<TreeNode>();
			while(!stk.isEmpty() || ptr != null) {
				if (ptr!=null) {
					stk.push(ptr);
					ptr = ptr.left;
				}
				else {
					ptr = (TreeNode) stk.peek();
					list.add(ptr.val);
					ptr = ptr.right;
					stk.pop();
				}
			}			
		}
		return list;        
    }
}

Submission Detail

  • 68 / 68 test cases passed.
  • Runtime: 1 ms
  • Your runtime beats 60.69 % of java submissions.

LeetCode - Algorithms - 29. Divide Two Integers

LeetCode – Divide Two Integers (Java) is the right answer, tested.

This problem can be solved based on the fact that any number can be converted to the format of the following, Power series of 2:

num=a_0*2^0+a_1*2^1+a_2*2^2+...+a_n*2^n

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
class Solution {
    public int divide(int dividend, int divisor) {
		if (divisor == 0)
			return Integer.MAX_VALUE;
		if (divisor == -1 && dividend == Integer.MIN_VALUE)
			return Integer.MAX_VALUE;

    	boolean sign = ((new Long(dividend)>0) && (new Long(divisor)>0)) || ((new Long(dividend)<0) && (new Long(divisor)<0)) ? true : false;

    	long dividend_abs = Math.abs(new Long(dividend));
    	long divisor_abs = Math.abs(new Long(divisor));

    	long quotient = 0;
		while (dividend_abs >= divisor_abs) {
			// calculate number of left shifts
			int numShift = 0;
			while (dividend_abs >= (divisor_abs << numShift)) {
				numShift++;
			}
			// dividend minus the largest shifted divisor
			quotient += 1 << (numShift - 1);
			dividend_abs -= (divisor_abs << (numShift - 1));
		}

    	return sign?new Long(quotient).intValue():-new Long(quotient).intValue();       
    }
}

Submission Detail

  • 989 / 989 test cases passed.
  • Runtime: 31 ms
  • Your runtime beats 30.12 % of java submissions.

LeetCode - Algorithms - 155. Min Stack

The solution of two stack is clear for me.

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
class MinStack {
	private Stack<Integer> stack;
	private Stack<Integer> minStack;

    /** initialize your data structure here. */
    public MinStack() {
    	stack = new Stack<Integer>();
    	minStack = new Stack<Integer>();
    }

    public void push(int x) {
    	stack.push(x);
    	if (minStack.isEmpty() || minStack.peek()>=x)
    		minStack.push(x);
    }

    public void pop() {
        int x = stack.pop();
        if (x==minStack.peek())
        	minStack.pop();
    }

    public int top() {
        return stack.peek();
    }

    public int getMin() {
        return minStack.peek();
    }
}

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack obj = new MinStack();
 * obj.push(x);
 * obj.pop();
 * int param_3 = obj.top();
 * int param_4 = obj.getMin();
 */

Submission Detail

  • 18 / 18 test cases passed.
  • Runtime: 64 ms
  • Your runtime beats 96.51 % of java submissions.

JavaScript

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
/**
 * initialize your data structure here.
 */
var MinStack = function(stk,minStk) {
	this.stk = [];
	this.minStk = [];    
};

/**
 * @param {number} x
 * @return {void}
 */
MinStack.prototype.push = function(x) {
    this.stk.push(x);
    if (this.minStk.length==0 || this.minStk[this.minStk.length-1]>=x)
    	this.minStk.push(x);
};

/**
 * @return {void}
 */
MinStack.prototype.pop = function() {
    var x = this.stk.pop();
    if (x==this.minStk[this.minStk.length-1])
    	this.minStk.pop();
};

/**
 * @return {number}
 */
MinStack.prototype.top = function() {
    return this.stk[this.stk.length-1];
};

/**
 * @return {number}
 */
MinStack.prototype.getMin = function() {
    return this.minStk[this.minStk.length-1];
};

/**
 * Your MinStack object will be instantiated and called as such:
 * var obj = Object.create(MinStack).createNew()
 * obj.push(x)
 * obj.pop()
 * var param_3 = obj.top()
 * var param_4 = obj.getMin()
 */

Submission Detail

  • 18 / 18 test cases passed.
  • Runtime: 68 ms
  • Your runtime beats 100.00 % of javascript submissions.

ref

LeetCode - Algorithms - 190. Reverse Bits

Simple as it labled, The problem is puzzled for it has problem with unsigned integer, and neith Java nor JavaScript has unsigned type. I’d like to pass it for some time. The code copied from Web passed in LeetCode, but it output wrong result for some input number.

Java

solution from 190. Reverse Bits

There is no unsigned integer type. If you need to work with unsigned values originating outside your program, they must be stored in a larger signed type. For example, unsigned bytes produced by an analog-to-digital converter, can be read into variables of type short. — THE Java™ Programming Language, Fourth Edition, By Ken Arnold, James Gosling, David Holmes

1
2
3
4
5
6
7
8
9
10
11
12
public class Solution {
    // you need treat n as an unsigned value
    public int reverseBits(int n) {
		int res = 0;
		for (int i = 31; i >= 0; i--) {
			if (((n >> i) & 1) == 1) {
				res += (1 << (31 - i));
			}
		}
		return res;        
    }
}

Submission Detail

  • 600 / 600 test cases passed.
  • Runtime: 1 ms
  • Your runtime beats 100.00 % of java submissions.

JavaScript

solution from 190. Reverse Bits – JavaScript 代码

1
2
3
4
5
6
7
8
9
10
11
/**
 * @param {number} n - a positive integer
 * @return {number} - a positive integer
 */
var reverseBits = function(n) {
    var result = 0;
    for (var i = 0; i < 32; ++i) {
        result |= (n >> i & 0x1) << (31 - i);
    }
    return result >>> 0;    
};

Submission Detail

  • 600 / 600 test cases passed.
  • Runtime: 88 ms
  • Your runtime beats 12.00 % of javascript submissions.

Bitwise and Bit Shift

Java Bitwise and Bit Shift Operators

Operator Description
| Bitwise OR
& Bitwise AND
~ Bitwise Complement
^ Bitwise XOR
<< Left Shift
>> Right Shift
>>> Unsigned Right Shift

example

1

System.out.printf("%d*%d=%d", 2,8,2<<3);

2

System.out.printf("%d/2=%d",11,11>>1);

3

public static boolean isOddNum(int n) {
    return (n & 1)==1;
}

4

public static int powerofTwo(int n) {
    return 2<<(n-1);
}

5

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/**
 * how to multiply two arbitrary integers a and b (a greater than b) 
 * using only bitshifts and addition
 * @param a
 * @param b
 * @return
 */
public static int multiply(int a, int b) {
	int c = 0;
	while (b!=0) {
		if ((b & 1)!=0)
			c+=a;
		a <<= 1;
		b >>= 1;
	}
	return c;
}

6

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/**
 * how to calculate a sum of two integers a and b 
 * using bitwise operators and zero-testing
 * @param a
 * @param b
 * @return
 */
public static int sum(int a, int b) {
	int c=0;
	while(a!=0) {
		c = b & a;
		b = b ^ a;
		c <<= 1;
		a = c;
	}
	return b;
}

JavaScript Bitwise Operators

Operator Name Description
& AND Sets each bit to 1 if both bits are 1
| OR Sets each bit to 1 if one of two bits is 1
^ XOR Sets each bit to 1 if only one of two bits is 1
~ NOT Inverts all the bits
<< Zero fill left shift Shifts left by pushing zeros in from the right and let the leftmost bits fall off
>> Signed right shift Shifts right by pushing copies of the leftmost bit in from the left, and let the rightmost bits fall off
>>> Zero fill right shift Shifts right by pushing zeros in from the left, and let the rightmost bits fall off

ref

LeetCode - Algorithms - 206. Reverse Linked List

Problem

206. Reverse Linked List

Follow up

A linked list can be reversed either iteratively or recursively. Could you implement both?

Java

iteratively

1

© LeetCode – Reverse Linked List (Java) - Java Solution 1 - Iterative

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
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
		if (head == null || head.next == null)
			return head;

		ListNode p1 = head;
		ListNode p2 = p1.next;

		head.next = null;
		while (p1 != null && p2 != null) {
			ListNode t = p2.next;
			p2.next = p1;
			p1 = p2;
			p2 = t;
		}

		return p1;
    }
}

Submission Detail

  • 27 / 27 test cases passed.
  • Runtime: 0 ms, faster than 100.00% of Java online submissions for Reverse Linked List.
  • Memory Usage: 39 MB, less than 22.36% of Java online submissions for Reverse Linked List.

2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
    	ListNode prev = null;
    	ListNode current = head;
    	ListNode next = null;
    	while(current!=null) {
    		next = current.next;
    		current.next = prev;
    		prev = current;
    		current = next;
    	}
    	head = prev;
        return head;
    }
}

Submission Detail

  • 27 / 27 test cases passed.
  • Runtime: 0 ms
  • Your runtime beats 100.00 % of java submissions.

recursively

1

© LeetCode – Reverse Linked List (Java) - Java Solution 2 - Recursive

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
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
		if (head == null || head.next == null)
			return head;

		//get second node
		ListNode second = head.next;
		//set first's next to be null
		head.next = null;

		ListNode rest = reverseList(second);
		second.next = head;

		return rest;
    }
}

Submission Detail

  • 27 / 27 test cases passed.
  • Runtime: 0 ms, faster than 100.00% of Java online submissions for Reverse Linked List.
  • Memory Usage: 39.2 MB, less than 22.97% of Java online submissions for Reverse Linked List.

2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
    	if (head==null || head.next==null)
    		return head;
    	ListNode p = reverseList(head.next);
    	head.next.next=head;
    	head.next=null;
        return p;
    }
}

Submission Detail

  • 27 / 27 test cases passed.
  • Runtime: 1 ms
  • Your runtime beats 6.80 % of java submissions.

Tail Recursive

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 reverseUtil(ListNode curr, ListNode prev) {
    	ListNode head = null;
    	if (curr.next==null) {
    		head = curr;
    		curr.next=prev;
    		return head;
    	}

    	ListNode next1 = curr.next;
    	curr.next=prev;
    	head = reverseUtil(next1,curr);
    	return head;
    }

    public ListNode reverseList(ListNode head) {
        if (head!=null)
          return reverseUtil(head,null);
        else
            return null;
    }
}

Submission Detail

  • 27 / 27 test cases passed.
  • Runtime: 0 ms
  • Your runtime beats 100.00 % of java submissions.