- 浏览: 130919 次
文章分类
- 全部博客 (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
[分析]
这道题思路直接,但bug free需要费些心力。第一版未优化的代码笔记长,未贴。
下面给出的两个实现,实现1是使用二分法找到新区间应插入的位置,然后检查是否需要和上一个区间合并(容易忽略),最后同后面的区间逐个检查是否需要合并。无需额外空间,Code Ganker 指出这种做法严格上非O(N),因为合并时有数组remove操作,最坏情况下是O(N^2),但跑leetcode测试用例这种实现比实现2效率高。
实现2:代码非常简洁,需要使用额外空间。先跳过新区间无交集且在新区间前面的,然后merge 和新区间有交集的,最后加上剩余的。
[ref]
http://blog.csdn.net/linhuanmars/article/details/22238433
http://blog.csdn.net/kenden23/article/details/17264441
这道题思路直接,但bug free需要费些心力。第一版未优化的代码笔记长,未贴。
下面给出的两个实现,实现1是使用二分法找到新区间应插入的位置,然后检查是否需要和上一个区间合并(容易忽略),最后同后面的区间逐个检查是否需要合并。无需额外空间,Code Ganker 指出这种做法严格上非O(N),因为合并时有数组remove操作,最坏情况下是O(N^2),但跑leetcode测试用例这种实现比实现2效率高。
实现2:代码非常简洁,需要使用额外空间。先跳过新区间无交集且在新区间前面的,然后merge 和新区间有交集的,最后加上剩余的。
[ref]
http://blog.csdn.net/linhuanmars/article/details/22238433
http://blog.csdn.net/kenden23/article/details/17264441
/** * Definition for an interval. * public class Interval { * int start; * int end; * Interval() { start = 0; end = 0; } * Interval(int s, int e) { start = s; end = e; } * } */ public class Solution { // Method 2: 使用额外空间,Time:O(N) public List<Interval> insert2(List<Interval> intervals, Interval newInterval) { List<Interval> result = new ArrayList<Interval>(); int i = 0; int N = intervals.size(); while (i < N && newInterval.start > intervals.get(i).end) { result.add(intervals.get(i++)); } if (i < N) { newInterval.start = Math.min(newInterval.start, intervals.get(i).start); } while (i < N && newInterval.end >= intervals.get(i).start) { newInterval.end = Math.max(newInterval.end, intervals.get(i++).end); } result.add(newInterval); while (i < N) { result.add(intervals.get(i++)); } return result; } // Method 1: 二分法查找插入位置,无额外空间 public List<Interval> insert(List<Interval> intervals, Interval newInterval) { if (intervals == null || intervals.size() == 0) { List<Interval> result = new ArrayList<Interval>(); result.add(newInterval); return result; } int N = intervals.size(); int i = findInsertPos(intervals, newInterval.start); // 判断是否需要和前一个区间merge if (i > 0 && intervals.get(i - 1).end >= newInterval.start) { newInterval.start = intervals.get(i - 1).start; newInterval.end = Math.max(newInterval.end, intervals.get(i - 1).end); intervals.remove(--i); } intervals.add(i, newInterval); i++; // 合并同newInterval有交集的区间 while (i < intervals.size() && newInterval.end >= intervals.get(i).start) { newInterval.end = Math.max(newInterval.end, intervals.get(i).end); intervals.remove(i); } return intervals; } public int findInsertPos(List<Interval> intervals, int target) { int left = 0, right = intervals.size() - 1; int mid = 0; while (left <= right) { mid = left + ((right - left) >> 1); Interval curr = intervals.get(mid); if (curr.start == target) return mid; else if (curr.start > target) right = mid - 1; else left = mid + 1; } return left; } }
发表评论
-
Smallest Rectangle Enclosing Black Pixels
2016-02-13 12:39 870An image is represented by a bi ... -
Leetcode - H-Index II
2015-09-06 09:39 1065Follow up for H-Index: What if ... -
Leetcode - H-Index
2015-09-06 09:08 1090Given an array of citations (ea ... -
Leetcode - Add Binary
2015-08-21 09:28 434[分析] 从低位往高位逐位相加,就是这么一个简单的题却花了我一 ... -
Leetcode - Longest Consecutive Sequence
2015-08-20 21:20 454[分析] base version说几句: 数组题一定要考虑重 ... -
Leetcode - First Missing Positive
2015-08-20 07:45 608[分析] 将各个正数放入相应下标处,使之满足nums[nums ... -
Leetcode - Set Matrix Zeros
2015-08-19 20:55 517Given a m x n matrix, if an ele ... -
Leetcode - Rotate Image
2015-08-19 19:51 467[分析] 自己的思路:从外到内一圈圈顺时针旋转90度,坐标映射 ... -
Missing Ranges
2015-08-19 09:48 486[分析] 此题若不考虑极大值极小值相关的corner case ... -
Leetcode - 3Sum Smaller
2015-08-18 22:12 1448Given an array of n integers nu ... -
Leetcode - Spiral Matrix II
2015-08-18 19:49 465Given an integer n, generate a ... -
Leetcode - Spiral Matrix
2015-08-18 09:50 393Given a matrix of m x n element ... -
Leetcode - Contains Duplicate II
2015-08-18 07:57 529Given an array of integers and ... -
Leetcode - Shortest Word Distance II
2015-08-18 07:25 1316This is a follow up of Shortest ... -
Leetcode - Shortest Word Distance III
2015-08-17 22:05 1628This is a follow up of Shortest ... -
Leetcode - Shortest Word Distance
2015-08-17 22:01 884Given a list of words and two w ... -
Leetcode - Maximum Gap
2015-08-16 10:17 467Given an unsorted array, find t ... -
Leetcode - Largest Number
2015-08-15 20:16 545Given a list of non negative in ... -
Leetcode - Insertion Sort List
2015-08-15 19:27 624Sort a linked list using insert ... -
Leetcode - Sort List
2015-08-15 17:41 443Sort a linked list in O(n log n ...
相关推荐
《leetcode-solutions》,刷算法题,需要有一定的英文阅读能力。。。
Algorithm-LeetCode-Sol-Res.zip,干净,易懂的解决方案和资源,为leetcode在线判断算法问题。,算法是为计算机程序高效、彻底地完成任务而创建的一组详细的准则。
IDEA 插件,lettcode刷题,leetcode-editor7.4版本下载进行本地导入(直接将压缩包拖进IDEA即可)
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-python 503.下一个更大元素 II一致,只是这里求的是下标的距离,而不是数值倒序搜索,用到栈,栈里存储索引情况1:若栈为
leetcode-cheat 的发布 它是什么 ? 这是一个chrome 扩展,可以帮助您更高效地使用 leetcode。您可以从 重要: leetcode-cheat 现在只支持中文版。 也就是说不完全支持leetcode.com,但是你可以用leetcode-cn.com代替...
leetcode 答案解析 golang解答
leetcode-editor,在ide中做leetcode练习,支持leetcode.com和leetcode-cn.com,以满足练习的基本需求。理论上支持:intellij idea phpstorm webstorm pycharm rubymine appcode clion goland datagrip rider mps ...
~/.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-Spider目录中修改config.json,其中outputDir需要填写该工程的/docs/views文件夹路径 { "username": "aaa", "password": "bbb", "outputDir": "/Users/liuyao/Downloads/LeetCode-Blog-Test/docs...
leetcode-tag-dynamic programming
leetcode-cli 注意:这个存储库是为了临时使用而分叉的。 注意:从 webbrowser 复制 cookie 并使用leetcode user -c可以临时修复不能。 一个享受 leetcode 的高效 cli 工具! 非常感谢 leetcode.com,一个非常棒的...
leetcode-tag-Tree
leetcode-tag-Stack
leetcode-tag-array
Algorithm-LeetCode-Solution-From-GuaZiDou.zip,Leetcode解决方案Gitbook,算法是为计算机程序高效、彻底地完成任务而创建的一组详细的准则。