đúng rồi, nghĩa là 1 1 1 2 cũng ra giá trị False.
chưa nghĩ ra cách giải 1 dòng =)
đúng rồi, nghĩa là 1 1 1 2 cũng ra giá trị False.
chưa nghĩ ra cách giải 1 dòng =)
chả hiểu thế nào, e thấy test như này
Input: sequence: [1, 2, 5, 3, 5]
Output: false
Expected Output: true
e thấy dãy đó xóa kiểu gì cũng false, mà bọn codefight bảo phải trả về True mới đúng :)))))
xóa số 5 ở giữa là xong mà…
chắc ko có cách 1 dòng…
xóa số 5 ở giữa --> 1 2 3 5 ?? có phải dãy tăng nghiêm ngặt đâu bác
1 < 2 < 3 < 5 ko phải à @_@
Thuật toán đơn giản: Search từ đầu đến cuối, nếu dãy có 1 lần không tăng duy nhất thì là đúng, còn nếu nhiều hơn thì là sai. Sao code lại dài như thế
int DecreasingCount = 0;
for (int i = 0; i < sequence.Length - 1; i += 1)
if (sequence[i] >= sequence[i + 1])
DecreasingCount += 1;
return DecreasingCount <= 1;
edit: Phải thêm dòng kiểm tra xem sequence[i + 1]
có phải phần tử cuối cùng không, nếu không thì kiểm tra tiếp xem sequence[i + 2]
có lớn hơn sequence[i]
không, nếu có thì DecreasingCount += 1
, không thì DecreasingCount = 2
edit #2: Vẫn sai, thôi dẹp đi -_-
C#
bool almostIncreasingSequence(int[] sequence)
{
int DecreasingCount = 0;
for (int i = 0; i < sequence.Length - 1; i += 1)
if (sequence[i] >= sequence[i + 1])
if (i == 0)
DecreasingCount += 1;
else if (i + 1 == sequence.Length - 1)
DecreasingCount += 1;
else
{
if (sequence[i] < sequence [i + 2] || sequence[i - 1] < sequence [i + 1])
DecreasingCount += 1;
else
DecreasingCount = 2;
}
return DecreasingCount <= 1;
}
C#
1 dòng như vầy có được ko
def almostIncresingSequence(s):
return 1 >= sum((p[i] >= p[i+1]) * (1 + (p[i] >= p[i+2] and p[i-1] >= p[i+1])) for i in range(1, len(s)) for p in ([-1000000] + s + [1000000],))
sai với input 1 2 1 2 rồi kìa, cách 1 dòng đầu tiên của mình đó =)
Sai cái giề, đây là đáp án của mình hồi mình còn chơi CF, vừa mới lên copy ra đấy
edit: Ơ đm, tại sao vừa chạy thử lại sai nhỉ, hay là hồi đó mình sửa lại rồi
viết 5 dòng chi cho khổ, 1 dòng 1 >= sum(a >= b for a, b in zip(sequence[:-1], sequence[1:]))
là được rồi, mà nó ra sai =)
1 2 1 2 chỉ có 2 1 là giảm, nhưng xóa 2 nó ra 1 1 2 hay xóa 1 nó ra 1 2 2 đều là dãy ko tăng dần (có 1 == 1 và 2 == 2)
Code theo phương pháp trâu bò
bool almostIncreasingSequence(int[] sequence)
{
for (int i = 0; i < sequence.Length - 1; i += 1)
if (sequence[i] >= sequence [i + 1])
return (IncreasingSequence(RemoveFromSequence(sequence,i))||IncreasingSequence(RemoveFromSequence(sequence,i + 1)));
return true;
}
bool IncreasingSequence(int[] sequence)
{
if (sequence.Length < 2)
return true;
for (int i = 0; i < sequence.Length - 1; i += 1)
if (sequence[i] >= sequence[i + 1])
return false;
return true;
}
int[] RemoveFromSequence(int[] sequence, int Position)
{
var Output = new int[sequence.Length - 1];
for (int i = 0; i < Position; i += 1)
Output[i] = sequence[i];
for (int i = Position + 1; i < sequence.Length; i += 1)
Output[i - 1] = sequence[i];
return Output;
}
Bác nào biết Python port sang cái
Code của mình, đã test qua các test case ở trên.
P/s: Đã thêm điều kiện phần removed_index > 0
bool almost_increasing_sequence(int *sequence, int length)
{
if (length == 1 || length == 2) return true;
int removed_index = -1;
for (int i = 0; i < length - 1; i++)
if (sequence[i] >= sequence[i + 1])
{
removed_index = i;
break;
}
if (removed_index == -1)
return true;
if (removed_index == length - 2)
return true;
if (removed_index > 0 && sequence[removed_index - 1] >= sequence[removed_index + 1])
{
if (sequence[removed_index] < sequence[removed_index + 2])
removed_index++;
else
return false;
}
for (int i = removed_index + 1; i < length - 1; i++)
if (sequence[i] >= sequence[i + 1])
return false;
return true;
}
E cám ơn bác, E chuyển code của bác sang python.
def almostIncreasingSequence(sequence):
if 2<=len(sequence)<=10**5:
if any(-10**5<=sequence[i]<=10**5 for i in range(0,len(sequence)-1)):
if 1<=len(sequence)<=2:
return True
removed_index = -1
for i in range(0,len(sequence)-1,1):
if sequence[i]>=sequence[i+1]:
removed_index=i
break
print(removed_index)
if removed_index == -1:
return True
if removed_index == len(sequence)-2:
return True
if removed_index > 0 and sequence[removed_index-1]>=sequence[removed_index+1]:
return False
for i in range(removed_index+1,len(sequence)-1,1):
if sequence[i]>=sequence[i+1]:
return False
return True
Qua chạy thử em thấy tạch ở case [1, 2, 3, 4, 3, 6] case này đáng lý vẫn là True, nhưng vẫn k thỏa mãn
removed_index > 0 and sequence[removed_index-1]>=sequence[removed_index+1]: và trả về False :((
Hay e chuyển sang python bị sai
Code đúng chạy được. (em đi mượn)
def first_bad_pair(sequence):
"""Tìm vị trí đầu tiên mà phần tử trước lớn hơn phần tử sau. Nếu không tìm thấy, trả về -1, nếu tìm thấy, trả về index của phần tử đó"""
for i in range(len(sequence)-1):
if sequence[i] >= sequence[i+1]:
return i
return -1
def almostIncreasingSequence(sequence):
"""Xóa phần tử được tìm thấy bởi hàm trên, sau đó check lại. Nếu vẫn còn thì trả về false, nếu không còn thì trả về True"""
j = first_bad_pair(sequence)
if j == -1:
return True # Không tìm thấy phần tử trước > phần tử sau nên dãy đã ngon
if first_bad_pair(sequence[j-1:j] + sequence[j+1:]) == -1:
return True #Xóa phần tử được tìm thấy, sau đó kiểm tra chuỗi còn lại.
if first_bad_pair(sequence[j:j+1] + sequence[j+2:]) == -1:
return True
return False
Đã sửa lại code thêm để pass test case mới của bạn rồi.
Nếu work 100% thì xài code mượn luôn đi
chưa test:
Tìm local_max
Nếu number of max_local < 2
compare index(max_local) -1 vs imdex(max_local)+1
array a[] as input
a = @(-infinity, a, +infinity)
maxlocal = a[i] if (a[i-1] <= a[i] && a[i] <= a[i+1]) //dấu = trong TH strictly
if count(maxlocal >1) return false
else
if count(maxlocal == 1)
if (a[i-1] >= a[i+1]) return false;
else return true ;
Cái này đếm số cặp nghịch thế được ko nhỉ, > 1 trả về false. = 1 thì remove ra tại vị trí đó.
người thứ 3 có suy nghĩ như vậy rồi Ko được, vd 1 2 1 2
code 1 dòng bị quá thời gian 1 test case, cay
Chắc sau khi xóa kiểm tra 2 element có bằng nhau không =))
Thế nên mới phải thêm 1 dòng kiểm tra if (sequence[i] < sequence [i + 2] || sequence[i - 1] < sequence [i + 1])
và đồng thời kiểm tra xem cặp này có nằm ở đầu hay cuối dãy không