小明思考

Just a software engineer
posts - 124, comments - 36, trackbacks - 0, articles - 0
  BlogJava :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理

数据结构和算法

Scramble String

posted @ 2013-05-22 22:25 小明 阅读(6122) | 评论 (0)  编辑 |

Subsets

posted @ 2013-05-21 22:50 小明 阅读(2106) | 评论 (0)  编辑 |

格雷码

posted @ 2013-05-20 21:09 小明 阅读(2568) | 评论 (0)  编辑 |

交叉字符串

posted @ 2013-05-10 20:47 小明 阅读(3221) | 评论 (4)  编辑 |

三个数之和

     摘要: 给定一个由n个整数组成的数组S，是否存在S中的三个数a,b,c使得 a+b+c=0?找出所有的不重复的和为0的三元组。

注意：
1.三元组的整数按照升序排列 a2.给出的结果中不能含有相同的三元组  阅读全文

posted @ 2013-05-01 23:13 小明 阅读(1911) | 评论 (0)  编辑 |

子序列计数

     摘要: 给定两个字符串S和T，计算S的子序列为T的个数。

这里的字符串的子序列指的是删除字符串的几个字符（也可以不删）而得到的新的字符串，但是不能改变字符的相对位置。

比如“ACE”是“ABCDE”的子序列，但是“AEC”就不是。

如果S＝“rabbbit” T＝“rabit”，有3种不同的子序列为T的构成方法，那么结果应该返回3。  阅读全文

posted @ 2013-04-26 23:33 小明 阅读(2013) | 评论 (1)  编辑 |

设置二叉树的next节点

     摘要: 给定一颗二叉树：
class TreeLinkNode {
TreeLinkNode left;
TreeLinkNode right;
TreeLinkNode next;
}
要求把所有节点的next节点设置成它右边的节点，如果没有右节点，设置成空。初始状态，所有的next的指针均为null.

要求:你只能使用常数的空间。

比如：
1
/ \
2 3
/ \ \
4 5 7
应该输出：

1 -> NULL
/ \
2 -> 3 -> NULL
/ \ \
4-> 5 -> 7 -> NULL  阅读全文

posted @ 2013-04-26 11:23 小明 阅读(2112) | 评论 (0)  编辑 |

最佳的股票买卖时间III

     摘要: 假设你有一个数组包含了每天的股票价格，它的第i个元素就是第i天的股票价格。

设计一个算法寻找最大的收益。你可以最多进行两次交易。
注意：你不能同时进行多次交易，也就是说你买股票之前，必须卖掉手中股票。  阅读全文

posted @ 2013-04-25 22:22 小明 阅读(2056) | 评论 (0)  编辑 |

最佳的股票买卖时间II

     摘要: 假设你有一个数组包含了每天的股票价格，它的第i个元素就是第i天的股票价格。

设计一个算法寻找最大的收益。你可以进行任意多次交易。但是，你不能同时进行多次交易，也就是说你买股票之前，必须卖掉手中股票。  阅读全文

posted @ 2013-04-19 21:50 小明 阅读(1838) | 评论 (0)  编辑 |

最佳的股票买卖时间

     摘要: 假设你有一个数组包含了每天的股票价格，它的第i个元素就是第i天的股票价格。

你只能进行一次交易（一次买进和一次卖出），设计一个算法求出最大的收益。  阅读全文

posted @ 2013-04-19 15:03 小明 阅读(1570) | 评论 (0)  编辑 |

二叉树最大的路径和

     摘要: 给定一个二叉树，寻找最大的路径和.
路径可以从任意节点开始到任意节点结束。（也可以是单个节点）

比如：对于二叉树
1
/ \
2 3
和最大的路径是2->1->3，结果为6
/**
* Definition for binary tree
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/  阅读全文

posted @ 2013-04-18 21:31 小明 阅读(4000) | 评论 (0)  编辑 |

字梯游戏II

     摘要: 给定两个单词(一个开始，一个结束）和一个字典，找出所有的最短的从开始单词到结束单词的变换序列的序列（可能不止一个），并满足：

1.每次只能变换一个字母
2.所有的中间单词必须存在于字典中

比如：
输入：
start = "hit"
end = "cog"
dict = ["hot","dot","dog","lot","log"]

那么最短的变化序列有两个
["hit","hot","dot","dog","cog"],
["hit","hot","lot","log","cog"]。
注意：
1. 所有单词的长度都是相同的
2. 所有单词都只含有小写的字母。  阅读全文

posted @ 2013-04-18 17:32 小明 阅读(1359) | 评论 (0)  编辑 |

合并排序好的数组

     摘要: 给定两个排序好的数组A和B,把B合并到A并保持排序。

public class Solution {
public void merge(int A[], int m, int B[], int n) {
//write your code here }
}

注意：
假定A有足够的额外的容量储存B的内容，m和n分别为A和B的初始化元素的个数。要求算法复杂度在O(m+n)。  阅读全文

posted @ 2013-04-18 13:44 小明 阅读(1275) | 评论 (0)  编辑 |

字梯游戏

     摘要: 给定两个单词(一个开始，一个结束）和一个字典，找出最短的从开始单词到结束单词的变换序列的长度，并满足：

1.每次只能变换一个字母
2.所有的中间单词必须存在于字典中

比如：
输入：
start = "hit"
end = "cog"
dict = ["hot","dot","dog","lot","log"]

那么最短的变化序列是"hit" -> "hot" -> "dot" -> "dog" -> "cog"，所以返回长度是5。
注意：
1. 如果找不到这样的序列，返回0
2. 所有单词的长度都是相同的
3. 所有单词都只含有小写的字母。  阅读全文

posted @ 2013-04-18 12:46 小明 阅读(1504) | 评论 (0)  编辑 |

二叉树求和问题

     摘要: 给定一个二叉树，每个节点的值是一个数字（0-9），每个从根节点到叶节点均能组成一个数字。
比如如果从根节点到叶节点的路径是1-2-3，那么这代表了123这个数字。
求出所有这样从根节点到叶节点的数字之和。

比如，对于二叉树
1
/ \
2 3

一共有两条路径1->2和1->3，那么求和的结果就是12+13=25
/**
* Definition for binary tree
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public int sumNumbers(TreeNode root) {
//write c  阅读全文

posted @ 2013-04-16 11:37 小明 阅读(2534) | 评论 (1)  编辑 |

Full 数据结构和算法 Archive