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

LeetCode - Algorithms - 20. Valid Parentheses

Difficulty:Easy的题，在面试现场，面对黑板，我毫无头绪没有任何思路，考官已经提示自己你想想有什么数据结构可以利用，自己还是没想通。

This is a problem that’s good to use a stack.

回来上网找线索，主要参考了这个20 LeetCode Java: Valid Parentheses – Easy，此题的关键确实就是数据结构，要用Stack（栈），其实在做表达式解析那两道题227. Basic Calculator II、224. Basic Calculator时已经碰到过，自己也做了题，但还是没理解透，遇到新问题又傻眼了。

代码是人家的，天下程序一大抄！！！但不理解的话，代码不会内化于你。看来自己做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
class Solution {
    public boolean isValid(String s) {
    	HashMap<Character, Character> pair = new HashMap<Character, Character>();
        pair.put(')','(');
        pair.put('}','{');
        pair.put(']','[');    	
        Stack<Character> stk = new Stack<Character>();
        char c = '\u0000';
        for(int i=0;i<s.length();i++) {
        	c = s.charAt(i);
        	switch(c) {
        	case '{':
        	case '[':
        	case '(':
        		stk.push(c);
        		break;
        	default:
        		if (stk.isEmpty() || pair.get(c)!=stk.pop())
        			return false;
        	}
        }
        if (stk.isEmpty())
        	return true;
        return false;        
    }
}

Submission Detail

  • 76 / 76 test cases passed.
  • Runtime: 5 ms
  • Your runtime beats 98.09 % 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
/**
 * @param {string} s
 * @return {boolean}
 */
var isValid = function(s) {
	var pair = {'\}':'\{','\]':'\[',')':'('};
	var stk = new Array();
	var c = '';
	for(var i=0;i<s.length;i++) {
		c = s[i];
		switch(c) {
		case '{':
		case '[':
		case '(':
			stk.push(c);
		    break;
		default:
			if (stk.length==0 || pair[c]!=stk.pop()) {
				return false;
			}
		}
	}
	if (stk.length==0) return true;
	return false;    
};

Submission Detail

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

Knowlege points of database especially mysql

Index

The best way to improve the performance of SELECT operations is to create indexes on one or more of the columns that are tested in the query.
Indexes are used to find rows with specific column values quickly. Without an index, MySQL must begin with the first row and then read through the entire table to find the relevant rows. The larger the table, the more this costs. If the table has an index for the columns in question, MySQL can quickly determine the position to seek to in the middle of the data file without having to look at all the data. If a table has 1,000 rows, this is at least 100 times faster than reading sequentially.

Select

表扫描（table scan）

  • 在表扫描中，每一个表中的文件块都会被顺序扫描，而且每一个记录都会被测试，看它是否会满足条件
  • 表扫描是在没有索引的情况下进行的

索引扫描（index scan）

  • 使用索引的扫描算法称之为索引扫描
  • 当有索引的时候，选择运算就会执行索引扫描

MySQL

Truncate diff Delete

TRUNCATE TABLE empties a table completely. It requires the DROP privilege.

Logically, TRUNCATE TABLE is similar to a DELETE statement that deletes all rows, or a sequence of DROP TABLE and CREATE TABLE statements. To achieve high performance, it bypasses the DML method of deleting data. Thus, it cannot be rolled back, it does not cause ON DELETE triggers to fire, and it cannot be performed for InnoDB tables with parent-child foreign key relationships.

Although TRUNCATE TABLE is similar to DELETE, it is classified as a DDL statement rather than a DML statement.

  • Any AUTO_INCREMENT value is reset to its start value. This is true even for MyISAM and InnoDB, which normally do not reuse sequence values.
  • When used with partitioned tables, TRUNCATE TABLE preserves the partitioning; that is, the data and index files are dropped and re-created, while the partition definitions (.par) file is unaffected.
  • The TRUNCATE TABLE statement does not invoke ON DELETE triggers.

ref

Partitioning

MySQL 5.6 Community binaries provided by Oracle include partitioning support.

SELECT PLUGIN_NAME as Name, PLUGIN_VERSION as Version, PLUGIN_STATUS as Status FROM INFORMATION_SCHEMA.PLUGINS WHERE PLUGIN_TYPE='STORAGE ENGINE';
Name Version Status
partition 1.0 ACTIVE

