Làm tý algorithms nào mấy tml

Thích_Yến_Trân · 27/10/22

Bài này xưa t học về cặp ngoặc đúng thì th có dạy dùng tham lam nhưng để gthich tự nhiên nhất thì t chịu

Thích_Yến_Trân · 27/10/22

LQDuy:
Học toán trên xnxx à

Này tin mà =))

peter184 · 27/10/22

LQDuy:
tao quên hết mẹ thuật toán rồi, giờ đang muốn học lại hehe hay mày lập 1 topic ae vào làm cùng luôn đề nội quy rõ ràng vào, thấy trình bày như bọn voz ấy

Tao thấy cái này hay á, lập topic anh em vô làm chơi

Bé mều · 27/10/22

Lê nin:
Giải cái db này làm gì nhỉ

Tạo fame. Có mấy nơi m giải hết là gg fb inbox mời m đi làm liền

Bé mều · 27/10/22

(I) vầy là valid Lồn r đấy

DướiNhững CơnMưa · 27/10/22

Bài này O(n) thôi, dùng stack hoặc 2 pointer hoặc dp or backtrack đều được

lucho · 27/10/22

peter184:
Mày nói từ dấu ")" đến dấu ")" cuối cùng, trong đoạn đó nếu gặp "(" thì return false. Trường hợp đó không đúng với case này "(())()", case này vẫn là true

À thế t hiểu sai đề
Kiểu ((*)()()() vẫn true đúng kh

themngucdep · 27/10/22

Bài này O(n), nếu dùng stack thì có thể lớn hơn O(n) trong t/h có dấu "*" (tao ko chắc vì chưa suy nghĩ sâu vô tối ưu thế nào).

1 cách chắc kèo để O(N) là biểu diễn cái biểu thức trên dưới dạng regular expresion của epsilon-NFA rồi viết engine convert epsilon-NFA về DFA, sau đó viết cái function để check DFA là xong. Viết thì phức tạp nhưng chắc chắn O(n), các compilers khi dịch các biểu thức cũng dùng phương pháp này thôi.

DướiNhững CơnMưa · 27/10/22

bài này cần đếm số ')'
số ')' cần bằng số '(' gọi là c đi

c sẽ nằm trong khoảng [cmin, cmax]

cmin là số lượng '(' tối thiểu (do có dấu * và cần được pair)
còn cmax là số lượng '(' tối đa có thể pair

ví dụ
đối với '(' thì cmin là 1
đối với '(*(' thì cmin là 1, cmax là 3 vì * có thể là '(' hoặc '' hoặc ')'

vậy điều kiện thỏa mãn đó là cmax sẽ luôn phải >= 0 và cmin = 0 sau khi duyệt hết

leductrung2812 · 27/10/22

Hóng

peter184 · 27/10/22

DướiNhững CơnMưa:
bài này cần đếm số ')'
số ')' cần bằng số '(' gọi là c đi

c sẽ nằm trong khoảng [cmin, cmax]

cmin là số lượng '(' tối thiểu (do có dấu * và cần được pair)
còn cmax là số lượng '(' tối đa có thể pair

ví dụ
đối với '(' thì cmin là 1
đối với '(*(' thì cmin là 1, cmax là 3 vì * có thể là '(' hoặc '' hoặc ')'

vậy điều kiện thỏa mãn đó là cmax sẽ luôn phải >= 0 và cmin = 0 sau khi duyệt hết

Hay

Freud5252 · 27/10/22

Tao dùng ít tiếng anh tại đéo học tin ở Việt Nam. Có j tự dịch nhé.

Ý tưởng của solution của tao là xử lý "*" riêng biệt cho mỗi trường hợp nó được coi là "(" , ")", và empty string.

Đầu tiên cho trường hợp "*" được coi như là "(".
Sử dụng 2 stack. 1 stack s1 lưu vị trí của "(" và 1 stack s2 lưu vị trí của "*". Nếu gặp ")" và s1 ko empty thì pop "(" ra khỏi s1. Còn nếu s1 empty và s2 ko empty thì pop "*" ra khỏi s2 (lúc này "*" sẽ được coi như là "(" ). Trong trường hợp gặp ")" và cả s1 lẫn s2 đều empty thì chắc chắn invalid và return False.

Sau khi traverse cái string xong thì m chắc chắn sẽ xử lý hết được các trường hợp "*" được coi là "(". Lúc này chỉ cần traverse 2 cái stack s1 s2 1 lần nữa. Mục đích là để xử lý những trường hợp "*" được coi là ")". Lúc này "*" sẽ được coi là ")" nên vị trí của nó buộc phải đứng sau "(". Vì s1 s2 lưu vị trí nên mày chỉ cần so sánh 2 cái entry cuối của s1 s2 là được. s1[-1] sẽ luôn luôn phải nhỏ hơn s2[-1] để pop cả 2 ra khỏi 2 stack. Nếu ko thì invalid luôn và return False. Lặp lại cho đến khi s1 hoăc s2 ko còn phần tử nào nữa.

Đến đây sẽ còn trường hợp cuối cùng là "*" được coi như là empty string. Lúc này nếu như s1 rỗng ko có phần tử nào tức là hết "(" và tất cả "*" sẽ đc coi là empty, hay valid. Còn nếu không thì sẽ invalid và return False.

Freud5252 · 27/10/22

Freud5252:
Tao dùng ít tiếng anh tại đéo học tin ở Việt Nam. Có j tự dịch nhé.

Ý tưởng của solution của tao là xử lý "*" riêng biệt cho mỗi trường hợp nó được coi là "(" , ")", và empty string.

Đầu tiên cho trường hợp "*" được coi như là "(".
Sử dụng 2 stack. 1 stack s1 lưu vị trí của "(" và 1 stack s2 lưu vị trí của "*". Nếu gặp ")" và s1 ko empty thì pop "(" ra khỏi s1. Còn nếu s1 empty và s2 ko empty thì pop "*" ra khỏi s2 (lúc này "*" sẽ được coi như là "(" ). Trong trường hợp gặp ")" và cả s1 lẫn s2 đều empty thì chắc chắn invalid và return False.

Sau khi traverse cái string xong thì m chắc chắn sẽ xử lý hết được các trường hợp "*" được coi là "(". Lúc này chỉ cần traverse 2 cái stack s1 s2 1 lần nữa. Mục đích là để xử lý những trường hợp "*" được coi là ")". Lúc này "*" sẽ được coi là ")" nên vị trí của nó buộc phải đứng sau "(". Vì s1 s2 lưu vị trí nên mày chỉ cần so sánh 2 cái entry cuối của s1 s2 là được. s1[-1] sẽ luôn luôn phải nhỏ hơn s2[-1] để pop cả 2 ra khỏi 2 stack. Nếu ko thì invalid luôn và return False. Lặp lại cho đến khi s1 hoăc s2 ko còn phần tử nào nữa.

Đến đây sẽ còn trường hợp cuối cùng là "*" được coi như là empty string. Lúc này nếu như s1 rỗng ko có phần tử nào tức là hết "(" và tất cả "*" sẽ đc coi là empty, hay valid. Còn nếu không thì sẽ invalid và return False.

Cái này vẫn O(n) nhưng space cũng là O(n). Dùng nhiều hơn các solution greedy khác.
Nhưng t thấy nó có vẻ dễ hiểu hơn :))

