Lexi's Leetcode solutions

Archive for August 2013

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

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:

别用傻乎乎的additional data structure,那样可以做,但是写起来太长。这个题上来的思路就是用左中右的inorder,这样一路下来,prev.next = curr,不断update当前的node为prev。但是写了半天,不知道怎么传prev,因为担心传java reference的问题;又回到了那个IntWrapper tree serialization的题。都是一个类型:https://leetcodenotes.wordpress.com/2013/08/24/phone-serializede-serialize-a-tree/

public void addSuccessor(Node node, Node[] prev) {
  if (node == null)
    return;
  addSuccessor(node.left, prev);
  if (prev[0] != null)
    prev[0].next = node;
  prev[0] = node;
  addSuccessor(node.right, prev);
}

类似题:找tree的in order traversal第x个节点:keep一个current node的index counter,同样是inorder的pattern,到当前node的时候counter++。这个init的i应该是-1,因为第一次找到最左边的节点的时候,i先+1,然后和x比较。

public TreeNode getNthNode(TreeNode node, IntWrapper i, int x) {
  if (node == null)
    return null;
  TreeNode foundAtLeft = getNthNode(node.left, i, x);
  i.val++;
  if (i.val == x)
    return node;
  if (foundAtLeft != null)
    return foundAtLeft;
  return getNthNode(node.right, i, x);
}

对这类题型其实不够熟悉,写了有15分钟才出来,太差了。总结一下。

BST一般找不到就null了,没办法keep track of走到哪个位置的信息。所以多传两个参数,leftBoundary和rightBoundary,分别表示“当前node为root的子树的left boundary – 当前子树的immediate prev)“和“immediate next”。因为你是top down的往下算,所以左右两边的boundary不断narrow down。当node == null时,此时的最靠近自己的boundary就起作用了,找他们之间最接近x的就行了。

这题和判断一棵树是不是BST是一个套路(后面有对比):

public TreeNode getClosest(TreeNode node, TreeNode leftBoundary, TreeNode rightBoundary, int x) {
  if (node == null)
    return getClosest(leftBoundary, rightBoundary, x);
  if (node.val < x) {
    return getClosest(node.right, node, rightBoundary, x);
  } else {
    return getClosest(node.left, leftBoundary, node, x);
  }
}
private TreeNode getClosest(TreeNode prev, TreeNode next, int x) {
  if (prev == null || next == null)
    return prev == null ? next : prev;
  if (next.val - x < x - prev.val)
    return next;
  else
    return prev;
}

附加:判断一棵树是不是BST,也是一路传下来boundary,不断看当前节点是不是满足上面传下来的左右boundary, 然后往下传的时候narrow down。最开始left, right, node都是null(没有左右节点限制)。

boolean isBST(Node node, Node leftBoundary, Node rightBoundary) {
  if (node == null)
    return true;
  if ((leftBoundary != null && node.val < leftBoundary.val) || (rightBoundary != null && node.val > rightBoundary.val))
    return false;
  if (!isBST(node.left, leftBoundary, node))
    return is BST(node.right, node, rightBoundary);
}

http://www.mitbbs.com/article_t1/JobHunting/32184907_0_1.html

思路(这个没怎么测试,不知道对不对,也想不明白time)。。

从头开始顺着摸,摸到摸过的,说明有loop。

什么时候结束?摸到下一个index out of boundry了,说明当前绳子结束。但是可能数组里中间还剩一大堆元素没动呢,所以要keep一个currRopeHead variable (当前绳子的头);从这个头的下一个开始往右找(左边不用找了,既然当前绳子在这开头,说明左边的小绳结早就处理过了),找到第一个没visited过的绳头,接着做。

test: {2, -1, 1, 4, 5, 0}这算是loop吗?感觉应该不算,所以一个visited array还不行,得用Map<Index, HashSet<ropeIndex>>才行。顺着当前绳子摸到的节点若在当前绳子上visit过才叫visit过。所以每次新生成绳子的时候,要把ropeIndex++。卧槽这越来越复杂了。

boolean hasCycle(int[] arr) {
  int[] visited = new int[arr.length]; 
  int i = 0; 
  int currRopeHead = i; 
  while (i < arr.length) { 
    if (visited[i])
    return true;
    visited[i] = true;
    int next = arr[i];
    if (next < 0 || next >= arr.length) {
      //rope is broken, will start a new one
      //find the first unvisited rope start
      boolean foundRopeHead;
      for (int j = currRopeHead + 1; j < arr.length; j++) {
        if (!visited[j]) {
          i = j;
          foundRopeHead = true;
          currRopehead = i;
          break;
        }
      }
      if (!foundRopeHead)
        return false;
    } else {
      i = next;
    }
  }
  return false;
}

太复杂了,还是用runner technique吧。两个runner用来看当前绳字有木有loop,外加一个set代表所有没vsit过的“绳头”。

