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.
答案
思路：时间复杂度O(n^3)的情况下是肯定可以算出结果的，那么意味着通过空间换时间应该是可以让时间复杂度达到O(n^2)，这是我自己发明的定律。首先定义静态内部类
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 |
static class Line { int k; int b; int denominator; Line(int k, int b, int denominator) { this.k = k; this.b = b; this.denominator = denominator; } @Override public boolean equals(Object o) { if (this == o) return true; if (o == null || getClass() != o.getClass()) return false; Line line = (Line) o; if(b*line.denominator != line.b*denominator) return false; if(k*line.denominator != line.k*denominator) return false; return true; } @Override public int hashCode() { int t = denominator; if(t == 0) t = 1; int result = k/t; result = 31 * result + b/t; return result; } } public static int maxPoints(Point[] points) { if(points == null) return 0; if(points.length == 1 || points.length == 2) return points.length; Map<Line, Set<Point>> map = new HashMap<>(); for(int i = 0; i < points.length; i++) { for(int j = i + 1; j < points.length; j++) { Point m = points[i]; Point n = points[j]; int k = n.y - m.y; int b = n.x * m.y - m.x * n.y; int denominator = n.x - m.x; if(denominator == 0) { k = Integer.MAX_VALUE; b = n.x; } Line line = new Line(k, b, denominator); if(map.containsKey(line)) { map.get(line).add(m); map.get(line).add(n); } else { Set<Point> set = new HashSet<>(); set.add(m); set.add(n); map.put(line, set); } } } int max = 0; for(Map.Entry<Line, Set<Point>> entry : map.entrySet()) { max = Math.max(max, entry.getValue().size()); } return max; } |
Trapping Rain Water
题目
Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.
For example, Given [0,1,0,2,1,0,1,3,2,1,2,1], return 6.
答案
思路：若在最尾端添加一个无限高的bar，则整个题目变的十分容易：由于最后一个bar是无限高的，所以盛下水后的形状就是一个梯度上升的阶梯状，只需要扫面一遍，遇到比当前最大值小的则表示可以盛下水。现在的问题是，没有这么一块无限高的bar，那怎么办？很简单，扫面一遍，找出最高的bar，然后以此为分界线，看成是2个带有无限高bar的阶梯状就OK了。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
public int trap(int[] A) { if(A == null || A.length < 3) return 0; int maxPos = 0; for(int i = 1; i < A.length; i++) { maxPos = A[i] > A[maxPos] ? i : maxPos; } int sum = 0; int nPos = 0; for(int i = 0; i < maxPos; i++) { if(A[i] <= A[nPos]) sum += A[nPos] - A[i]; else nPos = i; } nPos = A.length - 1; for(int i = A.length - 1; i > maxPos; i--) { if(A[i] <= A[nPos]) sum += A[nPos] - A[i]; else nPos = i; } return sum; } |
Word Break II
题目
Given a string s and a dictionary of words dict, add spaces in s to construct a sentence where each word is a valid dictionary word.
Return all such possible sentences.
For example, given
s = "catsanddog",
dict = ["cat", "cats", "and", "sand", "dog"].
A solution is ["cats and dog", "cat sand dog"].
答案
思路：没有思路，递归+一个
吐槽：采用前序遍历+深度优先方式会出现Time Limit Exceeded，原因是有一个测试用例是：
那么问题来了：要是有这样的用例该怎么办？（吐槽能让你吐出好程序么。。）
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 |
private Stack<String> pool = new Stack<>(); private List<String> list = new ArrayList<>(); public List<String> wordBreak(String s, Set<String> dict) { if(s == null || s.equals("")) return null; String word = ""; for(int i = s.length() - 1; i > -1; i--) { word = s.charAt(i) + word; if(dict.contains(word) && i == 0) { String w = ""; for(String str : pool) { w = str + " " + w; } w = word + " " + w; list.add(w.trim()); if(!pool.isEmpty())pool.pop(); } else if(dict.contains(word) && i != 0) { pool.push(word); wordBreak(s.substring(0, i), dict); } else if(!dict.contains(word) && i == 0) { if(!pool.isEmpty())pool.pop(); } } return list; } |
இдஇ #求何总添加留言表情#
All of these articles have saved me a lot of heehscdaa.
Voor je lijf, niet je gezicht! Deze scrub is juist zo mild dat je hem elke dag kunt gebruiken. Niet dat ik dagelijks scrub, want mijn douche staat te vol met allemaal fijne dopuueschllen ;)De tube bevat 200 ml, minder klein dan ie lijkt dus :)