沒想到 ...(?)
就先這樣吧QQ
char* minRemoveToMakeValid(char* s) {
int len = strlen(s);
int l=0, r=0, t_l=0;
char *ret = calloc (len+1, sizeof(char));
int idx = 0;
for (int i=0; i<len; i++)
{
switch (s[i])
{
case ('('):
{
l++;
t_l++;
ret[idx++] = s[i];
}
break;
case (')'):
if (l>0)
{
l--;
ret[idx++] = s[i];
}
break;
default :
ret[idx++] = s[i];
}
}
if (l<=0)
return ret;
for (int i=0; i<idx; i++)
s[i]= ret[i];
int n_idx = idx-1;
for (int i=idx-1; i>=0; i--)
{
switch (s[i])
{
case ('('):
if (r>0)
{
r--;
ret[n_idx--] = s[i];
}
break;
case (')'):
{
r++;
ret[n_idx--] = s[i];
}
break;
default :
ret[n_idx--] = s[i];
}
}
for (int i=n_idx+1; i<idx; i++)
{
ret[i-(n_idx+1)]= ret[i];
}
ret[idx-(n_idx+1)] = '\0';
return ret;
}
[20251029]更新
為了省一個array , 結果要倒過來倒過去還要copy ，真的有省到嗎XD
但還是有比上面漂亮一咪咪嗎～好像還有更漂亮的寫法(thinking 圖)
要小心return 的array 長度其實是s 的長度要加一！！！結束字元！
考慮到萬一原本就沒有括號在裡面的情況。
char* minRemoveToMakeValid(char* s) {
int len = strlen(s);
char *ret = calloc (len+1 , sizeof(char));
int l=0, r=0;
int idx =0 ;
for (int i=0; i<len; i++)
{
if (s[i]==')' && l>=r)
continue;
if (s[i]==')')
l++;
if (s[i]=='(')
r++;
ret[idx++]=s[i];
}
l=0;
r=0;
int r_idx=0;
for (int i=idx-1;i>=0; i--)
{
if (ret[i]=='(' && r>=l)
continue;
if (ret[i]==')')
l++;
if (ret[i]=='(')
r++;
s[r_idx++] = ret[i];
}
ret[r_idx]='\0';
for (int i=0; i<r_idx; i++)
ret[i]= s[r_idx-i-1];
return ret;
}
[20251107]更新
另一種寫法(?) 不是使用"從頭掃一遍 再從尾倒掃一遍"的方法
先全部算一次右括號有幾個, 再來就是
當右括號來-> 已經有已括號了嗎？
當左括號來-> 後面還有右括號嗎？ *注意: 還有的話，此時就要將右括號數目減一,
表示它已經被配對走了！
所以 ，倒回去第一個： "當右括號來-> 已經有已括號了嗎？" 此時若是配對到的，只需要減掉左括號就好，因為右括號剛才已經被預支走了！
就降只QQ
char* minRemoveToMakeValid(char* s) {
int len = strlen(s);
int start=0;
int end = 0;
for (int i=0; i<len; i++)
if (s[i]==')')
end++;
char *ret = calloc (len+1, sizeof(char));
int idx = 0;
for (int i=0; i<len; i++)
{
//printf("%d %d %s\n", start, end, ret);
if (s[i]==')')
{
if (start>0)
{
ret[idx++]=s[i];
start--;
}
else
end--;
}
else if (s[i]=='(')
{
if (end>0)
{
ret[idx++]=s[i];
start++;
end--;
}
}
else
ret[idx++]=s[i];
}
return ret;
}
（再一版）（是要寫幾版）
說是可以用stack紀錄左括號的index ，右括號要push時，要pop掉一個配對的左括號，
若沒有，偷偷把它改成別的值。
走完一輪，如果stack 還有東西，它們都是配對不到的左括號，也偷偷改成別的值。
最後掃一遍，把沒被標成要拿掉的都吐出output。以上。
char* minRemoveToMakeValid(char* s) {
int len = strlen (s);
int *idxs= calloc (len, sizeof (int));
int top = -1;
for (int i=0 ; i<len ; i++) {
if (s[i]=='(')
idxs[++top]=i;
else if (s[i]==')') {
if (top>=0)
--top;
else
s[i]='#';
}
}
while (top>=0)
s[idxs[top--]]='#';
char *ret = calloc (len+1, sizeof(char));
top = 0;
for (int i=0; i<len; i++) {
if (s[i]!='#')
ret[top++]=s[i];
}
ret[top]='\0';
return ret;
}
沒有留言:
張貼留言