Ma trận con đối xứng

Em có một bài này và muốn làm theo QHD

Em có công thức quy hồi như này

Tuy nhiên chỉ pass 1,2 test . Mọi người có thể cho biết e sai ở đâu không.

rogp10 viết 11:36 ngày 01/10/2018

Điều kiện bị thiếu rồi bạn.

Nguyễn Đình Biển viết 11:40 ngày 01/10/2018

Thiếu gì vậy @rogp10

rogp10 viết 11:32 ngày 01/10/2018

Giả sử bạn có ma trận con 2x2 đối xứng như sau:

A X
X B

giờ bạn muốn mở rộng ra thành 3x3 thì bạn phải kiểm tra 2 điều kiện chứ không phải 1.

Ma trận 3x3 sẽ ntn:

A X Y
X B Z
Y Z C

Nói chung bạn mở ra (m+1)x(m+1) thì bạn phải kiểm tra m điều kiện mới chính xác. Tức là bài này cấp O(n^3) hay O(kq*n^2).

Với lại b[n][n] cũng không phải là nghiệm vì ma trận lớn nhất có thể không tới ô đó được. Bạn phải scan lại sau đó.

Nguyễn Đình Biển viết 11:42 ngày 01/10/2018

Đoạn trên mình hiểu rồi. Còn phần độ khó mình không biết tính áng chừng được mấy bài dễ thôi. Để mình thử làm lại

Gió viết 11:37 ngày 01/10/2018

Bài này có thể cải tiến thành O(n^2*logn) nếu sử dụng hash

rogp10 viết 11:32 ngày 01/10/2018

Làm như thế nào vậy bạn?

Gió viết 11:30 ngày 01/10/2018

phần quy hoạch động thì công thức vẫn không thay đổi, tuy nhiên phần kiểm tra điều kiện mình sẽ tính trước mb[i][j] là độ dài dài nhất của dòng i, cột j

def max_bound(a,i,j):
    for k in range(1,min(i,j)+1):
           if a[i][j-k]!=a[i-k][j]:
               return k
    return min(i,j)

cách này có dpt là O(n)

để giảm thời gian của hàm này, sử dụng rolling_hash theo dòng, cột theo chiều ngược lại, sau đó sử dụng tìm kiếm nhị phân để tìm đoạn dài nhất.

Bình luận về bài viết này

Chia sẻ tin đăng đến bạn bè

Gửi Messenger

Bài liên quan

Nguyễn Đình Biển

0 chủ đề

0 bài viết

Tác giả nổi bật

Từ khóa nổi bật

AngularJS Blog Bootstrap C / C++ Cấu trúc dữ liệu & Giải thuật Cơ sở dữ liệu Codeigniter Công cụ lập trình CSS CSS cơ bản CSS3 Học Excel HTML HTML cơ bản HTML5 Java Javascript jQuery Json Lập trình mobile Laravel Linux MongoDB MySQL NodeJS Oracle Pascal PHP PHP cơ bản PHP nâng cao Python React Native ReactJS Ruby SEO SQL Server Swift Visual Basic VueJS WordPress XML

Chủ đề nổi bật

Ma trận con đối xứng

Đăng ký nhận thông báo

HỖ TRỢ HỌC VIÊN

VỀ CODE24H

HỢP TÁC VÀ LIÊN KẾT

KẾT NỐI VỚI CHÚNG TÔI

TẢI ỨNG DỤNG TRÊN ĐIỆN THOẠI