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.

LeetCode - Algorithms - 121. Best Time to Buy and Sell Stock

虽然难度标为Easy，但自己居然提交了好几次才通过了，而且是因为犯了逻辑错误。最后用个二重循环，倒也简单，但性能不好，不知道高效算法是如何做的？

Java

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

Submission Detail

  • 200 / 200 test cases passed.
  • Your runtime beats 4.30 % of java submissions.

在网上人家的一个O(n)时间复杂度的算法

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public int maxProfit(int[] prices) {
    	if (prices==null || prices.length<=1)
    		return 0;
        int r = 0;
        int minPrice = prices[0];
        for(int i=1;i<prices.length;i++) {
        	r = Math.max(r, prices[i]-minPrice);
        	minPrice = Math.min(minPrice, prices[i]);
        }
        return r;        
    }
}

Submission Detail

  • 200 / 200 test cases passed.
  • Your runtime beats 32.88 % of java submissions.

JavaScript

O(n2)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function(prices) {
	if (prices==null || prices.length==0)
		return 0;
	var r=0;
	var x = 0;
	for(var i=0;i<prices.length-1;i++) {
		for(var j=prices.length-1;j>i;j--) {
			x = prices[j]-prices[i];
			if (x>r)
				r = x;
		}
	}
	return r;    
};

Submission Detail

  • 200 / 200 test cases passed.
  • Your runtime beats 7.71 % of javascript submissions.

O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function(prices) {
	if (prices==null || prices.length<=1)
		return 0;
	var r=0;
	var minPrice = prices[0];
	for(var i=1;i<prices.length;i++) {
		r = Math.max(r,prices[i]-minPrice);
		minPrice = Math.min(minPrice,prices[i]);
	}
	return r;    
};

Submission Detail

  • 200 / 200 test cases passed.
  • Your runtime beats 84.89 % of javascript submissions.

英语学习相关网站

听力

Voice of America - Learn American English with VOA Learning English
https://learningenglish.voanews.com/

BBC Learning English | Pronunciation Tips
http://www.bbc.co.uk/worldservice/learningenglish/grammar/pron/

60-Second Science
https://www.scientificamerican.com/podcast/60-second-science/

Videos & Podcasts - Scientific American
https://www.scientificamerican.com/multimedia/

TED Radio Hour
https://www.npr.org/programs/ted-radio-hour

BBC - World Service - Home
https://www.bbc.co.uk/worldserviceradio

Learning English - 6 Minute English
http://www.bbc.co.uk/worldservice/learningenglish/general/sixminute/

词典

Dictionary by Merriam-Webster: America’s most-trusted online dictionary
https://www.merriam-webster.com/

Collins Dictionary
https://www.collinsdictionary.com/

Dictionary.com
https://www.dictionary.com/

报刊

https://medium.com/

https://www.theatlantic.com/

https://www.newyorker.com/

https://www.npr.org/

https://www.economist.com/

https://www.bloomberg.com/businessweek

https://www.bloomberg.com/canada

https://www.theguardian.com/observer

https://www.theguardian.com/international

http://www.bbc.com/

https://www.telegraph.co.uk/

其他

A Free Online Talking Dictionary of English Pronunciation
https://www.howjsay.com/

UsingEnglish.com was established in 2002 and is a general English language site specialising in English as a Second Language (ESL).
https://www.usingenglish.com/

Discovery Canada
https://www.discovery.ca/Home

English Language & Usage Stack Exchange is a question and answer site for linguists, etymologists, and serious English language enthusiasts.
https://english.stackexchange.com/

LeetCode - Algorithms - 119. Pascal's Triangle II

118. Pascal’s Triangle 的变脸题，用递归的方式实现了，还没想通如何用动态规划的方式实现。

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public List<Integer> getRow(int rowIndex) {
    	List<Integer> list = new ArrayList<Integer>();
    	if (rowIndex==0) {
    		list.add(1);
    		return list;
    	}
    	if (rowIndex==1) {
    		list.add(1);
    		list.add(1);
    		return list;
    	}    	
    	if (rowIndex>=2) {
    		List<Integer> row_pre = getRow(rowIndex-1);
    		list.add(1);
    		for(int i=1;i<rowIndex;i++) {
    			list.add(row_pre.get(i)+row_pre.get(i-1));
    		}
    		list.add(1);
    	}
    	return list;        
    }
}

Submission Detail

  • 34 / 34 test cases passed.
  • Your runtime beats 89.30 % 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
/**
 * @param {number} rowIndex
 * @return {number[]}
 */
var getRow = function(rowIndex) {
	if (rowIndex==0) {
		return [1];
	}
	if (rowIndex==1) {
		return [1,1];
	}
	var arr = [];
	if (rowIndex>=2) {
		arr.push(1);
		var preRow = getRow(rowIndex-1);
		for(var i=1;i<rowIndex;i++)
			arr.push(preRow[i]+preRow[i-1]);
		arr.push(1);
	}
	return arr;    
};

Submission Detail

  • 34 / 34 test cases passed.
  • Your runtime beats 93.58 % of javascript submissions.

LeetCode - Algorithms - 118. Pascal's Triangle

不难，不过写递归过程还是犯了些错误。 Pascal’s triangle 挺有名的，Binomial Coefficients好像是很重要的组合数学概念。

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
public List<List<Integer>> generate(int numRows) {
	List<List<Integer>> list = new ArrayList<List<Integer>>();

	if (numRows==1) {
    	List<Integer> list0 = new ArrayList<Integer>();
    	list0.add(1);
    	list.add(list0);
    	return list;    		
	}

	if (numRows==2) {
    	List<Integer> list0 = new ArrayList<Integer>();
    	list0.add(1);
    	list.add(list0);    		
    	List<Integer> list1 = new ArrayList<Integer>();
    	list1.add(1);
    	list1.add(1);
    	list.add(list1);
    	return list;    		
	}

	if (numRows>=3) {
    	List<List<Integer>> list_= generate(numRows-1);
    	List<Integer> list_pre = list_.get(numRows-2);
    	for(int i=0;i<list_.size();i++)
    		list.add(list_.get(i));
    	List<Integer> list_curr = new ArrayList<Integer>();
    	list_curr.add(1);
    	for(int i=1;i<numRows-1;i++) {
    		list_curr.add(list_pre.get(i)+list_pre.get(i-1));
    	}
    	list_curr.add(1);
    	list.add(list_curr);
	}
    return list;
}

Submission Detail

  • 15 / 15 test cases passed.
  • Your runtime beats 100.00 % 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
/**
 * @param {number} numRows
 * @return {number[][]}
 */
var generate = function(numRows) {
	  if (numRows==1) {
		  return [[1]];
	  }
	  if (numRows==2) {
		  return [[1],[1,1]];
	  }
	  var arr = [];
	  if (numRows>=3) {
		  var arr_ = generate(numRows-1);
		  var line_pre = arr_[numRows-2];
		  for(i=0;i<arr_.length;i++)
			  arr.push(arr_[i]);
		  var line_curr = [1];
		  for(i=1;i<numRows-1;i++) {
			  line_curr.push(line_pre[i]+line_pre[i-1]);
		  }
		  line_curr.push(1);
		  arr.push(line_curr);
	  }
	  return arr;    
};

Submission Detail

  • 15 / 15 test cases passed.
  • Your runtime beats 90.59 % of javascript submissions.