Archive for August 29th, 2013
- In: 面经
- Leave a Comment
想random只能用array，insert remove全O(1)只有hashmap，结合一下就可以了。
public class RandomSetStructure {
Map<Integer, Integer> map;
List<Integer> array;
Random random;
public void insert(int a) {
if (map.containsKey(a))
return;
array.add(a);
map.put(a, array.size() - 1);
}
public void remove(int a) throws Exception{
if (!map.containsKey(a))
throw new RuntimeException();
int index = map.get(a);
map.remove(a);
array.set(index, array.get(array.size() - 1));
map.put(array.get(index), index);
array.remove(array.size() - 1);
}
public int rand() {
if (map.isEmpty())
throw new RuntimeException();
return array.get(random.nextInt(array.size()));
}
}
Tags: data structure
- In: 面经
- Leave a Comment
Given a string, find longest substring which contains just two unique characters. 比如ABACDDCB, 返回CDDC。
自己做的O(n)的解法，不用额外空间，但是需要additional data structure。测了几个没问题。
思路：假设d[i – 1]是以arr[i – 1]为结尾的data，已经做好了。那d[i] =
- 如果arr[i]属于d[i – 1]的那个substring中的两个元素中的某一个，那么d[i]的长度直接是上一个加一。
- 不属于的话，要把arr[i]和上一个的“最后一段由一个字母组成的sequance“连起来。比如d[i – 1]的结果是BABB，然后arr[i]是C，就想把BB和C连起来生成新的substring BBC然后放在d[i]里。
- 这样的话，需要记录四个数据：length, index of last sequence ‘s beginning m, the char that is not the last (in above case, is A), and last letter (B)（这个不是必要的，可以用m来读，但是看着方便。
public class Data {
int len;
Character last;
Character notLast;
int m;// beginning index of last sequense
}
String findLongestSubString(String s) {
if (s.length() == 0)
return null;
Data prev = new Data(1, s.charAt(0), null, 0);
Data maxData = prev;
int maxEnd = 0;
for (int i = 1; i < s.length(); i++) {
Data curr = new Data();
Character charAtI = s.charAt(i);
if (charAtI.equals(prev.last) || prev.notLast == null || charAtI.equals(prev.notLast)) {
curr.len = prev.len + 1;
curr.notLast = charAtI.equals(prev.last) ? prev.notLast : prev.last;
curr.last = s.charAt(i);
curr.m = charAtI.equals(prev.last) ? curr.m : i;
} else {
curr.len = i - prev.m + 1;
curr.notLast = prev.last;
curr.last = s.charAt(i);
curr.m = i;
}
if (curr.len > maxData.len) {
maxData = curr;
maxEnd = i;
}
prev = curr;
}
String result = s.substring(maxEnd - maxData.len + 1, maxEnd + 1);
return result;
}
Tags: string
Lexi's Leetcode solutions 