两道google的题 - 未名空间MITBBS历史存档

g*r2012-11-17 08:11

1 楼

1. Given a array of integers , find 3 indexes i,j,k such that, i<
j这个怎么搞呢，O(n)可能吗？
2.You are given an array of n elements [1,2,....n]. For example {3,2,1,6,7,4
,5}.
Now we create a signature of this array by comparing every consecutive pir
of elements. If they increase, write I else write D. For example for the
above array, the signature would be "DDIIDI". The signature thus has a
length of N-1. Now the question is given a signature, compute the
lexicographically smallest permutation of [1,2,....n]. Write the below
function in language of your choice.

b*e2012-11-17 08:11

2 楼

第二题用贪心算法做应该就可以了。
第一题正好可以参考第二题的思路，从左到右扫描，每次只track一个Increase Pair,
遇到一个新的increase pair的时候做一个判断，如果该increase pair中的较大数比之
前increase pair中较大的数大，则返回结果，否则就track当前的increase pair并继
续扫描。

i<
,4

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

: 1. Given a array of integers , find 3 indexes i,j,k such that, i<
: j: 这个怎么搞呢，O(n)可能吗？
: 2.You are given an array of n elements [1,2,....n]. For example {3,2,1,6,7,4
: ,5}.
: Now we create a signature of this array by comparing every consecutive pir
: of elements. If they increase, write I else write D. For example for the
: above array, the signature would be "DDIIDI". The signature thus has a
: length of N-1. Now the question is given a signature, compute the
: lexicographically smallest permutation of [1,2,....n]. Write the below

b*u2012-11-17 08:11

3 楼

第一题能否这么弄
建一个大根堆，
和一个hash_map > map用于存储比key小，又出
现得比key早的value
对每一个新数x，首先放入堆，整理，然后对所有在x下面的值y， map[x].push_back(y)
最后对map[y]里的每一个值，
将(x, y, map[y][i])存入result
//===============================
第二题遍历一次signature，I 加一 D 减一，然后把最低值记下来，设为1，推出其余

a*o2012-11-17 08:11

4 楼

第一题不能o（n）吧，答案都不止n

,

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

: 第二题用贪心算法做应该就可以了。
: 第一题正好可以参考第二题的思路，从左到右扫描，每次只track一个Increase Pair,
: 遇到一个新的increase pair的时候做一个判断，如果该increase pair中的较大数比之
: 前increase pair中较大的数大，则返回结果，否则就track当前的increase pair并继
: 续扫描。
:
: i<
: ,4

b*e2012-11-17 08:11

5 楼

ca,没看清题目...要返回所有组合的话最坏情况下答案个数都有O(N3)个吧，不如直接
列举所有3个数的组合然后一一判断好了。

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

: 第一题不能o（n）吧，答案都不止n
:
: ,

D*d2012-11-17 08:11

6 楼

同意，除非这个 n 是可能的组合数

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

: 第一题不能o（n）吧，答案都不止n
:
: ,

g*r2012-11-17 08:11

7 楼

第一题是应该找到一个i,j,k就可。
你第二题说贪心是咋做的呢？说详细点行吗，谢谢了。

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

: ca,没看清题目...要返回所有组合的话最坏情况下答案个数都有O(N3)个吧，不如直接
: 列举所有3个数的组合然后一一判断好了。

b*e2012-11-17 08:11

8 楼

将初始数列设为1..n，然后扫描signature, 碰到“I”就跳过，碰到连续的"D"就翻转
相应位置上的数字。代码如下：
vector FindSmallestPermutation(string signature) {
vector res(signature.size() + 1, 0);
for (int i = 0; i < res.size(); i++) {
res[i] = i + 1;
}
int pos = 0;
int start = 0;
while (pos < signature.size()) {
if (signature[pos] == 'D') {
start = pos;
while (pos < signature.size() && signature[pos] == 'D')
pos++;
reverse(res.begin() + start, res.begin() + pos + 1);
}
else
pos++;
}
return res;
}

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

: 第一题是应该找到一个i,j,k就可。
: 你第二题说贪心是咋做的呢？说详细点行吗，谢谢了。

v*u2012-11-17 08:11

9 楼

