Lexi's Leetcode solutions

Archive for October 6th, 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);
}
Advertisements

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);
}

这题leetcode把关太松了,一个cache就让过了。实际上应该再加一个prefix tree把关,比如leetcode, le如果发现连个prefix都不是,那么lee, leet, leetc..都不要查了。所以算法是:

  1. 拿字典建prefix tree:O(字典大小*最长词的长度)
  2. i=0开始recurse, j=i开始一点点增长当前substring长度,若curr substring在字典里,就看看j + 1开头的剩下一半能不能成;能成就直接返回true,不能的话还得继续i++
  3. curr substring不在字典里,那应该j++的,但这时候先看一看curr是不是至少是个prefix,要是连prefix都不是,这个i直接作废,i++
  4. 每次做好了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;
}
Tags: