s*****1
发帖数: 134 | 1 Leetcode 最新题，我是想用bitset方法做的，但似乎开辟不了那么大的空间,我打算
正负都用一个byte array, 下面是我的打算
byte[] bs = new byte[1<<28];
或
int[] bs = new int[1<<26];
用这个方法出现了Runtime Error, 想请问是不是这个用法？
还是达到了memory limit了？
另外，此题用神马方法搞定啊？
拜谢各位大牛~ |
p*****2
发帖数: 21240 | |
l*********8
发帖数: 4642 | |
s*****1
发帖数: 134 | |
s*****1
发帖数: 134 | 5 刚才看懂~此法精辟~
膜拜二爷~
同时对于楼上longway兄弟也膜拜一下，能几秒种看懂也是神人~ |
p*****p
发帖数: 379 | 6 刚要跑large，网站挂了……
class Solution {
public:
int longestConsecutive(vector &num) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
unordered_set set;
int maxSize = 0;
for (int value : num) {
set.insert(value);
}
for (int value : num) {
maxSize = max(maxSize, getConsecutiveLength(&set, value));
}
return maxSize;
}
int getConsecutiveLength(unordered_set *set, int value) {
if (set->find(value) == set->end()) return 0;
set->erase(value);
return 1 + getConsecutiveLength(set, value - 1) +
getConsecutiveLength(set, value + 1);
}
}; |
c********t
发帖数: 5706 | 7 目测 似乎有个错 {-2147483648，2147483647} 啥结果？
【在 p*****p 的大作中提到】
: 刚要跑large，网站挂了……
: class Solution {
: public:
: int longestConsecutive(vector &num) {
: // Start typing your C/C++ solution below
: // DO NOT write int main() function
: unordered_set set;
: int maxSize = 0;
:
: for (int value : num) {
|
c********t
发帖数: 5706 | 8 我首先想到这个方法，但脑子一短路，寻思不是O(n),就改bitMap了，于是就和楼主一
样杯具了，原因当然就是 Integer positive-negative = negative, 初始化size为负
数啊。
【在 p*****2 的大作中提到】
: http://blog.sina.com.cn/s/blog_b9285de20101iqar.html
|
c********t
发帖数: 5706 | 9 感觉你和ls有一样的错 测测{-2147483648，2147483647}
如果你过了大case, 也许是leetcode没这样的case, 也许是我错了
【在 p*****2 的大作中提到】
: http://blog.sina.com.cn/s/blog_b9285de20101iqar.html
|
h**6
发帖数: 4160 | 10 这题是不是很像0、1矩阵中，求由1组成的最大联通图形的面积。 |
z***8
发帖数: 17 | 11
下面的code需要美化，不过应该是O(n):
void FakeRadixSort(vector &num, vector &temp, int N)
{
vector count;
count.resize(2*N);
int i=0;
for (i=0; i<2*N; i++)
{
count[i] = 0;
}
int size = num.size();
for (i=0; i
{
int index = num[i] % N;
index += N;
++ count[index];
}
for (i=1; i<2*N; i++)
{
count[i] += count[i-1];
}
for (i=size-1; i>=0; i--)
{
int index = num[i] % N;
index += N;
temp[count[index]-1] = num[i];
count[index] -= 1;
}
}
int longestConsecutive(vector &num)
{
// Start typing your C/C++ solution below
// DO NOT write int main() function
int size = num.size();
if (size == 0)
{
return 0;
}
if (size == 1)
{
return 1;
}
int N = 1;
while ( N < size)
{
N *= 10;
}
vector temp;
temp.resize(size);
FakeRadixSort(num, temp, N);
int start = 0;
int end = start;
int max = 1;
int len = 1;
while (end < size-1 && start < size)
{
int diff = temp[end+1] - temp[end];
if (diff == 0 || diff == 1)
{
++ end;
if (diff == 1)
{
len ++;
}
if (len > max)
{
max = len;
}
}
else
{
start = end + 1;
end = start;
len = 1;
}
};
return max;
}
【在 c********t 的大作中提到】
: 感觉你和ls有一样的错 测测{-2147483648，2147483647}
: 如果你过了大case, 也许是leetcode没这样的case, 也许是我错了
|
c********t
发帖数: 5706 | 12 不太像，如果sorted数组，才像
【在 h**6 的大作中提到】
: 这题是不是很像0、1矩阵中，求由1组成的最大联通图形的面积。
|
p*****p
发帖数: 379 | 13 在理，改一下
不过没有这个case
if (value == INT_MAX) {
return 1 + getConsecutiveLength(set, value - 1);
}
else if (value == INT_MIN) {
return 1 + getConsecutiveLength(set, value + 1);
}
return 1 + getConsecutiveLength(set, value - 1) +
getConsecutiveLength(set, value + 1);
【在 c********t 的大作中提到】
: 目测 似乎有个错 {-2147483648，2147483647} 啥结果？
|