Sharding

  • 分片、分库分表（Sharding）
  • 以 MySQL 为例，分库分表从阶段应该拆分为分表、分库，一般来说是先进行分表，分表的原动力在于 MySQL 单表性能问题
  • 是由于业务的不可控，所以大家往往采取比较保守的策略，这就是分表的原因。
  • 分库主要由于 MySQL 容量上，MySQL 的写入是很昂贵的操作。目前有一些云 RDS 通过计算与存储分离、log is database 的理念来很大程度解决了写入扩大的问题，但在这之前，更为普遍的解决方案就是把一个集群拆分成 N 个集群，即分库分表（sharding）。为了规避热点问题，绝大多数采用的方法就是 hash 切分，也有极少的范围、或者基于 Mapping 的查询切分。
  • 既然做了分表，那数据的分发、路由就需要进行处理，自下而上分为三层，分别 DB 层、中间层、应用层。DB 层实现，简单来说就是把路由信息加入到某个 Metedata 节点，同时加上一些诸如读写分离、HA 整合成一个 DB 服务或者产品，但这种方案实现复杂度非常高，有的逐步演变成了一种新的数据库，更为常见的是在中间层实现，而中间层又根据偏向 DB 还是偏向应用分为 DB proxy 和 JDBC proxy。
  • DB proxy高度依赖网络组件，它需要诸如 LVS/F5 等 VIP 来实现流量的负载均衡，如果跨 IDC，还依赖诸如 DNS 进行IDC 分发。同时部分 DBproxy 对 Prepare 这类操作支持不友好，所以它的问题概括来说：
    • 链路过长，每层都会增加响应时间
    • 网络单点，并且往往是整个公司层面的单点
    • 部分产品对Prepare 应用不友好，需要绑定 connection 信息
  • JDBC proxy最大的问题是违背了 DB 透明的原则，它需要对不同的语言编写 Driver，概括来说：
    • 语言限制，总会遭到一批 RD 同学的吐槽 “世界上最好的语言竟然不支持！”
    • 接入繁琐
    • DB 不透明

ref

LeetCode - Algorithms - 106. Construct Binary Tree from Inorder and Postorder Traversal

这题跟105. Construct Binary Tree from Preorder and Inorder Traversal是一个系列，代码抄袭了Construct Binary Tree from Inorder and Postorder Traversal，二叉树的算法应该说不难理解。

From the post-order array, we know that last element is the root. We can find the root in in-order array. Then we can identify the left and right sub-trees of the root from in-order array. Using the length of left sub-tree, we can identify left and right sub-trees in post-order array. Recursively, we can build up the tree.

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
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode buildTree(int[] inorder, int[] postorder) {
    	int inStart=0;
    	int inEnd=inorder.length-1;
    	int postStart=0;
    	int postEnd=postorder.length-1;
        return buildTree(inorder,inStart,inEnd,postorder,postStart,postEnd);
    }

    public TreeNode buildTree(int[] inorder, int inStart, int inEnd, int[] postorder, int postStart, int postEnd) {
    	if (inStart>inEnd || postStart>postEnd)
    		return null;

    	int rtVal = postorder[postEnd];
    	TreeNode rt = new TreeNode(rtVal);

    	int k=0;
    	for(int i=0;i<=inEnd;i++) {
    		if (inorder[i]==rtVal) {
    			k=i;
    			break;
    		}
    	}

    	rt.left = buildTree(inorder,inStart,k-1,postorder, postStart, postStart+k-inStart-1);
    	rt.right = buildTree(inorder,k+1,inEnd,postorder,postStart+k-inStart,postEnd-1);

    	return rt;
    }    
}

Submission Detail

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

LeetCode - Algorithms - 105. Construct Binary Tree from Preorder and Inorder Traversal

二叉树自己能理解一二，不算难。自己也观察出来了从Preorder里知道根结点，再在Inorder里划分左右子树，如此不断递归二分。代码抄袭了这个的：
LeetCode – Construct Binary Tree from Preorder and Inorder Traversal (Java)

