Lexi's Leetcode solutions

Posts Tagged ‘stack/queue

这个题一开始自己做死了,后来bf给讲用stack之后就一遍过了,代码也简单很多。思路

  1. 先用/来split string
  2. 然后看每一小段,若是”.”或者是“”(说明两个/连着),不入栈;若是”..”,pop;若是正常,push
  3. 最后再用string builder把”/”和栈中元素一个一个连起来。
public String simplifyPath(String path) {
    Stack<String> s = new Stack<String>();
    String[] split = path.split("/");
    for (String a : split) {
        if (!a.equals(".") && !a.isEmpty()) {
            if (a.equals("..")) {
                if (!s.isEmpty()) {
                    s.pop();
                }
            } else {
                s.push(a);
            }
        }
    }
    StringBuilder sb = new StringBuilder();
    while (!s.isEmpty()) {
        sb.insert(0, s.pop());
        sb.insert(0, "/");
    }
    return sb.length() == 0 ? "/" : sb.toString();
}
Advertisements

括号题也不是只用stack才能做,这题是算长度,所以stack那种一match就俩一起pop了的方式就不适合了。求极值,一维dp最好使。

  • d[i]: 以i开头的最长valid parentheses有多长。
  • d[i] =
    • if  (str[i] == ‘)’),以右括号开头必定invalid,d[i] = 0
    • if (str[i] == ‘(‘),以左括号开头
      1. 我们想看对应的有木有右括号。因为d[i + 1]代表的sequence肯定是左括号开头右括号结尾,所以我们想catch((…))这种情况。j = i + 1 + d[i + 1],正好就是str[i]后面越过完整sequence的下一个,若是右括号,d[i] = 2 + d[i + 1]
      2. 除此之外,还有包起来后因为把后面的右括号用了而导致跟再往后也连起来了的情况,如((..))()()()。所以d[i]还要再加上j后面那一段的d[j + 1]

这个定义和最长公共字串那题的定义类似,都是“以某个固定位置开始/结束”。看两头的方式又像palindrome。从后往前的一维dp也不常见。挺好玩的,一下复习好多东西。

public int longestValidParentheses(String s) {
    if (s.length() == 0)
        return 0;
    int maxLen = 0;
    int[] d = new int[s.length()];
    // d[i] means substring starts with i has max valid lenth of d[i]
    d[s.length() - 1] = 0;
    for (int i = s.length() - 2; i >= 0; i--) {
        if (s.charAt(i) == ')')
            d[i] = 0;
        else {
            int j = (i + 1) + d[i + 1];
            if (j < s.length() && s.charAt(j) == ')') {
                d[i] = d[i + 1] + 2; //(()())的外包情况
                if (j + 1 < s.length())
                    d[i] += d[j + 1];//()()的后面还有的情况
            }
        }
        maxLen = Math.max(maxLen, d[i]);
    }
    return maxLen;
}

—————————-用stack的做法———————————–

  1. stack里面装的一直是“还没配好对的那些可怜的括号的index”
  2. 是'(‘的时候push
  3. 是’)’的时候,说明可能配对了;看stack top是不是左括号,不是的话,push当前右括号
  4. 是的话,pop那个配对的左括号,然后update res:i和top的(最后一个配不成对的)index相减,就是i属于的这一段的当前最长。如果一pop就整个栈空了,说明前面全配好对了,那res就是最大=i+1
public int longestValidParentheses(String s) {
    int res = 0;
    Stack<Integer> stack = new Stack<Integer>();
    char[] arr = s.toCharArray();
    for (int i = 0; i < arr.length; i++) {
        if (arr[i] == ')' && !stack.isEmpty() && arr[stack.peek()] == '(') {
            stack.pop();
            if (stack.isEmpty())
                res = i + 1;
            else
                res = Math.max(res, i - stack.peek());
        } else {
            stack.push(i);
        }
    }
    return res;
}

倒是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);
}

用两个stack O(n)的方法:

  1. 一个stack s1 push root。
  2. 一边pop s1进s2,一边把pop的left, right push进s1(先左后右,这先进s2的是右边,左边在s2靠前部分,所以最后先print出来)
  3. 这样最后s2就是一个正好从上到下是post order的traversal,一边pop一边print就行了。
public void postOrderTwoStacks(TreeNode root) {
  Stack<TreeNode> s1 = new Stack<TreeNode>();
  Stack<TreeNode> s2 = new Stack<TreeNode>();
  s1.push(root);
  while (!s1.isEmpty()) {
    TreeNode pop = s1.pop();
    s2.push(pop);
    if (pop.left != null)
      s1.push(pop.left);
    if (pop.right != null)
      s1.push(pop.right);
  }
  while (!s2.isEmpty()) {
    System.out.print(s2.pop().val + ", ");
  }
}

用一个stack O(h)的方法:

  1. 一个stack,先push root
  2. keep一个prev variable表示刚才试过的node(在stack里尝试来着,不管最后是否把它pop出去了),一直在更新。
  3. stack.peek() == curr,每次用curr和prev比较
    • 如果prev是空或者prev是curr的parent,说明在top down的traverse,这时候可不能print prev(那就变成preorder了);而应该push curr的左子,木有才push右子,全都木有说明curr是leaf,就pop print就行了。
    • 如果prev是curr的左子,说明在从左下角往上traverse,这时若curr有右子,则push右子(应该traverse右子)- prev应该是已经pop出来的了。
    • 如果prev是curr的右子,说明从右下角往左上traverse,这时直接pop print curr就行了,因为这时root也该出来了。
public void postOrder(TreeNode root) {
  Stack<TreeNode> s = new Stack<TreeNode>();
  s.push(root);
  TreeNode prev = null;
  while (!s.isEmpty()) {
    TreeNode curr = s.peek();
    if (prev == null || prev.left == curr || prev.right == curr) { // top down
      if (curr.left != null)
        s.push(curr.left);
      else if (curr.right != null)
        s.push(curr.right);
      else {// is leaf
        popAndPrint(s, curr);
      }
    } else if (prev == curr.left) { // from left child to parent
      if (curr.right != null)
        s.push(curr.right);
      else {
        popAndPrint(s, curr);
      }
    } else { // prev.right == curr, from right child to parent
      popAndPrint(s, curr);
    }
    prev = curr;
  }
}
private void popAndPrint(Stack<TreeNode> s, TreeNode curr) {
  System.out.print(curr.val + ", ");
  s.pop();
}

这个没想到用stack,还傻乎乎的用一种括号配对的方法做,结果设了l1, l2, l3, r1, r2, r3六个变量,然后发现解决不了([)]这种交错的invalid问题。无奈之下看答案,原来一个stack轻松搞定。其实仔细想想,valid的前提条件是“不会出现(]这种不配的抱在一起“的情况,所以当扫到右半边时,一个stack直接比较前一个是不是自己家的左半就好了。

 

public boolean isValid(String s) {
  Stack<Character> stack = new Stack<Character>();
  for (int i = 0; i < s.length(); i++) {
    char c = s.charAt(i);
    switch (c) {
    case '(':
    case '{':
    case '[':
      stack.push(c);
      break;
    case ')':
      if (stack.isEmpty() || stack.pop() != '(')
        return false;
      break;
    case '}':
      if (stack.isEmpty() || stack.pop() != '{')
        return false;
      break;
    case ']':
      if (stack.isEmpty() || stack.pop() != '[')
        return false;
      break;
     }
   }
   return stack.isEmpty();
}