Bài tập almostIncreasingSequence trên codefight

python
python3

(Chém gió lên thần) #21

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

(Hung) #22

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


(Evil Artist) #23

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 ;


(Nguyen Ca) #24

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


(‏) #25

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


(Nguyen Ca) #26

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


(Trần Hoàn) #27

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:


(Lê Thiên Cường) #28

Chưa thấy bạn đánh dấu solution nên gửi bạn code của mình, chưa biết có chính xác không =))

def almostIncreasingSequence(sequence):
    delete = 0
    for i in range(1, len(sequence)-1):
        if sequence[i-1] >= sequence[i]:
            if sequence[i] >= sequence[i+1]:
                return False
            else:
                if (sequence[i+1] == sequence[i-1]) and (i>1):
                    return False
                if sequence[i+1] < sequence[i-1]:
                    j = i
                    while (sequence[j] >= sequence[i]) and (j>0):
                        j -= 1
                    if i - j >= 3:
                        return False
                delete += 1
        if delete > 1:
            return False
    return True

ý tưởng: nếu đang duyệt dãy thấy thằng nào thọt thì kiểm tra xem phải xóa bao nhiêu số

  1. s[i-1] >= s[i] >= s[i+1] tức là phải xóa 2 số để dãy tăng => False
  2. s[i-1] >= s[i] <= s[i+1]:
    Nếu s[i+1] > s[i-1] thì xóa 1 số (s[i])
    Nếu s[i+1] = s[i-1] (và i>1) thì phải xóa 2 số => False
    Nếu không hoặc là phải xóa s[i] và s[i+1] => False; hoặc là đếm xem có bao nhiêu số liền trước s[i] cần xóa (lớn hơn s[i])

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