这样的话,其实并不慢,原因是runner fast跑到绳子尽头为止,不多往后跑(如果没loop的话);如果有loop,那肯定在当前绳结跑两次之前也能追上slow而停止,所以还是O(k + k)的速度(k是当前绳结的长度)。然后这个绳子跑完了,上面所有经过的节点都从set里remove掉了,set就可以接着随便找一个当绳头,接着recursion。有一个怀疑就是然后从set里面random拿的一个节点不是绳头,而是绳子中间某个部分怎么办;后来想想那就相当于把一个长绳子分两半做,要是有loop怎么都分不开,要是没loop那分成的两半也各自没loop,时间还是一样的。

boolean hasLoop(int[] arr) {
  Set<Integer> unvisitedIndexSet = new HashSet<Integer>();
  for (int i = 0; i < arr.length; i++) {
    unvisitedIndexSet.add(i);
  }
  return hasLoop(arr, unvisitedIndexSet);
}
boolean hasLoop(int[] arr, Set<Integer> set) {
  if (set.isEmpty())
    return false;
  int randomHead = getRandomElement(set);
  int fast = randomHead;
  int slow = randomHead;
  set.remove(fast);
  while (fast != -1) {
    fast = arr[fast];
    set.remove(fast);
    if (fast == -1)
    break;
  else {
    fast = arr[fast];
    set.remove(fast);
  }
  slow = arr[slow];
  if (fast == slow)
    return true;
  }
  return hasLoop(arr, set);
}
Tags: ,

example: aabc matches c*a*b.

思路:

  1. 两个指针i, j,i指regular expression,j指真的string。
  2. 观察p[i+1],
    • 如果它不是*,说明没法skip p[i],则p[i]和s[j]必须match(相等或者p[i]是’.’ which matches everything)。如果不满足,直接返回false,没法matche了。
    • 如果它是*,说明当前位置可以是0个p[i], 1个p[i], 2个p[i]..
      1. 先试试“用0个p[i]“,即把p[i]和他后面的* skip掉。若recurse (i + 2, j)成功了,直接返回true,不成功,接着做第二步。
      2. 从“用1个p[i]“开始while循环,若p[i]和s[j] match, recurse on (i + 2, j + 1)(把*用掉了所以i+2),如果返回true就直接成了,否则就while继续循环“用2个p[i]“,即recurse on (i + 2, j + 2), recurse on (i + 2, j + 3)…循环的终止条件是p[i]和s[j]不match了,直接返回false。
public boolean isMatch(String s, String p) {
  return tryMatch(p, s, 0, 0);
}
private boolean tryMatch(String p, String s, int i, int j) {
  if (i == p.length())
    return j == s.length();
  if (i == p.length() - 1 || p.charAt(i + 1) != '*') { //下一个字母不是*,当前字母必须match
    if (matchChar(p, s, i, j))
      return tryMatch(p, s, i + 1, j + 1);
    else
      return false;
  } else { // p[i + 1] is *
    boolean skip = tryMatch(p, s, i + 2, j); //把当前字母去掉能行,就直接返回
    if (skip)
      return true;
    while (matchChar(p, s, i, j)) {//*当一个p[i]开始,当两个,当三个。。
      if (tryMatch(p, s, i + 2, j + 1))
        return true;
      j++;
    }
    return false;
  }
}
private boolean matchChar(String p, String s, int i, int j) {
  if (i >= p.length() || j >= s.length())
    return false;
  return p.charAt(i) == s.charAt(j) || p.charAt(i) == '.';
}
Tags: , ,

花一个小时看完了书,自己写了一遍,基本明白咋回事了。需要两个接口,Source and Listener(我自己瞎起的名字),Source是那个变的,Listener是那个被通知的。

  1. Source:
    • 一个private List<Listener> listeners;
    • 一个registerListener(Listener l)函数,把l加到listeners里面去
    • 一个removeListener(Listener l)函数,把l从listeners里面删掉
    • 一个notifyAllListeners()函数,里面对于每个listener, call listener的update()。不需要加parameter,只是通知list里面的监听者“有东西改了”, 具体改的是啥,让Listener里面的update函数自己从source reference里面pull去。
  2. Listener:
    • 一个private Source s
    • 一个constructor that takes a Source obj, 初始的时候就把“听谁”(source)给联系上。
    • 一个update()函数,里面把Source s cast成自己真监听的concrete type(比如“杂志”),然后从这个s里面pull data。

重点:

  • Source的notify函数只是负责告诉listeners,有变动了,你们来pull我的data吧。不用真把动的是哪个data传过去。当然也可以pass一个para说明到底是哪个data变了,client好知道具体pull哪个data。
  • Listener的update()函数只被source的notify叫,然后函数里面取出当前obj的source reference, cast, pull data and use it.
  • Register这些东西都是在main函数里叫的。
public class Magazine implements Source {
private List<Listner> subscribers;
 private String editorName;
 public String getEditorName() {
 return editorName;
 }
public Magazine () {
 this.subscribers = new ArrayList<Listner>();
 this.editorName = "Christina";
 }

