本文介绍了包?Python、Java、Haskell{在内的一pd~程语言的深度学习库?br />
Python
- Theano是一U用于用数列来定义和评估数学表辄 Python 库。它可以?Python 中深度学习算法的~写更ؓ单。很多其他的库是?Theano 为基开发的?/span>
- Caffe是一U以表达清晰、高速和模块化ؓ理念建立h的深度学习框架。它是由伯克利视觉和学习中心QBVLCQ和|上C贡献者共同开发的。谷歌的 DeepDream 人工囑փ处理E序正是建立?Caffe 框架之上。这个框架是一?BSD 许可的带?Python 接口?C++库?/span>
- nolearn包含大量其他经|络库中的包装器和抽象（wrappers and abstractionsQ，其中最值得注意的是 LasagneQ其中也包含一些机器学习的实用模块?/span>
- Genism是一个部|在 Python ~程语言中的深度学习工具包，用于通过高效的算法处理大型文本集?/span>
- Chainerq接深度学习中的法与实玎ͼ它强劌Ӏ灵z而敏锐，是一U用于深度学习的灉|的框架?/span>
- deepnet是一U基?GPU 的深度学习算法的 Python 实现Q比如：前馈经|络、受限玻兹曼机、深度信늽l、自~码器、深度玻兹曼机和卷U神l网l?/span>
- Hebel是一个在 Python 中用于带有神l网l的深度学习的库Q它通过 PyCUDA 使用带有 CUDA ?GPU 加速。它可实现大多数目前最重要的神l网l模型，提供了多U不同的Ȁzd数和训练方式Q如动量QNesterov 动量Q退出（dropoutQ和 前期停止Qearly stoppingQ?/span>
- CXXNET是一U快速，明的分布式深度学习框Ӟ它以 MShadow 为基。它是轻量可扩展的 C++/CUDA 经|络工具包，同时拥有友好?Python/Matlab 界面Q可供机器学习的训练和预用?/span>
- DeepPy是一U徏立在 Mumpy 之上?Python 化的深度学习框架?/span>
- DeepLearning是一个用 C++?Python 开发的深度学习库?/span>
C++
Java
- N-Dimensional Arrays for Java (ND4J)是一Uؓ JVM 设计的科学计库。它们被应用在生产环境中Q这意味着路径被设计成可以最的 RAM 内存需求来快速运行?/span>
- Deeplearning4j是第一个ؓ Java ?Scala ~写的消费开元分布式深度学习库。它被设计成在商业环境中使用Q而非研究工具?/span>
- Encog是一U先q的机器学习框架Q支持支持向量机QSupport Vector MachinesQ，人工经|络QArtificial Neural NetworksQ，基因~程QGenetic ProgrammingQ，贝叶斯网l（Bayesian NetworksQ，隐马科夫模型（Hidden Markov ModelsQ和 遗传法QGenetic AlgorithmsQ?/span>
Lua
- Torch是一U科学计框Ӟ可支持多U计机学习法?/span>
Haskell
- DNNGraph是一个用 Haskell ~写的深度神l网l生?DSL?/span>
.NET
- Accord.NET是一U?NET 机器学习框架Q包含声韛_囑փ处理库，它完全由 C# ~写。它是一Uؓ开发生产的计机视觉、计机听觉、信号处理和l计应用而设计的完整框架?/span>
R
]]>
一、ؓ什么要出国
其实Q之前从来没有考虑q要出国Q更没有惌能直接出国工作?/span>
二、如何出?/span>
对于普通h来说Q出国大致有三条路?/span>
W一条\是申请去国外留学Q?/span>
W二条\是先q入跨国公司的中国分公司工作一D|_
W三条\是直接参加外国公司的面试Q通过之后直接d外工作?/span>
鉴于W三条\非常难走Qؓ了保证成功，
三、申请学?/span>
甌学校从准备到最l完成，我大概用了一q时间?/span>
有了p成W之后Q就是撰写申h书。这斚w我完全没有经验，
最后，我申请了国和加拿大的十五所学校的计机专业的研I生Q?/span>
四、Facebook的面?/span>
参加Facebook的面试也完全是无意的Q?/span>
不过Q这ơ面试还是很有收莗第一ơ出国，
五、Google的面?/span>
参加h的面试可以说完全是老婆的怂恿?/span>
和HR通电话不久，我进行了W一ơ电话面试?/span>
于是Q我又被要求q行W二ơ电面。期间由于面试官临时有事爽约Q?/span>
虽然可以onsite面试了，
也许是放杄原因Q我前一天晚上睡得很好，W二天我_非常好?/span>
不过h毕竟是谷歌，面试W一轮一上来q了我一个下马威?/span>
但是Q不知道Z么，从第二轮开始，p来越利Q?/span>
四轮q后Q我l束了第一ơonsite面试。但是，三天之后Q?/span>
记得是一个礼拜之后的C拜五中午，
然而，让我没有惛_的是Q接下来的team match却异常艰难，
在我快要放弃的时候，拿到了美国一个公司的offerQ?/span>
回顾两年来的努力Q终于要实现自己的梦想了Q感慨万千?/span>
最后要感谢老婆一直以来的支持和鼓励，你一直是我前q的动力Q?/span>
]]>
有了q个x好办了Q第一遍从左到双数lleftMostHeightQ第二遍从右到左计算rightMostHeightQ在W二遍的同时可以计出i位置的结果了Q而且q不需要开I间来存放rightMostHeight数组?/div>
]]>[Leetcode] Permutation Sequence http://www.aygfsteel.com/menglee/archive/2014/01/07/408642.htmlMeng Lee Meng Lee Tue, 07 Jan 2014 08:06:00 GMT http://www.aygfsteel.com/menglee/archive/2014/01/07/408642.html http://www.aygfsteel.com/menglee/comments/408642.html http://www.aygfsteel.com/menglee/archive/2014/01/07/408642.html#Feedback 0 http://www.aygfsteel.com/menglee/comments/commentRss/408642.html http://www.aygfsteel.com/menglee/services/trackbacks/408642.html The set [1,2,3,…,n] contains a total of n! unique permutations.
旉复杂度是O(n)Q只扫了两遍?br />
1 public class TrappingRainWater {
2 public int trap(int A[], int n) {
3 if (n <= 2)
4 return 0;
5
6 int[] lmh = new int[n];
7 lmh[0] = 0;
8 int maxh = A[0];
9 for (int i = 1; i < n; ++i) {
10 lmh[i] = maxh;
11 if (maxh < A[i])
12 maxh = A[i];
13 }
14 int trapped = 0;
15 maxh = A[n - 1];
16 for (int i = n - 2; i > 0; --i) {
17 int left = lmh[i];
18 int right = maxh;
19 int container = Math.min(left, right);
20 if (container > A[i]) {
21 trapped += container - A[i];
22 }
23 if (maxh < A[i])
24 maxh = A[i];
25 }
26 return trapped;
27 }
28 }
2 public int trap(int A[], int n) {
3 if (n <= 2)
4 return 0;
5
6 int[] lmh = new int[n];
7 lmh[0] = 0;
8 int maxh = A[0];
9 for (int i = 1; i < n; ++i) {
10 lmh[i] = maxh;
11 if (maxh < A[i])
12 maxh = A[i];
13 }
14 int trapped = 0;
15 maxh = A[n - 1];
16 for (int i = n - 2; i > 0; --i) {
17 int left = lmh[i];
18 int right = maxh;
19 int container = Math.min(left, right);
20 if (container > A[i]) {
21 trapped += container - A[i];
22 }
23 if (maxh < A[i])
24 maxh = A[i];
25 }
26 return trapped;
27 }
28 }
]]>
By listing and labeling all of the permutations in order,
We get the following sequence (ie, for n = 3):
"123"
"132"
"213"
"231"
"312"
"321"
Given n and k, return the kth permutation sequence.
Note: Given n will be between 1 and 9 inclusive.
]]>[Leetcode] Scramble String http://www.aygfsteel.com/menglee/archive/2014/01/05/408521.htmlMeng Lee Meng Lee Sun, 05 Jan 2014 04:33:00 GMT http://www.aygfsteel.com/menglee/archive/2014/01/05/408521.html http://www.aygfsteel.com/menglee/comments/408521.html http://www.aygfsteel.com/menglee/archive/2014/01/05/408521.html#Feedback 0 http://www.aygfsteel.com/menglee/comments/commentRss/408521.html http://www.aygfsteel.com/menglee/services/trackbacks/408521.html Given a string s1, we may represent it as a binary tree by partitioning it to two non-empty substrings recursively.
q道题其实有很强的规律可循。首先，n个元素的排列L是n!。在下面的分析中Q让k的范围是0 <= k < n!。（题目代码实际上是1<=k<=n!)
可以看到一个规律，是qnQ个排列中，W一位的元素L(n-1)!一l出现的Q也p如果p = k / (n-1)!Q那么排列的最开始一个元素一定是arr[p]?/div>
]]>[Leetcode] Lowest Common Ancestor of a Binary Search Tree (BST) && Lowest Common Ancestor of Binary Tree http://www.aygfsteel.com/menglee/archive/2014/01/06/408544.htmlMeng Lee Meng Lee Mon, 06 Jan 2014 01:32:00 GMT http://www.aygfsteel.com/menglee/archive/2014/01/06/408544.html http://www.aygfsteel.com/menglee/comments/408544.html http://www.aygfsteel.com/menglee/archive/2014/01/06/408544.html#Feedback 0 http://www.aygfsteel.com/menglee/comments/commentRss/408544.html http://www.aygfsteel.com/menglee/services/trackbacks/408544.html
Given a binary tree, find the lowest common ancestor of two given nodes in the tree.
可以看到一个规律，是qnQ个排列中，W一位的元素L(n-1)!一l出现的Q也p如果p = k / (n-1)!Q那么排列的最开始一个元素一定是arr[p]?/div>
q个规律可以cL下去Q在剩余的n-1个元素中逐渐挑选出W二个，W三个，...Q到Wn个元素。程序就l束?/div>
1 /**
2 * The set [1,2,3,…,n] contains a total of n! unique permutations.
3 *
4 * By listing and labeling all of the permutations in order, We get the
5 * following sequence (ie, for n = 3):
6 *
7 * "123" "132" "213" "231" "312" "321" Given n and k, return the kth permutation
8 * sequence.
9 *
10 * Note: Given n will be between 1 and 9 inclusive.
11 *
12 */
13
14 public class PermutationSequence {
15 public String getPermutation(int n, int k) {
16 char[] arr = new char[n];
17 int pro = 1;
18 for (int i = 0; i < n; ++i) {
19 arr[i] = (char) ('1' + i);
20 pro *= (i + 1);
21 }
22 k = k - 1;
23 k %= pro;
24 pro /= n;
25 for (int i = 0; i < n - 1; ++i) {
26 int selectI = k / pro;
27 k = k % pro;
28 pro /= (n - i - 1);
29 int temp = arr[selectI + i];
30 for (int j = selectI; j > 0; --j) {
31 arr[i + j] = arr[i + j - 1];
32 }
33 arr[i] = (char) temp;
34 }
35 return String.valueOf(arr);
36 }
37 }
38
2 * The set [1,2,3,…,n] contains a total of n! unique permutations.
3 *
4 * By listing and labeling all of the permutations in order, We get the
5 * following sequence (ie, for n = 3):
6 *
7 * "123" "132" "213" "231" "312" "321" Given n and k, return the kth permutation
8 * sequence.
9 *
10 * Note: Given n will be between 1 and 9 inclusive.
11 *
12 */
13
14 public class PermutationSequence {
15 public String getPermutation(int n, int k) {
16 char[] arr = new char[n];
17 int pro = 1;
18 for (int i = 0; i < n; ++i) {
19 arr[i] = (char) ('1' + i);
20 pro *= (i + 1);
21 }
22 k = k - 1;
23 k %= pro;
24 pro /= n;
25 for (int i = 0; i < n - 1; ++i) {
26 int selectI = k / pro;
27 k = k % pro;
28 pro /= (n - i - 1);
29 int temp = arr[selectI + i];
30 for (int j = selectI; j > 0; --j) {
31 arr[i + j] = arr[i + j - 1];
32 }
33 arr[i] = (char) temp;
34 }
35 return String.valueOf(arr);
36 }
37 }
38
]]>
Lowest Common Ancestor of a Binary Search Tree (BST)
Given a binary search tree (BST), find the lowest common ancestor of two given nodes in the BST.
_______6______
/ \
___2__ ___8__
/ \ / \
0 _4 7 9
/ \
3 5
Using the above tree as an example, the lowest common ancestor (LCA) of nodes 2 and 8 is 6.
But how about LCA of nodes 2 and 4? Should it be 6 or 2?
According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between
two nodes v and w as the lowest node in T that has both v and w as descendants (where we allow a
node to be a descendant of itself).” Since a node can be a descendant of itself, the LCA of 2 and
4 should be 2, according to this definition.
Hint:
A top-down walk from the root of the tree is enough.
1 public class LowestCommonAncestorOfaBinarySearchTree {
2 public TreeNode LCA(TreeNode root, TreeNode p, TreeNode q) {
3 if (root == null || p == null || q == null)
4 return null;
5 if (Math.max(p.val, q.val) < root.val)
6 return LCA(root.left, p, q);
7 if (Math.min(p.val, q.val) > root.val)
8 return LCA(root.right, p, q);
9 return root;
10 }
11 }
2 public TreeNode LCA(TreeNode root, TreeNode p, TreeNode q) {
3 if (root == null || p == null || q == null)
4 return null;
5 if (Math.max(p.val, q.val) < root.val)
6 return LCA(root.left, p, q);
7 if (Math.min(p.val, q.val) > root.val)
8 return LCA(root.right, p, q);
9 return root;
10 }
11 }
Given a binary tree, find the lowest common ancestor of two given nodes in the tree.
_______3______
/ \
___5__ ___1__
/ \ / \
6 _2 0 8
/ \
7 4
If you are not so sure about the definition of lowest common ancestor (LCA), please refer to my previous
post: Lowest Common Ancestor of a Binary Search Tree (BST) or the definition of LCA here. Using the tree
above as an example, the LCA of nodes 5 and 1 is 3. Please note that LCA for nodes 5 and 4 is 5.
Hint:
Top-down or bottom-up? Consider both approaches and see which one is more efficient.
1 public class LowestCommonAncestorOfBinaryTree {
2 public TreeNode LCA(TreeNode root, TreeNode p, TreeNode q) {
3 if (root == null)
4 return null;
5 if (root == p || root == q)
6 return root;
7 TreeNode left = LCA(root.left, p, q);
8 TreeNode right = LCA(root.right, p, q);
9 if (left != null && right != null)
10 return root;
11 return left != null ? left : right;
12 }
13 }
2 public TreeNode LCA(TreeNode root, TreeNode p, TreeNode q) {
3 if (root == null)
4 return null;
5 if (root == p || root == q)
6 return root;
7 TreeNode left = LCA(root.left, p, q);
8 TreeNode right = LCA(root.right, p, q);
9 if (left != null && right != null)
10 return root;
11 return left != null ? left : right;
12 }
13 }
]]>
Below is one possible representation of s1 = "great":
great
/ \
gr eat
/ \ / \
g r e at
/ \
a t
To scramble the string, we may choose any non-leaf node and swap its two children.
For example, if we choose the node "gr" and swap its two children, it produces a scrambled string "rgeat".
rgeat
/ \
rg eat
/ \ / \
r g e at
/ \
a t
We say that "rgeat" is a scrambled string of "great".
Similarly, if we continue to swap the children of nodes "eat" and "at", it produces a scrambled string "rgtae".
rgtae
/ \
rg tae
/ \ / \
r g ta e
/ \
t a
We say that "rgtae" is a scrambled string of "great".
Given two strings s1 and s2 of the same length, determine if s2 is a scrambled string of s1.
1 public class ScrambleString {
2 public boolean isScramble(String s1, String s2) {
3 if (s1.length() != s2.length())
4 return false;
5 if (s1.equals(s2))
6 return true;
7
8 int[] A = new int[26];
9 for (int i = 0; i < s1.length(); i++) {
10 ++A[s1.charAt(i) - 'a'];
11 }
12
13 for (int j = 0; j < s2.length(); j++) {
14 --A[s2.charAt(j) - 'a'];
15 }
16
17 for (int k = 0; k < 26; k++) {
18 if (A[k] != 0)
19 return false;
20 }
21
22 for (int i = 1; i < s1.length(); i++) {
23 boolean result = isScramble(s1.substring(0, i), s2.substring(0, i))
24 && isScramble(s1.substring(i), s2.substring(i));
25 result = result
26 || (isScramble(s1.substring(0, i),
27 s2.substring(s2.length() - i, s2.length())) && isScramble(
28 s1.substring(i), s2.substring(0, s2.length() - i)));
29 if (result)
30 return true;
31 }
32 return false;
33 }
34 }
2 public boolean isScramble(String s1, String s2) {
3 if (s1.length() != s2.length())
4 return false;
5 if (s1.equals(s2))
6 return true;
7
8 int[] A = new int[26];
9 for (int i = 0; i < s1.length(); i++) {
10 ++A[s1.charAt(i) - 'a'];
11 }
12
13 for (int j = 0; j < s2.length(); j++) {
14 --A[s2.charAt(j) - 'a'];
15 }
16
17 for (int k = 0; k < 26; k++) {
18 if (A[k] != 0)
19 return false;
20 }
21
22 for (int i = 1; i < s1.length(); i++) {
23 boolean result = isScramble(s1.substring(0, i), s2.substring(0, i))
24 && isScramble(s1.substring(i), s2.substring(i));
25 result = result
26 || (isScramble(s1.substring(0, i),
27 s2.substring(s2.length() - i, s2.length())) && isScramble(
28 s1.substring(i), s2.substring(0, s2.length() - i)));
29 if (result)
30 return true;
31 }
32 return false;
33 }
34 }
]]>
Above is a histogram where width of each bar is 1, given height = [2,1,5,6,2,3].
The largest rectangle is shown in the shaded area, which has area = 10 unit.
For example,
Given height = [2,1,5,6,2,3],
return 10.
本题需要用栈l护一个高度单调递增的序列下标，如果遇到一个元素比当前栈顶元素高度，那么出栈Qƈ计算当前最大面U。如果栈为空Q需要特D考虑?br />
本题需要用栈l护一个高度单调递增的序列下标，如果遇到一个元素比当前栈顶元素高度，那么出栈Qƈ计算当前最大面U。如果栈为空Q需要特D考虑?br />
1 public class LargestRectangleinHistogram {
2 public int largestRectangleArea(int[] height) {
3 Stack<Integer> stack = new Stack<Integer>();
4 int i = 0;
5 int maxArea = 0;
6 int[] h = new int[height.length + 1];
7 h = Arrays.copyOf(height, height.length + 1);
8 while (i < h.length) {
9 if (stack.isEmpty() || h[stack.peek()] <= h[i]) {
10 stack.push(i++);
11 } else {
12 int t = stack.pop();
13 maxArea = Math.max(maxArea, h[t] * (stack.isEmpty() ? i : i - stack.peek() - 1));
14 }
15 }
16 return maxArea;
17 }
18 }
2 public int largestRectangleArea(int[] height) {
3 Stack<Integer> stack = new Stack<Integer>();
4 int i = 0;
5 int maxArea = 0;
6 int[] h = new int[height.length + 1];
7 h = Arrays.copyOf(height, height.length + 1);
8 while (i < h.length) {
9 if (stack.isEmpty() || h[stack.peek()] <= h[i]) {
10 stack.push(i++);
11 } else {
12 int t = stack.pop();
13 maxArea = Math.max(maxArea, h[t] * (stack.isEmpty() ? i : i - stack.peek() - 1));
14 }
15 }
16 return maxArea;
17 }
18 }
]]>
For example:
Given binary tree {1,#,2,3},
1
\
2
/
3
return [1,3,2].
Note: Recursive solution is trivial, could you do it iteratively?
切记p节点初始时指向root.left。代码如下：
切记p节点初始时指向root.left。代码如下：
1 public class BinaryTreeInorderTraversal {
2 public ArrayList<Integer> inorderTraversal(TreeNode root) {
3 ArrayList<Integer> inOrder = new ArrayList<Integer>();
4 if (root == null)
5 return inOrder;
6 Stack<TreeNode> s = new Stack<TreeNode>();
7 s.add(root);
8 TreeNode p = root.left;
9 while (!s.empty()) {
10 while (p != null) {
11 s.add(p);
12 p = p.left;
13 }
14 TreeNode n = s.pop();
15 inOrder.add(n.val);
16 p = n.right;
17 if (p != null) {
18 s.add(p);
19 p = p.left;
20 }
21 }
22 return inOrder;
23 }
24 }
2 public ArrayList<Integer> inorderTraversal(TreeNode root) {
3 ArrayList<Integer> inOrder = new ArrayList<Integer>();
4 if (root == null)
5 return inOrder;
6 Stack<TreeNode> s = new Stack<TreeNode>();
7 s.add(root);
8 TreeNode p = root.left;
9 while (!s.empty()) {
10 while (p != null) {
11 s.add(p);
12 p = p.left;
13 }
14 TreeNode n = s.pop();
15 inOrder.add(n.val);
16 p = n.right;
17 if (p != null) {
18 s.add(p);
19 p = p.left;
20 }
21 }
22 return inOrder;
23 }
24 }
]]>
Note:
Elements in a subset must be in non-descending order.
The solution set must not contain duplicate subsets.
For example,
If S = [1,2,2], a solution is:
[
[2],
[1],
[1,2,2],
[2,2],
[1,2],
[]
]
׃元素中可能存在重复，因此较之于Subset的实玎ͼ需要加一些判断。如果碰C重复元素Q只需要在上一ơP代新增的子集的基上再q行q代卛_。实C码如下：
׃元素中可能存在重复，因此较之于Subset的实玎ͼ需要加一些判断。如果碰C重复元素Q只需要在上一ơP代新增的子集的基上再q行q代卛_。实C码如下：
1 public class SubsetsII {
2 public ArrayList<ArrayList<Integer>> subsetsWithDup(int[] num) {
3 ArrayList<ArrayList<Integer>> ret = new ArrayList<ArrayList<Integer>>();
4 ArrayList<ArrayList<Integer>> lastLevel = null;
5 ret.add(new ArrayList<Integer>());
6 Arrays.sort(num);
7 for (int i = 0; i < num.length; i++) {
8 ArrayList<ArrayList<Integer>> tmp = new ArrayList<ArrayList<Integer>>();
9 ArrayList<ArrayList<Integer>> prev = i == 0 || num[i] != num[i - 1] ? ret : lastLevel;
10 for (ArrayList<Integer> s : prev) {
11 ArrayList<Integer> newSet = new ArrayList<Integer>(s);
12 newSet.add(num[i]);
13 tmp.add(newSet);
14 }
15 ret.addAll(tmp);
16 lastLevel = tmp;
17 }
18 return ret;
19 }
20 }
2 public ArrayList<ArrayList<Integer>> subsetsWithDup(int[] num) {
3 ArrayList<ArrayList<Integer>> ret = new ArrayList<ArrayList<Integer>>();
4 ArrayList<ArrayList<Integer>> lastLevel = null;
5 ret.add(new ArrayList<Integer>());
6 Arrays.sort(num);
7 for (int i = 0; i < num.length; i++) {
8 ArrayList<ArrayList<Integer>> tmp = new ArrayList<ArrayList<Integer>>();
9 ArrayList<ArrayList<Integer>> prev = i == 0 || num[i] != num[i - 1] ? ret : lastLevel;
10 for (ArrayList<Integer> s : prev) {
11 ArrayList<Integer> newSet = new ArrayList<Integer>(s);
12 newSet.add(num[i]);
13 tmp.add(newSet);
14 }
15 ret.addAll(tmp);
16 lastLevel = tmp;
17 }
18 return ret;
19 }
20 }
]]>
Only one letter can be changed at a time
Each intermediate word must exist in the dictionary
For example,
Given:
start = "hit"
end = "cog"
dict = ["hot","dot","dog","lot","log"]
Return
[
["hit","hot","dot","dog","cog"],
["hit","hot","lot","log","cog"]
]
Note:
All words have the same length.
All words contain only lowercase alphabetic characters.
q个题目应该是leetcode上比较难的题目了。刚开始我采用了和Word Ladder怼的做法，只是用ArrayList记录了当前变换\径，在小数据的情况下可以AcceptQ但是大数据时。究其原因，是由于ؓ每个当前节点记录变换路径的时候，需要复制之前的ArrayListQ这个时间开销较大?br />其实Q我们可以采用一个Map<String, HashSet<String>>l构Q记录字典单词的每一个前驱，q样我们可以从end反向遍历Q构造出转换路径?br />同时Q我利用了两个ArrayListQ交替记录上一层和下一层的节点Q如果下一层节点ؓI，则不存在路径Q立卌回。如果下一层中出现了endQ证明找C所有的最短\径，停止搜烦开始构造\径。实C码如下：
q个题目应该是leetcode上比较难的题目了。刚开始我采用了和Word Ladder怼的做法，只是用ArrayList记录了当前变换\径，在小数据的情况下可以AcceptQ但是大数据时。究其原因，是由于ؓ每个当前节点记录变换路径的时候，需要复制之前的ArrayListQ这个时间开销较大?br />其实Q我们可以采用一个Map<String, HashSet<String>>l构Q记录字典单词的每一个前驱，q样我们可以从end反向遍历Q构造出转换路径?br />同时Q我利用了两个ArrayListQ交替记录上一层和下一层的节点Q如果下一层节点ؓI，则不存在路径Q立卌回。如果下一层中出现了endQ证明找C所有的最短\径，停止搜烦开始构造\径。实C码如下：
1 public class WordLadderII {
2 private void GeneratePath(Map<String, ArrayList<String>> prevMap,
3 ArrayList<String> path, String word,
4 ArrayList<ArrayList<String>> ret) {
5 if (prevMap.get(word).size() == 0) {
6 path.add(0, word);
7 ArrayList<String> curPath = new ArrayList<String>(path);
8 ret.add(curPath);
9 path.remove(0);
10 return;
11 }
12
13 path.add(0, word);
14 for (String pt : prevMap.get(word)) {
15 GeneratePath(prevMap, path, pt, ret);
16 }
17 path.remove(0);
18 }
19
20 public ArrayList<ArrayList<String>> findLadders(String start, String end,
21 HashSet<String> dict) {
22 ArrayList<ArrayList<String>> ret = new ArrayList<ArrayList<String>>();
23 Map<String, ArrayList<String>> prevMap = new HashMap<String, ArrayList<String>>();
24 dict.add(start);
25 dict.add(end);
26 for (String d : dict) {
27 prevMap.put(d, new ArrayList<String>());
28 }
29 ArrayList<HashSet<String>> candidates = new ArrayList<HashSet<String>>();
30 candidates.add(new HashSet<String>());
31 candidates.add(new HashSet<String>());
32 int current = 0;
33 int previous = 1;
34 candidates.get(current).add(start);
35 while (true) {
36 current = current == 0 ? 1 : 0;
37 previous = previous == 0 ? 1 : 0;
38 for (String d : candidates.get(previous)) {
39 dict.remove(d);
40 }
41 candidates.get(current).clear();
42 for (String wd : candidates.get(previous)) {
43 for (int pos = 0; pos < wd.length(); ++pos) {
44 StringBuffer word = new StringBuffer(wd);
45 for (int i = 'a'; i <= 'z'; ++i) {
46 if (wd.charAt(pos) == i) {
47 continue;
48 }
49
50 word.setCharAt(pos, (char) i);
51
52 if (dict.contains(word.toString())) {
53 prevMap.get(word.toString()).add(wd);
54 candidates.get(current).add(word.toString());
55 }
56 }
57 }
58 }
59
60 if (candidates.get(current).size() == 0) {
61 return ret;
62 }
63 if (candidates.get(current).contains(end)) {
64 break;
65 }
66 }
67
68 ArrayList<String> path = new ArrayList<String>();
69 GeneratePath(prevMap, path, end, ret);
70
71 return ret;
72 }
73 }
2 private void GeneratePath(Map<String, ArrayList<String>> prevMap,
3 ArrayList<String> path, String word,
4 ArrayList<ArrayList<String>> ret) {
5 if (prevMap.get(word).size() == 0) {
6 path.add(0, word);
7 ArrayList<String> curPath = new ArrayList<String>(path);
8 ret.add(curPath);
9 path.remove(0);
10 return;
11 }
12
13 path.add(0, word);
14 for (String pt : prevMap.get(word)) {
15 GeneratePath(prevMap, path, pt, ret);
16 }
17 path.remove(0);
18 }
19
20 public ArrayList<ArrayList<String>> findLadders(String start, String end,
21 HashSet<String> dict) {
22 ArrayList<ArrayList<String>> ret = new ArrayList<ArrayList<String>>();
23 Map<String, ArrayList<String>> prevMap = new HashMap<String, ArrayList<String>>();
24 dict.add(start);
25 dict.add(end);
26 for (String d : dict) {
27 prevMap.put(d, new ArrayList<String>());
28 }
29 ArrayList<HashSet<String>> candidates = new ArrayList<HashSet<String>>();
30 candidates.add(new HashSet<String>());
31 candidates.add(new HashSet<String>());
32 int current = 0;
33 int previous = 1;
34 candidates.get(current).add(start);
35 while (true) {
36 current = current == 0 ? 1 : 0;
37 previous = previous == 0 ? 1 : 0;
38 for (String d : candidates.get(previous)) {
39 dict.remove(d);
40 }
41 candidates.get(current).clear();
42 for (String wd : candidates.get(previous)) {
43 for (int pos = 0; pos < wd.length(); ++pos) {
44 StringBuffer word = new StringBuffer(wd);
45 for (int i = 'a'; i <= 'z'; ++i) {
46 if (wd.charAt(pos) == i) {
47 continue;
48 }
49
50 word.setCharAt(pos, (char) i);
51
52 if (dict.contains(word.toString())) {
53 prevMap.get(word.toString()).add(wd);
54 candidates.get(current).add(word.toString());
55 }
56 }
57 }
58 }
59
60 if (candidates.get(current).size() == 0) {
61 return ret;
62 }
63 if (candidates.get(current).contains(end)) {
64 break;
65 }
66 }
67
68 ArrayList<String> path = new ArrayList<String>();
69 GeneratePath(prevMap, path, end, ret);
70
71 return ret;
72 }
73 }
]]>