DướiNhững CơnMưa · 27/10/22

DướiNhững CơnMưa · 27/10/22

peter184:
Hay

JavaScript:

checkValidString=(s,m=n=0)=>(x=[...s].some(v=>(v==')'?n--:n++,v=='('?m++:(m=Math.max(m-1,0)),n<0?1:0)),x?0:!m)

code t đấy mới submit xong, Time O(n), Space O(1)

Comet · 27/10/22

Code:

int c1, c2 = 0
for (int i=0; i<s.length; i++) {
    if (s[i] == ‘(‘ ) c1 +=1
    if (s[i] == ‘)’ ) c1 -=1
    if (s[i] == ‘*’ ) c2 +=1
    if (c1<0 && c2>0) {
       c1 +=1
       c2 -=1
    }
    if (c1<0 && c2<=0) return false
}
if (c1==0) return true
if (c2>=c1) return true
return false

Đại khái thế

lucho · 28/10/22

Chúng m ko để ý điều kiện ( left, ) right à mà chỉ chăm chăm vào đếm thế.

Dongu2009 · 28/10/22

clorua7:
có phải thế này ko tụi bây
đếm từ đầu đến đít
( thì cộng 1 vào A
) thì trừ A đi 1
* thì cộng 1 vào B
nếu A bé hơn 0 thì {
nếu B <= 0 thì loại (break)
trừ B đi 1 cộng 1 vào A }
nếu A = 0 thì B := 0

Mày trả lời giống ý tao 👍

Làm tý algorithms nào mấy tml

Thích_Yến_Trân

Sinh lý yếu

Thích_Yến_Trân

Sinh lý yếu

peter184

Thanh niên hoi

Bé mều

Người phá đò sông Đà

Bé mều

Người phá đò sông Đà

DướiNhững CơnMưa

Trái Tim Của Gió♥

lucho

Người phá đò sông Đà

themngucdep

Bò lái xe

DướiNhững CơnMưa

Trái Tim Của Gió♥

leductrung2812

Người phá đò sông Đà

peter184

Thanh niên hoi

Freud5252

Trâu lái đò

Freud5252

Trâu lái đò

DướiNhững CơnMưa

Trái Tim Của Gió♥

DướiNhững CơnMưa

Trái Tim Của Gió♥

Comet

Cái lồn nhăn nheo

lucho

Người phá đò sông Đà

Dongu2009

Bò lái xe

Có thể bạn quan tâm