一道简单算法题求助 - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>JobHunting - 待字闺中

一道简单算法题求助

一道简单算法题求助# JobHunting - 待字闺中

w*n2018-05-20 07:05

1 楼

Given a sequence of integers as an array, determine whether it is possible
to obtain a strictly increasing sequence by removing no more than one
element from the array.
写一个方法，判断一个给定的 int 数组（长度 > 2）能不能从数组中去除一个
int，使这个新数组严格递增。
比如数组位【1，3，2，1】 , 不能除去一个元素使数组严格递增，返回false；
数组【1，3，2】，除去一个元素可得【1，3】，或者【1，2】，可以严格递增，返
回true；
数组中的int 范围为 10的-5次方到 10的5次方。数组长度为2 到10的5次方。
我的解法：
boolean almostIncreasingSequence(int[] sequence) {
if(sequence.length ==2 ){
return true;
}

boolean result = true;

for(int i = 0; iresult = true;
int [] arr = Arrays.copyOf(sequence, sequence.length);
System.arraycopy(arr, i+1 , arr , i, sequence.length-1-i);
for(int j = 0; j < arr.length -2; j++){
if(arr[j] >= arr[j+1]){
result = false;
break;
}
}

if(result) break;
}

return result;
}
虽然结果对，但是超时。请问有没有好的解法？

m*q2018-05-20 07:05

2 楼

找到第一个非递增的pair，看看去掉pair的第一个或者第二个，剩下的是不是递增。
O(n) 不知道有木有更好的解法

m*q2018-05-20 07:05

3 楼

你的算法太暴力。O(n2)了。不要每个都去判断

w*n2018-05-20 07:05

4 楼

多谢大侠指导，我再痛苦的想一下，想不出来就得麻烦你给答案了。

i*r2018-05-20 07:05

5 楼

可不可以换一个思路。
let's define original array(n) = {x1, x2, ..., xn}
let's compute the "diff of array(n)" = {x2- x1, x3 - x2, ..., xn - x(n-1)}.
While doing above computation, if within "diff of array(n)", there is only 1
element less than 0, than return true. OW, return false.

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

: Given a sequence of integers as an array, determine whether it is possible
: to obtain a strictly increasing sequence by removing no more than one
: element from the array.
: 写一个方法，判断一个给定的 int 数组（长度 > 2）能不能从数组中去除一个
: int，使这个新数组严格递增。
: 比如数组位【1，3，2，1】 , 不能除去一个元素使数组严格递增，返回false；
: 数组【1，3，2】，除去一个元素可得【1，3】，或者【1，2】，可以严格递增，返
: 回true；
: 数组中的int 范围为 10的-5次方到 10的5次方。数组长度为2 到10的5次方。
: 我的解法：

M*d2018-05-20 07:05

6 楼

恕我愚钝，987654321，怎么obtain a strictly increasing sequence by removing <
1 number ?

g*y2018-05-20 07:05

7 楼

这个是不可以的，楼上的意思是这样的情况不需要每次都删除就可以。

<

【在 M*******d 的大作中提到】

: 恕我愚钝，987654321，怎么obtain a strictly increasing sequence by removing <
: 1 number ?

J*42018-05-20 07:05

8 楼

