a***o
发帖数: 1182 | 1 大家讨论一下,目前只想到brute force, 从length=1开始
看看每个是不是在subarray里面,事先可以把长度为length的subarray放到
一个hash table里面
Find shortest array (S), with all elements 0 <= S[i] <= X, that is not
subarray (Subarray has to be in same order, but not necessary consecutive)
of the given array A.
For example:
A = [0, 1, 0, 2, 0, 2]
X = 2
Solution is either [1, 1] or [2, 1]
X = 1
A = [0, 0, 1, 1, 0, 1]
Soluti is [1,0,0] | p******9
发帖数: 47 | 2 提供一个比较麻烦的O(n)解法，应该有更简单的做法
将其看成字符串，建后缀树，一层一层的往下走，直到某一层不是满的，我们可以知道
答案就在这一层上，将走过的路径和未出现的字符组成的新的字符串就是解。 | a***o
发帖数: 1182 | 3 subarray不需要连续的啊,后缀树也能用?
【在 p******9 的大作中提到】
: 提供一个比较麻烦的O(n)解法，应该有更简单的做法
: 将其看成字符串，建后缀树，一层一层的往下走，直到某一层不是满的，我们可以知道
: 答案就在这一层上，将走过的路径和未出现的字符组成的新的字符串就是解。
| p******9
发帖数: 47 | 4 对，后缀树相当于把这个字符内所有包含过的子串都涵盖了，按刚才算法走一遍，我们
就可以知道最短的不是原字符串子串的字符串，也就是答案的解 | a***o
发帖数: 1182 | 5 不太理解,比如abcd
后缀树包含了abcd, bcd, cd,d
那ad不在里面呀?
【在 p******9 的大作中提到】
: 对，后缀树相当于把这个字符内所有包含过的子串都涵盖了，按刚才算法走一遍，我们
: 就可以知道最短的不是原字符串子串的字符串，也就是答案的解
| p******9
发帖数: 47 | 6 拿你刚才的例子来说，第一层是满的，因为a,b,c,d这四个字符都包含了，第二层a下面
只有b一个结点，b下面只有c一个结点，c下面只有d一个结点，都是空的，那么我们在
第二层随意填加一个没出现的字符加上已有的字符，就组成了一个没出现过的子串，如
ac，ad，bd，ba，ca，cb，da，db，dc都可以。
我感觉这种方法还是太麻烦，求大神们给更好的方法。 | a***o
发帖数: 1182 | 7 ac,ad不符合条件啊,看原题,不需要连续的...
【在 p******9 的大作中提到】
: 拿你刚才的例子来说，第一层是满的，因为a,b,c,d这四个字符都包含了，第二层a下面
: 只有b一个结点，b下面只有c一个结点，c下面只有d一个结点，都是空的，那么我们在
: 第二层随意填加一个没出现的字符加上已有的字符，就组成了一个没出现过的子串，如
: ac，ad，bd，ba，ca，cb，da，db，dc都可以。
: 我感觉这种方法还是太麻烦，求大神们给更好的方法。
| p******9
发帖数: 47 | | l*********8
发帖数: 4642 | 9 看不懂题目啊。
在这个例子里：
A = [0, 1, 0, 2, 0, 2]
X = 2
一个答案是[1, 1]
哪里来两个1？
另外，要最短的sub-array, 那么只包含一个元素的sub-array不就是最短的？？
【在 a***o 的大作中提到】
: 大家讨论一下,目前只想到brute force, 从length=1开始
: 看看每个是不是在subarray里面,事先可以把长度为length的subarray放到
: 一个hash table里面
: Find shortest array (S), with all elements 0 <= S[i] <= X, that is not
: subarray (Subarray has to be in same order, but not necessary consecutive)
: of the given array A.
: For example:
: A = [0, 1, 0, 2, 0, 2]
: X = 2
: Solution is either [1, 1] or [2, 1]
| a***o
发帖数: 1182 | 10 是最短的非subarray...
1,1是自己创造的
【在 l*********8 的大作中提到】
: 看不懂题目啊。
: 在这个例子里：
: A = [0, 1, 0, 2, 0, 2]
: X = 2
: 一个答案是[1, 1]
: 哪里来两个1？
: 另外，要最短的sub-array, 那么只包含一个元素的sub-array不就是最短的？？
| | | l*********8
发帖数: 4642 | 11 I see, 谢谢！
有意思的题目。
【在 a***o 的大作中提到】
: 是最短的非subarray...
: 1,1是自己创造的
| m****i
发帖数: 650 | 12 For example:
A = [0, 1, 0, 2, 0, 2]
X = 2
Solution is either [1, 1] or [2, 1]
[2,2]不可以么？
X = 1
A = [0, 0, 1, 1, 0, 1]
Soluti is [1,0,0]
[1,1,1] 不可以么？ | a***o
发帖数: 1182 | 13 不可以,请看subarray定义...
【在 m****i 的大作中提到】
: For example:
: A = [0, 1, 0, 2, 0, 2]
: X = 2
: Solution is either [1, 1] or [2, 1]
: [2,2]不可以么？
: X = 1
: A = [0, 0, 1, 1, 0, 1]
: Soluti is [1,0,0]
: [1,1,1] 不可以么？
| x*****0
发帖数: 452 | | p****e
发帖数: 3548 | | p****e
发帖数: 3548 | 16 不知对不，欢迎测试
// Type your C++ code and click the "Run Code" button!
// Your code output will be shown on the left.
// Click on the "Show input" button to enter input data to be read
#include
using namespace std;
int findnotsubarray(vector &rlt, vector &temp, int &X, int a[],
int &length, int start)
{
if(start>=length) return 0;
for(int t=0; t<=X; ++t)
{
int i = start;
for(; i
{
if(t==a[i])
{
break;
}
}
if(i == length)
{
temp.push_back(t);
if(rlt.size() == 0 || rlt.size() > temp.size())
rlt.assign(temp.begin(), temp.end());
temp.pop_back();
return 2;
}
}
if(rlt.size() == 0 || rlt.size() > temp.size()+2)
{
int found = 0;
for(int t=0; t<=X; ++t)
{
int newstart = start;
for(;newstart
if(t == a[newstart])
{
++newstart;
break;
}
temp.push_back(t);
int f = findnotsubarray(rlt, temp, X, a, length, newstart);
if(f == 2)
{
temp.pop_back();
return 1;
}
else if(f)
found = 1;
temp.pop_back();
}
return found;
}
else if(rlt.size() > 0)
return 1;
else
return 0;
}
int main() {
// Start typing your code here...
vector rlt, temp;
int X = 1, length = 6;
int a[6] = {0, 0, 1, 1, 0, 1};
if(findnotsubarray(rlt, temp, X, a, length, 0))
{
for(int i=0; i
cout<
cout<
}
else
cout<<"The size of subarray is lager than original array's."<
return 0;
} |
|
