g*******r 发帖数: 44 | 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****e 发帖数: 45 | 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*****u 发帖数: 648 | 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***o 发帖数: 1182 | 4 第一题不能o(n)吧,答案都不止n
,
【在 b****e 的大作中提到】 : 第二题用贪心算法做应该就可以了。 : 第一题正好可以参考第二题的思路,从左到右扫描,每次只track一个Increase Pair, : 遇到一个新的increase pair的时候做一个判断,如果该increase pair中的较大数比之 : 前increase pair中较大的数大,则返回结果,否则就track当前的increase pair并继 : 续扫描。 : : i< : ,4
| b****e 发帖数: 45 | 5 ca,没看清题目...要返回所有组合的话最坏情况下答案个数都有O(N3)个吧,不如直接
列举所有3个数的组合然后一一判断好了。
【在 a***o 的大作中提到】 : 第一题不能o(n)吧,答案都不止n : : ,
| D**********d 发帖数: 849 | 6 同意,除非这个 n 是可能的组合数
【在 a***o 的大作中提到】 : 第一题不能o(n)吧,答案都不止n : : ,
| g*******r 发帖数: 44 | 7 第一题是应该找到一个i,j,k就可。
你第二题说贪心是咋做的呢?说详细点行吗,谢谢了。
【在 b****e 的大作中提到】 : ca,没看清题目...要返回所有组合的话最坏情况下答案个数都有O(N3)个吧,不如直接 : 列举所有3个数的组合然后一一判断好了。
| b****e 发帖数: 45 | 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*****u 发帖数: 1796 | 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********r 发帖数: 286 | 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;i
if(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*****2 发帖数: 21240 | 11
如果这样的话,不是跟那个股票的第三题类似了吗?
【在 g*******r 的大作中提到】 : 第一题是应该找到一个i,j,k就可。 : 你第二题说贪心是咋做的呢?说详细点行吗,谢谢了。
| h****n 发帖数: 1093 | 12 貌似比股票第三题还简单一点,那个需要找差值最大的
【在 p*****2 的大作中提到】 : : 如果这样的话,不是跟那个股票的第三题类似了吗?
| p*****2 发帖数: 21240 | 13
是呀。两边扫纪录左边最小值,右边最大值就可以了。没什么难度了。
【在 h****n 的大作中提到】 : 貌似比股票第三题还简单一点,那个需要找差值最大的
| q****m 发帖数: 177 | 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****m 发帖数: 177 | 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*****1 发帖数: 134 | 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*****1 发帖数: 134 | 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*****2 发帖数: 21240 | 18 写了一下第一题
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--)
{
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****e 发帖数: 45 | 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*****1 发帖数: 134 | 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********i 发帖数: 568 | 21 bool find_increasing_triple(int A, int len, int first=0; int second=0;int
third=0){
for(i=0;i
if(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;j
if(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]=5
for 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*****2 发帖数: 21240 | 22
出的
你看看我的那个对吗
【在 s*****1 的大作中提到】 : 这个解法应该也是不对的,我如果给定 1,100,99,100的话,根据这个算法是显示不出的 : 但的确有解,那就是 1,99,100。 : 或如给定 1,100,99,100,96的话,也不行吧 : 我再看看上面一个解法
| z********i 发帖数: 568 | 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****e 发帖数: 45 | 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*****1 发帖数: 134 | 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********i 发帖数: 568 | 26 把lexicographically smallest 改成lexicographically largest。greedy algorithm
still works or not?
,4
【在 g*******r 的大作中提到】 : 第一题是应该找到一个i,j,k就可。 : 你第二题说贪心是咋做的呢?说详细点行吗,谢谢了。
| h****n 发帖数: 1093 | 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;i
dp[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****n 发帖数: 1093 | 28 应该一样的思路吧。。
初始化序列 n....1
然后扫描,遇到连续的I比如(i,j)是I,则翻转这段即可,遇到D则skip
algorithm
【在 z********i 的大作中提到】 : 把lexicographically smallest 改成lexicographically largest。greedy algorithm : still works or not? : : ,4
| s*****1 发帖数: 134 | 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*****u 发帖数: 1796 | 30 可以的啊,第一步的时候arr[1]
,就
前位
【在 s*****1 的大作中提到】 : 这个想法好厉害啊! :
| | | b***m 发帖数: 5987 | 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*******4 发帖数: 64 | 32 lis的特殊情况
【在 b***m 的大作中提到】 : 我也总算是看明白了。求空间O(1)的解法。 : : [i-1]; :="" ...................="">
| C*******n 发帖数: 24 | 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****n 发帖数: 1093 | 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****n 发帖数: 1093 | 35 lis需要 nlgn的复杂度
lis的特殊情况
★ Sent from iPhone App: iReader Mitbbs Lite 7.56
【在 f*******4 的大作中提到】 : lis的特殊情况
| f*******4 发帖数: 64 | 36 这里的特殊就是3is...
【在 h****n 的大作中提到】 : lis需要 nlgn的复杂度 : : lis的特殊情况 : ★ Sent from iPhone App: iReader Mitbbs Lite 7.56
| s********1 发帖数: 10 | 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*********n 发帖数: 4553 | 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*********g 发帖数: 93 | 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*****i 发帖数: 136 | 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********k 发帖数: 6180 | 41 貌似不能直接扫描左最小,右边最大吧,比如3.4.5.1.7,这样扫出来最小最大是1,7,
而返回应该是3,4,5
【在 p*****2 的大作中提到】 : : 出的 : 你看看我的那个对吗
| w***o 发帖数: 109 | 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********k 发帖数: 6180 | 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***o 发帖数: 109 | 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********f 发帖数: 410 | 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********f 发帖数: 410 | 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****x 发帖数: 2483 | 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****x 发帖数: 2483 | 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*******b 发帖数: 2586 | 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*******b 发帖数: 2586 | 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********t 发帖数: 5706 | 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********t 发帖数: 5706 | 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; i
if(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*********3 发帖数: 389 | 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********t 发帖数: 5706 | 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*********m 发帖数: 726 | 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()) {
|
|