Bài tập almostIncreasingSequence trên codefight

đú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 =)

2 Likes

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 :)))))

1 Like

xóa số 5 ở giữa là xong mà…

chắc ko có cách 1 dòng…

2 Likes

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 Like

1 < 2 < 3 < 5 ko phải à @_@

2 Likes

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ế :expressionless:

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 -_-

Summary

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#

3 Likes

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],))
2 Likes

sai với input 1 2 1 2 rồi kìa, cách 1 dòng đầu tiên của mình đó =)

2 Likes

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 :expressionless:

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

3 Likes

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)

2 Likes

Code theo phương pháp trâu bò :joy:

C#
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

3 Likes

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;
}
6 Likes

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 :confused:

3 Likes

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
4 Likes

Đã 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 :grin:

3 Likes

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 ;

1 Like

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í đó.

2 Likes

người thứ 3 có suy nghĩ như vậy rồi :joy: Ko được, vd 1 2 1 2

code 1 dòng bị quá thời gian 1 test case, cay

3 Likes

Chắc sau khi xóa kiểm tra 2 element có bằng nhau không =))

2 Likes

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 :confused:

3 Likes
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?