一道简单算法题求助

阿钟 发表于 2018-5-22 09:49
我在我机器上运行是好的啊……

补充内容 (2018-5-22 09:52):

Input: sequence: [10, 1, 2, 3, 4, 5]
Output:false
Expected Output: true

Input: sequence: [123, -17, -5, 1, 2, 3, 12, 43, 45]
Output: false
Expected Output: true

Input: sequence: [3, 4, 5, 10, 20, 10, 20, 30]
Output: true
Expected Output: false

刚想了一个思路，不确定对不对：

假设一个数组A，长度length，有可能有两种情况，
1. 数组严格递增，则返回true
2. 数组不是严格递增，需要判断

对于2的情况，如果A里只删一个元素就能变成严格递增的，不妨设该元素为A[i]，则一定有A[0...i-1]和A[i+1...length-1]分别为严格递增并且A[i-1]<A[i+1]；

所以综上1和2两种情况，扫描两遍数组A，找到最大的p使得A[0...p]是严格递增的，找到最小的q使得A[q...length-1]是严格递增的，如果
p>=q返回true，如果p+1 == q并且A[p]<A[q]返回true，其它返回false

不知道这个算法正确不

回头看了一眼， 竟然讨论如此激烈。。 意外。。

几个想法

1) op的答案有点看不懂， 如果有解释最好了。
2) 用 LIS的解法应该没问题， 是nlgn的速度，就看LIS的长度是不是 >= length - 1即可
3) 用dp解, dp[i, j] = true if sequence[i to j] is strictly increasing。 但是这个应该是n方，毕竟每一个点都得走一遍， 不知道是不是太慢

1. boolean almostIncreasingSequence(int[] sequence)
   
2.     {
   
3.         int n = sequence.length;
   
4.         f = new Boolean[n][n];
   
5.         for(int i = 0; i < n; i++)
   
6.             f[i][i] = true;
   
7.         dp(sequence, 0, n - 1);
   
8.         // for(Boolean[] ff : f)
   
9.         //     System.out.printf("%s \n", Arrays.toString(ff));
   
10.         for(int i = 1; i < n - 1; i++)
    
11.             if(f[0][i - 1] != null && f[i + 1][n - 1] != null && f[0][i -1]
    
12.                 && f[i + 1][n - 1] && sequence[i - 1] < sequence[i + 1]) return true;
    
13.         return false;
    
14.     }
    
15. 
    
16.     Boolean[][] f;
    
17. 
    
18.     boolean dp(int[] seq, int left, int right)
    
19.     {
    
20.         // System.out.printf("%d %d \n",left, right);
    
21.         if(left == right) return f[left][right] = true;
    
22.         if(left + 1 == right) return f[left][right] = seq[left] < seq[right];
    
23.         if(f[left][right] != null) return f[left][right];
    
24.         boolean res = false;
    
25.         for(int i = left; i < right; i++)
    
26.         {
    
27.             boolean li = dp(seq, left, i), ri = dp(seq, i + 1, right);
    
28.             res |= seq[i] < seq[i + 1] && li && ri;
    
29.         }
    
30.         return f[left][right] = res;
    
31.     }
    

复制代码

4) 用单一解， 这个不太成熟。。基本就是说可以退后一次。 因为如果可以变成strictly increasing的话，就代表可以往回撤一次。

1.     boolean almostIncreasingSequence(int[] sequence)
   
2.     {
   
3.         boolean f = false;
   
4.         for(int i = 1, j = 0; i < sequence.length; i++)
   
5.         {
   
6.             // System.out.printf("%d %d \n", i, j);
   
7.             if(sequence[j] < sequence[i]) j++;
   
8.             else
   
9.             {
   
10.                 j--;
    
11.                 // j too big | too small
    
12.                 if(f) return false;
    
13.                 f = true;
    
14.             }
    
15.         }
    
16.         return true;
    
17.     }   

复制代码

爆炸。。 刚才试了几个例子发现没一个对的。。

还是LIS靠谱。。

1.     boolean almostIncreasingSequence(int[] sequence)
   
2.     {
   
3.         int[] lis = new int[sequence.length];
   
4.         int k = 0;
   
5.         for(int n : sequence)
   
6.         {
   
7.             if(k < 1) lis[k++] = n;
   
8.             else
   
9.             {
   
10.                 int lo = 0, hi = k;
    
11.                 while(lo < hi)
    
12.                 {
    
13.                     int m = (lo + hi) / 2;
    
14.                     if(lis[m] < n) lo = m + 1;
    
15.                     else hi = m;
    
16.                 }
    
17.                 if(lo == k)
    
18.                     lis[k++] = n;
    
19.                 else
    
20.                     lis[lo] = Math.min(lis[lo], n);
    
21.             }
    
22.         }
    
23.         // System.out.printf("%s %d\n", Arrays.toString(lis), k);
    
24.         return k >= sequence.length - 1;
    
25.     }

复制代码

补充内容 (2018-5-22 11:10):
能过这个就应该能过这道题。。
https://leetcode.com/problems/lo ... quence/description/

Google了一下这个题目的网站，验证了一下我的算法，是对的，哈哈哈，上面的LIS也是对的。https://i.imgur.com/nlrJgJ5.png

补充内容 (2018-5-22 11:54):
题外话，其实这个题目跟我店面fb的一个题目很类似。。。。我有写面经

sickcat 发表于 2018-5-22 10:27
Input: sequence: [10, 1, 2, 3, 4, 5]
Output:false
Expected Output: true

嗯嗯 对 这个是wa了 哈哈

受版上大牛门的启发， 特别是randrand1  大侠的解法，自己想出来了一个双检查法： 终于通过了。非常感谢大侠们的帮助。
public class AlmostIncreasingSequnece {
       
    boolean almostIncreasingSequence(int[] s) {
                int index = -1;                               
               
                for(int i =1; i<s.length; i++) {
                        if(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 && index<a.length-1) {
                         if(a[index-2]>= a[index])flag1 = false;
                         if(a[index-1]>=a[index+1]) flag2 = false;
                 }
                           
                 return (flag1 || flag2);                 
         }
}

受这一篇 hsfzxjy 的回答的启发，写了一个比较简单易懂的O(n)解

1. bool almostIncreasingSequence(vector<int> sequence) {
   
2.     int n = sequence.size();
   
3.     vector<int> diff(n - 1);
   
4.     for (int i = 0; i < n - 1; ++i) {
   
5.         diff[i] = sequence[i + 1] - sequence[i];
   
6.     }
   
7.     int count = 0, index = -1;
   
8.     for (int i = 0; i < n - 1; ++i) {
   
9.         if (diff[i] <= 0) {
   
10.             ++count;
    
11.             index = i;
    
12.         }
    
13.         if (count > 1) return false;
    
14.     }
    
15.     if (count == 1) {
    
16.         if (index == 0 || index == n - 2) return true;
    
17.         if (index > 0 && (diff[index] + diff[index - 1] > 0)) return true;
    
18.         if (index < n - 2 && (diff[index] + diff[index + 1] > 0)) return true;
    
19.     }
    
20.     return false;
    
21. }

复制代码