 public void changeEditorName(String newEditor) {
 this.editorName = newEditor;
 notifyListners();
 }
@Override
 public void registerListner(Listner l) {
 subscribers.add(l);
 }
@Override
 public void removeListner(Listner l) {
 if (subscribers.contains(l))
 subscribers.remove(l);
 }
@Override
 public void notifyListners() {
 for (Listner subscriber : subscribers) {
 subscriber.update();
 }
 }
public static void main(String[] args) {
 Magazine m = new Magazine();
 Subscriber sub1 = new Subscriber(m, "sub1");
 Subscriber sub2 = new Subscriber(m, "sub2");
 m.registerListner(sub1);
 m.registerListner(sub2);
 m.changeEditorName("Meredith");
 m.removeListner(sub2);
 m.changeEditorName("Alex");
 }
}

public class Subscriber implements Listner {
private Source magazine;
private String name;
private String currentEditorName;

public Subscriber(Source s, String name) {//this is how one listner bind to one subject.
this.name = name;
this.magazine = s;
}

@Override
public void update() {
//each subscriber knows the subject is a magazine, so it can cast it's subject to magazine and use this subject's properties.
String newEditor = ((Magazine) this.magazine).getEditorName();
this.currentEditorName = newEditor;
System.out.println(name + ": Updating editor name to " + newEditor);
}

没啥可说的,对于每个cell,如过和word的开头字母一致,就生成一个新的全是false的visited[][], 进去原matrix开始前后左右的找。直到word的每个字母都找到为止。

要点:之前做的是直接

  // left, right, up, down
  return find(board, i, j - 1, word, index + 1, visited) || find(board, i, j + 1, word, index + 1, visited)
  || find(board, i - 1, j, word, index + 1, visited) || find(board, i + 1, j, word, index + 1, visited);

这样就挂了!因为往左走的一路已经Update visited[][]了,然后没人去undo它,往右走的一支就直接拿来用了,不就乱套了么!所以在mark true的时候,函数结尾给undo一下,就可以保证一对儿出现,路径在反上来的被清理。

public boolean exist(char[][] board, String word) {
  for (int i = 0; i < board.length; i++) {
    for (int j = 0; j < board[0].length; j++) {
      if (board[i][j] == word.charAt(0)) {
        boolean found = find(board, i, j, word, 0, new boolean[board.length][board[0].length]);
        if (found)
          return true;
      }
    }
  }
  return false;
}
private boolean find(char[][] board, int i, int j, String word, int index, boolean[][] visited) {
  if (i < 0 || j < 0 || i >= board.length || j >= board[0].length)
    return false;
  if (board[i][j] != word.charAt(index) || visited[i][j])
    return false;
  visited[i][j] = true;
  if (index == word.length() - 1)
    return true;
  // left, right, up, down
  boolean found = find(board, i, j - 1, word, index + 1, visited) || find(board, i, j + 1, word, index + 1, visited)
                || find(board, i - 1, j, word, index + 1, visited) || find(board, i + 1, j, word, index + 1, visited);
  visited[i][j] = false;//这样就能保证每次true的能给false回来
  return found;
}

五分钟bug free,忍不住有成就感。

思路:root <= x,说明肯定不在左边,往右找;root >x,有可能是本身:如果root.left没找到,那就是本身了;如果找到了,那就返回找到那个。

public TreeNode getImmediateNext(TreeNode node, int x) {
  if (node == null)
    return null;
  if (node.val <= x) {
    return getImmediateNext(node.right, x);
  } else {
    TreeNode parent = node;
    TreeNode findAtLeft = getImmediateNext(node.left, x);
    return findAtLeft== null ? parent : findAtLeft;
  }
}
Tags: ,

private int findKth(int[] A, int[] B, int k) {
if (A.length == 0 && B.length == 0)
return 0;
return findKth(A, B, 0, 0, k);
}

private int findKth(int[] A, int[] B, int i, int j, int k) {
if (A.length – i > B.length – j)
return findKth(B, A, j, i, k);
if (i == A.length)
return B[j – 1 + k]; // the kth starting from j
if (k == 1) //when trying to find the first, just return the smaller head
return Math.min(A[i], B[j]);
int m1, m2; // section size
if (A.length – i < k / 2) { // A’s left over (start from A[i] to A[last]) can’t slice a size k/2 section
m1 = A.length – i;
} else {
m1 = k / 2;
}
m2 = k – m1;
int i1 = i + m1 – 1; // the pivot’s index in A
int j1 = j + m2 – 1;
if (A[i1] < B[j1]) // abandon A’s left section including A[i1]
return findKth(A, B, i1 + 1, j, k – m1);
else if (A[i1] > B[j1]) {// abandon B’s left section including B[j1],
return findKth(A, B, i, j1 + 1, k – m2);
} else {
return A[i1];
}
}