thảo luận [Học Tập] Topic thuật toán

Tập Làm Coder · 11/4/22

Đời Cơ Bản Là Buồn đã nói:
Khong thay ai sai priority queue nhi?

à nhầm, build mất O(N),như tui dùng duyệt tìm max từng cái là xong cũng O(N) ko mệt build pq làm gì

thaygiao3 · 11/4/22

Đời Cơ Bản Là Buồn đã nói:
Khong thay ai sai priority queue nhi?

Pq 2 phần tử, bác dùng làm j, pq thì mỗi vòng lặp là log(2) cho lần push và log(3) cho lần pop, dùng 2 biến thì nó cũng thế

socola_smile · 12/4/22

ashley_nguci đã nói:
build O(n) sao bác nhỉ, chạy tuần tự mảng, mỗi phần tử cho vào pq phải là O(nlogn) chứ

Heapify chỉ O(n) thôi bác

via theNEXTvoz for iPhone

jacky1996 · 27/4/22

topic hay, làm sóng lại nào mấy bác

Đời Cơ Bản Là Buồn · 27/4/22

socola_smile đã nói:
Heapify chỉ O(n) thôi bác

via theNEXTvoz for iPhone

heapify: log(n)
build heap: nlog(n) :rolleyes:

socola_smile · 27/4/22

Đời Cơ Bản Là Buồn đã nói:
heapify: log(n)
build heap: nlog(n)

Heapify nào logn đó bác :byebye:

via theNEXTvoz for iPhone

socola_smile · 27/4/22

À đại khái là nhiều chỗ gọi cái hàm biến cái array thành heap là heapify, ý em là heapify là quá trình này. Và nó tốn O(n) :byebye:

via theNEXTvoz for iPhone

snake_case · 6/5/22

https://codeforces.com/problemset/problem/1672/B

Bác nào hiểu đề bài này không? Theo em hiểu good string phải bắt đầu bằng A và kết thúc bằng B mà làm hoài toàn sai :cry:

thuyduong2007 · 6/5/22

snake_case đã nói:
https://codeforces.com/problemset/problem/1672/B
Xem tệp đính kèm 1145506
Bác nào hiểu đề bài này không? Theo em hiểu good string phải bắt đầu bằng A và kết thúc bằng B mà làm hoài toàn sai

Không phải bắt đầu bằng A, kết thúc bằng B. Mà toàn bộ là A trừ chữ cái cuối cùng là B.

snake_case · 6/5/22

thuyduong2007 đã nói:
Không phải bắt đầu bằng A, kết thúc bằng B. Mà toàn bộ là A trừ chữ cái cuối cùng là B.

AABBABAAAABABABAABAB
Vậy sao test case này nó lại YES được bác nhỉ
Mà test case này lại sai
ABB
Em vẫn chưa hiểu lắm

thuyduong2007 · 6/5/22

snake_case đã nói:
AABBABAAAABABABAABAB
Vậy sao test case này nó lại YES được bác nhỉ
Mà test case này lại sai
ABB
Em vẫn chưa hiểu lắm

Cái này dễ hiểu mà. Cái đầu tiên thì là do chèn AB vào giữa AB thì sẽ đc AABB. Còn cái thứ 2 thì B không phải là good string. Nên không thể lấy B chèn vào AB hoặc ngược lại.

thuyduong2007 · 6/5/22

Bài này theo t thì dùng stack. Nó khá giống bài https://leetcode.com/problems/valid-parentheses/. Nhưng nó khó hơn 1 xíu chỗ xử lý thằng A thôi.

v0ztrash · 6/5/22

snake_case đã nói:
AABBABAAAABABABAABAB
Vậy sao test case này nó lại YES được bác nhỉ
Mà test case này lại sai
ABB
Em vẫn chưa hiểu lắm

Bác đọc kĩ đề, goodstring nhỏ nhất là AB, tiếp theo là AAB, AAAB, AAAAB,…. Vì các goodstring đều có tối đa 1 B và tối thiểu 1 A, nên khi ghép vào thì đằng trước các vị trí B phải tồn tại A. Làm 1 cái biến đếm A đặt là cnt, khi gặp B nếu cnt>0 thì trừ đi 1. Nếu bằng 0 thì in ra No. Duyệt hết dãy mà chưa vi phạm thì in yes

