LeetCode(1) -- 226, 231, 232

LeetCode Day 1:

P226. Invert Binary Tree (Easy)

        4
       /  \
      2    7
     / \  / \
    1   3 6  9

        4
       / \
      7   2
     / \ / \
    9  6 3  1

我的思路：

用递归把每个节点的左右子节点对换。

我的代码：

public class E_226_InvertBinaryTree {
    public TreeNode invertTree(TreeNode root) {
        TreeNode temp;
        if (root != null) {
            temp = root.left;
            root.left = root.right;
            root.right = temp;
            invertTree(root.left);
            invertTree(root.right);
        }
        return root;
    }
}

题比较简单，超过100%

答案

public TreeNode invertTree(TreeNode root) {
    if (root == null) {
        return null;
    }
    TreeNode right = invertTree(root.right);
    TreeNode left = invertTree(root.left);
    root.left = right;
    root.right = left;
    return root;
}

P231. Power of Two (Easy)

一个整数，判断它是不是2的幂。

我的思路：

一直除以2，只要出现余数就返回false。

我的代码：

public class E_231_PowerOfTwo {
    public boolean isPowerOfTwo(int n) {
        while (n != 1) {
            if (n % 2 != 0) {
                return false;
            }
            n = n / 2;
        }
        return true;
    }
}

超时了。。。

突然想到位运算，2的倍数的二进制表示，一定是一个以1开头，后面全是0的形式。比如2是10，4是100，8是1000。。。

改了代码：

public class E_231_PowerOfTwo {
    public static boolean isPowerOfTwo(int n) {
        while((n & 1) == 0){
            n = n >> 1;
        }
        return n == 1;
    }
}

自以为绝妙了，结果又超时了。。。

查了下知乎, n & (n-1)将n唯一的一个1消去，应该返回0。

再一次改进代码：

public class E_231_PowerOfTwo {
    public static boolean isPowerOfTwo(int n) {
        if (n <= 0) {
            return false;
        }
        return (n & (n-1)) == 0;
    }
}

答案：

class Solution {
    public boolean isPowerOfTwo(int n) {
        if(n==0) return false;
        long x = (long) n;
        return (x == ((~x + 1) & x));
    }
}

思路差不多：取反，加1，跟自己做“和”运算，应该还等于自己。

比如1000，取反0111，加1变成1000，再跟1000做和还是1000。

P232. Implement Queue using Stacks (Easy)

用Stack实现Queue

我的思路：

准备两个stack,第二个作为暂存区，每次push, 都把第一个stack暂存到第二个stack, 然后把新加的值放到最底下，再把stack2里的数搬运回来。

public class E_232_ImplementQueueUsingStacks {
    /** Initialize your data structure here. */
    private Stack<Integer> stack1 = new Stack<>();
    private Stack<Integer> stack2 = new Stack<>();
    public E_232_ImplementQueueUsingStacks() {

    }

    /** Push element x to the back of queue. */
    public void push(int x) {
        if (stack1.empty()){
            stack1.push(x);
        } else {
            while (!stack1.empty()) {
                stack2.push(stack1.pop());
            }
            stack1.push(x);
            while (!stack2.empty()) {
                stack1.push(stack2.pop());
            }
        }
    }

    /** Removes the element from in front of queue and returns that element. */
    public int pop() {
        return stack1.pop();
    }

    /** Get the front element. */
    public int peek() {
        return stack1.peek();
    }

    /** Returns whether the queue is empty. */
    public boolean empty() {
        return stack1.empty();
    }

}

超过31.5%，比较慢。

答案：

class MyQueue {

    /** Initialize your data structure here. */
    private Stack<Integer> s1 = new Stack<>();
    private Stack<Integer> s2 = new Stack<>();
    private int front;
    public MyQueue() {

    }

    /** Push element x to the back of queue. */
    public void push(int x) {
        if (s1.empty())
            front = x;
        s1.push(x);
    }

    /** Removes the element from in front of queue and returns that element. */
    public int pop() {
        if (s2.isEmpty()) {
            while (!s1.isEmpty()) {
                s2.push(s1.pop());
            }
        }
        return s2.pop();
    }

    /** Get the front element. */
    public int peek() {
        if (!s2.isEmpty()) {
            return s2.peek();
        }
        return front;
    }

    /** Returns whether the queue is empty. */
    public boolean empty() {
        return s1.isEmpty() && s2.isEmpty();
    }
}

/**
 * Your MyQueue object will be instantiated and called as such:
 * MyQueue obj = new MyQueue();
 * obj.push(x);
 * int param_2 = obj.pop();
 * int param_3 = obj.peek();
 * boolean param_4 = obj.empty();
 */

充分利用两个Stack, push时永远往第一个stack里放，pop时永远从第二个stack里拿，直到拿空，再把第一个stack里的东西缓存到第二个stack里面。这样平均时间复杂度就降为O(1)。