一道简单算法题求助

729654213 发表于 2018-5-22 02:58
返回false的条件: array中有两个value满足a1 = a3，相当于找peak value，感觉可以用binary search的方法，O ...

应该不行吧, 1 2 3 4 5 6 7 0 8, 你第一个二分到了5之后,你怎么知道往左走还是往右走呢?

这样应该没有问题了。

1. /* package whatever; // don't place package name! */
   
2. 
   
3. import java.util.*;
   
4. import java.lang.*;
   
5. import java.io.*;
   
6. 
   
7. /* Name of the class has to be "Main" only if the class is public. */
   
8. class Ideone {
   
9. static boolean IgnoreIdxCheck(int[] sequence, int idx) {
   
10.   for (int i = idx + 2; i < sequence.length; ++i) {
    
11.    if (i == idx) continue;
    
12.    if (sequence[i - 1] >= sequence[i]) return false;
    
13.   }
    
14.   if (idx != 0 && idx + 1 != sequence.length && sequence[idx - 1] >= sequence[idx + 1]) return false;
    
15.   return true;
    
16. }
    
17. static boolean almostIncreasingSequence(int[] sequence) {
    
18.   int idx = -1;
    
19.   for (int i = 1; i < sequence.length; ++i) {
    
20.    if (sequence[i-1] >= sequence[i]) {
    
21.     idx = i;
    
22.     break;
    
23.    }
    
24.   }
    
25.   if (idx == -1) return true;
    
26.   return IgnoreIdxCheck(sequence, idx - 1) || IgnoreIdxCheck(sequence, idx);
    
27. }
    
28. 
    
29. public static void main(String[] args) throws java.lang.Exception {
    
30.   System.out.println(almostIncreasingSequence(new int[] {
    
31.    1,
    
32.    2,
    
33.    2
    
34.   }) == true);
    
35.   System.out.println(almostIncreasingSequence(new int[] {
    
36.    1,
    
37.    3,
    
38.    2,
    
39.    1
    
40.   }) == false);
    
41. }
    
42. }

复制代码

vegito2002 发表于 2018-5-22 05:08
应该不行吧, 1 2 3 4 5 6 7 0 8, 你第一个二分到了5之后,你怎么知道往左走还是往右走呢?

好问题啊 没考虑到。。。水平不佳。。。但又没法删评论了T.T
又想了想 只能扫一遍先把递减的（例子里面是0）找出来，然后考虑删7还是0，再往下面走，这样的话，应该还是O(N)

有没有可能这样做：从0到n遍历，如果遇到不满足条件的的一对数字a_n+1<=a_n, 分之一：删掉a_n+1，从n开始，分之二：删掉a_n从a_n-1开始，然后对两个分支继续遍历，如果再遇到不符合条件的一堆数字，就直接return false

1. 
   
2. public class IncreasingSeq {
   
3.         public static void main(String [] args) {
   
4.                 System.out.println(aISeq(new int[] {1,2,3,4,5,6,3,4,9}) == false);
   
5.                 System.out.println(aISeq(new int[] {1,2,3,4,5,6,4,9}) == true);
   
6.                 System.out.println(aISeq(new int[] {1,2,7,3,4}) == true);
   
7.                 System.out.println(aISeq(new int[] {1,2,7,3,4,3,4}) == false);
   
8.                 System.out.println(aISeq(new int[] {1,2,7,6,3,4,}) == false);
   
9.                 System.out.println(aISeq(new int[] {1,2,3}) == true);
   
10.                 System.out.println(aISeq(new int[] {1,3,2}) == true);
    
11.                 System.out.println(aISeq(new int[] {1,2,3,4,5,6,0,7}) == true);
    
12.         }
    
13.        
    
14.         public static boolean aISeq(int[] A){
    
15.                 boolean adj = false;
    
16.                 int count = 0;
    
17.                 for(int i = 1;i<A.length;i++) {
    
18.                         int gap = A[i]-A[i-1];
    
19.                         count+= gap;
    
20.                         if(count < i-1 || gap<=0) {
    
21.                                 if(adj) return false;
    
22.                                 else {
    
23.                                         adj = true;
    
24.                                 }
    
25.                         }       
    
26.                 }
    
27.                 return true;
    
28.         }
    
29. }
    

复制代码

也来说一下自己的思路？
首先这是一个int array，如果数列严格递增的话，A[i]-A[i-1] >=1, 那么考虑sum of A[i]-A[i-1], 在任何时候一定>=i
如果中间有最多一位非严格递增的话，那么设A’ 为删除A中某element之后A'严格递增，原数列sum of A[i]-A[i-1],  少算一个元素，在任何时候一定>=i-1
在某位非严格递增可以用A[i]-A[i-1] <=0 判定
然后如果两次违反上述规律return false就可以了，其它情况return true

阿钟 发表于 2018-5-22 06:34
也来说一下自己的思路？
首先这是一个int array，如果数列严格递增的话，A-A >=1, 那么考虑sum of A-A ...

这个没完全理解，但是我找到了一个特列，
System.out.println(aISeq(new int[] {1,2,4,2}) == true);

补充内容 (2018-5-22 06:48):
。。。看错了

randrand1 发表于 2018-5-22 06:44
这个没完全理解，但是我找到了一个特列，
System.out.println(aISeq(new int[] {1,2,4,2}) == true);

System.out.println(aISeq(new int[] {-2147483648,1, 2147483647}) == true); 这个算是特列

randrand1 发表于 2018-5-22 06:52
System.out.println(aISeq(new int[] {-2147483648,1, 2147483647}) == true); 这个算是特列

overflow改用long 就行了 虽然思路应该没啥问题 写成这样就是有点懒得check前后哪个大……

补充内容 (2018-5-22 07:40):
哦，不过我觉得用long可能也有点问题，如果array太大那么还是会overflow……为了防止不overflow那么我们还是暴力考虑删哪个吧

补充内容 (2018-5-22 07:49):
啊 不对gap的最大就是-2147483648,2147483647，而且如果我们只考虑两两相邻差的全部累积，那么count最大也就是从-2147483648到 2147483647，因为是telescoping sum, count = A[i] -A[0] 但用long也是解得略难看了

阿钟 发表于 2018-5-22 06:34
也来说一下自己的思路？
首先这是一个int array，如果数列严格递增的话，A-A >=1, 那么考虑sum of A-A ...

运行你的code
[1, 3, 2] 为false， 但正确结果为true。
[1, 1, 1, 2, 3] Output:true Expected Output: false
[1, 2, 3, 4, 99, 5, 6] Output: false Expected Output: true

sickcat 发表于 2018-5-22 09:41
运行你的code
[1, 3, 2] 为false， 但正确结果为true。
[1, 1, 1, 2, 3] Output:true Expected Outpu ...

我在我机器上运行是好的啊……

补充内容 (2018-5-22 09:52):
不过我还是没能解决overflow的问题 233 就当它是个错误解吧