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;
    }
}

Combination Sum III leetcode

Find all possible combinations of k numbers that add up to a number n, given that only numbers from 1 to 9 can be used and each combination should be a unique set of numbers.

Ensure that numbers within the set are sorted in ascending order.

Example 1:

Input: k = 3, n = 7

Output:

[[1,2,4]]

Example 2:

Input: k = 3, n = 9

Output:

[[1,2,6], [1,3,5], [2,3,4]]

public class Solution {
    public List<List<Integer>> combinationSum3(int k, int n) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        if (k <= 0) {
            return res;
        }
        List<Integer> tem = new ArrayList<Integer>();
        helper(res, tem, k, n, 1, 0, 0);
        return res;
    }
    public void helper(List<List<Integer>> res, List<Integer> tem, int k, int n, int pos, int sum, int count) {
        if (sum == n && count == k) {
            res.add(new ArrayList<Integer>(tem));
            return;
        }

        for (int i = pos; i <= 9; i++) {
            tem.add(i);
            helper(res, tem, k, n, i + 1, sum + i, count+1);
            tem.remove(tem.size() - 1);
        }
    }
}

Kth Largest Element in an Array leetcode

Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element.

For example,
Given [3,2,1,5,6,4] and k = 2, return 5.
用quick selecte的方法

//pivot为left
public class Solution {
    public int findKthLargest(int[] nums, int k) {
        return find(nums, 0, nums.length - 1, nums.length - k);
    }
    public int find (int[] nums, int i, int j, int k) {
        int left = i;
        int right = j;
        int pivot = nums[left];
        while (left < right) {//为< 不是<=
            while (left < right && nums[right] > pivot) {//必须先right--
                right--;
            }
            while (left < right && nums[left] <= pivot) {
                left++;
            }
            
            swap(nums, left, right);
            
        }
        swap(nums,right, i);
        if (left == k) {
            return nums[k];
        } else if (left < k) {
            return find(nums, left + 1, j, k);
        } else {
            return find(nums, i, left - 1, k);
        }
    }
    public void swap(int[] nums, int i, int j) {
        int tem = nums[i];
        nums[i] = nums[j];
        nums[j] = tem;
    }
}
//pivot为right
public class Solution {
    public int findKthLargest(int[] nums, int k) {
        return find(nums, 0, nums.length - 1, nums.length - k);
    }
    public int find (int[] nums, int i, int j, int k) {
        int left = i;
        int right = j;
        int pivot = nums[right];
        while (left < right) {
            while (left < right && nums[left] < pivot) {//右pivot时候先左边 反之亦然
                left++;
            }
            while (left < right && nums[right] >= pivot) {
                right--;
            }
            if (left < right) {//此判定可有可无, 因为不会出现left> right情况
                swap(nums, left, right);
            }
            
        }
        swap(nums,left, j);
        if (left == k) {
            return nums[k];
        } else if (left < k) {
            return find(nums, left + 1, j, k);
        } else {
            return find(nums, i, left - 1, k);
        }
    }
    public void swap(int[] nums, int i, int j) {
        int tem = nums[i];
        nums[i] = nums[j];
        nums[j] = tem;
    }
}

Priority Queue的解法

public class Solution {
    public int findKthLargest(int[] nums, int k) {
        PriorityQueue<Integer> queue = new PriorityQueue<Integer>();
        for (int i : nums) {
            queue.offer(i);
        }
        for (int i = 0; i < nums.length - k ; i++) {
            queue.poll();
        }
        return queue.peek();
    }
}