第一题：
设potentiali=0 （数组起始下标），从左向右扫描，如果比arr[potentiali]大
，就把当前位置设成potentialj，否则把potentiali更新为当前位置
potentiali, potentialj设置好以后，继续向右扫描，如果比arr[potentialj]大，就
完成，否则和arr[potentiali]比较，如果比poteniali小，就更新potentiali为当前位
置，否则把potentialj更新为当前位置。
中间省略了一点步骤就是为potentialj记住它的potentiali，这个不会影响复杂度。

,4

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

: 1. Given a array of integers , find 3 indexes i,j,k such that, i<
: j: 这个怎么搞呢，O(n)可能吗？
: 2.You are given an array of n elements [1,2,....n]. For example {3,2,1,6,7,4
: ,5}.
: Now we create a signature of this array by comparing every consecutive pir
: of elements. If they increase, write I else write D. For example for the
: above array, the signature would be "DDIIDI". The signature thus has a
: length of N-1. Now the question is given a signature, compute the
: lexicographically smallest permutation of [1,2,....n]. Write the below

c*r2012-11-17 08:11

10 楼

随手写了一下第一题，请大牛们指教轻拍：
public static void findit(int[] a)
{
if(a==null || a.length<4)
{
return;
}
int min = a[0];
int minindex = 0;
int mid = a[0];
int midindex = 0;
int max = a[0];
int maxindex = 0;

for(int i=0;iif(a[i]{
min = a[i];
minindex = i;
}else if(max>a[i]&&a[i]>min){
max = a[i];
maxindex =i;
}
else
{
mid = max;
midindex = maxindex;
max = a[i];
maxindex =i;
}

if(min{
System.out.println(min + " " + mid + " " + max);
return;
}
}

}

/**

,4

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

: 1. Given a array of integers , find 3 indexes i,j,k such that, i<
: j: 这个怎么搞呢，O(n)可能吗？
: 2.You are given an array of n elements [1,2,....n]. For example {3,2,1,6,7,4
: ,5}.
: Now we create a signature of this array by comparing every consecutive pir
: of elements. If they increase, write I else write D. For example for the
: above array, the signature would be "DDIIDI". The signature thus has a
: length of N-1. Now the question is given a signature, compute the
: lexicographically smallest permutation of [1,2,....n]. Write the below

p*22012-11-17 08:11

11 楼

如果这样的话，不是跟那个股票的第三题类似了吗？

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

: 第一题是应该找到一个i,j,k就可。
: 你第二题说贪心是咋做的呢？说详细点行吗，谢谢了。

h*n2012-11-17 08:11

12 楼

貌似比股票第三题还简单一点，那个需要找差值最大的

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

:
: 如果这样的话，不是跟那个股票的第三题类似了吗？

p*22012-11-17 08:11

13 楼

是呀。两边扫纪录左边最小值，右边最大值就可以了。没什么难度了。

【在 h****n 的大作中提到】

: 貌似比股票第三题还简单一点，那个需要找差值最大的

q*m2012-11-17 08:11

14 楼

#2, DDIIDI-> 3, 2, 1, 4, 6, 5, 7

,4

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

: 1. Given a array of integers , find 3 indexes i,j,k such that, i<
: j: 这个怎么搞呢，O(n)可能吗？
: 2.You are given an array of n elements [1,2,....n]. For example {3,2,1,6,7,4
: ,5}.
: Now we create a signature of this array by comparing every consecutive pir
: of elements. If they increase, write I else write D. For example for the
: above array, the signature would be "DDIIDI". The signature thus has a
: length of N-1. Now the question is given a signature, compute the
: lexicographically smallest permutation of [1,2,....n]. Write the below

q*m2012-11-17 08:11

15 楼

#1, if the array is decreasing , then no solution .

,4

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

: 1. Given a array of integers , find 3 indexes i,j,k such that, i<
: j: 这个怎么搞呢，O(n)可能吗？
: 2.You are given an array of n elements [1,2,....n]. For example {3,2,1,6,7,4
: ,5}.
: Now we create a signature of this array by comparing every consecutive pir
: of elements. If they increase, write I else write D. For example for the
: above array, the signature would be "DDIIDI". The signature thus has a
: length of N-1. Now the question is given a signature, compute the
: lexicographically smallest permutation of [1,2,....n]. Write the below

s*12012-11-17 08:11

16 楼

这个算法应该是不对的吧，如给定 100,0,1,2, 这个算法是找不到三连数的，因为他
假定0就是i了

【在 v*****u 的大作中提到】

: 第一题：
: 设potentiali=0 （数组起始下标），从左向右扫描，如果比arr[potentiali]大
: ，就把当前位置设成potentialj，否则把potentiali更新为当前位置
: potentiali, potentialj设置好以后，继续向右扫描，如果比arr[potentialj]大，就
: 完成，否则和arr[potentiali]比较，如果比poteniali小，就更新potentiali为当前位
: 置，否则把potentialj更新为当前位置。
: 中间省略了一点步骤就是为potentialj记住它的potentiali，这个不会影响复杂度。
:
: ,4

s*12012-11-17 08:11

17 楼

这个算法也是不对的，
如果给定 input 是 -2，-101，-100，-102，-1的话
那么这个算法给出的
min i=3, a[i]=-102
mid j=2, a[j]=-100
max k=4, a[k]=-1
这里 i,j,k的顺序是不对的，所以是输不出来的
但是我给的input应该是能出来 -101，-102，-1的
有没有大牛给一个O(N)的解法啊，我觉得这题没有想象中的简单啊！

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

: 随手写了一下第一题，请大牛们指教轻拍：
: public static void findit(int[] a)
: {
: if(a==null || a.length<4)
: {
: return;
: }
: int min = a[0];
: int minindex = 0;
: int mid = a[0];

p*22012-11-17 08:11

18 楼

写了一下第一题
static void Find(int[] arr)
{
int n=arr.length;
int[] dp=new int[n];
dp[n-1]=n-1;
for(int i=1;idp[i]=arr[i]for(int i=n-2;i>0;i--)
{
if(arr[i]>arr[dp[i-1]] && arr[i]{
System.out.printf("%d %d %d", dp[i-1], i, dp[i+1]);
return;
}

dp[i]=arr[i]>arr[dp[i+1]]?i:dp[i+1];
}

System.out.println("can't find");
}

b*e2012-11-17 08:11

19 楼

刚写了个第一题的代码：
vector FindIncreasingNum(vector vec) {
int first = INT_MAX;
int second = INT_MAX;
for (int i = 1; i < vec.size(); i++) {
if (vec[i] > vec[i - 1]) {
if (vec[i] > second) {
vector res;
res.push_back(first);
res.push_back(second);
res.push_back(vec[i]);
return res;
}
else {
first = vec[i - 1];
second = vec[i];
}
}
}
return vector();
}

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

: 这个算法也是不对的，
: 如果给定 input 是 -2，-101，-100，-102，-1的话
: 那么这个算法给出的
: min i=3, a[i]=-102
: mid j=2, a[j]=-100
: max k=4, a[k]=-1
: 这里 i,j,k的顺序是不对的，所以是输不出来的
: 但是我给的input应该是能出来 -101，-102，-1的
: 有没有大牛给一个O(N)的解法啊，我觉得这题没有想象中的简单啊！

s*12012-11-17 08:11

20 楼

这个解法应该也是不对的，我如果给定 1,100,99,100的话，根据这个算法是显示不出的
但的确有解，那就是 1,99,100。
或如给定 1,100,99,100,96的话，也不行吧
我再看看上面一个解法

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

: 刚写了个第一题的代码：
: vector FindIncreasingNum(vector vec) {
: int first = INT_MAX;
: int second = INT_MAX;
: for (int i = 1; i < vec.size(); i++) {
: if (vec[i] > vec[i - 1]) {
: if (vec[i] > second) {
: vector res;
: res.push_back(first);
: res.push_back(second);

z*i2012-11-17 08:11

21 楼

bool find_increasing_triple(int A, int len, int first=0; int second=0;int
third=0){
for(i=0;iif(second==0){
if(A[i]>A[first])
second =i;
else if(A[i]first=i;
}else{
if(A[i]>A[second]){
third=i;
int j;
for(j=0;jif(A[j]first=j;
return true;
}else if(A[i]A[first]){
second=i;
}else if(A[i]first=i;
}
}
}
}
Idea:
找到first index，then寻找second index(A[second]>A[first]).
Consider an example:
10(A[first]) 20(A[seoncd]).
Case 1: If A[i]=30>A[second], DONE(i=third).
Case 2: If A[i]=25 between A[first] and A[second], second=i;
Case 3: If A[i]=5for future A[i]>A[second], there is an increasing triple i>(first'!=first, find it again), so Case 1 can still be applied.
for future A[i](=8 or 18) between A[first](=5) and A[second](=20), Case 2
still can be applied.
for future A[i]=(3)
,4

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

: 1. Given a array of integers , find 3 indexes i,j,k such that, i<
: j: 这个怎么搞呢，O(n)可能吗？
: 2.You are given an array of n elements [1,2,....n]. For example {3,2,1,6,7,4
: ,5}.
: Now we create a signature of this array by comparing every consecutive pir
: of elements. If they increase, write I else write D. For example for the
: above array, the signature would be "DDIIDI". The signature thus has a
: length of N-1. Now the question is given a signature, compute the
: lexicographically smallest permutation of [1,2,....n]. Write the below

p*22012-11-17 08:11

22 楼

出的
你看看我的那个对吗

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

: 这个解法应该也是不对的，我如果给定 1,100,99,100的话，根据这个算法是显示不出的
: 但的确有解，那就是 1,99,100。
: 或如给定 1,100,99,100,96的话，也不行吧
: 我再看看上面一个解法

z*i2012-11-17 08:11

23 楼

好像start=pos-1吧。
能证明这是lexicological最小的吗？

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

: 将初始数列设为1..n，然后扫描signature, 碰到“I”就跳过，碰到连续的"D"就翻转
: 相应位置上的数字。代码如下：
: vector FindSmallestPermutation(string signature) {
: vector res(signature.size() + 1, 0);
: for (int i = 0; i < res.size(); i++) {
: res[i] = i + 1;
: }
: int pos = 0;
: int start = 0;
: while (pos < signature.size()) {

b*e2012-11-17 08:11

24 楼

多谢!确实是个很低级的错误...
不过我觉得这个办法修改一下还是可行的。按照你的提醒，更新的思路如下：
1. 对每一个值，都判断是否大于first并且小于second, 如果是则更新second为当前值;
2. 用一个新的min_val变量记录当前为止遇到的最小值，遇到increased pair时，如果
不能返回结果，则更新first使其为min_val, 并继续扫描。
更新后的代码如下，请指正~
vector FindIncreasingNum(vector vec) {
if (vec.size() < 3)
return vector();
int first = INT_MAX;
int second = INT_MAX;
int min_val = vec[0];
for (int i = 1; i < vec.size(); i++) {
if (vec[i] > vec[i - 1]) {
if (vec[i] > second) {
vector res;
res.push_back(first);
res.push_back(second);
res.push_back(vec[i]);
return res;
}
else {
first = min_val;
second = vec[i];
}
}
else {
if (vec[i] > first && vec[i] < second)
second = vec[i];
else if (vec[i] < min_val)
min_val = vec[i];
}
}
return vector();
}

出的

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

: 这个解法应该也是不对的，我如果给定 1,100,99,100的话，根据这个算法是显示不出的
: 但的确有解，那就是 1,99,100。
: 或如给定 1,100,99,100,96的话，也不行吧
: 我再看看上面一个解法

s*12012-11-17 08:11

25 楼

这个应该是对的，和ziyouzizai的思路是一致的，
peking2的思路看不懂额，能否稍微提示一下？

值;

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

: 多谢!确实是个很低级的错误...
: 不过我觉得这个办法修改一下还是可行的。按照你的提醒，更新的思路如下：
: 1. 对每一个值，都判断是否大于first并且小于second, 如果是则更新second为当前值;
: 2. 用一个新的min_val变量记录当前为止遇到的最小值，遇到increased pair时，如果
: 不能返回结果，则更新first使其为min_val, 并继续扫描。
: 更新后的代码如下，请指正~
: vector FindIncreasingNum(vector vec) {
: if (vec.size() < 3)
: return vector();
: int first = INT_MAX;

z*i2012-11-17 08:11

26 楼

把lexicographically smallest 改成lexicographically largest。greedy algorithm
still works or not?

,4

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

: 第一题是应该找到一个i,j,k就可。
: 你第二题说贪心是咋做的呢？说详细点行吗，谢谢了。

h*n2012-11-17 08:11

27 楼

二爷的算法应该可以，我做个注释：
另外缺点是开辟了一个array，不知道有没有空间O（1）的算法
static void Find(int[] arr)
{
int n=arr.length;
int[] dp=new int[n];
dp[n-1]=n-1;
//dp数组里保存到从最左边到当前i元素为止最小的数的index
for(int i=1;idp[i]=arr[i]
for(int i=n-2;i>0;i--)
{
/×如果当前元素比最左边到当前元素最小元素大，且当前元素比最右边
到当前元素最大元素小的话，则结果存在，输出×/
if(arr[i]>arr[dp[i-1]] && arr[i]{
System.out.printf("%d %d %d", dp[i-1], i, dp[i+1]);
return;
}
//dp数组i的右边此时动态更新从最右边往i元素看最大的数的index
dp[i]=arr[i]>arr[dp[i+1]]?i:dp[i+1];
}

System.out.println("can't find");
}

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

: 写了一下第一题
: static void Find(int[] arr)
: {
: int n=arr.length;
: int[] dp=new int[n];
: dp[n-1]=n-1;
: for(int i=1;i: dp[i]=arr[i]: for(int i=n-2;i>0;i--)
: {

h*n2012-11-17 08:11

28 楼

应该一样的思路吧。。
初始化序列 n....1
然后扫描，遇到连续的I比如（i,j）是I，则翻转这段即可，遇到D则skip

algorithm

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

: 把lexicographically smallest 改成lexicographically largest。greedy algorithm
: still works or not?
:
: ,4

s*12012-11-17 08:11

29 楼

这个想法好厉害啊！

【在 h****n 的大作中提到】

: 二爷的算法应该可以，我做个注释：
: 另外缺点是开辟了一个array，不知道有没有空间O（1）的算法
: static void Find(int[] arr)
: {
: int n=arr.length;
: int[] dp=new int[n];
: dp[n-1]=n-1;
: //dp数组里保存到从最左边到当前i元素为止最小的数的index
: for(int i=1;i: dp[i]=arr[i]

v*u2012-11-17 08:11

30 楼

可以的啊，第一步的时候arr[1]
，就
前位

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

: 这个想法好厉害啊！
:

b*m2012-11-17 08:11

31 楼

我也总算是看明白了。求空间O(1)的解法。

[i-1]; :="" ...................="">

【在 h****n 的大作中提到】

: 二爷的算法应该可以，我做个注释：
: 另外缺点是开辟了一个array，不知道有没有空间O（1）的算法
: static void Find(int[] arr)
: {
: int n=arr.length;
: int[] dp=new int[n];
: dp[n-1]=n-1;
: //dp数组里保存到从最左边到当前i元素为止最小的数的index
: for(int i=1;i: dp[i]=arr[i]

f*42012-11-17 08:11

32 楼

lis的特殊情况

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

: 我也总算是看明白了。求空间O(1)的解法。
:
: [i-1]; :="" ...................="">

C*n2012-11-17 08:11

33 楼

感觉第一题的解法略有问题，举个例子，数组是[1, 2, 3, 4]，signature是DDI，这个
算法在遇到第一个D时
交换了1和3，在遇到了第二个D时交换了2和1。也就是说在处理完第二个D的时候数组变
成了[3, 1, 2, 4]，前两个paire已经不符合DD了

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

: 将初始数列设为1..n，然后扫描signature, 碰到“I”就跳过，碰到连续的"D"就翻转
: 相应位置上的数字。代码如下：
: vector FindSmallestPermutation(string signature) {
: vector res(signature.size() + 1, 0);
: for (int i = 0; i < res.size(); i++) {
: res[i] = i + 1;
: }
: int pos = 0;
: int start = 0;
: while (pos < signature.size()) {

h*n2012-11-17 08:11

34 楼

连续的要一并处理而不是一个一个处理

感觉第一题的解法略有问题，举个例子，数组是[1, 2, 3, 4]，signature是DDI，这个
算法在遇到第一个D时交换了1和3，在遇到了第二个D时交换了2和1。也就是说在......
..
★ Sent from iPhone App: iReader Mitbbs Lite 7.56

【在 C*******n 的大作中提到】

: 感觉第一题的解法略有问题，举个例子，数组是[1, 2, 3, 4]，signature是DDI，这个
: 算法在遇到第一个D时
: 交换了1和3，在遇到了第二个D时交换了2和1。也就是说在处理完第二个D的时候数组变
: 成了[3, 1, 2, 4]，前两个paire已经不符合DD了

h*n2012-11-17 08:11

35 楼

lis需要 nlgn的复杂度

lis的特殊情况
★ Sent from iPhone App: iReader Mitbbs Lite 7.56

【在 f*******4 的大作中提到】

: lis的特殊情况

f*42012-11-17 08:11

36 楼

这里的特殊就是3is...

【在 h****n 的大作中提到】

: lis需要 nlgn的复杂度
:
: lis的特殊情况
: ★ Sent from iPhone App: iReader Mitbbs Lite 7.56

s*12012-11-17 08:11

37 楼

From the original array build two arrays.
i) LMin[i] contains index of the min element seen so far from the left
including a[i].
ii) RMax[i] contains index of the max element seen so far from the right
including a[i].
consider the following array:
a =4,7,5,1,3,8,9,6,2
LMin=0,0,0,3,3,3,3,3,3
RMax=6,6,6,6,6,6,6,7,8
Now for i=1 to n if a[LMin[i]] < a[i] < a[RMax[i] print LMin[i],i,RMax[i]
Time complexity: O(n)
Space Complexity: O(n)

r*n2012-11-17 08:11

38 楼

solution to Q1
std::vector find3idx( const std::vector& a ){
std::vector idx;
int sz = a.size();
if( sz == 0 ) return idx;
idx.push_back(0);
for(int i = 1; i < sz; i++){
if( a[i] < a[idx.back()] ) {
idx.back() = i;
continue;
}else if( a[i] > a[idx.back()] ){
idx.push_back(i);
if( idx.size() == 3 ) return idx;
}
}
return idx;
}
I assume it is the user's responsibility to check whether idx.size() == 3
before he uses it.

I*g2012-11-17 08:11

39 楼

用两个值保存：
1 当前最小的值
2 当前满足存在i < j && a[i] < a[j]
中最小的a[j]
两个值初始为无穷大
suppose 从[0,m-1] 的时候这两个值是x,y
那么在考虑a[m] 的值的时候：
如果：
1) a[m]> y 找到a[m], y, x
2) a[m] < x, update x = a[m]
3) x < a[m] < y, update y = a[m]
这个好像是可以证明的因为我们一直维护了满足1 和 2 的两个值

【在 h****n 的大作中提到】

: 二爷的算法应该可以，我做个注释：
: 另外缺点是开辟了一个array，不知道有没有空间O（1）的算法
: static void Find(int[] arr)
: {
: int n=arr.length;
: int[] dp=new int[n];
: dp[n-1]=n-1;
: //dp数组里保存到从最左边到当前i元素为止最小的数的index
: for(int i=1;i: dp[i]=arr[i]

l*i2012-11-17 08:11

40 楼

数组是1 6 2 5 4 3的话, 最小的permutation是1 2 3 4 5 6么, 如果是，这个code就
有问题了。

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

: 将初始数列设为1..n，然后扫描signature, 碰到“I”就跳过，碰到连续的"D"就翻转
: 相应位置上的数字。代码如下：
: vector FindSmallestPermutation(string signature) {
: vector res(signature.size() + 1, 0);
: for (int i = 0; i < res.size(); i++) {
: res[i] = i + 1;
: }
: int pos = 0;
: int start = 0;
: while (pos < signature.size()) {

s*k2012-11-17 08:11

41 楼

貌似不能直接扫描左最小，右边最大吧，比如3.4.5.1.7,这样扫出来最小最大是1,7，
而返回应该是3,4，5

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

:
: 出的
: 你看看我的那个对吗

w*o2012-11-17 08:11

42 楼

不是只保留一个最小值和一个最大值，二爷的是意思是保留从左到右的所有当前最小值
，比如扫3的时候，当前最小值是3，到4的时候，当前最小值仍然是3，到5的时候，当
前最小值还是3，只有到1的时候才更新当前最小值为1
同样找所有从右到左的当前最大值，
这样虽然不能找到3，4，5，但能找到3，5，7.反正能找到一组就行。

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

: 貌似不能直接扫描左最小，右边最大吧，比如3.4.5.1.7,这样扫出来最小最大是1,7，
: 而返回应该是3,4，5

s*k2012-11-17 08:11

43 楼

没有仔细看程序，不过随时更新min val可能有问题吧，比如4519,45本身没法构成
tripple，然后遇到1之后把1放到第一位也不对吧

值;

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

: 多谢!确实是个很低级的错误...
: 不过我觉得这个办法修改一下还是可行的。按照你的提醒，更新的思路如下：
: 1. 对每一个值，都判断是否大于first并且小于second, 如果是则更新second为当前值;
: 2. 用一个新的min_val变量记录当前为止遇到的最小值，遇到increased pair时，如果
: 不能返回结果，则更新first使其为min_val, 并继续扫描。
: 更新后的代码如下，请指正~
: vector FindIncreasingNum(vector vec) {
: if (vec.size() < 3)
: return vector();
: int first = INT_MAX;

w*o2012-11-17 08:11

44 楼

第一题，O(n) with O(1) space:
public static void main(String[] args) {
int[] test = {-2,-101,-100,-102,-1};

int[] ret = new int[3];
int count = 1;
int min = 0;
for(int i = 1; i < test.length; i++) {
int x = test[i];
if(x > test[ret[count - 1]]) {
ret[count++] = i;
if(count == 3) break;
} else {
if(x <= test[min])
min = i;
else {
ret[0] = min;
ret[1] = i;
count = 2;
}
}
}
if(count == 3)
System.out.println("found!");
else
System.out.println("can not find");
}

Y*f2012-11-17 08:11

45 楼

反转的思路不错

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

: 将初始数列设为1..n，然后扫描signature, 碰到“I”就跳过，碰到连续的"D"就翻转
: 相应位置上的数字。代码如下：
: vector FindSmallestPermutation(string signature) {
: vector res(signature.size() + 1, 0);
: for (int i = 0; i < res.size(); i++) {
: res[i] = i + 1;
: }
: int pos = 0;
: int start = 0;
: while (pos < signature.size()) {

Y*f2012-11-17 08:11

46 楼

我写的第一题，和前面的思路差不多，找到输出3个元素的数组，否则返回空数组
vector incrSeq(vector& vect)
{
int curMin = INT_MAX;
vector ret(3, INT_MAX);
for (int i = 1; i < vect.size(); i++)
{
if (vect[i] > ret[1])
{
ret[2] = vect[i];
return ret;
}
else if (vect[i] < curMin)
curMin = vect[i];
else if (vect[i] < ret[1])
{
ret[0] = curMin;
ret[1] = vect[i];
}
}
ret.clear();
return ret;
}

,4

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

: 1. Given a array of integers , find 3 indexes i,j,k such that, i<
: j: 这个怎么搞呢，O(n)可能吗？
: 2.You are given an array of n elements [1,2,....n]. For example {3,2,1,6,7,4
: ,5}.
: Now we create a signature of this array by comparing every consecutive pir
: of elements. If they increase, write I else write D. For example for the
: above array, the signature would be "DDIIDI". The signature thus has a
: length of N-1. Now the question is given a signature, compute the
: lexicographically smallest permutation of [1,2,....n]. Write the below

w*x2012-11-17 08:11

47 楼

谁给看看这题是不是对的？

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

: 第一题，O(n) with O(1) space:
: public static void main(String[] args) {
: int[] test = {-2,-101,-100,-102,-1};
:
: int[] ret = new int[3];
: int count = 1;
: int min = 0;
: for(int i = 1; i < test.length; i++) {
: int x = test[i];
: if(x > test[ret[count - 1]]) {

w*x2012-11-17 08:11

48 楼

第二题是不是要以I*D* 为单位数，每次取最小的区间
比如DDIIIDDIID
DD ==> 区间[1,3] => 3 2 1
IIIDD ==> 区间[4,8] => 4 5 8 7 6
IID ==> 区间[9,11] ==> 9, 11, 10

l*b2012-11-17 08:11

49 楼

对的吧，我也刚写了个，发现思路一样
void threeIncSeq(vector seq) {
/* find three index i,j,k seq[i] < seq[j] < seq[k] */
int cl = -1, ch = -1, t = 0;
int i, n = seq.size();
for(i = 1; i < n; ++i) {
if(ch != -1 && seq[i] > seq[ch])
break;
if(seq[i] > seq[t]) {
cl = t;
ch = i;
t = cl;
}
else
t = i;
}
if(i < n && ch != -1)
cout << seq[cl] << " " << seq[ch] << " " << seq[i] << endl;
}

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

: 第二题是不是要以I*D* 为单位数，每次取最小的区间
: 比如DDIIIDDIID
: DD ==> 区间[1,3] => 3 2 1
: IIIDD ==> 区间[4,8] => 4 5 8 7 6
: IID ==> 区间[9,11] ==> 9, 11, 10

l*b2012-11-17 08:11

50 楼

嗯。。我是按这个写的，感觉比翻转容易写错，改了3，4遍
void reconstruct(string &s) {
/* reconstruct minimal lexical seq with DIDI */
int n = s.size();
int m = 1; // minimal current availabe number
int i = 0;
while(i < n) {
if(s[i] == 'I') {
cout << m++ << " "; // output
i++;
}
else {
int j;
for(j = i; j < n && s[j] != 'I'; ++j)
;
int t = m + j - i + 1;
for(; i <= j; ++i)
cout << m + j - i << " "; // output
m = t;
}
}
if(s[n-1] == 'I')
cout << m; // output
cout << endl;
}

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

: 第二题是不是要以I*D* 为单位数，每次取最小的区间
: 比如DDIIIDDIID
: DD ==> 区间[1,3] => 3 2 1
: IIIDD ==> 区间[4,8] => 4 5 8 7 6
: IID ==> 区间[9,11] ==> 9, 11, 10

c*t2012-11-17 08:11

51 楼

第一题，简单些的思路，一个min数组存a[i]左面min,一个max数组存a[i]右面max
找min[i]发现前面大家都说过了，自己写了一个，看完二爷的，自卑了，还是研究一下O(1)空间
吧

,4

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

: 1. Given a array of integers , find 3 indexes i,j,k such that, i<
: j: 这个怎么搞呢，O(n)可能吗？
: 2.You are given an array of n elements [1,2,....n]. For example {3,2,1,6,7,4
: ,5}.
: Now we create a signature of this array by comparing every consecutive pir
: of elements. If they increase, write I else write D. For example for the
: above array, the signature would be "DDIIDI". The signature thus has a
: length of N-1. Now the question is given a signature, compute the
: lexicographically smallest permutation of [1,2,....n]. Write the below

c*t2012-11-17 08:11

52 楼

加一个previous min 变量，写了一个干用逻辑做的, O(1)。帮忙看看对不对？
public static void find2(int[] arr) {
if (arr == null || arr.length < 3)
return;
int n = arr.length;

int premin =0, mid=-1, min=-1;

for(int i=1; iif(mid == -1) {
if(arr[i]>arr[premin]) mid=i;
else premin=i;
}else{
if(arr[i]else if (arr[i]mid=i;
if(min!=-1) premin = min;
}else if(arr[i] > arr[mid]){
System.out.println(arr[premin]+" "+arr[mid]+" "+arr[i]);
}
}
}
}

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

: 第一题，简单些的思路，一个min数组存a[i]左面min,一个max数组存a[i]右面max
: 找min[i]: 发现前面大家都说过了，自己写了一个，看完二爷的，自卑了，还是研究一下O(1)空间
: 吧
:
: ,4

s*32012-11-17 08:11

53 楼

好像有问题。
1,100,1,99,100
Change:
else if (arr[i] < arr[mid]) {
to:
else if (arr[i] < arr[mid] && arr[i] > arr[premin]) {

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

: 加一个previous min 变量，写了一个干用逻辑做的, O(1)。帮忙看看对不对？
: public static void find2(int[] arr) {
: if (arr == null || arr.length < 3)
: return;
: int n = arr.length;
:
: int premin =0, mid=-1, min=-1;
:
: for(int i=1; i: if(mid == -1) {

c*t2012-11-17 08:11

54 楼

是的。多谢！

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

: 好像有问题。
: 1,100,1,99,100
: Change:
: else if (arr[i] < arr[mid]) {
: to:
: else if (arr[i] < arr[mid] && arr[i] > arr[premin]) {

f*m2012-11-17 08:11

55 楼

能否用backtracking？从左到右每个位置都有机会取值1~9，某一位invalid的条件是根
据这一位前面各位的取值以及D，I情况，这一位小于1或者大于9。若某一位invalid，
则backtrack，前一位取另一个值。
不过麻烦了些。

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

: 将初始数列设为1..n，然后扫描signature, 碰到“I”就跳过，碰到连续的"D"就翻转
: 相应位置上的数字。代码如下：
: vector FindSmallestPermutation(string signature) {
: vector res(signature.size() + 1, 0);
: for (int i = 0; i < res.size(); i++) {
: res[i] = i + 1;
: }
: int pos = 0;
: int start = 0;
: while (pos < signature.size()) {