算法细节系列（32）：有趣的数学
版权声明：本文为博主原创文章，未经博主允许不得转载。 https://cloud.tencent.com/developer/article/1434796
算法细节系列（32）：有趣的数学
详细代码可以fork下Github上leetcode项目，不定期更新。
题目摘自leetcode：
- Leetcode 335. Self Crossing
- Leetcode 273. Integer to English Words
- Leetcode 166. Fraction to Recurring Decimal
- Leetcode 149. Max Points on a Line
Leetcode 335. Self Crossing
很有意思的一道题，逆时针走，问会不会出现相交的情况，看了很多题解，只给出了计算的方法，令人含糊。
这是一道模式题，只要走到一定的步数，后续判断的逻辑是一套，所以判断存在相交的有限种情况即可，水平有限，不太好证，靠想象。
说说此题真正的思考过程吧，在模拟行走过程中，我们已经能判断一些基本条件了。比如：
- 当x的长度小于等于3的时候，意味着三条边，根据上述规则，三条边是不可能构成self cross的。
现在考虑四条边的情况：
四条变可以相交，与原点重合或者相交，所以遇到此情况返回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;
}Leetcode 273. Integer to English Words
递归，没什么好说的，思路很简单，关键在于简化代码。自己的代码略复杂，如下：
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();
}Leetcode 166. Fraction to Recurring Decimal
核心思想不难：
主要就是找到某个重复的数就好了，比如：0.123123…找到第二个1就可以停止计算了。
代码经历了几个版本才改对，需要注意的几点：
- 起初，我用Map记录出现的数，但当遇到0.003003的情况时，失效了，所以不能记录单个的数，相反应该记录numerator，当出现numerator相同的情况时，自然就是循环开始的地方。
- 关于负号的前置判断，用异或。
- 遇到 1 / -2147483648的情况，用long来防止溢出吧。
代码如下：
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();
}Leetcode 149. Max Points on a Line
刚开始想了一个O(n3)O(n^3)的算法，但估计过不了，所以在想的是如何用来表示一条直线呢？两个点确定一条直线且能够得到唯一的斜率，所以我们可以在O(n2)O(n^2)时间内，得到所有直线的斜率，统计斜率的次数就是所求的点数，当然还需要维护一个max。
斜率用double表示精度高，需要考虑的边界条件：
- 横坐标一样，如何处理？ （斜率为0，原本可以直接放在斜率的求解公式中，但不知道为什么会得到0.0和-0.0的区别）
- 纵坐标一样，如何处理？（斜率表示为无穷大，当然你可以单独计数处理，无所谓）
- 还存在一种情况，坐标点重合，单独处理。
代码如下：
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构成的线段，所以一条斜率就表示一个点在该条直线上。
本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2017年06月08日，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录