版权声明:本文为博主原创文章,未经博主允许不得转载。 https://cloud.tencent.com/developer/article/1434796
详细代码可以fork下Github上leetcode项目,不定期更新。
题目摘自leetcode:
很有意思的一道题,逆时针走,问会不会出现相交的情况,看了很多题解,只给出了计算的方法,令人含糊。
这是一道模式题,只要走到一定的步数,后续判断的逻辑是一套,所以判断存在相交的有限种情况即可,水平有限,不太好证,靠想象。
说说此题真正的思考过程吧,在模拟行走过程中,我们已经能判断一些基本条件了。比如:
现在考虑四条边的情况:
四条变可以相交,与原点重合或者相交,所以遇到此情况返回false。此时,第五条边的走向貌似就只剩下三种情况了,在第一条边的左侧和右侧,还有就是在第一条边重合的位置!
见图2,这是一种self cross的情况,但如果遇到左侧和右侧该怎么办呢?
起码遇到第五条边在第一条边左侧的情况时,我们可以考虑把第一条边删除!【关键的步骤】,删除第一条边之后,后续的判断逻辑和之前就完全重合了!所以它能适用于第六条边,第七条边的判断。。。
当遇到第五条边在右侧的情形时,我们就来到了图3,此时还存在一种相交的情况,正是图3所给的情况,如果遇到此情况,返回false。
嘿,除此之外,第七条边以后的任何一条边都不可能再和第一条边相交了!不信你画一个出来试试。所以可以安全删除第一条边,算法的模式开始了,此时所有的情况,都以第二条边为起点,进行交点判断,这就证明了算法的正确性。
代码如下:
public boolean isSelfCrossing(int[] x) {
if (x.length <= 3) return false;
for (int l = 3; l < x.length; ++l){
if (x[l] >= x[l-2] && x[l-1] <= x[l-3]) return true;
if (l >= 4){
if (x[l] + x[l-4] >= x[l-2] && x[l-1] == x[l-3]) return true;
}
if (l >= 5){
if (x[l-2] >= x[l-4] && x[l] + x[l-4] >= x[l-2] && x[l-1] + x[l-5] >= x[l-3] && x[l-1] <= x[l-3]) return true;
}
}
return false;
}
递归,没什么好说的,思路很简单,关键在于简化代码。自己的代码略复杂,如下:
private final String[] LESS_THAN_20 = {"Zero", "One", "Two", "Three", "Four", "Five", "Six", "Seven", "Eight", "Nine", "Ten", "Eleven", "Twelve", "Thirteen", "Fourteen", "Fifteen", "Sixteen", "Seventeen", "Eighteen", "Nineteen"};
private final String[] TENS = {"", "Ten", "Twenty", "Thirty", "Forty", "Fifty", "Sixty", "Seventy", "Eighty", "Ninety"};
private final int[] BIT = {1000000000,1000000,1000,100};
public String numberToWords(int num) {
if (num >= 0 && num < 100){
if (num >= 0 && num < 20){
return LESS_THAN_20[num];
}
if (num >= 20){
String ans = TENS[num / 10 ] + " " + LESS_THAN_20[num % 10];
if (num % 10 == 0){
return ans.substring(0, ans.length()-5);
}
return ans;
}
}
String nums = Integer.toString(num);
int n = nums.length();
StringBuilder sb = new StringBuilder();
if (n == 10){
sb.append(numberToWords(num / BIT[0]) + " Billion ");
}
if (n >= 7 && num / BIT[1] % 1000 != 0){
sb.append(numberToWords(num / BIT[1] % 1000) + " Million ");
}
if (n >= 4 && num / BIT[2] % 1000 != 0){
sb.append(numberToWords(num / BIT[2] % 1000) + " Thousand ");
}
if (n >= 3 && num / BIT[3] % 10 != 0){
sb.append(numberToWords(num / BIT[3] % 10) + " Hundred ");
}
sb.append(numberToWords(num % 100));
return sb.toString().replace(" Zero", "");
}
对于一些100,1000,1000000这种测试用例,我的代码需要加入很多不必要的判断,其次对于0的处理也不够零活,0的处理可以再开一个递归函数解决,这种合并在一块,自然有很多麻烦。
所以0的问题一定是把它看成空串,而不能把它当作”Zero”元素,最后遇到首尾有空格的情况使用String自带的trim()函数解决就好了。
代码如下:
private final String[] LESS_THAN_20 = {"", "One", "Two", "Three", "Four", "Five", "Six", "Seven", "Eight", "Nine", "Ten", "Eleven", "Twelve", "Thirteen", "Fourteen", "Fifteen", "Sixteen", "Seventeen", "Eighteen", "Nineteen"};
private final String[] TENS = {"", "Ten", "Twenty", "Thirty", "Forty", "Fifty", "Sixty", "Seventy", "Eighty", "Ninety"};
public String numberToWords(int num) {
if (num == 0) return "Zero";
return helper(num);
}
private String helper(int num){
String ans = "";
if (num < 20) ans = LESS_THAN_20[num];
else if (num < 100) ans = TENS[num / 10] + " " + LESS_THAN_20[num % 10];
else if (num < 1000) ans = helper(num / 100) + " Hundred " + helper(num % 100);
else if (num < 1000000) ans = helper(num / 1000) + " Thousand " + helper(num % 1000);
else if (num < 1000000000) ans = helper(num/1000000) + " Million " + helper(num % 1000000);
else ans = helper(num/1000000000) + " Billion " + helper(num % 1000000000);
return ans.trim();
}
核心思想不难:
主要就是找到某个重复的数就好了,比如:0.123123…找到第二个1就可以停止计算了。
代码经历了几个版本才改对,需要注意的几点:
代码如下:
public String fractionToDecimal(int numerator, int denominator) {
if (numerator == 0) return "0";
StringBuilder sb = new StringBuilder();
sb.append((((numerator & 1 << 31) ^ (denominator & 1 << 31)) != 0) ? "-" : "");
long num = Math.abs((long)numerator);
long den = Math.abs((long)denominator);
long k = num / den;
sb.append(k);
num %= den;
if (num == 0) return sb.toString();
sb.append(".");
//fraction
Map<Long,Integer> map = new HashMap<>();
while (num != 0){
num *= 10;
long fact = num / den;
if (map.containsKey(num)){
int index = map.get(num);
sb.append(")");
sb.insert(index-1, "(");
break;
}
sb.append(fact);
map.put(num,sb.length());
num %= den;
}
return sb.toString();
}
刚开始想了一个O(n3)O(n^3)的算法,但估计过不了,所以在想的是如何用来表示一条直线呢?两个点确定一条直线且能够得到唯一的斜率,所以我们可以在O(n2)O(n^2)时间内,得到所有直线的斜率,统计斜率的次数就是所求的点数,当然还需要维护一个max。
斜率用double表示精度高,需要考虑的边界条件:
代码如下:
public int maxPoints(Point[] points) {
if (points==null) return 0;
if (points.length<=2) return points.length;
int res = 0;
Map<Double, Integer> map;
for (int i = 0; i < points.length; ++i){
int dup = 1;
int max = 0;
map = new HashMap<>();
for (int j = i + 1; j < points.length; ++j){
if (points[j].y == points[i].y && points[j].x == points[i].x){
dup++;
continue;
}
if (points[j].y == points[i].y){
map.put(0.0, map.getOrDefault(0.0, 0) + 1);
continue;
}
if (points[j].x == points[i].x){
map.put(Double.MAX_VALUE, map.getOrDefault(Double.MAX_VALUE, 0) + 1);
continue;
}
int x = points[j].x;
int y = points[j].y;
double k = (double)(y - points[i].y) / (double) (x - points[i].x);
map.put(k, map.getOrDefault(k, 0) + 1);
}
for (int val : map.values()){
max = Math.max(max, val);
}
res = Math.max(res, max + dup);
}
return res;
}
遍历的角度可以这么看:固定一个点i,与所有j构成的线段,所以一条斜率就表示一个点在该条直线上。