Lexi's Leetcode solutions

Archive for the ‘面经’ Category

比如{1, 2, 4, 5},3的supposed index就应该是2(把4的位置顶替了)。

facts:

  • because in the end, when p’s next is q, the mid will == p, and new left section will be [q, p](q is mid – 1 and p stays); new right section will be [q, p] (p is mid + 1 and q stays), which ever, we want to return the p because we didn’t find x!
  •  is there a possibility where in the end p’s next is not q? like p q somehow points to the same element, then it’s the same, we want to return p.
  • that’s all the possible combinations. There’s no way [p, somethinglese, q] in the end, that will always transform to scenario 1 or scenario 2.
int findSupposedIndex(int[] arr, int x, int p, int q) {
  if (p > q)
    return p;
  int mid = (p + q) / 2;
  if (arr[mid] == x)
      return mid;
  else if (arr[mid] > x)
      return findSupposedIndex(arr, x, p, mid - 1);
  else
      return findSupposedIndex(arr, x, mid + 1, q);
Advertisements

想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: ,

五分钟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: ,