likesky3
- 浏览: 137511 次
-
最新评论
-
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
文章列表
An image is represented by a binary matrix with 0 as a white pixel and 1 as a black pixel. The black pixels are connected, i.e., there is only one black region. Pixels are connected horizontally and vertically. Given the location (x, y) of one of the black pixels, return the area of the smallest (axi ...
Given two 1d vectors, implement an iterator to return their elements alternately.
For example, given two 1d vectors:
v1 = [1, 2]
v2 = [3, 4, 5, 6]
By calling next repeatedly until hasNext returns false, the order of elements returned by next should be: [1, 3, 2, 4, 5, 6].
Follow up: What if you ar ...
原文链接：
http://blog.csdn.net/asce1885/article/details/43271531
英文原文：
http://www.javacodegeeks.com/2013/01/the-builder-pattern-in-practice.html
我不会详细介绍这个模式，因为已经有大量的文章或者书籍对该模式进行过详细的解析。我将告诉你的是为什么以及什么时候你应该考虑使用它。值得一提的是，我所介绍的这个模式和设计模式四人帮的书（《设计模式:可复用面向对象软件的基础》）里面的有些许区别。四人帮书里面介绍的生成器模式重点在抽象出对象创建的步骤，并通过调用不同的具体实 ...
Inorder Successor in BST
- 博客分类：
- Tree
[分析]
参考https://leetcode.com/discuss/59728/10-and-4-lines-o-h-java-c
& https://leetcode.com/discuss/59787/share-my-java-recursive-solution
不理解参考代码中为什么最后需要额外判断left.val > p.val
public class Solution {
// Method 3: recursion
public TreeNode inorderSuccessor(TreeNode root, TreeNode p) ...
[分析]
最近公共祖先(LCA)是一个经典问题，以前没有好好研究过这个问题，不知道还有个Tarjan算法，今天开了眼界。一般有两种方法分别适用不同场景：
1）递归算法，适合在线单次查询，如本题；
2）Tarjan算法，适合批量查询，输入是一颗树和N对定点，为每个顶点（u,v）确定LCA。
有兴趣的同学看参考https://github.com/julycoding/The-Art-Of-Programming-By-July/blob/master/ebook/zh/03.03.md， July讲得很全面清楚。
抛开算法本身做这道题目还有些学习点：
思路1：分别求出root到p和q的路径，求两 ...
[分析]
思路1：遍历所有节点找到和 target最接近的 k 个元素，能否有个数据结构在遍历过程中维护已遍历元素离target最近的呢？PriorityQueue具备这种能力。我们需要个最小堆，堆元素需要保存两个信息，一个是树节点元素值，一个是这个元素和target的差的绝对值。但PriorityQueue是没有“堆底”概念的，当堆的size 增长到 k 后，如何删除堆中最大元素呢？ 为实现删除最小堆中最大值的操作，可以再维护一个最大堆，两个堆同步更新，需要从堆中删除元素时一定时删除最大堆的堆顶元素。
实现注意点：
1）想清楚堆节点元素保存什么信息
2）新定义的Pair类要么实现了Compa ...
Follow up for H-Index: What if the citations array is sorted in ascending order? Could you optimize your algorithm?
[分析]
思路：二分查找。参考解法
https://leetcode.com/discuss/56122/standard-binary-search
自己的实现倒也是二分查找，但因为没有理解二分查找的精髓，写得磕磕碰碰，修修补补才被Accept，代码因此也不好看，yb君一开始甚至以为是错误的。看讨论区高票解法时觉得不理解，为什么不用考虑我实现中需要的特殊情形呢，为 ...
Leetcode - H-Index
- 博客分类：
- Array
Given an array of citations (each citation is a non-negative integer) of a researcher, write a function to compute the researcher's h-index.
According to the definition of h-index on Wikipedia: "A scientist has index h if h of his/her N papers have at least h citations each, and the other N − h ...
[分析]
这题通过率之所以非常低是因为有很多corner case，代码写得不好时就很容易在各种corner case上刷跟头，第二十遍才被Accept，自己还真是有耐心。然后看到讨论区中的解答，一对比，差距啊，努力努力再努力！
注意：不需要添加“and”
大神漂亮的作品：
https://leetcode.com/discuss/55462/my-clean-java-solution-very-easy-to-understand
public class Solution {
public String numberToWords(int num) {
i ...
[分析]
思路1参考https://leetcode.com/discuss/44537/my-java-ac-code-with-priorityqueues
记录下目前的理解：目标是求出所有拐点。所谓拐点是指让当前x坐标高度发生变化的点，当前x坐标的高度是x处所有楼房的最大高度。所有楼房的左右两顶点加入到考察集合，排序该集合，排序后使用最大堆来保存当前的楼高状态，遍历到左顶点时将高度加入最大堆，右顶点时将高度从最大堆中删除。最大堆堆顶是当前已遍历x坐标的最大高度，一旦堆顶元素变化说明拐点出现了。
各顶点排序规则是若两个点x坐标不同，按x坐标排序，否则需要分三种情况讨论：1）一个是左顶点一个是 ...
There is a new alien language which uses the latin alphabet. However, the order among letters are unknown to you. You receive a list of words from the dictionary, where words are sorted lexicographically by the rules of this new language. Derive the order of letters in this language.
For example,
Gi ...
[分析]
在题I代码基础上增加记录拓扑遍历顺序即可。
public class Solution {
public int[] findOrder(int numCourses, int[][] prerequisites) {
if (prerequisites == null)
return new int[0];
int[] order = new int[numCourses];
List<Set<Integer>> graph = new ArrayList<S ...
[分析]
拓扑排序的经典应用。review时发现自己搞反了课程直接的依赖关系，但却真切地被Accept，
图上画了画，发现搞反后若输出排序结果就是和原来相反，但不影响本题的正确性。
网上搜了搜逆拓扑，发现其是有可用之处的，参见下面这篇博文：
http://blog.csdn.net/guodongxiaren/article/details/37988833
另一篇博文提出拓扑排序是所有节点dfs的逆后序，也就是每个节点任务完成的时间的逆序排序 ，这个洞见也挺有意思的https://m.oschina.net/blog/419291
public class Solution {
...
[分析]
自己使用HashMap + LinkedList/ArrayList的都会超时，讨论区看到使用LinkedHashMap实现的版本https://leetcode.com/discuss/42891/probably-the-best-java-solution-extend-linkedhashmap，这个数据结构自己平常没用过，正好学习了~
import java.util.LinkedHashMap;
public class LRUCache {
private int capacity;
private Map<Integer,Integer ...
A strobogrammatic number is a number that looks the same when rotated 180 degrees (looked at upside down).
Write a function to count the total strobogrammatic numbers that exist in the range of low <= num <= high.
For example,
Given low = "50", high = "100", return 3. Beca ...