- 浏览: 129272 次
文章分类
- 全部博客 (189)
- Tree (14)
- Dynamic Programming (34)
- Array (20)
- Search (1)
- Hash (12)
- Backtracking (22)
- Divide and Conque (8)
- Greedy (6)
- Stack (12)
- software (0)
- List (7)
- Math (22)
- Two pointers (16)
- String (20)
- Linux (1)
- Sliding Window (4)
- Finite State Machine (1)
- Breadth-first Search (7)
- Graph (4)
- DFS (6)
- BFS (3)
- Sort (9)
- 基础概念 (2)
- 沟通表达 (0)
- Heap (2)
- Binary Search (15)
- 小结 (1)
- Bit Manipulation (8)
- Union Find (4)
- Topological Sort (1)
- PriorityQueue (1)
- Design Pattern (1)
- Design (1)
- Iterator (1)
- Queue (1)
最新评论
-
likesky3:
看了数据结构书得知并不是迭代和递归的区别,yb君的写法的效果是 ...
Leetcode - Graph Valid Tree -
likesky3:
迭代和递归的区别吧~
Leetcode - Graph Valid Tree -
qb_2008:
还有一种find写法:int find(int p) { i ...
Leetcode - Graph Valid Tree -
qb_2008:
要看懂这些技巧的代码确实比较困难。我是这么看懂的:1. 明白这 ...
Leetcode - Single Num II -
qb_2008:
public int singleNumber2(int[] ...
Leetcode - Single Num II
[分析]
两条直线若包含一个公共点且斜率相同,则为同一条直线。因此依次将数组中各点设为公共点,并计算所有未当过公共点的其他点同当当前公共点形成直线的斜率,使用哈希表保存各斜率直线上的点数,遍历过程中同时更新维护一条直线上包含的最多点数。
实现1中key直接就是double类型的斜率,实现时有几个注意点:
1)斜率为0时要单独判断并显式赋值为0,double类型0 和 -0是不等的
2)需要考虑输入中可能存在重复点
3)map,same, max为什么要放在循环里头定义?为什么需要max 和ret两个变量?因为它们统计的是以points[i]为公共点时数据,max可以看做时局部最大值,ret是全局最大值,不可混淆
实现2中key是斜率计算分式化简后的结果,避免使用double实际计算出斜率,参考
https://leetcode.com/discuss/9011/c-o-n-2-solution-for-your-reference
PS: leetcode 允许加打印语句进行调试啦~
两条直线若包含一个公共点且斜率相同,则为同一条直线。因此依次将数组中各点设为公共点,并计算所有未当过公共点的其他点同当当前公共点形成直线的斜率,使用哈希表保存各斜率直线上的点数,遍历过程中同时更新维护一条直线上包含的最多点数。
实现1中key直接就是double类型的斜率,实现时有几个注意点:
1)斜率为0时要单独判断并显式赋值为0,double类型0 和 -0是不等的
2)需要考虑输入中可能存在重复点
3)map,same, max为什么要放在循环里头定义?为什么需要max 和ret两个变量?因为它们统计的是以points[i]为公共点时数据,max可以看做时局部最大值,ret是全局最大值,不可混淆
实现2中key是斜率计算分式化简后的结果,避免使用double实际计算出斜率,参考
https://leetcode.com/discuss/9011/c-o-n-2-solution-for-your-reference
PS: leetcode 允许加打印语句进行调试啦~
/** * 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 { // Method 2 public int maxPoints(Point[] points) { if (points == null) return 0; if (points.length < 3) return points.length; int globalMax = 2; int N = points.length; for (int i = 0; i < N - 2; i++) { HashMap<String, Integer> map = new HashMap<String, Integer>(); int same = 0; int localMax = 1; //attention, not init to 0 int x1 = points[i].x, y1 = points[i].y; for (int j = i + 1; j < N; j++) { int x2 = points[j].x, y2 = points[j].y; int deltaX = x2 - x1; int deltaY = y2 - y1; int gcd = gcd(deltaX, deltaY); if (gcd == 0) { same++; continue; } deltaX /= gcd; deltaY /= gcd; String slope = deltaY + "/" + deltaX; if (map.containsKey(slope)) map.put(slope, map.get(slope) + 1); else map.put(slope, 2); localMax = Math.max(localMax, map.get(slope)); } globalMax = Math.max(globalMax, localMax + same); } return globalMax; } public int gcd(int a, int b) { return b != 0 ? gcd(b, a % b) : a; } // Method 1 public int maxPoints1(Point[] points) { if (points == null) return 0; if (points.length < 3) return points.length; int ret = 0; int N = points.length; for (int i = 0; i < N; i++) { HashMap<Double, Integer> map = new HashMap<Double, Integer>(); long x1 = points[i].x, y1 = points[i].y; int same = 0; int max = 1; for (int j = i + 1; j < N; j++) { long x2 = points[j].x, y2 = points[j].y; if (x1 == x2 && y1 == y2) {// specail attention same++; } else if (x1 == x2) { if (map.containsKey(Double.MAX_VALUE)) map.put(Double.MAX_VALUE, map.get(Double.MAX_VALUE) + 1); else map.put(Double.MAX_VALUE, 2); max = Math.max(max, map.get(Double.MAX_VALUE)); } else { double slope = 0; if (y1 == y2) slope = 0; // special attention, consider case[2, 3], [3, 3], [-5, 3] else slope = 1.0 * (y2 - y1) / (x2 - x1);; if (map.containsKey(slope)) map.put(slope, map.get(slope) + 1); else map.put(slope, 2); max = Math.max(max, map.get(slope)); } } // System.out.println(max + " " + same); ret = Math.max(ret, max + same); } return ret; } }
发表评论
-
Leetcode - Integer to English Words
2015-09-04 20:53 1056[分析] 这题通过率之所以非常低是因为有很多corner ca ... -
Leetcode - LRU Cache
2015-09-03 18:31 496[分析] 自己使用HashMap + LinkedList/A ... -
Leetcode - Strobogrammatic Number III
2015-09-03 16:45 2119A strobogrammatic number is a n ... -
Leetcode - Basic Calculator II
2015-08-27 09:16 859mplement a basic calculator to ... -
Leetcode - Factorial Trailing Zeroes
2015-08-25 09:00 389[思路] 数乘积结果的后缀0,其实就是数结果中有多少个因子10 ... -
Leetcode - Ugly Number II
2015-08-24 22:54 1109[分析] 暴力的办法就是从1开始检查每个数是否是丑数,发现丑数 ... -
Leetcode - Excel Sheet Column Title
2015-08-24 10:24 604[分析] 十进制转26进制,需要注意的是26进制是以1为最小数 ... -
Leetcode - Fraction to Recurring Decimal
2015-08-23 10:05 423[分析] 处理int型整数运算时,为避免溢出,省事的做法就是内 ... -
Leetcode - Isomorphic Strings
2015-08-23 09:51 502[分析] 思路1:维护两个哈希表,char[] map, bo ... -
Leetcode - Palindrome Permutation
2015-08-22 16:24 1143[分析] 思路2让我大开眼界,顺便学习下BitSet~ [re ... -
Leetcode - Group Shifted String
2015-08-22 16:20 1678Given a string, we can "sh ... -
Leetcode - Count Primes
2015-08-22 13:42 470[ref] https://en.wikipedia.org/ ... -
Leetcode - Strobogrammatic Number
2015-08-22 10:48 1055A strobogrammatic number is a n ... -
Leetcode - Two Sum III - Data Structure Design
2015-08-21 10:30 651[分析] find的version1 版本注意num2Occu ... -
Leetcode - Add Binary
2015-08-21 09:28 426[分析] 从低位往高位逐位相加,就是这么一个简单的题却花了我一 ... -
Leetcode - Longest Consecutive Sequence
2015-08-20 21:20 447[分析] base version说几句: 数组题一定要考虑重 ... -
Leetcode - Rotate Image
2015-08-19 19:51 459[分析] 自己的思路:从外到内一圈圈顺时针旋转90度,坐标映射 ... -
Missing Ranges
2015-08-19 09:48 479[分析] 此题若不考虑极大值极小值相关的corner case ... -
Leetcode - Contains Duplicate II
2015-08-18 07:57 522Given an array of integers and ... -
Leetcode - Shortest Word Distance II
2015-08-18 07:25 1308This is a follow up of Shortest ...
相关推荐
《leetcode-solutions》,刷算法题,需要有一定的英文阅读能力。。。
IDEA 插件,lettcode刷题,leetcode-editor7.4版本下载进行本地导入(直接将压缩包拖进IDEA即可)
Algorithm-LeetCode-Sol-Res.zip,干净,易懂的解决方案和资源,为leetcode在线判断算法问题。,算法是为计算机程序高效、彻底地完成任务而创建的一组详细的准则。
Algorithm-leetcode-spider.zip,leetcode公司,算法是为计算机程序高效、彻底地完成任务而创建的一组详细的准则。
在IDE中解决LeetCode问题,支持leetcode.com与leetcode-cn.com,满足基本的做题需求。 理论上支持: IntelliJ IDEA PhpStorm WebStorm PyCharm RubyMine AppCode CLion GoLand DataGrip Rider MPS Android Studio。
leetcode-cli-plugins leetcode-cli 的第 3 方插件。 什么是 如何使用 如何使用 插件 名称 描述 增强的命令 按公司或标签过滤问题 list 不要在同一台计算机上使 Chrome 的会话过期 login 不要在同一台计算机上使 ...
leetcode 答案解析 golang解答
解题思路思路和LeetCode-python 503.下一个更大元素 II一致,只是这里求的是下标的距离,而不是数值倒序搜索,用到栈,栈里存储索引情况1:若栈为
leetcode-cheat 的发布 它是什么 ? 这是一个chrome 扩展,可以帮助您更高效地使用 leetcode。您可以从 重要: leetcode-cheat 现在只支持中文版。 也就是说不完全支持leetcode.com,但是你可以用leetcode-cn.com代替...
~/.vscode/extensions/leetcode.vscode-leetcode-0.17.0/node_modules/vsc-leetcode-cli/bin/leetcode /usr/local/bin/leetcode 修改模板 open ~/.vscode/extensions/leetcode.vscode-leetcode-0.17.0/node_modules/...
leetcode-helper-1.7.1
leetcode-tag-dynamic programming
leetcode-editor,在ide中做leetcode练习,支持leetcode.com和leetcode-cn.com,以满足练习的基本需求。理论上支持:intellij idea phpstorm webstorm pycharm rubymine appcode clion goland datagrip rider mps ...
leetcode-tag-Tree
leetcode-tag-Stack
leetcode-tag-array
Algorithm-LeetCode-Solution-From-GuaZiDou.zip,Leetcode解决方案Gitbook,算法是为计算机程序高效、彻底地完成任务而创建的一组详细的准则。
leetcode-cli 注意:这个存储库是为了临时使用而分叉的。 注意:从 webbrowser 复制 cookie 并使用leetcode user -c可以临时修复不能。 一个享受 leetcode 的高效 cli 工具! 非常感谢 leetcode.com,一个非常棒的...
leetcode-链表笔记
然后进入到LeetCode-Spider目录中修改config.json,其中outputDir需要填写该工程的/docs/views文件夹路径 { "username": "aaa", "password": "bbb", "outputDir": "/Users/liuyao/Downloads/LeetCode-Blog-Test/docs...