From the pre-order array, we know that first element is the root. We can find the root in in-order array. Then we can identify the left and right sub-trees of the root from in-order array. Using the length of left sub-tree, we can identify left and right sub-trees in pre-order array. Recursively, we can build up the tree.

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
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
    	int preStart=0;
    	int preEnd=preorder.length-1;
    	int inStart = 0;
    	int inEnd = inorder.length-1;
        return buildTree(preorder,preStart,preEnd,inorder,inStart,inEnd);
    }

    public TreeNode buildTree(int[] preorder, int preStart,int preEnd, int[] inorder, int inStart, int inEnd) {
    	if (preStart>preEnd || inStart>inEnd)
    	  return null;

    	int val = preorder[preStart];
    	TreeNode rt = new TreeNode(val);

    	int k=0;
    	for(int i=0;i<=inEnd;i++) {
    		if (inorder[i]==val) {
    			k=i;
    			break;
    		}
    	}

    	rt.left = buildTree(preorder, preStart+1, preStart+(k-inStart),inorder,inStart,k-1);
    	rt.right = buildTree(preorder, preStart+(k-inStart)+1, preEnd, inorder, k+1, inEnd);

    	return rt;
    }    
}

Submission Detail

  • 203 / 203 test cases passed.
  • Runtime: 13 ms
  • Your runtime beats 55.29 % of java submissions.

LeetCode - Algorithms - 518. Coin Change 2

变个样，又不知道怎么解决了，动态规划确实不是那么好理解。根据上一题的经验，还是从递归入手，先实现递归，再琢磨动态规划的解决方案，就有点循序渐进的味道。正如 What is an easy way to understand the coin change problem in dynamic programming? 的一个回答所言：

Instead of thinking about filling a matrix, think in terms of the recurrence relation. I have seen a lot of people who try to think dynamic programming problems in terms of filling a table/array. But this approach is problematic. For example, if the state representation has more than two dimensions, then this approach does not help much.

The essence of dynamic programming is the idea of a state space and a recurrence relation between states. Once you figure that out for any problem, implementation is straightforward.

参考了这些，虽然还是没有完全理解，程序在leetcode上通过了，程序其实就短短的几行，The code has a O(NC) pseudo-polynomial complexity where N is the amount and C the number of input coins。

Java

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public int change(int amount, int[] coins) {
    	int[] dp = new int[amount+1];
    	dp[0]=1;
    	for(int i=0;i<coins.length;i++) {
    		for(int j=coins[i];j<=amount;++j) {
    			dp[j]+=dp[j-coins[i]];
    		}    		
    	}
    	return dp[amount];        
    }
}

Submission Detail

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

JavaScript

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/**
 * @param {number} amount
 * @param {number[]} coins
 * @return {number}
 */
var change = function(amount, coins) {
	var dp = new Array(amount+1);
	for(var i=0;i<dp.length;i++)
		dp[i]=0;
	dp[0]=1;
	for(var i=0;i<amount;i++)
		for(var j=coins[i];j<=amount;++j)
			dp[j]+=dp[j-coins[i]];
	return dp[amount];    
};

Submission Detail

  • 27 / 27 test cases passed.
  • Runtime: 60 ms
  • Your runtime beats 89.86 % of javascript submissions.

LeetCode - Algorithms - 322. Coin Change

被这题卡住了，因为动态规划好像不好理解，看《算法图解》第九章，说动态规划都从一个网格开始，需要具备 Overlapping Sub-problems 与 Optimal Substructure。上网找线索与提示，最后发现先用递归方式实现，再看动态规划的方案就好理解些。主要参考了这几个：

原来 Change-making problem 是 Knapsack problem 的一类，背包问题还属于NP问题呢。

此题递归方式的实现是指数时间复杂度，跟动态规划的实现相比差距确实极其明显。递归方式的解法完全不可用，输入[1,2,5],100则报Time Limit Exceeded。

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
class Solution {
    public int coinChange(int[] coins, int amount) {
    	if (amount==0) return 0;

    	int n=-1;

    	int[] MC = new int[amount+1];
    	MC[0]=0;
    	for(int i=1;i<=amount;i++) {
    		MC[i] = Integer.MAX_VALUE;
    	}

    	for(int i=1;i<=amount;i++) {
    		for(int j=0;j<coins.length;j++) {
    			if (i>=coins[j]) {
    				int numCoins = MC[i-coins[j]];
    				if (numCoins!=Integer.MAX_VALUE && (numCoins+1<MC[i])) {
    					MC[i] = numCoins+1;
    				}
    			}
    		}
    	}
    	n=MC[amount];

    	if (n==Integer.MIN_VALUE || n==Integer.MAX_VALUE || n==0) n = -1;
    	return n;      
    }
}

