Kth Smallest Element in a BST leetcode

Given a binary search tree, write a function kthSmallest to find the kth smallest element in it.

Note: 
You may assume k is always valid, 1 ≤ k ≤ BST's total elements.

非递归方法: 类似线序遍历, 每访问到一个最小的count++, 直到count == k

public class Solution {
    public int kthSmallest(TreeNode root, int k) {
        Stack<TreeNode> stack = new Stack<TreeNode>();
        TreeNode node = root;
        int count = 0;
        while (!stack.isEmpty() || node != null) {
            if (node != null) {
                stack.push(node);
                node = node.left;
            } else {
                TreeNode tem = stack.pop();
                count++;
                
                if (count == k) {
                    return tem.val;
                }
                node = tem.right;
            }
        }
        return 0;
    }
}

递归方法:

public class Solution {
    public int kthSmallest(TreeNode root, int k) {
        int count = count(root.left);
        if (count + 1 > k) {
            return kthSmallest(root.left, k);
        } else if (count + 1 < k) {
            return kthSmallest(root.right, k - count- 1);
        } else {
            return root.val;
        }
    }
    public int count(TreeNode root) {
        if (root == null) {
            return 0;
        }
        return count(root.left) + count(root.right) + 1;
    }
}

Majority Element II leetcode

Given an integer array of size n, find all elements that appear more than ⌊ n/3 ⌋ times. The algorithm should run in linear time and in O(1) space.

public class Solution {
    public List<Integer> majorityElement(int[] nums) {
        List<Integer> res = new ArrayList<Integer>();
        if (nums == null || nums.length == 0) {
            return res;
        }
        int n1 = 0, n2 = 0;
        int count1 = 0, count2 = 0;
        for (int s : nums) {
            if (count1 == 0) {
                n1 = s;
                count1++;
            } else if (count2 == 0 && n1 != s) {
                n2 = s;
                count2++;
            } else if (s == n1) {
                count1++;
            } else if (s == n2) {
                count2++;
            } else {
                count1--;
                count2--;
            }
        }
        count1 = 0;
        count2 = 0;
        for (int s  : nums) {
            if (s == n1) {
                count1++;
            } else if (s == n2) {
                count2++;
            }
        }
        if (count1 > nums.length / 3) {
            res.add(n1);
        }
        if (count2 > nums.length / 3) {
            res.add(n2);
        }
        return res;
    }
}

Basic Calculator II leetcode

Implement a basic calculator to evaluate a simple expression string.

The expression string contains only non-negative integers, +, -, *, / operators and empty spaces . The integer division should truncate toward zero.

You may assume that the given expression is always valid.

Some examples:

"3+2*2" = 7
" 3/2 " = 1
" 3+5 / 2 " = 5

这回没有括号, sign记录符号, num记录数字, 每当遇到新的符号时候入栈数字 更新sign

public class Solution {
    public int calculate(String s) {
        s = s.replace(" ", "");
        Stack<Integer> stack = new Stack<Integer>();
        char sign = '+';
        int num = 0 ;
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (Character.isDigit(c)) {
                num = num* 10 + c - '0';
            }
            if (!Character.isDigit(c) || i == s.length() - 1) {
                if (sign == '+') {
                    stack.push(num);
                } else if (sign == '-'){
                    stack.push(-num);
                } else if (sign == '*') {
                    int m = stack.pop();
                    stack.push(m * num);
                } else if (sign == '/') {
                    int m = stack.pop();
                    stack.push(m/num);
                }
                num = 0;
                sign = c;
            }
        }
        int res = 0;
        for (int i : stack) {
            res += i;
        }
        return res;
    }
}

Implement Stack using Queues leetcode

mplement the following operations of a stack using queues.

• push(x) -- Push element x onto stack.
• pop() -- Removes the element on top of the stack.
• top() -- Get the top element.
• empty() -- Return whether the stack is empty.

Notes:

• You must use only standard operations of a queue -- which means only push to back, peek/pop from front, size, and is empty operations are valid.
• Depending on your language, queue may not be supported natively. You may simulate a queue by using a list or deque (double-ended queue), as long as you use only standard operations of a queue.
• You may assume that all operations are valid (for example, no pop or top operations will be called on an empty stack).

方法1: push() O(1), pop() O(n), peek() O(n) 用两个queue 来实现, 每次pop事后都把q1前边的都推入q2中, 最后一个出列, 然后q1, q2互换, top时候同理, 只是最后一个元素也入列q2.

class MyStack {
    Queue<Integer> q1 = new LinkedList<Integer>();
    Queue<Integer> q2 = new LinkedList<Integer>();
    public void push(int x) {
        q1.offer(x);
    }

    // Removes the element on top of the stack.
    public void pop() {
        while (q1.size() > 1) {
            q2.offer(q1.poll());
        }
        q1.poll();
        Queue tem = q1;
        q1 = q2;
        q2 = tem;
    }

    // Get the top element.
    public int top() {
        while (q1.size() > 1) {
            q2.offer(q1.poll());
        }
        int res = q1.peek();
        q2.offer(q1.poll());
        Queue tem = q1;
        q1 = q2;
        q2 = tem;
        return res;
    }