这个不是很简单吗，难道我想错了。定义icount初为0。从数组第一个和下一个比较，
如果下一个比第一个小，则计数器icount加1.同时丢掉这个叫下一个的元素，用接下来
的再比较，如果icount超过1就直接返回FALSE，循环结束icount小于等于1就返回true.
int icnt=0 ,m=0,n=1
while(n{
if (a[m]>a[n])
{icnt ;
if (icnt>1) return false ;
n ;
}
else
{
m ;
n ;
}
}
return true;

J*42018-05-20 07:05

9 楼

怎么加加符号没了

J*42018-05-20 07:05

10 楼

icnt,m,n后面各少两加号。买买提bug把两加号给丢了

w*n2018-05-20 07:05

11 楼

非常感谢你的回答，但是你这个解答有错：
数组【1，2，1，2】正确结果为false
但是你的返回true

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

: icnt,m,n后面各少两加号。买买提bug把两加号给丢了

J*42018-05-20 07:05

12 楼

丢掉的处理改正，应该丢掉两个并记录
int icnt=0 ,m=0,n=1,jump=0,m1;
while(n{if (a[m]>a[n])
{icnt=icnt 1;
if (icnt>1) return false ;
m1=m;
if (m=0) m=2;else m=m -1;
n=n 1;
jump=2;
}else{
m=m 1 jump;
n=n 1;
jump=0;
}}
if (icnt=0) return true;
if (m1=0) {
if (a[1]}else
{if ( (a[m1-1]

d*n2018-05-20 07:05

13 楼

班车上手机作答一下
先从前往后扫相邻的两两比较遇到不递增的则删掉较大数此后若一直递增则true
再从后往前扫两两比较遇到不递减的则删掉较小的此后若一直递减则true
最后俩结果或一下

d*n2018-05-20 07:05

14 楼

3天不刷题赶不上刘少奇现在完全没有做题的感觉了

J*42018-05-20 07:05

15 楼

处理改正，应该丢掉两个并记录
int icnt=0 ,m=0,n=1,jump=0,m1;
while(n{if (a[m]>a[n])
{icnt=icnt 1;
if (icnt>1) return false ;
m1=m;
if (m=0) m=2;else m=m -1;
n=n 1;
jump=2;
}else{
m=m 1 jump;
n=n 1;
jump=0;
}}
if (icnt=0) return true;
if (m1=0) {
if (a[1]}else
{if ( (a[m1-1]

J*42018-05-20 07:05

16 楼

买买题真垃圾，怎么提交老丢字符。改正的主体思路是一路每两个比下去，当下一个比
上一个小，就把这两个丢掉但记录。然后继续每相邻两个比较，当出现两次下一个比上
一个小则返回FALSE。当循环结束如果从没出下一个比上一个大现则返回true，如果只
出现一次就比较那两个丢掉的元素，只要其中一个在那隔两位的数中间就返回true，否
则FALSE

c*e2018-05-20 07:05

17 楼

对，根本不用丢。
如果相邻两个的逆序多于一个，false；如果没有逆序，true；如果正好一个，看去掉
这两个数之一是否单调

: 买买题真垃圾，怎么提交老丢字符。改正的主体思路是一路每两个比下去，当下
一个比

: 上一个小，就把这两个丢掉但记录。然后继续每相邻两个比较，当出现两次下一
个比上

: 一个小则返回FALSE。当循环结束如果从没出下一个比上一个大现则返回true，
如果只

: 出现一次就比较那两个丢掉的元素，只要其中一个在那隔两位的数中间就返回
true，否

: 则FALSE

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

: 买买题真垃圾，怎么提交老丢字符。改正的主体思路是一路每两个比下去，当下一个比
: 上一个小，就把这两个丢掉但记录。然后继续每相邻两个比较，当出现两次下一个比上
: 一个小则返回FALSE。当循环结束如果从没出下一个比上一个大现则返回true，如果只
: 出现一次就比较那两个丢掉的元素，只要其中一个在那隔两位的数中间就返回true，否
: 则FALSE

i*l2018-05-20 07:05

18 楼

如果定义反序为当前数字大于等于前一个数字，难道不是就检查有没有不超过两个
反序的情况吗？还有一个隐含的条件，当前数字大于前一个数字，但是小于以前
的数字中最大的，那么也属于反序。反序的数目小于 2 的情况都是 ok的。
O(n) 复杂度
bool resolve(const std::vector& data)
{
int prev = INT_MIN, mmax = INT_MIN, k = 0;
for (int i : data) {
if (i <= prev || i <= mmax) k++;
prev = i;
mmax = std::max(i, mmax);
if (k >= 2) break;
}
return k < 2;
}

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

i*l2018-05-20 07:05

19 楼

貌似 prev 多余了，就时刻 track 以前的最大值就行
bool resolve(const std::vector& data)
{
int mmax = INT_MIN, k = 0;
for (int i : data) {
if (i <=mmax) k++;
mmax = std::max(i, mmax);
if (k >= 2) break;
}
return k < 2;
}

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

: 如果定义反序为当前数字大于等于前一个数字，难道不是就检查有没有不超过两个
: 反序的情况吗？还有一个隐含的条件，当前数字大于前一个数字，但是小于以前
: 的数字中最大的，那么也属于反序。反序的数目小于 2 的情况都是 ok的。
: O(n) 复杂度
: bool resolve(const std::vector& data)
: {
: int prev = INT_MIN, mmax = INT_MIN, k = 0;
: for (int i : data) {
: if (i <= prev || i <= mmax) k++;
: prev = i;

J*42018-05-20 07:05

20 楼

用电脑再发一次。处理改正，应该丢掉两个并记录，最后处理
int icnt=0 ,m=0,n=1,jump=0,m1;
while(n{if (a[m]>a[n])
{icnt=icnt+1;
if (icnt>1) return false ;
m1=m;
if (m=0) m=2;else m=m -1;
n=n+1;
jump=2;
}else{
m=m+1+jump;
n=n+1;
jump=0;
}}
if (icnt=0) return true;
if (m1=0) {
if (a[1]}else
{if ( (a[m1-1]2]) ) return true
}
return FALSE

J*42018-05-20 07:05

21 楼

是的，你表达比我简练，我就是这个意思。丢只是比较时指针索引跳过去而已，考虑到
边界状况炒年程序如下，这次用电脑发布
int icnt=0 ,m=0,n=1,jump=0,m1;
while(n{if (a[m]>=a[n])
{icnt=icnt+1;
if (icnt>1) return false ;
m1=m;
if (m=0) m=2;else m=m -1;
n=n+1;
jump=2;
}else{
m=m+1+jump;
n=n+1;
jump=0;
}}
if (icnt=0) return true;
if (m1=0) {
if (a[1]}else
{if ( (a[m1-1]2]) ) return true
}
return FALSE

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

: 对，根本不用丢。
: 如果相邻两个的逆序多于一个，false；如果没有逆序，true；如果正好一个，看去掉
: 这两个数之一是否单调
:
:
: 买买题真垃圾，怎么提交老丢字符。改正的主体思路是一路每两个比下去，当下
: 一个比
:
: 上一个小，就把这两个丢掉但记录。然后继续每相邻两个比较，当出现两次下一
: 个比上
:
: 一个小则返回FALSE。当循环结束如果从没出下一个比上一个大现则返回true，
: 如果只

z*n2018-05-20 07:05

22 楼

<
我又读了遍题目，理解错题意了。。

【在 M*******d 的大作中提到】

: 恕我愚钝，987654321，怎么obtain a strictly increasing sequence by removing <
: 1 number ?

J*42018-05-20 07:05

23 楼

边界考虑最前和最后
int icnt=0 ,m=0,n=1,jump=0,m1;
while(n{if (a[m]>=a[n])
{icnt++;
m1=m;
}
m++;
n++;
}}
if (icnt>1 ) return false;
if (icnt=0) return true;
if (m1=0) {
if (a[1]}else if (m1=length(a)-2)
{
if (a[m1-1]}
else
{if ( (a[m1-1]2]) ) return true
}
return FALSE

m*r2018-05-20 07:05

24 楼

取第一个，第二个的样本增量,（如果是严格递增，则其中一个必定成立），顶多1次全
扫描+3次判别就可以决定结果呀

m*r2018-05-20 07:05

25 楼

取第1个，第3个的样本增量,（如果是严格递增，则其中一个必定成立），顶多1次全扫
描+4次判别就可以决定结果呀

w*n2018-05-20 07:05

26 楼

受版上大牛门的启发，自己想出来了一个双检查法：终于通过了。非常感谢大侠们的
帮助。
public class AlmostIncreasingSequnece {

boolean almostIncreasingSequence(int[] s) {
int index = -1;

for(int i =1; iif(s[i-1]>= s[i]) {
index = i;
break;
}
}

if(index == -1) return true;
return check(s, index);
}

boolean check(int [] a, int index) {
for(int i = index; i< a.length-1 ; i++) {
if(a[i]>= a[i+1]) return false;
}
boolean flag1 = true;
boolean flag2 = true;

//Double check! remove a[index] and a[index-1]
// Need to remove a[index] check if a[index-1]>=a[index+1]
// and to remove a[index-1] check if a[index-2]>=a[index]

// If either condition is true, return true.
if(index >1 && indexif(a[index-2]>= a[index])flag1 = false;
if(a[index-1]>=a[index+1]) flag2 = false;
}

return (flag1 || flag2);
}
}

s*h2018-05-20 07:05

27 楼

一遍扫描即可，代码如下：
bool IsAlmostIncreasing(const vector& array) {
if (array.size() <= 2) {
return true;
}
bool deletedFlag = false;
int prev = INT_MIN;
for (size_t i = 0; i < array.size() - 1; i++) {
int cur = array[i];
int next = array[i + 1];
if (cur < next) {
prev = cur;
} else if (deletedFlag) {
// already deleted one element, return false
return false;
} else if (cur == next) {
// can delete cur (i.e. no-op except setting flag) (same effect,
either delete cur or next)
deletedFlag = true;
} else {
// if next is even <= then prev, then have to delete next, otherwise
delete cur (i.e. no-op except setting flag).
if (next <= prev) {
prev = cur;
i++;
}
deletedFlag = true;
}
}
return true;
}

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

s*s2018-05-20 07:05

28 楼

扫一遍即可，代码
https://codepad.remoteinterview.io/SFJPYQRHTK

i*l2018-05-20 07:05

29 楼

Sigh, 有反例不 work，怪不得大家代码都比我长一点.
修正后的代码才真正 work:
bool resolve(const std::vector& data)
{
int mmax = -20000, prev_mmax = -20000, k = 0;
for (int i=0; i < data.size() && k < 2; i++) {
if (data[i] >= prev_mmax && data[i] <= mmax) {
k++;
mmax = data[i];
}
else if (data[i] <= prev_mmax) { k++; }
else {
prev_mmax = mmax;
mmax = data[i];
}
}
return k < 2;
}

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

: 貌似 prev 多余了，就时刻 track 以前的最大值就行
: bool resolve(const std::vector& data)
: {
: int mmax = INT_MIN, k = 0;
: for (int i : data) {
: if (i <=mmax) k++;
: mmax = std::max(i, mmax);
: if (k >= 2) break;
: }
: return k < 2;