LeetCode 221-230

221. 最大正方形

暴力法：

class Solution {
    private boolean judge(char[][] matrix, int row, int col, int d) {
        for (int i = row; i < row + d; i++) {
            for (int j = col; j < col + d; j++) {
                if (matrix[i][j] == '0') {
                    return false;
                }
            }
        }
        return true;
    }

    public int maximalSquare(char[][] matrix) {
        if (matrix.length == 0) {
            return 0;
        }
        int row = matrix.length, col = matrix[0].length;
        int d = Math.min(row, col);
        while (d >= 0) {
            for (int i = 0; i < row - d + 1; i++) {
                for (int j = 0; j < col - d + 1; j++) {
                    if (judge(matrix, i, j, d)) {
                        return d * d;
                    }
                }
            }
            d--;
        }
        return 0;
    }
}

动态规划：
dp[i][j]代表以第i行第j列的格子作为正方形最右下顶点的正方形最大边长。

边界：
第一行和第一列的某个格子如果为0，则dp值为0。如果为1，则dp值为1。

转移方程：
matrix[i][j]如果等于1，则dp[i][j] 与它左边，上边，左上 三个格子有关。等于三者最小值+1。
matrix[i][j]如果等于0，则dp[i][j] = 0

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

222. 完全二叉树的节点个数

class Solution {
    public int countNodes(TreeNode root) {
        if (root == null) {
            return 0;
        }
        return countNodes(root.left) + countNodes(root.right) + 1;
    }
}

223. 矩形面积

用两个矩形面积相加再减去交集面积。

class Solution {
    private int getInter(int[] a, int[] b) {
        long res = (long)Math.min(a[1], b[1]) - (long)Math.max(a[0], b[0]);
        return res >= 0 ? (int)res : 0;
    }

    public int computeArea(int A, int B, int C, int D, int E, int F, int G, int H) {
        int[] rec1X = {A, C}, rec1Y = {B, D}, rec2X = {E, G}, rec2Y = {F, H};
        return (C - A) * (D - B) + (G - E) * (H - F) - getInter(rec1X, rec2X) * getInter(rec1Y, rec2Y);
    }
}

224. 基本计算器

中缀转后缀，再用后缀求值。

class Solution {
    Map<String, Integer> inPriority, outPriority;

    public Solution() {
        inPriority = new HashMap<>();//栈内优先级
        outPriority = new HashMap<>();//栈外优先级
        inPriority.put("#", 0);
        inPriority.put("(", 1);
        inPriority.put("*", 5);
        inPriority.put("/", 5);
        inPriority.put("+", 3);
        inPriority.put("-", 3);
        inPriority.put(")", 6);
        outPriority.put("#", 0);
        outPriority.put("(", 6);
        outPriority.put("*", 4);
        outPriority.put("/", 4);
        outPriority.put("+", 2);
        outPriority.put("-", 2);
        outPriority.put(")", 1);
    }

    public int calculate(String s) {
        List<String> infix = new ArrayList<>();//中缀表达式
        boolean flag = false;//只有遇到数字时，flag才为true，避免把初始0加进去。
        int num = 0;
        for (char c : s.toCharArray()) {
            if (c == ' ') {
                continue;
            } else if (Character.isDigit(c)) {
                flag = true;
                num = num * 10 + (c - '0');
            } else {
                if (flag == true) {
                    infix.add(String.valueOf(num));
                    flag = false;
                    num = 0;
                }
                infix.add(String.valueOf(c));
            }
        }
        if (flag == true) {
            infix.add(String.valueOf(num));
        }
        List<String> rpn = getRpn(infix);
        return (int) cal(rpn);
    }

    //中缀表达式转后缀
    public List<String> getRpn(List<String> infix) {
        Deque<String> stack = new ArrayDeque<>();
        stack.push("#");
        List<String> rpn = new ArrayList<>();
        for (String str : infix) {
            if ("(".equals(str) || ")".equals(str) || "+".equals(str) || "-".equals(str) ||
                    "*".equals(str) || "/".equals(str)) {
                if (comparePriority(stack.peek(), str) == 1) {
                    stack.push(str);
                } else if (comparePriority(stack.peek(), str) == 0) {
                    stack.pop();
                } else {
                    while (comparePriority(stack.peek(), str) == -1) {
                        String z = stack.pop();
                        rpn.add(z);
                    }
                    if (")".equals(str)) {
                        stack.pop();
                    } else {
                        stack.push(str);
                    }
                }
            } else {
                rpn.add(str);
            }
        }
        while (!stack.isEmpty()) {
            rpn.add(stack.pop());
        }
        rpn.remove(rpn.size() - 1);
        return rpn;
    }