Submission Detail

  • 182 / 182 test cases passed.
  • Runtime: 37 ms
  • Your runtime beats 28.19 % 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
/**
 * @param {number[]} coins
 * @param {number} amount
 * @return {number}
 */
var coinChange = function(coins, amount) {
	if (amount==0) return 0;

	var n=-1;
	var MC = new Array(amount+1);
	MC[0]=0;
	for(var i=1;i<=amount;i++)
		MC[i]=Number.MAX_VALUE;

	for(var i=1;i<=amount;i++) {
		for(var j=0;j<coins.length;j++) {
			if (i>=coins[j]) {
				var cc = MC[i-coins[j]];
				if (cc!=Number.MAX_VALUE && (cc+1<MC[i]))
					MC[i] = cc+1;
			}
		}
	}
	n = MC[amount];

	if (n==Number.MIN_VALUE || n==Number.MAX_VALUE || n==0) n = -1;

	return n;    
};

Submission Detail

  • 182 / 182 test cases passed.
  • Runtime: 80 ms
  • Your runtime beats 95.69 % of javascript submissions.

LeetCode - Algorithms - 224. Basic Calculator

Java

1

代码见前一篇

Submission Detail

  • 37 / 37 test cases passed.
  • Runtime: 143 ms
  • Your runtime beats 6.05 % of java submissions.

2 Shunting-yard algorithm

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

class Solution {
    public int calculate(String s) {
        return evalRPN(infixToPostfix(s.replaceAll(" ","")));      
    }
    
    private int evalRPN(List<String> exprlist){
        LinkedList<Integer> stack = new LinkedList<Integer>();

        for (String token : exprlist) {
            Integer tokenNum = null;
            try{
                tokenNum = Integer.parseInt(token);
            }catch(NumberFormatException e){}
            if(tokenNum != null){
                stack.push(Integer.parseInt(token+""));
            }else if(token.equals("-")){
                int secondOperand = stack.pop();
                int firstOperand = stack.pop();
                stack.push(firstOperand - secondOperand);
            }else if(token.equals("+")){
                int secondOperand = stack.pop();
                int firstOperand = stack.pop();
                stack.push(firstOperand + secondOperand);
            }else{
                return 0;
            }
        }
        int r = stack.pop();
        return r;
    }    
    
    private List<String> infixToPostfix(String infix) {
        List<String> list = new ArrayList<String>();
        final String ops = "-+";

        Stack<Integer> stack = new Stack<Integer>();

        StringTokenizer st = new StringTokenizer(infix,"[\\+\\-()]",true);
        while (st.hasMoreTokens()) {
            String token = st.nextToken();
            if (token.isEmpty())
                continue;
            char c = token.charAt(0);
            int idx = ops.indexOf(c);

            if (idx != -1) {
                if (stack.isEmpty())
                    stack.push(idx);

                else {
                    while (!stack.isEmpty()) {
                        int prec2 = stack.peek() / 2;
                        int prec1 = idx / 2;
                        if (prec2 > prec1 || prec2 == prec1)
                            list.add( ops.charAt(stack.pop()) + "" );
                        else break;
                    }
                    stack.push(idx);
                }
            }
            else if (c == '(') {
                stack.push(-2);
            }
            else if (c == ')') {
                while (stack.peek() != -2)
                    list.add( ops.charAt(stack.pop())+"" );
                stack.pop();
            }
            else {
                list.add( token );
            }
        }
        while (!stack.isEmpty())
            list.add( ops.charAt(stack.pop())+"" );
        return list;
    }    
}

Submission Detail

  • 37 / 37 test cases passed.
  • Runtime: 172 ms, faster than 7.80% of Java online submissions for Basic Calculator.
  • Memory Usage: 55.4 MB, less than 20.00% of Java online submissions for Basic Calculator.

Resources

LeetCode - Algorithms - 227. Basic Calculator II

这题是关于表达式解析的，2007年学习数据结构曾经实现过，思路是把中缀表达式转换为后缀表达式，再结合栈这种数据结构计算后缀表达式，就拿来执行下，结果LeetCode test case 1*2-3/4+5*6-7*8+9/10 报了个错 java.lang.ArithmeticException: / by zero，用StringTokenizer把操作符与操作数拆开，改了下原来的代码，最终运行通过了，但自己对其中的机理还是有点知其然而不知其所以然。

