Lexi's Leetcode solutions

Posts Tagged ‘二分法

这题上来没法下手,咬牙看了半天用dfs写出了个差不多的,最后卡在两个list merge上。实在看不出规律(后来发现是自己例子都写错了!!),上网一查,大神回复:

假设有n-1的答案为:G0, G1, …, Gn,想得到n的答案,只需要在G0…Gn左边加上一个0,再把G0…Gn颠倒顺序,在左边加上一个1即可。比如n=3(在分界线上倒映):

000
001
011
010
---
110
111
101
100

用dfs可以每次求出左边是0,然后求出左边是1的,合一起就是了。两个教训:

  1. 这种数学题找规律,千万别自己把例子写错了。那样打死也看不出规律的。
  2. 拿到一题往死里想个10分钟总能想出点眉目的,别放弃。
public ArrayList<Integer> grayCode(int n) {
    if (n == 0) {
        ArrayList<Integer> list = new ArrayList<Integer>();
        list.add(0);
        return list;
    }
    return getGrayCode(n - 1);
}
private ArrayList<Integer> getGrayCode(int pos) {
    if (pos == 0) {
        ArrayList<Integer> list = new ArrayList<Integer>();
        list.add(0);
        list.add(1);
        return list;
    }
    ArrayList<Integer> result = new ArrayList<Integer>();
    ArrayList<Integer> startsWithZero = getGrayCode(pos - 1);
    ArrayList<Integer> startsWithOne = new ArrayList<Integer>();
    for (int i = startsWithZero.size() - 1; i >= 0; i--) {
        startsWithOne.add(startsWithZero.get(i) + (1 << pos));
    }
    result.addAll(startsWithZero);
    result.addAll(startsWithOne);
    return result;
}
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: