leetcode longest consecutive sequence还是想不通！ - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>Java - 爪哇娇娃

leetcode longest consecutive sequence还是想不通！

leetcode longest consecutive sequence还是想不通！# Java - 爪哇娇娃

D*62013-06-26 07:06

1 楼

【以下文字转载自 ChineseClassics 讨论区】
发信人: Doha2006 (DOHA), 信区: ChineseClassics
标题: 免费中文期刊在线阅读，谢xiaozhu
发信站: BBS 未名空间站 (Mon Dec 29 23:18:23 2008)
呵呵，我顺着xiaozhu提供的线索，找到这个免费中文期刊在线阅读。不过，国内把《
读者》也算做期刊里，似乎期刊的定义很模糊么。不过真有不少休闲杂志呢。
http://www.eywedu.com/Journal.asp

c*p2013-06-26 07:06

2 楼

前几天在job问过，但还是想不通，所有又来这里问了。
这回我按网友建议把求hashtable size改成直接count删去的个数了，还是不能通过大
oj。所以又跑来问问我到底哪里出了问题？！
http://www.mitbbs.com/article_t0/JobHunting/32465791.html
原帖在这里。
我新的代码：
import java.util.*;
public class Solution {
public int longestConsecutive(int[] num) {

if(num == null || num.length == 0){
return 0;
}
int max = 1;
int count = 1;
Hashtable hash = new Hashtable();
for(int i = 0; i < num.length; i++){
if(!hash.containsKey(num[i])){
hash.put(num[i], 1);
}
}

for(int i = 0; i < num.length; i++){
if(hash.containsKey(num[i])){
int value = num[i];
count = 1 + check(hash, value + 1, 1) + check(hash,
value - 1, -1);
hash.remove(num[i]);
max = Math.max(max, count);
}
}
return max;
}
public int check(Hashtable hash, int value, int flag){
if(hash.containsKey(value)){
if(flag == 1){
hash.remove(value);
return 1 + check(hash, value + 1, flag);
}else if(flag == -1){
hash.remove(value);
return 1 + check(hash, value - 1, flag);
}
}
return 0;
}
}

z*e2013-06-26 07:06

3 楼

完整代码，基本上是白话，直接看就是了
import java.util.*;
public class Solution {
public int longestConsecutive(int[] num) {
// Start typing your Java solution below
// DO NOT write main() function
int max = 1;

Map map = new HashMap();

for(int i:num){
if(!map.containsKey(i)){
Interval interval = new Interval();
if(map.containsKey(i+1)) interval.upperBound = map.get(i+1).
upperBound;
else interval.upperBound = i;
if(map.containsKey(i-1)) interval.lowerBound = map.get(i-1).
lowerBound;
else interval.lowerBound = i;

map.put(i,interval);

//here is the critical part
map.get(interval.upperBound).lowerBound = interval.
lowerBound;
map.get(interval.lowerBound).upperBound = interval.
upperBound;

if(interval.upperBound - interval.lowerBound+1 > max) max =
interval.upperBound - interval.lowerBound+1;
}
}

return max;
}
}
class Interval{
int upperBound;
int lowerBound;
}

c*p2013-06-26 07:06

4 楼

我读过类似的代码，大概知道怎么回事。
可是我就是钻牛角尖，不知道我自己代码，到底哪里耗时过大了。

【在 z****e 的大作中提到】

