Thích_Yến_Trân
Lồn phải lá han
Làm tý algorithms nào mấy tml
- Tạo bởi Thích_Yến_Trân
- Start date
Thích_Yến_Trân
Lồn phải lá han
lucho
Người phá đò sông Đà
Khó quá bạn, trư chịu
Tầm này đệ quy trư còn chưa vững, quy hoạch động là gì còn ko biết
darkeagle1236
Xàm 0 Lít
Dùng stack là đc
dococaubai
Xàm 0 Lít
peter184
Thanh niên hoi
Tao cho chạy 2 pointers. Một cái ở đầu và một cái ở cuối. Và hai biến để đếm số ngoặc trái, ngoặc phải
int left = 0, right = s.length() - 1;
int countLeft = 0, countRight = 0;
while (left <= right) {
If s.charAt(left) == "(" {
countLeft++;
left++;
}
If s.charAt(right) == ")" {
counRight++;
right--;
}
If s.charAt(left) == "*" or s.charAt(right) == "*" {
If(countRight < countLeft) countRight++;
Else If countRight > countLeft countLeft++;
}
Left++;
Right--;
}
Return countRight == countLeft;
int left = 0, right = s.length() - 1;
int countLeft = 0, countRight = 0;
while (left <= right) {
If s.charAt(left) == "(" {
countLeft++;
left++;
}
If s.charAt(right) == ")" {
counRight++;
right--;
}
If s.charAt(left) == "*" or s.charAt(right) == "*" {
If(countRight < countLeft) countRight++;
Else If countRight > countLeft countLeft++;
}
Left++;
Right--;
}
Return countRight == countLeft;
blackjed32
Chú bộ đội
Ý nó là string “)(“ vi phạm rule thứ 3 nên invalid. K fai example 3
peter184
Thanh niên hoi
Ý tưởng tao là vậy. Cho hai pointer chạy hai đầu, xong đếm ngoặc trái ngoặc phải. Nếu trên đường đi gặp *, nếu số ngoặc trái bé hơn ngoặc phải thì countLeft++. Nếu số ngoặc phải bé hơn ngoặc trái thì countRight++. Còn bằng nhau thì kệ mẹ. Hết vòng lặp, ra ngoài xem số ngoặc trái có bằng ngoặc phải k.
blackjed32
Chú bộ đội
peter184
Thanh niên hoi
Tao có để edge case ở trên kìa mày
blackjed32
Chú bộ đội
lucho
Người phá đò sông Đà
mải xem fim sếch, giờ mới đọc đề xong
mẹ bài xàm loz này có gì đâu
1. duyệt 1 lượt từ dấu ')' đầu tiên đến dấu cuối cùng chuỗi có dấu '(' thì return false // đến đây để chắc kèo '(' luôn ở nửa trái, ')' ở nửa phải
2. đếm xem bao nhiêu dấu '(', ')', bao nhiêu dấu * ở trước '(' cuối cùng , bao nhiêu dấu * ở sau ')' đầu tiên, bao nhiêu dấu * ở giữa ( cuối cùng và ) đầu tiên // gọi là starleft, starmid, starright
nếu '(' = ')' thì return true
nếu '(' > ')' k lần, nếu k <= starright + starmid thì return true; k > starright + starmid return false;
nếu '(' < ')' k lần, nếu k <= starleft + starmid thì return true; k > starleft + starmid return false;
mẹ bài xàm loz này có gì đâu
1. duyệt 1 lượt từ dấu ')' đầu tiên đến dấu cuối cùng chuỗi có dấu '(' thì return false // đến đây để chắc kèo '(' luôn ở nửa trái, ')' ở nửa phải
2. đếm xem bao nhiêu dấu '(', ')', bao nhiêu dấu * ở trước '(' cuối cùng , bao nhiêu dấu * ở sau ')' đầu tiên, bao nhiêu dấu * ở giữa ( cuối cùng và ) đầu tiên // gọi là starleft, starmid, starright
nếu '(' = ')' thì return true
nếu '(' > ')' k lần, nếu k <= starright + starmid thì return true; k > starright + starmid return false;
nếu '(' < ')' k lần, nếu k <= starleft + starmid thì return true; k > starleft + starmid return false;
lucho
Người phá đò sông Đà
ý tưởng là thế, rất mạch lạc rõ ràng và vô cùng dễ hiểumải xem fim sếch, giờ mới đọc đề xong
mẹ bài xàm loz này có gì đâu
1. duyệt 1 lượt từ dấu ')' đầu tiên đến dấu cuối cùng chuỗi có dấu '(' thì return false // đến đây để chắc kèo '(' luôn ở nửa trái, ')' ở nửa phải
2. đếm xem bao nhiêu dấu '(', ')', bao nhiêu dấu * ở trước '(' cuối cùng , bao nhiêu dấu * ở sau ')' đầu tiên, bao nhiêu dấu * ở giữa ( cuối cùng và ) đầu tiên // gọi là starleft, starmid, starright
nếu '(' = ')' thì return true
nếu '(' > ')' k lần, nếu k <= starright + starmid thì return true; k > starright + starmid return false;
nếu '(' < ')' k lần, nếu k <= starleft + starmid thì return true; k > starleft + starmid return false;
nhưng code có vẻ dài
quá nhiều vòng for đơn
peter184
Thanh niên hoi
Ý thứ 1 của mày nếu test cái này sẽ bị sai "(((())))()"mải xem fim sếch, giờ mới đọc đề xong
mẹ bài xàm loz này có gì đâu
1. duyệt 1 lượt từ dấu ')' đầu tiên đến dấu cuối cùng chuỗi có dấu '(' thì return false // đến đây để chắc kèo '(' luôn ở nửa trái, ')' ở nửa phải
2. đếm xem bao nhiêu dấu '(', ')', bao nhiêu dấu * ở trước '(' cuối cùng , bao nhiêu dấu * ở sau ')' đầu tiên, bao nhiêu dấu * ở giữa ( cuối cùng và ) đầu tiên // gọi là starleft, starmid, starright
nếu '(' = ')' thì return true
nếu '(' > ')' k lần, nếu k <= starright + starmid thì return true; k > starright + starmid return false;
nếu '(' < ')' k lần, nếu k <= starleft + starmid thì return true; k > starleft + starmid return false;
peter184
Thanh niên hoi
Cái này thì không có trong edge cases. Cái này handle bằng logic mà mày implement thôi. Mà t thấy thuật toán của tao cũng đ đúng lắm. Để chút về nhà mở máy ra xem
Thích_Yến_Trân
Lồn phải lá han
Có j mấy tml thử submit xem https://leetcode.com/problems/valid-parenthesis-string/description/