    private int comparePriority(String in, String out) {
        if (outPriority.get(out) > inPriority.get(in)) {
            return 1;
        } else if (outPriority.get(out) == inPriority.get(in)) {
            return 0;
        } else {
            return -1;
        }
    }

    //后缀表达式求值
    public double cal(List<String> s) {
        Deque<Double> stack = new ArrayDeque<>();
        for (int i = 0; i < s.size(); i++) {
            double a, b;
            if (s.get(i).equals("+")) {
                b = stack.pop();
                a = stack.pop();
                stack.push(a + b);
                continue;
            } else if (s.get(i).equals("-")) {
                b = stack.pop();
                a = stack.pop();
                stack.push(a - b);
                continue;
            } else if (s.get(i).equals("*")) {
                b = stack.pop();
                a = stack.pop();
                stack.push(a * b);
                continue;
            } else if (s.get(i).equals("/")) {
                b = stack.pop();
                a = stack.pop();
                stack.push(a / b);
                continue;
            } else {
                stack.push(Double.valueOf(s.get(i)));
            }
        }
        return stack.peek();
    }
}

225. 用队列实现栈

两个队列实现栈：

class MyStack {

    Queue<Integer> q1, q2;

    /**
     * Initialize your data structure here.
     */
    public MyStack() {
        q1 = new LinkedList();
        q2 = new LinkedList();
    }

    /**
     * Push element x onto stack.
     */
    public void push(int x) {
        q1.offer(x);
        while (!q2.isEmpty()) {
            q1.offer(q2.poll());
        }
        Queue<Integer> temp = q1;
        q1 = q2;
        q2 = temp;
    }

    /**
     * Removes the element on top of the stack and returns that element.
     */
    public int pop() {
        return q2.poll();
    }

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

    /**
     * Returns whether the stack is empty.
     */
    public boolean empty() {
        return q2.isEmpty();
    }
}

一个队列实现栈:

class MyStack {
    Queue<Integer> q;
    /** Initialize your data structure here. */
    public MyStack() {
        q = new LinkedList<>();
    }

    /** Push element x onto stack. */
    public void push(int x) {
        int size = q.size();
        q.offer(x);
        for (int i = 0; i < size; i++) {
            q.offer(q.poll());
        }
    }

    /** Removes the element on top of the stack and returns that element. */
    public int pop() {
        return q.poll();
    }

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

    /** Returns whether the stack is empty. */
    public boolean empty() {
        return q.isEmpty();
    }
}

226. 翻转二叉树

后序遍历访问根结点的时候交换左右子树。

class Solution {
    public void postOrder(TreeNode root) {
        if (root == null) {
            return;
        }
        postOrder(root.left);
        postOrder(root.right);
        TreeNode temp = root.left;
        root.left = root.right;
        root.right = temp;
    }

    public TreeNode invertTree(TreeNode root) {
        postOrder(root);
        return root;
    }
}

227. 基本计算器 II

直接复制224题了。

class Solution {
    Map<String, Integer> inPriority, outPriority;

    public Solution() {
        inPriority = new HashMap<>();//栈内优先级
        outPriority = new HashMap<>();//栈外优先级
        inPriority.put("#", 0);
        inPriority.put("(", 1);
        inPriority.put("*", 5);
        inPriority.put("/", 5);
        inPriority.put("+", 3);
        inPriority.put("-", 3);
        inPriority.put(")", 6);
        outPriority.put("#", 0);
        outPriority.put("(", 6);
        outPriority.put("*", 4);
        outPriority.put("/", 4);
        outPriority.put("+", 2);
        outPriority.put("-", 2);
        outPriority.put(")", 1);
    }

    public int calculate(String s) {
        List<String> infix = new ArrayList<>();//中缀表达式
        boolean flag = false;
        int num = 0;
        for (char c : s.toCharArray()) {
            if (c == ' ') {
                continue;
            } else if (Character.isDigit(c)) {
                flag = true;
                num = num * 10 + (c - '0');
            } else {
                if (flag == true) {
                    infix.add(String.valueOf(num));
                    flag = false;
                    num = 0;
                }
                infix.add(String.valueOf(c));
            }
        }
        if (flag == true) {
            infix.add(String.valueOf(num));
        }
        List<String> rpn = getRpn(infix);
        return (int) cal(rpn);
    }

