billy_don
Senior Member
á à cắt ghép chuỗi dám dùng thẳng String
@billy_don mang cẩu đầu trảm ra xử lý nào, quê mặt hội java quá
thảo luận Leetcode mỗi ngày
- Người tạo chủ đề _Gia_Cat_Luong_
- Ngày bắt đầu
- Trạng thái
Người quan sát cô đơn
Senior Member
á à cắt ghép chuỗi dám dùng thẳng String
@billy_don mang cẩu đầu trảm ra xử lý nào, quê mặt hội java quá
huhu e biết lỗi r mà mấy a ơi
Java:
class Solution {
int index = -1;
public String reverseParentheses(String s) {
char[] arr = s.toCharArray();
return buildString(arr);
}
public String buildString(char[] arr){
index++;
StringBuilder sb = new StringBuilder();
while(index<arr.length) {
if(arr[index]=='(') {
String temp = buildString(arr);
sb.append(temp);
}
else if(arr[index]==')') {
sb = sb.reverse();
break;
}
else
sb.append(arr[index]);
index++;
}
return sb.toString();
}
}
Konstante
Senior Member
Cách teleport hay vãi
C-like:
impl Solution {
pub fn reverse_parentheses(s: String) -> String {
let s = s.as_bytes();
let goto = {
let mut goto = vec![0; s.len()];
let mut ops = Vec::new();
s.iter().enumerate().for_each(|(i, c)| {
match *c {
b'(' => ops.push(i),
b')' => {
let from = unsafe { ops.pop().unwrap_unchecked() };
goto[from] = i;
goto[i] = from
}
_ => {}
}
});
goto
};
let mut out = Vec::new();
let (mut direction, mut pos) = (1i32, 0i32);
while (pos as usize) < s.len() {
match s[pos as usize] {
b'(' | b')' => {
pos = goto[pos as usize] as i32;
direction = -direction;
}
_ => out.push(s[pos as usize]),
}
pos += direction;
}
unsafe { String::from_utf8_unchecked(out) }
}
}
small-lambda
Senior Member
billy_don
Senior Member
Còn bài của fen xì O mấy đâu sao k thấy, anh tự do nay cũng lủi đâu r chưa thấy làmnày sao O(n) được fency ơi
vicejuniordev
Senior Member
Mình đang tính thế này:này sao O(n) được fency ơi
- Khởi tạo list hết O(N)
- Mỗi lần call hàm Reverse sẽ tốn maximum là O(N), vì mình call theo từng cặp parentheses. (Index sẽ giảm dần). Cho nên cái này tính là O(N). Ví dụ, n = 10 , maximum là 5 cặp "()" thì số lần chạy sẽ là : 8 + 6 + 4 + 2.
- Loop cuối cùng để tạo result - O(N).
Người quan sát cô đơn
Senior Member
tự do bảo chấp cả nhóm hết kì euro này mà. Trong thớt euro thấy trận nào cũng kêu bú đẫm, chắc khỏi cần làm thợ gõ nữa rồi.
billy_don
Senior Member
tự do bảo chấp cả nhóm hết kì euro này mà. Trong thớt euro thấy trận nào cũng kêu bú đẫm, chắc khỏi cần làm thợ gõ nữa rồi.
ko nhận card dưới 500k nha @freedom.9
maskup
Senior Member
xét chuỗi có độ dài n có dạng ((...(abc...)...))
gọi k là số cặp ngoặc '()', x là độ dài chuỗi 'abc...'
ta phải reverse k lần chuỗi x => time complex = k * x
dễ thấy 2k + x = n, k * x lớn nhất khi k = n / 4, x = n / 2 (AM-GM)
=> time complex = n^2 / 8 = O(n^ 2)
Sửa lần cuối:
wjbu404
Senior Member
O(n^2) nhưng lại chạy 0ms, có vẻ là do constraints nhỏ
C++:
class Solution {
public:
string reverseParentheses(string str) {
stack<int> stk;
string result;
for (char ch : str) {
if (ch == '(') {
stk.push(result.size());
} else if (ch == ')') {
int start = stk.top();
stk.pop();
reverse(result.begin() + start, result.end());
} else {
result += ch;
}
}
return result;
}
};
freedom.9
Senior Member
tự do bảo chấp cả nhóm hết kì euro này mà. Trong thớt euro thấy trận nào cũng kêu bú đẫm, chắc khỏi cần làm thợ gõ nữa rồi.
Mấy nay đủ combo nên ko luyện leetcode, euro, chuyển nhà, vợ mang bầu
Hết Euro comeback với anh em, mẹ nó tụi Hà Lan với Uruguay đưa trư xa bờ quá
kiếm 10 năm subscription leetcode khó quá 
wtosale02
Senior Member
C++:
class Solution {
public:
string reverseParentheses(string s) {
stack<char> st;
queue<char> q;
for (int i = 0; i < s.size(); i++) {
if (s[i] != ')') {
st.push(s[i]);
} else {
char charTop = st.top();
while (charTop != '(') {
st.pop();
q.push(charTop);
charTop = st.top();
}
// remove '('
st.pop();
while (!q.empty()) {
char charFront = q.front();
q.pop();
st.push(charFront);
}
}
}
string result = "";
while (!st.empty()) {
char c = st.top();
st.pop();
result = c + result;
}
return result;
}
};Cố chấp ko xem giải, nghĩ cả ngày mới ra. Có vẻ solution của em lởm nhất rồi
thangkc89
Senior Member
Đang buồn ngủ chợt nhớ chưa làm daily leetcode, bật dậy code để giữ chuỗi xong tỉnh mịa ngủ 
s = "abc(def(ghi)jkl)mno"
depth = 000(111(222)111)000
1. Thay vì reverse k lần tương ứng với k cặp parenthesis lồng nhau, ta nhận thấy là nếu depth là chẵn thì giữ nguyên thứ tự, lẻ thì đảo được
2. Để có thể tìm được cái ngoặc tương ứng với ngoặc hiện tại đang check thì ta có thể pre process trước, tạo 1 mảng pos, pos[ i ]= j tức là (i,j) hoặc (j,i) là 1 cặp ngoặc đúng
-> Kết hợp 2 cái trên là code ra O(n) thôi
depth = 000(111(222)111)000
1. Thay vì reverse k lần tương ứng với k cặp parenthesis lồng nhau, ta nhận thấy là nếu depth là chẵn thì giữ nguyên thứ tự, lẻ thì đảo được
2. Để có thể tìm được cái ngoặc tương ứng với ngoặc hiện tại đang check thì ta có thể pre process trước, tạo 1 mảng pos, pos[ i ]= j tức là (i,j) hoặc (j,i) là 1 cặp ngoặc đúng
-> Kết hợp 2 cái trên là code ra O(n) thôi
Python:
class Solution:
def reverseParentheses(self, s: str) -> str:
pos = [-1] * len(s)
stack = []
for i, c in enumerate(s):
if c == '(':
stack.append(i)
elif c == ')':
prev = stack.pop()
pos[prev] = i
pos[i] = prev
ans = []
def backward_traverse(l, r):
while r >= l:
if s[r] == ')':
forward_traverse(pos[r]+1, r-1)
r = pos[r]-1
else:
ans.append(s[r])
r -= 1
def forward_traverse(l, r):
while l <= r:
if s[l] == '(':
backward_traverse(l+1, pos[l]-1)
l = pos[l]+1
else:
ans.append(s[l])
l += 1
forward_traverse(0, len(s) - 1)
return ''.join(ans)
Sửa lần cuối:
vicejuniordev
Senior Member
maskup
Senior Member
vicejuniordev
Senior Member
N của mình là tính theo start index và end index của mỗi cặp parentheses. Ví dụ (abc(de)ghj). Lần 1 là n = 10 ( start index =1 , end index = 10 - abc(de)ghj), lần 2 thì là n = 2 - chuỗi cần reverse chỉ là de thôi, không phải reverse tất cả.n của mình là độ dài của chuỗi input, không đổi.
n của fence là gì á
via theNEXTvoz for iPhone
maskup
Senior Member
nếu vậy thì cần đánh giá dựa trên tổng tất các 'n'
mình có đưa ra worst case ở trên, thì sum('n') của fence <= input.length^2 / 8 = O(input.length ^ 2).
Thầy ông cố nội
Junior Member
JavaScript:
var maximumGain = function(s, x, y) {
const calculate = (pair, point) => {
const stack = [];
let total_points = 0;
for (const c of arr) {
if (c == pair[1] && stack.length > 0 && stack[stack.length - 1] == pair[0]) {
stack.pop();
total_points += point;
} else {
stack.push(c);
}
}
arr = stack;
return total_points;
}
let arr = s.split('');
let ans = 0;
let pairs = x > y ? ["ab", "ba"] : ["ba", "ab"];
let points = x > y ? [x, y] : [y, x];
ans += calculate(pairs[0], points[0]);
ans += calculate(pairs[1], points[1]);
return ans;
};vicejuniordev
Senior Member
Python:
class Solution:
def maximumGain(self, s: str, x: int, y: int) -> int:
# Stack
def calculate(s, p1, s1,p2, s2 ):
stack = []
res = 0
for char in s:
if stack and stack[-1] + char == p1:
stack.pop()
res += s1
else:
stack.append(char)
rem = []
while stack:
c = stack.pop()
if rem and c + rem[-1] == p2:
res += s2
rem.pop()
else:
rem.append(c)
return res
if x > y:
return calculate(s, "ab",x, "ba", y)
else:
return calculate(s, "ba", y, "ab", x)
anoldvozer1710.v2
Senior Member
cái djt, medium giả cầy. Mất mọe cả tiếng đồng hồ mới làm đc, may hôm nay ko có task 
. Greedy mới chả stack 
. Greedy mới chả stack
JavaScript:
function maximumGain(s: string, x: number, y: number): number {
let res = 0;
const remove = (str: string, type: string) => {
const stack: string[] = [];
for (let i = 0; i < str.length; i++) {
if (str[i] === type[1] && stack.length && stack[stack.length - 1] === type[0]) stack.pop()
else stack.push(str[i])
}
let ans = '';
while (stack.length) ans = stack.pop() + ans;
return ans
}
const str1 = remove(s, x > y ? 'ab' : 'ba');
let count = (s.length - str1.length) / 2;
res+= count * Math.max(x, y);
const str2 = remove(str1, x > y ? 'ba' : 'ab');
count = (str1.length - str2.length) / 2;
res+= count * Math.min(x, y);
return res;
};- Trạng thái
Chủ đề tương tự