: 完整代码，基本上是白话，直接看就是了
: import java.util.*;
: public class Solution {
: public int longestConsecutive(int[] num) {
: // Start typing your Java solution below
: // DO NOT write main() function
: int max = 1;
:
: Map map = new HashMap();
:

o*22013-06-26 07:06

5 楼

我不是很明白“不能通过大oj”是什么意思，只是从一个程序员的角度指出你的程序的
两个问题。
一个是你的算法的问题，很明显你的思路是建立在“先排序，再寻找”的基础上，所以
有很多多余的操作。比如：
1，每个元素都要先在hash里找一次，排除掉重复元素；
2，然后为了探测序列的边缘，每个元素在hash里又找一次；
3，一个序列里，除了第一个被挑中的元素，其他所有的元素在被删除后，在hash里又
找一次，一共三次；
4，每个元素都要在hash里删除一次。
另一个是编程技术问题，你是用递归来探测序列的边缘的，为什么不直接用循环呢？
for (int i = 0; i < num.length; i++) {
if (hash.containsKey (num[i])) {
int lower = num[i];
while (hash.containsKey (lower - 1)) {
lower--;
}
int upper = num[i];
while (hash.containsKey (upper + 1)) {
upper++;
}
int seqSize = upper - lower + 1;
max = Math.max (max, seqSize);
for (int value = lower; value <= upper; value++) {
hash.remove (value);
}
}
}

c*p2013-06-26 07:06

6 楼

谢谢指出问题，我好好想想，然后改改看。

【在 o**2 的大作中提到】

: 我不是很明白“不能通过大oj”是什么意思，只是从一个程序员的角度指出你的程序的
: 两个问题。
: 一个是你的算法的问题，很明显你的思路是建立在“先排序，再寻找”的基础上，所以
: 有很多多余的操作。比如：
: 1，每个元素都要先在hash里找一次，排除掉重复元素；
: 2，然后为了探测序列的边缘，每个元素在hash里又找一次；
: 3，一个序列里，除了第一个被挑中的元素，其他所有的元素在被删除后，在hash里又
: 找一次，一共三次；
: 4，每个元素都要在hash里删除一次。
: 另一个是编程技术问题，你是用递归来探测序列的边缘的，为什么不直接用循环呢？

c*p2013-06-26 07:06

7 楼

外行菜鸟再多问一句，递归和循环，哪个好？
谢谢这么热心帮忙！

【在 o**2 的大作中提到】

l*s2013-06-26 07:06

8 楼

loop is much more efficient, while recursion is more human-readable.

【在 c********p 的大作中提到】

: 外行菜鸟再多问一句，递归和循环，哪个好？
: 谢谢这么热心帮忙！

b*y2013-06-26 07:06

9 楼

True, 循环用的内存少，而递归会导致程序不断的有allocate stack, 这些stack多了
就占内存了。

【在 l*********s 的大作中提到】

: loop is much more efficient, while recursion is more human-readable.

c*p2013-06-26 07:06

10 楼

阿？这样阿。。。其实。。。我一看到recursion我就晕了阿。。。。我更喜欢写
iteration

【在 l*********s 的大作中提到】

: loop is much more efficient, while recursion is more human-readable.

o*22013-06-26 07:06

11 楼

上面两位朋友谈了一下递归和循环在技术、实现上的区别。我这里来说一下它们所代表
的不同的思维方式。
递归相当与一个黑盒，它的功能，或者说输入/输出已经定义好了。以至于它可以在自
己的内部公事公办，再调用它自己，当然，每次的输入会有不同。
而循环就是一个白盒，你知道事情的所有细节，可以直接把逻辑写出来。
至于哪一个好，就看这个事情的复杂程度。如果大多数人都觉得这个事情很简单，就应
该用白盒。反之，用黑盒。
你的这个算法，明显要用白盒，因为太简单了。

【在 c********p 的大作中提到】

: 外行菜鸟再多问一句，递归和循环，哪个好？
: 谢谢这么热心帮忙！

z*e2013-06-26 07:06

12 楼

我一直都觉得递归more readable是编程初期埋下的最大的炸弹
实际上递归就像楼上说的，就是一个black box，一不小心就会出问题
loop的话，只要严格按照规范写，想写错不太容易

【在 c********p 的大作中提到】

: 阿？这样阿。。。其实。。。我一看到recursion我就晕了阿。。。。我更喜欢写
: iteration

w*z2013-06-26 07:06

13 楼

太多就overflow 了，jvm 可以设stack size. 实际工作中，很少用递归。

【在 b******y 的大作中提到】

:
: True, 循环用的内存少，而递归会导致程序不断的有allocate stack, 这些stack多了
: 就占内存了。

g*g2013-06-26 07:06

14 楼

碰上树状结构，不递归不行。

【在 w**z 的大作中提到】

: 太多就overflow 了，jvm 可以设stack size. 实际工作中，很少用递归。

o*22013-06-26 07:06

15 楼

从技术上来说，递归是通过函数调用来隐式地使用堆栈数据结构来保存本次调用的状态
和返回点，所以递归百分之百可以通过显式地使用堆栈数据结构被改写成非递归。
但对一些特定的问题或数据结构，递归是最佳选择，估计 goodbug 指的是这个。

【在 g*****g 的大作中提到】

: 碰上树状结构，不递归不行。

g*g2013-06-26 07:06

16 楼

代码最重要的是容易维护，所以虽然递归都可以压栈实现，大部分时候不可取。

【在 o**2 的大作中提到】

: 从技术上来说，递归是通过函数调用来隐式地使用堆栈数据结构来保存本次调用的状态
: 和返回点，所以递归百分之百可以通过显式地使用堆栈数据结构被改写成非递归。
: 但对一些特定的问题或数据结构，递归是最佳选择，估计 goodbug 指的是这个。

p*e2013-06-26 07:06

17 楼

Why this code can not pass large oj? Stack overflow is the reason.
Let's think about test case: int[] sum={1,2,3,...,9999,10000};
The recursion times is 10000!

【在 c********p 的大作中提到】

: 前几天在job问过，但还是想不通，所有又来这里问了。
: 这回我按网友建议把求hashtable size改成直接count删去的个数了，还是不能通过大
: oj。所以又跑来问问我到底哪里出了问题？！
: http://www.mitbbs.com/article_t0/JobHunting/32465791.html
: 原帖在这里。
: 我新的代码：
: import java.util.*;
: public class Solution {
: public int longestConsecutive(int[] num) {
: