leetcode1190反转每对括号间的子串

朴灿烈づ我的快乐病毒、 2022-09-03 14:13 93阅读 0赞

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTY3MjQwNA_size_16_color_FFFFFF_t_70]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTY3MjQwNA_size_16_color_FFFFFF_t_70 1]  
思路

1.  从最里面的括号开始反转
2.  如果从最里面开始反转的话，就是后进先出，用栈，先匹配到最里面的括号
3.  非常重要的一点，`栈中保存的是'('的位置`
4.  对’(‘和’)'之间的字符串进行反转
5.  写main函数的时候干了蠢事，用了const字符串，结果交换函数用不了，搞了半天没看出来

代码

#include<stdio.h>
    #include<string.h>
    #include<ctype.h>
    #include<stdlib.h>
    
    void reverse(char *s,int start,int end){ 
        int start_i=start;
        int end_i=end;
        char temp;
        while (start_i<end_i)
        { 
            temp = s[start_i];
            s[start_i]=s[end_i];
            s[end_i]=temp;
            start_i++;
            end_i--;
        }
        
    }
    char* reverseParentheses(char * s){ 
        int len = strlen(s);
        int i=0,tl=0,count=0,j=0;
        for(i=0;i<len;i++){ 
            if(isalpha(s[i])){ 
                tl++;
            }
            else count++;
        }
        char *re =(char*)malloc((tl+1)*sizeof(char));
        i=0;j=len-1;
        int stack[len],top=-1;
        memset(stack,0,len*sizeof(int));
    
        for(i=0;i<len;i++){ 
            if(s[i]=='('){ 
                stack[++top]=i;
            }
            else if(s[i]==')'){ 
                reverse(s,stack[top--]+1,i-1);
            }
        }
        for(i=0;i<len;i++)
            printf("%c",s[i]);
        printf("\n");
        i=0;
        j=0;
        while (i<len)
        { 
            if(isalpha(s[i]))
                re[j++]=s[i++];
            else
                i++;
        }
        re[j]='\0';
        return re;
    }
    
    int main(){ 
        char s[] = "sxmdll(q)eki(x)";
        char* re = reverseParentheses(s);
        printf("re = %s\n",re);
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTY3MjQwNA_size_16_color_FFFFFF_t_70]: /images/20220829/95349740faeb4ef488e6518c4b288c32.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTY3MjQwNA_size_16_color_FFFFFF_t_70 1]: /images/20220829/e20c75c096b9463ebb413dda29eb6f1e.png