A
BAN USERGood one
printInterleavingsSorted("ab".toCharArray(), "cd".toCharArray(), "", 0, 0);
private static void printInterleavingsSorted(char[] c1, char[] c2, String prefix, int i, int j) {
if (i == c1.length) {
System.out.println(prefix + new String(c2, j, c2.length - j));
return;
}
if (j == c2.length) {
System.out.println(prefix + new String(c1, i, c1.length - i));
return;
}
if (c1[i] <= c2[j]) {
printInterleavingsSorted(c1, c2, prefix + c1[i], i + 1, j);
printInterleavingsSorted(c1, c2, prefix + c2[j], i, j + 1);
} else {
printInterleavingsSorted(c1, c2, prefix + c2[j], i, j + 1);
printInterleavingsSorted(c1, c2, prefix + c1[i], i + 1, j);
}
}
Exponential
private static boolean possible(List<Integer> l, int x) {
int size = l.size();
if (size == 1) {
return l.get(0) == x;
}
for (int i = 1; i < size; i++) {
int a = l.get(i - 1);
int b = l.get(i);
l.remove(0);
l.set(i - 1, a + b);
if (possible(l, x))
return true;
l.set(i - 1, a - b);
if (possible(l, x))
return true;
l.set(i - 1, a * b);
if (possible(l, x))
return true;
if (b != 0 && a % b == 0) {
l.set(i - 1, a / b);
if (possible(l, x))
return true;
}
l.set(i - 1, b);
l.add(i - 1, a);
}
return false;
}
package cc.goog;
import java.util.Collection;
import java.util.Iterator;
public class IteratorForNegetiveNumbers implements Iterator<Integer> {
private Iterator<Integer> i;
private Integer lastRead = null;
public IteratorForNegetiveNumbers(Collection<Integer> c) {
this.i = c.iterator();
}
@Override
public boolean hasNext() {
while (i.hasNext()) {
Integer x = i.next();
if (x != null && x < 0) {
lastRead = x;
return true;
}
}
return false;
}
@Override
public Integer next() {
if (lastRead != null) {
lastRead = null;
return lastRead;
}
while (true) {
Integer x = i.next();
if (x != null && x < 0) {
return x;
}
}
}
@Override
public void remove() {
throw new UnsupportedOperationException();
}
}
private static String toUnderscoreCase(String s) {
if (s == null || "".equals(s))
return s;
char[] c = s.toCharArray();
char[] r = new char[c.length * 2];
int j = 0;
for (int i = 0; i < c.length; i++) {
if (i > 0 && isUpperCase(c[i])) {
r[j++] = '_';
}
r[j++] = toLowerCase(c[i]);
}
return new String(r, 0, j + 1);
}
private static char toLowerCase(char c) {
if (isUpperCase(c)) {
return (char) (c+32);
}
return c;
}
private static boolean isUpperCase(char c) {
return c > 64 && c < 91;
}
package cc.goog;
import java.util.HashMap;
import java.util.Map;
import java.util.Random;
public class SpecialSet<T> {
private Map<T, Integer> elementVsIndex = new HashMap<T, Integer>();
private Map<Integer, T> indexVsElement = new HashMap<Integer, T>();
private Random r = new Random();
public void insert(T t) {
if (elementVsIndex.containsKey(t))
return;
int maxIndex = elementVsIndex.size();
elementVsIndex.put(t, maxIndex);
indexVsElement.put(maxIndex, t);
}
public void remove(T t) {
int maxIndex = elementVsIndex.size() - 1;
Integer removedIndex = elementVsIndex.remove(t);
if (removedIndex != null) {
T e = indexVsElement.remove(maxIndex);
if (e != null) {
elementVsIndex.put(e, removedIndex);
indexVsElement.put(removedIndex, e);
}
}
}
public T getRandomElement() {
int maxIndex = elementVsIndex.size();
int randomIndex = r.nextInt(maxIndex);
return indexVsElement.get(randomIndex);
}
}
private static boolean matches(char[] s, char[] p, int i, int j) {
if (j < 0) {
return i < 0;
}
if (i < -1)
return false;
if (i > -1 && s[i] == p[j]) {
return matches(s, p, i - 1, j - 1);
}
if (p[j] == '?') {
return matches(s, p, i, j - 1) || matches(s, p, i - 1, j - 1);
}
if (p[j] == '*') {
return matches(s, p, i, j - 1) || matches(s, p, i - 1, j - 1)
|| matches(s, p, i - 1, j);
}
return false;
}
- A March 02, 2013