原来java7以后可以在switch的case语句里用String类型。

Strings in switch Statements

In the JDK 7 release, you can use a String object in the expression of a switch statement.

Basic Calculator这系列的题看来也是比较经典的，表达式解析好像是数据结构与编译原理的交叉点之一。

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
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
import java.util.StringTokenizer;

class Solution {
	public int postfixCalculator(List<String> postfixExpr) {
		Stack<Integer> stk = new Stack<Integer>();
		for (int i = 0; i < postfixExpr.size(); i++) {
			String s = postfixExpr.get(i);
			int a, b, x;
			switch (s) {
			case "*":
				if (!stk.isEmpty()) {
					a = stk.pop().intValue();
					b = stk.pop().intValue();
					x = a * b;
					stk.push(new Integer(x));
				}
				break;
			case "+":
				if (!stk.isEmpty()) {
					a = stk.pop().intValue();
					b = stk.pop().intValue();
					x = a + b;
					stk.push(new Integer(x));
				}
				break;
			case "-":
				if (!stk.isEmpty()) {
					a = stk.pop().intValue();
					b = stk.pop().intValue();
					x = b - a;
					stk.push(new Integer(x));
				}
				break;
			case "/":
				if (!stk.isEmpty()) {
					a = stk.pop().intValue();
					b = stk.pop().intValue();
					x = b / a;
					stk.push(new Integer(x));
				}
				break;
			default:
				stk.push(new Integer(s));
				break;
			}
		}
		int ret = 0;
		if (!stk.isEmpty())
			ret = stk.pop().intValue();
		return ret;
	}

	public List<String> infix2postfix(String infixExpr) {
		List<String> r = new ArrayList<String>();
		Stack<String> stk = new Stack<String>();
		List<String> list = new ArrayList<String>();
		StringTokenizer st = new StringTokenizer(infixExpr,"[\\+\\-\\*/()]",true);
	     while (st.hasMoreTokens()) {
	         list.add(st.nextToken());
	     }
		for (int i = 0; i < list.size(); i++) {
			String s = list.get(i);
			switch (s) {
			case "*":
			case "/":
				while (!stk.isEmpty() && (stk.peek().equals("*") || stk.peek().equals("/"))) {
					r.add( stk.pop() );
				}
				stk.push(s);
				break;
			case "+":
			case "-":
				while (!stk.isEmpty() && !stk.peek().equals("(")) {
					r.add( stk.pop() );
				}
				stk.push(s);
				break;
			case "(":
				stk.push(s);
				break;
			case ")":
				while (!stk.isEmpty() && !stk.peek().equals("(")) {
					r.add(stk.pop());
				}
				if (stk.peek().equals("("))
					stk.pop();
				break;
			default:
				r.add(s);
			}
		}

		while (stk != null && !stk.isEmpty()) {
			r.add( stk.pop() );
		}

		return r;
	}    

    public int calculate(String s) {
        return postfixCalculator(infix2postfix(s.replaceAll(" ", "")));
    }
}

Submission Detail

  • 109 / 109 test cases passed.
  • Runtime: 98 ms
  • Your runtime beats 5.79 % of java submissions.

LeetCode - Algorithms - 122. Best Time to Buy and Sell Stock II

自己已经意识到就是在输入数组里找递增子序列，但还是没想通。上网找点提示，参考了LeetCode – Best Time to Buy and Sell Stock II (Java)，看了人家的，恍然大悟，不难，但就是想不到。

这系列 Best Time to Buy and Sell Stock 的题看来也是比较经典的

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public int maxProfit(int[] prices) {
    	int profit = 0;
    	int diff = 0;
    	for(int i=1;i<prices.length;i++) {
    		diff = prices[i]-prices[i-1];
    			if (diff>0) {
    				profit+=diff;
    			}
    	}
        return profit;        
    }
}

Submission Detail

  • 201 / 201 test cases passed.
  • Your runtime beats 99.86 % of java submissions.

JavaScript

1
2
3
4
5
6
7
8
9
10
11
12
13
14
/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function(prices) {
	var profit = 0;
	var diff = 0;
	for(var i=1;i<prices.length;i++) {
		diff = prices[i]-prices[i-1];
		if (diff>0)
			profit+=diff;
	}
	return profit;    
};

Submission Detail

  • 201 / 201 test cases passed.
  • Your runtime beats 18.88 % of javascript submissions.