Lexi's Leetcode solutions

Archive for the ‘面经’ Category

这个题和前几天做的另一道“找二叉树的第n个元素“一样,用到的是pass-count technique:用一个IntWrapper keep track of 线性的index。无论tree怎么走,这个index是不断增加的。

serialize很简单,用#表示null,然后中左右(pre order)的traverse一遍就变成serialize的文件了。

deserialize的话,和preorder一样,怎么来的就怎么populate回去。是#,说明populate null,就不用往下做了;不是的话,继续做;重点是要keep track of current element in the array,就用到了一个Integer wrapper好能把count的这个值一路传下去。需要特别小心的是,这个count要一直增加,不管当前是不是#!

Node deserialize(char[] arr, IntWrapper i) {
  i.val++;//这个不能放if后面!
  if (arr[i.val] == '#')
    return null;
  Node newNode = new Node(arr[i.val]);
  newNode.left = deserialize(arr, i);
  newNode.right = deserialize(arr, i);
  return newNode;
}

Iterator pattern is a design pattern in which an iterator is used to traverse a container and access the container’s elements. The iterator pattern decouples algorithms from containers; in some cases, algorithms are necessarily container-specific and thus cannot be decoupled. It provide a way to access the elements of an aggregate object sequentially without exposing its underlying representation.

这个模式可以保证不同的容器统一用一个interface来traverse,比如正常用for的话,array的traverse要用arr[i],arrayList的要用get(i),map更是得map.entrySet.get..,各种syntax不同,所以即使对每个element干的事儿一样,traverse也要写三遍,太麻烦了。如果用iterator,所有traverse统一用next()就行了。具体iterator是怎么next()的,自己再在容器里面写(大不了就三个容器都implement MyContainer,全写一遍next()函数对于该容器是怎么取下一个的。反正一劳永逸,next()一旦定义了,以后任何client都可以随便用)。其实对于ArrayList, Map之类这么长用的,java已经都给写好了iterator (e.g. List list = new List(); Iterator it = list.iterator();)。下面是例子:

  1. Container要implement Iterable<Type>
  2. Container里面写个implement Iterator<Type> 的iterator inner class
  3. Container里要有个iterator() method用来生成一个iterator
  4. Inner iterator class里面implement next(), hasNext()两个method.
public class TreeInPreOrderIterable implements Iterable<TreeNode> {
  private TreeNode root;
  private class TreeIterator implements Iterator<TreeNode> {
    Stack<TreeNode> stack;
    private TreeIterator(TreeNode root) {
      stack = new Stack<TreeNode>();
      if (root != null)
        stack.push(root);
    }
    @Override
    public TreeNode next() {
      if (hasNext()) {
        TreeNode pop = stack.pop();
        if (pop.right != null)
          stack.push(pop.right);
        if (pop.left != null) 
          stack.push(pop.left);
        return pop;
      } else {
        throw new NoSuchElementException(); 
      }
    }
    @Override
    public boolean hasNext() {
      return !stack.isEmpty();
    }
  }
  @Override
  public Iterator<TreeNode> iterator() {
    return new TreeIterator(this.root);
  }
}

单链表只让过一次,所以不能先把size找出来再rand(size)。

解法:reservoir  sampling

  1. 每次在curr处,假设curr的之前这段list的random element已经找到了,此时决定curr要不要把之前找到的result替换掉?在第i个node上,选中第i个node为result的概率是1/i。所以以1/i的概率用curr来替换已经找好的previous random result.
  2. 这样interative的linked list往后一个个移动,直到最后一个也做完,说明result就是list所有元素都consider了的random结果。
ListNode getRandom(ListNode head) {
  int count = 1;
  ListNode result = head;
  ListNode curr = head;
  while (curr != null) {
    int rand = generateRandBetween(1, count);
    if (rand % count == 1) //this condition will happen with prob of 1/count
      result = curr;
    curr = curr.next;
    count++;
  }
  return result;
}

蓄水池抽样的原理:

从很大(不知道有多大)的水池里取k滴水。假设在i – i处已经取了k滴水了,现在决定要不要拿i来替换已有的某个k中的元素。同样,替换的概率是1/i,但是替换k中的哪一滴水呢?所以整体概率应该是(1/i) * k。

rand = generateRandBetween(1, i);
if (rand % i <= k) //should replace something in result with arr[i]
   result[rand%i] = arr[i];

 

Tags:

Blog Stats

  • 221,455 hits
June 2020
M T W T F S S
1234567
891011121314
15161718192021
22232425262728
2930