Posts Tagged ‘二分法’
- In: leetcode
- 2 Comments
这题上来没法下手，咬牙看了半天用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的，合一起就是了。两个教训：
- 这种数学题找规律，千万别自己把例子写错了。那样打死也看不出规律的。
- 拿到一题往死里想个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;
}
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;
}
Tags: 二分法
Lexi's Leetcode solutions 