CodeSignal 刷题 —— almostIncreasingSequence

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.

Example

  • For sequence = [1, 3, 2, 1], the output should be
    almostIncreasingSequence(sequence) = false.

    There is no one element in this array that can be removed in order to get a strictly increasing sequence.

  • For sequence = [1, 3, 2], the output should be
    almostIncreasingSequence(sequence) = true.

    You can remove 3 from the array to get the strictly increasing sequence [1, 2]. Alternately, you can remove 2 to get the strictly increasing sequence [1, 3].

Input/Output

    • [execution time limit] 0.5 seconds (cpp)

    • [input] array.integer sequence

      Guaranteed constraints:
      2 ≤ sequence.length ≤ 105,
      -105 ≤ sequence[i] ≤ 105.

    • [output] boolean

      • Return true if it is possible to remove one element from the array in order to get a strictly increasing sequence, otherwise return false.

Python3解法:

 1 import copy
 2 
 3 def isSequence(lst):
 4     for i in range(len(lst)):
 5         if lst.count(lst[i]) > 1:      #如果列表中有重复的数字,返回False
 6             return False
 7     sort_lst = copy.copy(lst)
 8     sort_lst.sort()
 9     if lst == sort_lst:
10         return True
11     else:
12         return False
13 
14 
15 def almostIncreasingSequence(sequence):
16     if isSequence(sequence):
17         return True
18     i = 0
19     while i < len(sequence):
20         sequence_copy = copy.copy(sequence)
21         del sequence_copy[i]                   # 循环,一个一个删除,查看剩余序列是否严格递增有序
22         if isSequence(sequence_copy):
23             return True
24         i += 1
25 
26     return False
27 
28 print(almostIncreasingSequence([1,2,1,2]))

C++解法:

 1 bool isSequence(vector<int> sequence)
 2 {
 3     set<int>iset;
 4     for(auto e: sequence)
 5         iset.insert(e);
 6     if(iset.size() != sequence.size())     //如果sequence中有重复元素,返回false
 7         return false;
 8 
 9     vector<int>v = sequence;               //如果sequence与排序后的v相等,则说明sequence是递增有序的
10     sort(v.begin(), v.end());
11     if(sequence == v)
12         return true;
13     else
14         return false;
15 
16 }
17 
18 bool almostIncreasingSequence(std::vector<int> sequence) 
19 {
20     if (isSequence(sequence))
21         return true;
22     int i = 0;
23     while (i < sequence.size())
24     {
25         vector<int> v = sequence;
26         v.erase(v.begin() + i);
27         if(isSequence(v))
28             return true;
29         ++i;
30     }
31     return false;
32 }
原文地址:https://www.cnblogs.com/FengZeng666/p/9749953.html