【每日刷题】Day33

【每日刷题】Day33

🥕个人主页：开敲🍉

🔥所属专栏：每日刷题🍍

🌼文章目录🌼

1. 20. 有效的括号 - 力扣（LeetCode）

2. 445. 两数相加 II - 力扣（LeetCode）

3. 1021. 删除最外层的括号 - 力扣（LeetCode）

1. 20. 有效的括号 - 力扣（LeetCode）

//思路：栈的基本使用。

typedef char STDataType;

typedef struct Stack

{

    STDataType* arr;

    int top;

    int capacity;

}ST;

//初始化栈

void StackInit(ST* st)

{

    st->arr = NULL;

    st->top = 0;

    st->capacity = 0;

}

//入栈

void StackPush(ST* st,STDataType s)

{

    assert(st);

    if(st->top==st->capacity)

    {

        int newcapacity = st->capacity == 0?4:2*st->capacity;

        STDataType* tmp = (STDataType*)realloc(st->arr,newcapacity*sizeof(STDataType));

        if(tmp==NULL)

        {

            perror("malloc:");

            exit(-1);

        }

        st->capacity = newcapacity;

        st->arr = tmp;

    }

    st->arr[st->top] = s;

    st->top++;

}

//获取栈顶元素

STDataType StackTop(ST* st)

{

    assert(st);

    assert(st->top>0);

    return st->arr[st->top-1];

}

//出栈

void StackPop(ST* st)

{

    assert(st);

    assert(st->top>0);

    st->top--;

}

//判断栈是否为空

bool StackEmpty(ST* st)

{

    assert(st);

    return st->top == 0;

}

 

bool isValid(char* s)

{

    ST st;

    StackInit(&st);//初始化栈

    while(*s)

    {

        if(*s=='{'||*s=='['||*s=='(')//如果遇到左括号，则入栈

        {

            StackPush(&st,*s);

        }

        else//如果遇到右括号，将栈中元素出栈

        {

            if(StackEmpty(&st))//如果前面没有入过栈，则直接返回

            {

                return false;

            }

            STDataType tmp = StackTop(&st);//先取得栈顶元素，判断是否与右括号匹配

            StackPop(&st);//出栈

            if((tmp=='('&&*s!=')')//如果不匹配，直接返回

            ||(tmp=='{'&&*s!='}')

            ||(tmp=='['&&*s!=']'))

            {

                return false;

            }

        }

        s++;

    }

    bool ret = StackEmpty(&st);//判断栈是否为空，为空说明所有左括号均与右括号匹配，为true，否则为false

    return ret;

}

2. 445. 两数相加 II - 力扣（LeetCode）

//思路：栈和链表的基本使用。

typedef struct ListNode LN;

 

int max(int x,int y)

{

    return x>y?x:y;

}

struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2)

{

    LN* newhead = NULL;

    int i = 0;

    int j = 0;

    int arr1[100] = {0};

    int arr2[100] = {0};

    LN* pmove1 = l1;

    LN* pmove2 = l2;

    int flag = 0;

    while(pmove1)//链表1入栈

    {

        arr1[i++] = pmove1->val;

        pmove1 = pmove1->next;

    }

    while(pmove2)//链表2入栈

    {

        arr2[j++] = pmove2->val;

        pmove2 = pmove2->next;

    }

    i--;//定位栈顶元素

    j--;

    while(i>=0||j>=0)//两个栈同时出栈，元素相加，判断是否需要进位

    {

        LN* newnode = (LN*)malloc(sizeof(LN));//新节点，以头插的方式插入新链表

        newnode->next = newhead;

        newhead = newnode;

        int x = i>=0?arr1[i]:0;//栈1元素

        int y = j>=0?arr2[j]:0;//栈2元素

        int tmp = (x+y+flag)%10;

        newnode->val = tmp;

        if(x+y+flag>=10)//判断是否进位

        {

            flag = 1;

        }

        else

        {

            flag = 0;

        }

        if(i>=0)//防止栈越界访问

        {

            i--;

        }

        if(j>=0)

        {

            j--;

        }

    }

    if(flag)//如果出了循环，flag还为1，则说明最高位进了1，创建新节点，节点val为1，头插进链表中

    {

        LN* newnode = (LN*)malloc(sizeof(LN));

        newnode->next = newhead;

        newnode->val = 1;

        newhead = newnode;

    }

    return newhead;

}

3. 1021. 删除最外层的括号 - 力扣（LeetCode）

//0ms  100％思路：与第一题类似，栈的基础使用。

typedef int STDataType;

//栈结构体

typedef struct Stack

{

    STDataType* arr;

    int top;

    int capacity;

}ST;

 

//初始化栈

void StackInit(ST* st)

{

    assert(st);

    st->arr = NULL;

    st->capacity = st->top = 0;

}

 

//释放栈

void StackRelease(ST* st)

{

    assert(st);

    free(st->arr);

    st->arr = NULL;

    st->capacity = st->top = 0;

}

 

//判空

bool StackEmpty(ST* st)

{

    assert(st);

    return st->top == 0;

}

 

//入栈

void StackPush(ST* st, STDataType x)

{

    assert(st);

    if (st->top == st->capacity)

    {

        int newcapacity = st->capacity == 0 ? 4 : 2 * st->capacity;

        STDataType* tmp = (STDataType*)realloc(st->arr,sizeof(STDataType) * newcapacity);

        if (tmp == NULL)

        {

            perror("malloc:");

            exit(-1);

        }

        st->arr = tmp;

        st->capacity = newcapacity;

    }

    st->arr[st->top] = x;

    st->top++;

}

 

//出栈

void StackPop(ST* st)

{

    assert(st);

    assert(st->top > 0);

    st->top--;

}

 

//获取栈顶元素

STDataType StackTop(ST* st)

{

    assert(st);

    assert(st->top > 0);

    return st->arr[st->top - 1];

}

 

char* removeOuterParentheses(char* s)

{

    ST st;

    StackInit(&st);//初始化栈

    char* arr = (char*)malloc(sizeof(char)*100000);//新空间存储删除后的字符串

    int count = 0;

    while(*s)

    {

        if(*s=='(')//如果为左括号入栈

        {

            StackPush(&st,*s);

        }

        if(st.top>1)//如果栈中元素大于1，说明当前*s不是要删除的括号，直接放入创建好的空间中

        {

            arr[count++] = *s;

        }

        if(*s==')')//如果是右括号，与栈中左括号匹配，出栈

        {

            StackPop(&st);

        }

        s++;

    }

    arr[count] = '\0';

    return arr;

}