    //中缀表达式转后缀
    public List<String> getRpn(List<String> infix) {
        Deque<String> stack = new ArrayDeque<>();
        stack.push("#");
        List<String> rpn = new ArrayList<>();
        for (String str : infix) {
            if ("(".equals(str) || ")".equals(str) || "+".equals(str) || "-".equals(str) ||
                    "*".equals(str) || "/".equals(str)) {
                if (comparePriority(stack.peek(), str) == 1) {
                    stack.push(str);
                } else if (comparePriority(stack.peek(), str) == 0) {
                    stack.pop();
                } else {
                    while (comparePriority(stack.peek(), str) == -1) {
                        String z = stack.pop();
                        rpn.add(z);
                    }
                    if (")".equals(str)) {
                        stack.pop();
                    } else {
                        stack.push(str);
                    }
                }
            } else {
                rpn.add(str);
            }
        }
        while (!stack.isEmpty()) {
            rpn.add(stack.pop());
        }
        rpn.remove(rpn.size() - 1);
        return rpn;
    }

    private int comparePriority(String in, String out) {
        if (outPriority.get(out) > inPriority.get(in)) {
            return 1;
        } else if (outPriority.get(out) == inPriority.get(in)) {
            return 0;
        } else {
            return -1;
        }
    }

    //后缀表达式求值
    public int cal(List<String> s) {
        Deque<Integer> stack = new ArrayDeque<>();
        for (int i = 0; i < s.size(); i++) {
            int a, b;
            if (s.get(i).equals("+")) {
                b = stack.pop();
                a = stack.pop();
                stack.push(a + b);
                continue;
            } else if (s.get(i).equals("-")) {
                b = stack.pop();
                a = stack.pop();
                stack.push(a - b);
                continue;
            } else if (s.get(i).equals("*")) {
                b = stack.pop();
                a = stack.pop();
                stack.push(a * b);
                continue;
            } else if (s.get(i).equals("/")) {
                b = stack.pop();
                a = stack.pop();
                stack.push(a / b);
                continue;
            } else {
                stack.push(Integer.valueOf(s.get(i)));
            }
        }
        return stack.peek();
    }
}

228. 汇总区间

class Solution {
    public List<String> summaryRanges(int[] nums) {
        if (nums.length == 0) {
            return new ArrayList<>();
        }
        List<String> res = new ArrayList<>();
        int begin = 0, end = 0;
        for (int i = 0; i < nums.length - 1; i++) {
            if (nums[i] == nums[i + 1] - 1) {
                end++;
            } else {
                if (begin == end) {
                    res.add(nums[begin] + "");
                } else {
                    res.add(nums[begin] + "->" + nums[end]);
                }
                begin = i + 1;
                end = i + 1;
            }
        }
        if (begin == end) {
            res.add(nums[begin] + "");
        } else {
            res.add(nums[begin] + "->" + nums[end]);
        }
        return res;
    }
}

229. 求众数 II

时间复杂度On,空间复杂度On

class Solution {
    public List<Integer> majorityElement(int[] nums) {
        Set<Integer> set = new HashSet<>();
        int n = nums.length / 3;
        Map<Integer, Integer> map = new HashMap<>();
        for (int i : nums) {
            map.put(i, map.getOrDefault(i, 0) + 1);
            if (map.get(i) > n) {
                set.add(i);
            }
        }
        return new ArrayList<>(set);
    }
}

摩尔投票算法，最多可能有两个候选人，初始都设为第一个人，不断遍历，如果等于第一个候选人，第一个候选人票数count1加1，如果等于第二个候选人，第二个候选人票数count2加1，如果count1等于0，更换第一个候选人，如果count2等于0，更换第二个候选人，如果两个候选人的票数都不等于0且都不等于nums[i]，则两个候选人票数都减1。
最后答案可能有一个人也有可能有两个人，得把两个候选人都判断一下出现的次数才行。
时间复杂度On，空间复杂度O1:

class Solution {
    public List<Integer> majorityElement(int[] nums) {
        int res1 = nums[0], res2 = nums[0], count1 = 0, count2 = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == res1) {
                count1++;
            } else if (nums[i] == res2) {
                count2++;
            } else if (count1 == 0) {
                res1 = nums[i];
                count1 = 1;
            } else if (count2 == 0) {
                res2 = nums[i];
                count2 = 1;
            } else {
                count1--;
                count2--;
            }
        }
        count1 = 0;
        count2 = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == res1) {
                count1++;
            } else if (nums[i] == res2) {
                count2++;
            }
        }
        List<Integer> res = new ArrayList<>();
        if (count1 > nums.length / 3) {
            res.add(res1);
        }
        if (count2 > nums.length / 3) {
            res.add(res2);
        }
        return res;
    }
}

230. 二叉搜索树中第K小的元素

中序遍历得到有序的集合，然后直接找到第K小的元素。

class Solution {
    List<Integer> list = new ArrayList<>();

    public void inOrder(TreeNode root) {
        if (root == null) {
            return;
        }
        inOrder(root.left);
        list.add(root.val);
        inOrder(root.right);
    }

    public int kthSmallest(TreeNode root, int k) {
        inOrder(root);
        return list.get(k - 1);
    }
}