thuyduong2007 · 6/5/22

v0ztrash đã nói:
Bác đọc kĩ đề, goodstring nhỏ nhất là AB, tiếp theo là AAB, AAAB, AAAAB,…. Vì các goodstring đều có tối đa 1 B và tối thiểu 1 A, nên khi ghép vào thì đằng trước các vị trí B phải tồn tại A. Làm 1 cái biến đếm A đặt là cnt, khi gặp B nếu cnt>0 thì trừ đi 1. Nếu bằng 0 thì in ra No. Duyệt hết dãy mà chưa vi phạm thì in yes

Cách này chuẩn này.

snake_case · 6/5/22

thuyduong2007 đã nói:
Bài này theo t thì dùng stack. Nó khá giống bài https://leetcode.com/problems/valid-parentheses/. Nhưng nó khó hơn 1 xíu chỗ xử lý thằng A thôi.

v0ztrash đã nói:
Bác đọc kĩ đề, goodstring nhỏ nhất là AB, tiếp theo là AAB, AAAB, AAAAB,…. Vì các goodstring đều có tối đa 1 B và tối thiểu 1 A, nên khi ghép vào thì đằng trước các vị trí B phải tồn tại A. Làm 1 cái biến đếm A đặt là cnt, khi gặp B nếu cnt>0 thì trừ đi 1. Nếu bằng 0 thì in ra No. Duyệt hết dãy mà chưa vi phạm thì in yes

Vâng để em đọc lại xem, tồi quá bài 800 mà cũng không nổi :beat_brick:

thuyduong2007 · 6/5/22

snake_case đã nói:
Vâng để em đọc lại xem, tồi quá bài 800 mà cũng không nổi

Cách này chuẩn này.

v0ztrash đã nói:
Bác đọc kĩ đề, goodstring nhỏ nhất là AB, tiếp theo là AAB, AAAB, AAAAB,…. Vì các goodstring đều có tối đa 1 B và tối thiểu 1 A, nên khi ghép vào thì đằng trước các vị trí B phải tồn tại A. Làm 1 cái biến đếm A đặt là cnt, khi gặp B nếu cnt>0 thì trừ đi 1. Nếu bằng 0 thì in ra No. Duyệt hết dãy mà chưa vi phạm thì in yes

Dùng stack như t nói hơi quá. K cần đến đâu. Vì bản chất nó chỉ cần lưu mỗi thằng A thôi mà. Nên count là đủ rồi.

v0ztrash · 6/5/22

à quên còn corner case, ví dụ A, hoặc AA cũng không thoả. Vì vậy cần check phần tử cuối, bắt buộc phải bằng B

thuyduong2007 · 6/5/22

v0ztrash đã nói:
à quên còn corner case, ví dụ A, hoặc AA cũng không thoả. Vì vậy cần check phần tử cuối, bắt buộc phải bằng B

Chech cái này đầu tiên. Phần tử cuối lúc nào cũng phải = B. Rồi sau đó làm y như trên.

Gâu Gâu Gâu Gâu · 7/5/22

v0ztrash đã nói:
Bác đọc kĩ đề, goodstring nhỏ nhất là AB, tiếp theo là AAB, AAAB, AAAAB,…. Vì các goodstring đều có tối đa 1 B và tối thiểu 1 A, nên khi ghép vào thì đằng trước các vị trí B phải tồn tại A. Làm 1 cái biến đếm A đặt là cnt, khi gặp B nếu cnt>0 thì trừ đi 1. Nếu bằng 0 thì in ra No. Duyệt hết dãy mà chưa vi phạm thì in yes

trước B phải tồn tại A thì xét s[i ] == s[i-1] == B thì No luôn chứ count A chi nữa

thuyduong2007 · 7/5/22

Gâu Gâu Gâu Gâu đã nói:
trước B phải tồn tại A thì xét s[i ] == s[i-1] == B thì No luôn chứ count A chi nữa

Đọc kỹ lại đề đi bạn

thảo luận [Học Tập] Topic thuật toán

Member

Senior Member

Senior Member

Senior Member

Junior Member

Senior Member

Senior Member

Senior Member

Member

Senior Member

Member

Member

Senior Member

Member

Senior Member

Member

Senior Member

Member

Senior Member

Member

Chủ đề tương tự

Thống kê chủ đề

Chia sẻ trang này