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.

LeetCode - Algorithms - 387. First Unique Character in a String

虽然是Easy的题，自己却想不出来，最后只好参考了这个 Given a string, find its first non-repeating character 的思路，倒也很容易看明白，一点就破的题。

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
class Solution {
    public int firstUniqChar(String s) {
    	Map<Character,Integer> count = new HashMap<Character,Integer>();
    	char c = '\u0000';
    	for(int i=0;i<s.length();i++) {
    		c = s.charAt(i);
    		if (count.containsKey(c)) {
    			count.put(c, count.get(c)+1);
    		}
    		else {
    			count.put(c, 1);
    		}
    	}

        int r = -1;
        for(int i=0;i<s.length();i++) {
        	if (count.get(s.charAt(i))==1) {
        		r = i;
        		break;
        	}
        }
        return r;        
    }
}

Submission Detail

  • 104 / 104 test cases passed.
  • Runtime: 61 ms
  • Your runtime beats 25.39 % 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
/**
 * @param {string} s
 * @return {number}
 */
var firstUniqChar = function(s) {
	var count = {};
	for(var i=0;i<s.length;i++) {
		if (typeof count[s[i]]!="undefined" && count[s[i]]!=null) {
			count[s[i]]++;
		}
		else {
			count[s[i]]=1;
		}
	}
	var r=-1;
	for(var i=0;i<s.length;i++) {
		if (count[s[i]]==1) {
			r=i;
			break;
		}
	}
	return r;    
};

Submission Detail

  • 104 / 104 test cases passed.
  • Runtime: 108 ms
  • Your runtime beats 37.23 % of javascript submissions.

Maven

POM

Project Object Model（项目对象模型）

坐标

在 POM 中，groupId, artifactId, packaging, version 叫作 maven 坐标，它能唯一的确定一个项目。有了 maven 坐标，我们就可以用它来指定我们的项目所依赖的其他项目，插件，或者父项目。一般 maven 坐标写成如下的格式：

    groupId:artifactId:packaging:version
  • groupId 定义了项目属于哪个组，这有助于在大的范围上区别项目
  • artifactId 定义了这个项目在组中唯一的 ID
  • version 指明当前项目的版本

其他

  • name 是一个用户友好的项目名称
  • modelVersion 指定 POM 模型的版本
  • packaging 指定了项目发布时的打包类型

Maven项目结构

目录 目的
${basedir} 存放 pom.xml和所有的子目录
${basedir}/src/main/java 项目的 java源代码
${basedir}/src/main/resources 项目的资源，比如说 property文件
${basedir}/src/test/java 项目的测试类，比如说 JUnit代码
${basedir}/src/test/resources 测试使用的资源
  • 编译后 的 classes 会放在 ${basedir}/target/classes 下面
  • JAR 文件会放在 ${basedir}/target 下面（默认情况下会产生 JAR 文件）

Maven 插件

mvn 本身不会做太多的事情，它不知道怎么样编译或者怎么样打包。它把构建的任务交给插件去做。插件定义了常用的构建逻辑，能够被重复利用。这样做的好处是，一旦插件有了更新，那么所有的 maven 用户都能得到更新。

Maven 生命周期

生命周期指项目的构建过程，它包含了一系列的有序的阶段 (phase)，而一个阶段就是构建过程中的一个步骤。

maven 能支持不同的生命周期，但是最常用的是默认的Maven生命周期 (default Maven lifecycle )。如果你没有对它进行任何的插件配置或者定制的话，那么上面的命令 mvn package 会依次执行默认生命周期中直到包括 package 阶段前的所有阶段的插件目标：

  1. process-resources 阶段：resources:resources
  2. compile 阶段：compiler:compile
  3. process-classes 阶段：(默认无目标)
  4. process-test-resources 阶段：resources:testResources
  5. test-compile 阶段：compiler:testCompile
  6. test 阶段：surefire:test
  7. prepare-package 阶段：(默认无目标)
  8. package 阶段：jar:jar

dependencies

  • 在 POM 中，依赖关系是在 dependencies 部分中定义的。
  • maven 提供了传递依赖的特性，所谓传递依赖是指 maven 会检查被依赖的 jar 文件，把它的依赖关系纳入最终解决的依赖关系链中。
  • 在 POM 的 dependencies 部分中，scope 决定了依赖关系的适用范围。
    • 我们还可以指定 scope 为 provided，意思是 JDK 或者容器会提供所需的jar文件。
    • scope 的默认值是 compile，即任何时候都会被包含在 classpath 中，在打包的时候也会被包括进去。

Maven 库

远程库

maven 默认的远程库(http://repo1.maven.org/maven2)

本地库

本地库是指 maven 下载了插件或者 jar 文件后存放在本地机器上的拷贝。在 Linux 上，它的位置在 ~/.m2/repository，在 Windows XP 上，在 C:\Documents and Settings\username.m2\repository ，在 Windows 7 上，在 C:\Users\username.m2\repository。

当 maven 查找需要的 jar 文件时，它会先在本地库中寻找，只有在找不到的情况下，才会去远程库中找。

mvn

  • mvn install -DskipTests
  • mvn clean install : executes the clean build life cycle and the install build phase in the default build life cycle.
  • mvn install:install-file -Dfile=xxx.jar -DgroupId=xxx -DartifactId=xxx -Dversion=xxx -Dpackaging=jar

common

  • mvn clean : Clears the target directory into which Maven normally builds your project.
  • mvn package : Builds the project and packages the resulting JAR file into the target directory.
  • mvn package -Dmaven.test.skip=true : Builds the project and packages the resulting JAR file into the target directory - without running the unit tests during the build.
  • mvn install : Builds the project described by your Maven POM file and installs the resulting artifact (JAR) into your local Maven repository

build phase command

  • mvn pre-clean
  • mvn compile
  • mvn package

build phases

The most commonly used build phases in the default build life cycle are:

Build Phase Description
validate Validates that the project is correct and all necessary information is available. This also makes sure the dependencies are downloaded.
compile Compiles the source code of the project.
test Runs the tests against the compiled source code using a suitable unit testing framework. These tests should not require the code be packaged or deployed.
package Packs the compiled code in its distributable format, such as a JAR.
install Install the package into the local repository, for use as a dependency in other projects locally.
deploy Copies the final package to the remote repository for sharing with other developers and projects.

ref