    // Return whether the stack is empty.
    public boolean empty() {
        return q1.isEmpty();
    }
}

方法2: push() O(n), pop() O(1), peek() O(1) 用两个queue 来实现, 每次push时候都入列q2, 然后再把q1的元素都一一入列q2直到q1空为止, 然后q1 q2互换. 这样q1内元素的出列顺序和stack中的顺序相同 所以pop 和 top功能就是q1的 poll() 和peek()

class MyStack {
    Queue<Integer> q1 = new LinkedList<Integer>();
    Queue<Integer> q2 = new LinkedList<Integer>();
    public void push(int x) {
        q2.offer(x);
        while (!q1.isEmpty()) {
            q2.offer(q1.poll());
        }
        Queue tem = q1;
        q1 = q2;
        q2 = tem;
    }

    // Removes the element on top of the stack.
    public void pop() {
        q1.poll();
    }

    // Get the top element.
    public int top() {
        
        return q1.peek();
    }

    // Return whether the stack is empty.
    public boolean empty() {
        return q1.isEmpty();
    }
}

Basic Calculator leetcode

Implement a basic calculator to evaluate a simple expression string.

The expression string may contain open ( and closing parentheses ), the plus + or minus sign -, non-negative integers and empty spaces .

You may assume that the given expression is always valid.

Some examples:

"1 + 1" = 2
" 2-1 + 2 " = 3
"(1+(4+5+2)-3)+(6+8)" = 23

因为只有加减法 我们只要考虑括号的问题, 如果括号前面是+号, 括号内运算并不改变, 之间做加减法并入结果中, 如果括号前面是-号, 那么括号内加法, 结果就要减去相应的数. 所以我们用sign来记录数字前面的加减号, stack内部存括号外面的加减号, 这样每次运算只需要num*sign*stack.peek()
用stack和一个sign来记录符号,遇到加号 sign为1, 遇到减号sign 为-1, 遇到左括号 计算当前的符号(sign* stack.peek()) 压入栈内, 遇到右括号 出栈, 遇到数字把数字* sign* stack.peek()加入结果中

public class Solution {
    public int calculate(String s) {
        Stack<Integer> stack = new Stack<Integer>();
        stack.push(1);// 先压入一个1进栈，可以理解为有个大括号在最外面

        s = s.replace(" ", "");
        int sign = 1, res = 0;
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == '+') {
                sign = 1;
            } else if (c == '-') {
                sign = -1;
            } else if (c == '(') {
                stack.push(sign * stack.peek());
                sign = 1;
            } else if (c == ')') {
                stack.pop();
            } else {
                int num = 0;
                while (i < s.length() && Character.isDigit(s.charAt(i))) {
                    num = num * 10 + s.charAt(i) - '0';
                    i++;
                }
                res += num * sign * stack.peek();
                i--;
            }
        }
        return res;
    }
}

Count Complete Tree Nodes leetcode

Given a complete binary tree, count the number of nodes.

Definition of a complete binary tree from Wikipedia:
In a complete binary tree every level, except possibly the last, is completely filled, and all nodes in the last level are as far left as possible. It can have between 1 and 2h nodes inclusive at the last level h.
先找到从root出发到最左和最右的距离, 如果距离相等说明最后一行自左到右都有node 总共2^n - 1个
如果不相等, 递归的找出左右不同的敌方和个数

public class Solution {
    public int countNodes(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int left = findleft(root);
        int right = findright(root);
        if (left == right) {
            return (2<<left - 1) - 1;//减号优先等级大于<<
        } else {
            return countNodes(root.left) + countNodes(root.right) + 1;
        }
    }
    public int findleft(TreeNode root) {
        int res = 0;
        while (root != null) {
            root = root.left;
            res++;
        }
        return res;
    }
    public int findright(TreeNode root) {
        int res = 0;
        while (root != null) {
            root = root.right;
            res++;
        }
        return res;
    }
}

Maximal Square

Given a 2D binary matrix filled with 0's and 1's, find the largest square containing all 1's and return its area.

For example, given the following matrix:

1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0

Return 4.

public class Solution {
    public int maximalSquare(char[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0] == null || matrix[0].length == 0) {
            return 0;
        }
        int m = matrix.length;
        int n = matrix[0].length;
        int[][] dp = new int[m][n];
        int max = 0;
        for (int i = 0; i < m; i++) {
            if (matrix[i][0] == '1') {
                dp[i][0] = 1;
            }
        }
        for (int i = 0; i < n; i++) {
            if (matrix[0][i] == '1') {
                dp[0][i] = 1;
            }
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (matrix[i][j] == '1') {
                    dp[i][j] = Math.min(dp[i - 1][j], Math.min(dp[i - 1][j - 1], dp[i][j - 1])) + 1; 
                } else {
                    dp[i][j] = 0;
                }
            }
        }
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (dp[i][j] > max) {
                    max = dp[i][j];
                }
            }
        }
        return max * max;
    }
}