LeetCode特集----Marth

7. Reverse Integer
Reverse digits of an integer.
Example1: x = 123, return 321 Example2: x = -123, return -321
Have you thought about this? Here are some good questions to ask before coding. Bonus points for you if you have already thought through this!
If the integer’s last digit is 0, what should the output be? ie, cases such as 10, 100.
Did you notice that the reversed integer might overflow? Assume the input is a 32-bit integer, then the reverse of 1000000003 overflows. How should you handle such cases?
For the purpose of this problem, assume that your function returns 0 when the reversed integer overflows. 考え方:オーバーフローを処理することが肝心です.

public class Solution {
    public int reverse(int x) {
        boolean isNegtive = false;
        if(x < 0) {
            if(x == Integer.MIN_VALUE)
                return 0;
            x = -x;
            isNegtive = true;
        }

        int ret = 0;
        while(x != 0) {
            int i = x % 10;
            x /= 10;
            if(ret > Integer.MAX_VALUE / 10) {
                return 0;
            } 
            else if(ret == Integer.MAX_VALUE / 10 && 
                    ((isNegtive && i > -(Integer.MIN_VALUE % 10)) || (!isNegtive && i > Integer.MAX_VALUE % 10))) {
                return 0;
            }
            ret = ret * 10 + i;
        }
        return isNegtive ? -ret : ret;
    }
}

50. Pow(x, n)
考え方:この問題はいろいろな状況を考慮して、nがint型の最小の負数であれば、絶対値を取るとオーバーフローします.

public class Solution {
    public double myPow(double x, int n) {
        double ans = 1;
        long absN = Math.abs((long)n);
        while(absN > 0) {
            if((absN&1)==1) ans *= x;
            absN >>= 1;
            x *= x;
        }
        return n < 0 ?  1/ans : ans;
    }
}

149. Max Points on a Line
Given n points on a 2D plane, find the maximum number of points that lie on the same straight line. 構想:A line is determined by two factors,say y=ax+b.If two points(x 1,y 1)(x 2,y 2)are on the same line(Of course).Consider the gap between two points.We have (y2-y1)=a(x2-x1),a=(y2-y1)/(x2-x1) a is a rational, b is canceled since b is a constant. If a third point (x3,y3) are on the same line. So we must have y3=ax3+b. Thus,(y3-y1)/(x3-x1)=(y2-y1)/(x2-x1)=a. Since a is a rational, there exists y0 and x0, y0/x0=(y3-y1)/(x3-x1)=(y2-y1)/(x2-x1)=a. So we can use y0&x0 to track a 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.length < 3) return points.length;

        Map> map = new HashMap<>();
        int ret = 0;
        for(int i=0; iint overlap = 0, max = 0;
            for(int j=i+1; jint x = points[j].x - points[i].x;
                int y = points[j].y - points[i].y;
                if(x == 0 && y == 0) {
                    overlap++;
                    continue;
                }
                int gcd = generateGCD(x, y);
                if(gcd != 0) {
                    x /= gcd;
                    y /= gcd;
                }

                if(map.containsKey(x)) {
                    if(map.get(x).containsKey(y)) {
                        map.get(x).put(y, map.get(x).get(y)+1);
                    }
                    else {
                        map.get(x).put(y, 1);
                    }
                }
                else {
                    Map subMap = new HashMap<>();
                    subMap.put(y, 1);
                    map.put(x, subMap);
                }
                max = Math.max(max, map.get(x).get(y));
             }
             ret = Math.max(ret, max+overlap+1);
        }
        return ret;
    }

    private int generateGCD(int a, int b) {
        if(b == 0) return a;
        else return generateGCD(b, a%b);
    }
}

150. Evaluate Reverse Polish Notation
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:["2","1","+","3",""""-->((2+1)3)->9["4","13","5","/","+"->(4+(13/5)->6考え方:stack.非加算乗算に遭遇するとスタックが圧縮され、オペレータに遭遇するとスタックの上部の2つの要素が計算され、結果がスタックに格納されます.

 public class Solution {
    public int evalRPN(String[] tokens) {
        Deque stack = new LinkedList<>();
        for(String token : tokens) {
            switch (token) {
                case "+":
                    stack.push(stack.pop() + stack.pop());
                    break;
                case "-":
                    stack.push(-stack.pop() + stack.pop());
                    break;
                case "*":
                    stack.push(stack.pop() * stack.pop());
                    break;
                case "/":
                    int a = stack.pop(), b = stack.pop();
                    stack.push(b / a);
                    break;
                default:
                    stack.push(Integer.parseInt(token));
            }
        }
        return stack.pop();
    }
}