Archive for October 6th, 2013
[leetcode] sqrt(int) | 求一个正整数的平方根
Posted on: October 6, 2013
这题真是做了挺久，尼玛还是二分法不熟悉。。怎么终止还是想了很久。
二分法永远是(p, mid – 1)和(mid + 1, q)， 不要想什么(p, mid)之类的，那样范围永远没法缩小，最后肯定死循环。
二分的模板终止条件永远是p > q，不要去想p == q + 1, p == q这些，这些都可以经过下一次recurse再分解成p > q的形式。
最后p > q说明没找到，比如foo(5, 4)，即那么x应该是在4，5之间，这个时候p的值是5，q的值是4，说明小的那个是q,大的那个是p。所以二分法找x应该在的index那题返回p（返回较大的），这题应该返回q（返回较小的）。别去考虑p==q之类的的情况，那种再走一遍就会又形成p > q。若是找到了，更会在mid==x这个catch里直接接住，不用在终止条件处考虑。
还有一个要注意的地方：代码中间有mid * mid这种式子，这个就很可能overflow，所以要在出现这个之前接住overflow的情况。因为整数的乘法可能导致溢出，而溢出的监测和整数加法直接判断是否小于0是不同的（整数加法溢出时和会<0因为第一位bit被从0顶到1了），因为整数的乘法有可能多次溢出，当奇书次溢出时是负数，当偶数次溢出时时整数。网上看的巧妙的解决办法是干脆不要乘，而是用x/mid和mid比较。
public int sqrt(int x) {
return sqrt(x, 1, x);
}
private int sqrt(int x, int p, int q) {
if (p > q)
return q;
int mid = (p + q) / 2;
if (x / mid == mid)
return mid;
else if (x / mid < mid )
return sqrt(x, p, mid - 1);
else
return sqrt(x, mid + 1, q);
}
For example, given s = "catsanddog", dict = ["cat", "cats", "and", "sand", "dog"], the solution is ["cats and dog", "cat sand dog"]
这题是cache里面存数组: Map<Integer, List<String>> cache，和上题思路一样，不过边界条件不好想：
- 找不到的时候是返回空list还是null?
- 找到结尾正好成功了(i == string.len)的时候，返回空还是null?
这两种情况必须区分。因为要在每个list entry里生成新的substring，所以还是找不到的时候返回空list比较好（空的正好不用进loop了）；而找到头的时候，刚好check null，然后把当前词尾返回，catch了最后一个词不用加” “的情况。
public ArrayList<String> wordBreak(String s, Set<String> dict) {
if (s == null || s.length() == 0)
return new ArrayList<String>();
HashMap<Integer, ArrayList<String>> cache = new HashMap<Integer, ArrayList<String>>();
return split(s, dict, 0, cache);
}
private ArrayList<String> split(String s, Set<String> dict, int i, HashMap<Integer, ArrayList<String>> cache) {
if (i == s.length())
return null;
if (cache.containsKey(i))
return cache.get(i);
ArrayList<String> result = new ArrayList<String>();
for (int j = i; j < s.length(); j++) {
String curr = s.substring(i, j + 1);
if (dict.contains(curr)) {
ArrayList<String> rest = split(s, dict, j + 1, cache);
if (rest == null) {
StringBuilder sb = new StringBuilder();
sb.append(curr);
result.add(sb.toString());
} else {
for (String tail : rest) {
StringBuilder sb = new StringBuilder();
sb.append(curr).append(" ").append(tail);
result.add(sb.toString());
}
}
}
}
cache.put(i, result);
return cache.get(i);
}
- In: classic | leetcode
- Leave a Comment
这题leetcode把关太松了，一个cache就让过了。实际上应该再加一个prefix tree把关，比如leetcode， le如果发现连个prefix都不是，那么lee, leet, leetc..都不要查了。所以算法是：
- 拿字典建prefix tree：O(字典大小*最长词的长度）
- i=0开始recurse, j=i开始一点点增长当前substring长度，若curr substring在字典里，就看看j + 1开头的剩下一半能不能成；能成就直接返回true，不能的话还得继续i++
- curr substring不在字典里，那应该j++的，但这时候先看一看curr是不是至少是个prefix，要是连prefix都不是，这个i直接作废，i++
- 每次做好了cache一下，boolean cache[i]表示以i开头到词尾的这个substring能不能用字典组成
public class Node {
char c;
Node[] children;
public Node (char ch){
c = ch;
children = new Node[26];
}
}
public boolean wordBreak(String s, Set<String> dict) {
if (s == null || s.length() == 0)
return false;
return canSplit(s, dict, 0, new HashMap<Integer, Boolean>(), makePrefixTree(dict));
}
private Node makePrefixTree(Set<String> dict) {
Node root = new Node('0');
for (String s : dict) {
insertWord(root, s);
}
return root;
}
private void insertWord(Node root, String s) {
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (root.children[c - 'a'] == null) {
root.children[c - 'a'] = new Node(c);
}
root = root.children[c - 'a'];
}
}
private boolean canSplit(String s, Set<String> dict, int i, HashMap<Integer, Boolean> cache, Node root) {
if (i == s.length())
return true;
if (cache.containsKey(i))
return cache.get(i);
boolean canSplit = false;
for (int j = i; j < s.length(); j++) {
String first = s.substring(i, j + 1);
if (dict.contains(first)) {
if (canSplit(s, dict, j + 1, cache, root)) {
canSplit = true;
break;
} //cannot split to the end, try split by i, j + 1
} else {
//does not contain first word, try split by i, j + 1
if (!containsAsPrefx(first, root)) {
//does not even contain first word as prefix, then can't start by i, split by i + 1
break;
}
}
}
cache.put(i, canSplit);
return cache.get(i);
}
private boolean containsAsPrefx(String s, Node root) {
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (root.children[c - 'a'] == null)
return false;
root = root.children[c - 'a'];
}
return true;
}
Lexi's Leetcode solutions 