2019.7.1***习记录

Given a binary tree, find its minimum depth.The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf nodes.

public class Solution{
    public int run(TreeNode root){
        if(root == null)
            return 0;
        if(root.left == null && root.right == null)
            return 1;
        if(root.left == null)
            return run(root.right) + 1;
        if(root.right == null)
            return run(root.left) + 1;
        int left = run(root.left) + 1;
        int right = run(root.right) + 1;
        return Math.min(left , right);
    }
}

Evaluate the value of an arithmetic expression in Reverse Polish Notation.

Valid operators are+,-,*,/. Each operand may be an integer or another expression.

Some examples:

import java.util.Stack;
public class Solution {
    public int evalRPN(String[] tokens) {
        if(tokens == null || tokens.length == 0){
            return 0;
        }
        Stack<Integer> stack = new Stack<Integer>();
        for(int i = 0;i < tokens.length; i++){
            if(tokens[i].equals("+")){
                int num1 = stack.pop();
                int num2 = stack.pop();
                int res = num2 + num1;
                stack.push(res);
            }else if(tokens[i].equals("-")){
                int num1 = stack.pop();
                int num2 = stack.pop();
                int res = num2 - num1;
                stack.push(res);
            }else if(tokens[i].equals("*")){
                int num1 = stack.pop();
                int num2 = stack.pop();
                int res = num2 * num1;
                stack.push(res);
            }else if(tokens[i].equals("/")){
                int num1 = stack.pop();
                int num2 = stack.pop();
                int res = num2 / num1;
                stack.push(res);
            }else{int num = Integer.parseInt(tokens[i]);
            stack.push(num);
             }
        }
        return stack.size() == 1 ? stack.pop() : 0;
    }
}

Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.

/**
 * Definition for a point.
 * class Point {
 *     int x;
 *     int y;
 *     Point() { x = 0; y = 0; }
 *     Point(int a, int b) { x = a; y = b; }
 * }
 */
public class Solution {
    public int maxPoints(Point[] points) {
        if(points == null || points.length == 0 || points.length < 3){
            return points.length;
        }
        int res = 0;
        for(int i = 1;i < points.length;i++){
            int count = 0;
            long a = points[i].x;
            long b = points[i].y;
            long dx = a - points[i - 1].x;
            long dy = b - points[i - 1].y;
            if(dx == 0 && dy == 0){
                for(int j = 0;j < points.length;j++){
                    if(points[j].x == a && points[j].y == b){
                        count++;
                    }
                }
            }else{
                for(int j = 0;j < points.length;j++){
                    if((points[j].x - a)*dy == (points[j].y - b)*dx){
                        count++;
                    }
                }
            }
            res = Math.max(res , count);
        }
        return res;
    }
}