Lexi's Leetcode solutions

Posts Tagged ‘easy

倒是20分钟写出来了bugfree,比较喜欢这种利用data structure的题,感觉试一试总能想出来。

这个题就是基本BFS,要点是生成新节点的同时,怎么把新节点和其他新节点连起来呢?这就需要一个新旧节点对应map,每次生成新节点A’,要把dequeue的这个parent B对应的新节点B’和当前作为child的新节点A’连起来。注意单向连就行了(B’->A)’,因为下次把A当作root的时候,还会经历B作为child,这时再A’->B’。

public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
  if (node == null)
    return null;
  Queue<UndirectedGraphNode> q = new LinkedList<UndirectedGraphNode>(); 
  Map<UndirectedGraphNode, UndirectedGraphNode> map = new HashMap<UndirectedGraphNode, UndirectedGraphNode>();
  enqueueAndClone(q, node, map);
  while (!q.isEmpty()) {
    UndirectedGraphNode parent = q.poll();
    for (UndirectedGraphNode child : parent.neighbors) {
      if (!map.containsKey(child))
        enqueueAndClone(q, child, map);
      map.get(parent).neighbors.add(map.get(child));//不管是否visit过,都要单向连接 
    }
  }
  return map.get(node);
}
private void enqueueAndClone(Queue<UndirectedGraphNode> q, UndirectedGraphNode node, Map<UndirectedGraphNode, UndirectedGraphNode> map) {
  q.add(node);
  UndirectedGraphNode newNode = new UndirectedGraphNode(node.label);
  map.put(node, newNode);
}
Advertisements

经典题,注意balanced的定义:左右子树都balance,且高度差<=1。所以下面这个也是balanced的,即使a的做右子树都不是完全树。

    a
   / \ 
  b   d
 /     \
c       e

唯一的trick:不用生成新的data structure来保存“boolean isBalanced, int height”,直接用height = -1表示不平衡就行。

public boolean isBalanced(TreeNode root) {
  return getHeight(root) >= 0;
}
private int getHeight(TreeNode root) {
  if (root == null)
    return 0;
  int leftHeight = getHeight(root.left);
  if (leftHeight < 0)
    return -1;
  int rightHeight = getHeight(root.right);
  if (rightHeight < 0)
    return -1;
  if (Math.abs(leftHeight - rightHeight) > 1)
    return -1;
  return Math.max(leftHeight, rightHeight) + 1;
}
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: ,

和电话号码一样,基本的DFS。mark一下,下次再准备面试的时候可能就忘了这种题型了。

public ArrayList<String> restoreIpAddresses(String s) {
  ArrayList<String> result = new ArrayList<String>();
  String[] curr = new String[4];
  restore(s, 0, curr, result);
  return result;
}
private void restore(String s, int level, String[] curr, ArrayList<String> result) {
  if (level == 4) {
    if (s.isEmpty()) {
      result.add(convertToIpString(curr));
    }
    return;
  } else if (s.isEmpty())
  return;
 
  for (int i = 1; i <= 3 && i <= s.length(); i++) {
    String left = s.substring(0, i);
    String right = s.substring(i);
    if (validIp(left)) {
      curr[level] = left;
      restore(right, level+ 1, curr, result);
    }
  }
}
private boolean validIp(String s) {
  if (s.length() > 1 && s.charAt(0) == '0')
    return false;
  return Integer.valueOf(s) < 256;
}
private String convertToIpString(String[] curr) {
  StringBuilder sb = new StringBuilder();
  for (String s : curr) {
    sb.append(s);
    sb.append(".");
  }
  sb.deleteCharAt(sb.length() - 1);
  return sb.toString();
}
Tags: ,

很简单的题,因为熟悉了用两个list做tree的bfs,所以这里一层一层iterate就行了,上一层反正已经做完了,所以能直接横着遍历上一层,把下一层populate了。轻松过。

Tags: , ,

本来觉得是弱智题,但是基本从来不top down的做树的题,写完还真挂在bug上了。

top down利用leaf的树题一般是这样的pattern:

void topDown(Node node) {
    if (node == null)
        //this means reaching a branch that only one side has something, the other side is this (null)
    if (node.left == null && root.right == null)
        //this is leaf, do something, then return;
    topDown(node.left);
    topDown(node.right);
}

和平时做的preorder(中左右)的区别:preOrder这种遍历下来,的确会在empty node的时候停,但是不能判断什么时候到了叶子节点。而topDown利用了叶子节点的定义来判断当前节点是否叶子,可以这时候做一些运算。

void preOrder(Node node) {
   if (node == null)
   //this could either mean parent is a leaf, or parent's this branch is empty but has another child
   }
   preOrder(node.left);
   preOrder(node.right);
}
Tags: , ,

这题CC150上做过,属于简单题。但是做的过程中发现两个问题,关于generic linked list的:

  1. 最好别用while (curr != null && curr.next != null)这种循环,改成带prev指针的比较好,清晰易懂。然后出while循环的时候,每次用的prev都判断一下是否是null,是的话就什么也不用做。
  2. 注意连接两个list的时候,小心list的最后一个next是不是指回来了,忘了清空。这样有loop的危险。
  3. 多拿几个combination试试,做到branch coverage!(这里就是”全<x, 全>=x,先<x后>=x,先>=x后<x“这四种情况)。

自己写完觉得很恶心,但是一看书基本一样,说明这种linked list题就是恶心,立刻释然了。

Tags: ,