149. Max Points on a Line

Description

Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.
数学问题，一个二维坐标系上分布着若干个点，找出一条直线，使得这条直线过最多的点
Given two integers representing the numerator and denominator of a fraction, return the fraction in string format.
If the fractional part is repeating, enclose the repeating part in parentheses.
For example,
Given numerator = 1, denominator = 2, return “0.5”.
Given numerator = 2, denominator = 1, return “2”.
Given numerator = 2, denominator = 3, return “0.(6)”.
这道题给我的感觉有点像写匹配问题，考虑的情况特别的多…
Given an integer n, return the number of trailing zeroes in n!.

Solution

[leetcode 149] Max Points on a Line

过一条直线的点肯定都有相同的斜率，那么以一个点为基点，依次遍历其它的点，算出斜率，并存储在Map中，这样过基点和其它所有点组成的直线的斜率都存储在Map中了，Map中的value对应着该斜率相同的点得个数，找出最大值；对于基点，可以是任意一个点，这样就需要一层for来遍历。其中还涉及到斜率不存在的问题，需要另计，还有重复的点得问题。最后由于斜率是小数，对于double类型可能不能够表示，需要用到Java中的BigDecimal类（不用该类，leetcode中会有一个test过不了）。
参考：Accepted Java solution, easy to understand.
这是点类

class Point {
     int x;
     int y;
     Point() { x = 0; y = 0; }
     Point(int a, int b) { x = a; y = b; }
 }

代码如下：

public int maxPoints(Point[] points) {
    if(points.length <= 0) return 0;
    if(points.length <= 2) return points.length;
    int result = 0;
    for(int i = 0; i < points.length; i++){
        HashMap<BigDecimal, Integer> hm = new HashMap<BigDecimal, Integer>();
        int samex = 1;
        int samep = 0;
        for(int j = 0; j < points.length; j++){
            if(j != i){
                if((points[j].x == points[i].x) && (points[j].y == points[i].y)){
                    samep++;
                }
                if(points[j].x == points[i].x){
                    samex++;
                    continue;
                }
                BigDecimal dy=new BigDecimal(points[j].y - points[i].y);
                BigDecimal dx=new BigDecimal(points[j].x - points[i].x);
                BigDecimal k =dy.divide(dx, MathContext.DECIMAL128) ;
                if(hm.containsKey(k)){
                    hm.put(k,hm.get(k) + 1);
                }else{
                    hm.put(k, 2);
                }
                result = Math.max(result, hm.get(k) + samep);
            }
        }
        result = Math.max(result, samex);
    }
    return result;
}

[leetcode 166] Fraction to Recurring Decimal

题目让我们计算分子除以分母的结果，用字符串表示。我先想到的就是用除和取余来做，先对整数部分运算，如果第一次取余的结果为0，表示可以整除，直接返回就可以了；如果取余结果不为0，就需要进入到while循环中来判断是否有循环位，循环位的理解是对于一个序列，如果从i开始的元素到j结束的元素部分一直被后面的元素再重复，就说明该序列在循环，题目中要求在元素i前加上(，在j后面加上)，然后结束循环即可。
这里遇到了很多问题，比如每次添加到res时，应该都是正数，这就要求在最前面需要对分子分母作绝对值处理；作为绝对值处理后又会发现对于情况(0，-5)返回的结果竟然是-0，有需要作处理；对于leetcode惯例(-1，-2147483648)，我们知道int中负数的范围可以到-2147483648，但是正数的范围只能到2147483647，那没办法只能使用long整形了，总算完工，代码如下：

public static String fractionToDecimal(int numerator, int denominator) {
    StringBuilder res=new StringBuilder("");
    Map<Long,Integer> map=new HashMap<>();
    res.append(((numerator >=0) ^ (denominator >=0)) ? "-" : "");
    long num=Math.abs((long)numerator);
    long den=Math.abs((long)denominator);
    res.append(String.valueOf(num/den));
    num=num%den;
    if(num==0)return res.toString().equals("-0")?"0":res.toString();
    res.append(".");
    while (num!=0){
        map.put(num,res.length());
        num=num*10;
        res.append(String.valueOf(num/den));
        num=num%den;
        if(map.containsKey(num)){
            res.insert((int)(map.get(num)),'(');
            res.append(')');
            break;
        }
    }
    //System.out.println(res.toString());
    return res.toString();
}

最后一点需要所以下
String 字符串常量
StringBuffer 字符串变量（线程安全）
StringBuilder 字符串变量（非线程安全）比StringBuffer快
String相加会从新生成，而类是对当前操作。

[leetcode 172] Factorial Trailing Zeroes

问n!中有多少个0，这道题目就是找规律，只有5才有可能组成0，也就是说有多少个5的因子就可能有多少个0，那么为什么说可能呢，因为5只有和偶数才能生成0，那么0的个数由因子5的个数与偶数的个数的最小值决定。这里举个例子来理解：
5=1*5，10=2*5，15=3*5,20=4*5,25=5*5,30=6*5,...50=2*25=2*5*5,...
上面显示的是第一轮的情况，注意看和5乘的因子在递增，即又一轮会出现5的情况，即：
25=1*5*5,50=2*5*5,75=3*5*5,100=4*5*5,125=5*5*5,...
继续观察最前面和5乘的因子，又是一个递增，即又有一轮会出现5的情况，很显然需要递归解决，这样我们就有如下代码：

1	return n == 0 ? 0 : n / 5 + trailingZeroes(n / 5);