67. Add Binary
真不知道String builder还有reverse方法。。。本来都准备用Stack了。。。
public class Solution { public String addBinary(String a, String b) { StringBuilder sb = new StringBuilder(); int i = a.length() - 1, j = b.length() - 1, promote = 0; while (i >=0 || j >= 0) { int sum = promote; if (i >= 0) sum += a.charAt(i--) - '0'; if (j >= 0) sum += b.charAt(j--) - '0'; sb.append(sum % 2); promote = sum / 2; } if (promote != 0) sb.append(promote); return sb.reverse().toString(); } }149. Max Points on a Line
这道题没有AC，因为double对这个test case：
[[0,0],[94911151,94911150],[94911152,94911151]]精度不够。
比较好的方法是产生最大公约数，再用x 和y一起作为key。
/** * 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 <= 1) { return points.length; } int max = 0; for (int i = 0; i < points.length - 1; i++) { int dup = 1; Map<Double, Integer> pointMap = new HashMap<Double, Integer>(); for (int j = 0; j < points.length; j++) { if(j==i) continue; if(points[i].y==points[j].y && points[i].x==points[j].x) { dup++; continue; } double grad = getGrad(points[i], points[j]); if (!pointMap.containsKey(grad)) { pointMap.put(grad, 1); } else { pointMap.put(grad, pointMap.get(grad) + 1); } } if (pointMap.size() == 0) max=max > dup ? max : dup; for (Double k : pointMap.keySet()) { max = max < pointMap.get(k) + dup ? pointMap.get(k) + dup: max; } } return max; } private double getGrad(Point a, Point b) { int xDiff = a.x - b.x; int yDiff = a.y - b.y; if (xDiff == 0) return Double.MAX_VALUE; return (double) yDiff / xDiff; } }