C语言leetcode刷题笔记3

第8题：876.链表的中间结点
- 遍历数节点个数
- 快慢指针
第9题：874.比较含退格的字符串
第10题：155.最小栈
- 法1：getMin内部实现查找
- 法2：getmin直接返回值
- 补充：栈的使用
- - 例子
  - 优化：传递指针
  - 优化：初始化、动态分配、释放

第8题：876.链表的中间结点

给你单链表的头结点 head ，请你找出并返回链表的中间结点。

如果有两个中间结点，则返回第二个中间结点。

示例 1：

输入：head = [1,2,3,4,5]
输出：[3,4,5]
解释：链表只有一个中间结点，值为 3 。

遍历数节点个数

struct ListNode* middleNode(struct ListNode* head) {
    int count=0;
    struct ListNode*t=head;
    while(t)
    {
        t=t->next;
        count++;
        
    }
   // count++;
    count=count/2;
    t=head;
    while(count){
        
        t=t->next;
        count--;
    }
    return t;
    
}

快慢指针

struct ListNode* middleNode(struct ListNode* head) {
    struct ListNode* show=head;
    struct ListNode* fast=head;
    while(fast->next!=NULL)
    {
        
        fast=fast->next->next;
        show=show->next;
        if(fast==NULL)break;
    }
    return show;
}

第9题：874.比较含退格的字符串

给定 s 和 t 两个字符串，当它们分别被输入到空白的文本编辑器后，如果两者相等，返回 true 。# 代表退格字符。

注意：如果对空文本输入退格字符，文本继续为空。

示例 1：

输入：s = “ab#c”, t = “ad#c”
输出：true
解释：s 和 t 都会变成 “ac”。

void simplify(char* s) {
    int sl = strlen(s);
    int p = 0;
    for (int i = 0; i < sl; i++) {
        if (s[i] == '#') {
            if (p > 0)
                p--;

        }
        else
            s[p++] = s[i];
    }
    s[p] = '\0';
    return;
}
bool backspaceCompare(char* s, char* t) {
simplify(s);
simplify(t);
   
    return strcmp(s, t) == 0;
}

第10题：155.最小栈

设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。

实现 MinStack 类:

MinStack() 初始化堆栈对象。
void push(int val) 将元素val推入堆栈。
void pop() 删除堆栈顶部的元素。
int top() 获取堆栈顶部的元素。
int getMin() 获取堆栈中的最小元素。

示例 1:

输入：
[“MinStack”,“push”,“push”,“push”,“getMin”,“pop”,“top”,“getMin”]
[[],[-2],[0],[-3],[],[],[],[]]

输出：
[null,null,null,null,-3,null,0,-2]

解释：
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); --> 返回 -3.
minStack.pop();
minStack.top(); --> 返回 0.
minStack.getMin(); --> 返回 -2.

法1：getMin内部实现查找



typedef struct {
    int value[10001];
    int stacktop;

} MinStack;


MinStack* minStackCreate() {
    MinStack* obj = malloc(sizeof(MinStack));
    obj->stacktop = 0;

    return obj;
}

void minStackPush(MinStack* obj, int val) {
    obj->value[obj->stacktop] = val;
    (obj->stacktop)++;
}

void minStackPop(MinStack* obj) {
    if (obj->stacktop)
    {
        //obj[stacktop-1].value =INT_MAX;
         (obj->stacktop)--;

    }
       
}

int minStackTop(MinStack* obj) {
    if (obj->stacktop)
        return obj->value[(obj->stacktop)-1];
    else
        return 0;
}

int minStackGetMin(MinStack* obj) {
    if (obj->stacktop) 
    {
        if(obj->stacktop==1)return obj->value[0];
        int Mi = obj->value[0];
        
        for (int i = 1; i < obj->stacktop; i++) 
        {
        if (obj->value[i] < Mi)
            Mi = obj->value[i];
        }
        return Mi;
    }
    else
        return 0;
}

void minStackFree(MinStack* obj) { free(obj); }

/**
 * Your MinStack struct will be instantiated and called as such:
 * MinStack* obj = minStackCreate();
 * minStackPush(obj, val);

 * minStackPop(obj);

 * int param_3 = minStackTop(obj);

 * int param_4 = minStackGetMin(obj);

 * minStackFree(obj);
*/

在这里插入图片描述

法2：getmin直接返回值

typedef struct {
     int *data;//data[100]
    int *mins;
    int size;
    
} MinStack;


MinStack* minStackCreate() {
    MinStack* obj=(MinStack*)malloc(sizeof(MinStack));
    obj->data=NULL;
    obj->mins=NULL;
    obj->size=0;
    return obj;
    
}

void minStackPush(MinStack* obj, int val) {
    obj->data=(int*)realloc(obj->data,sizeof(int)*(obj->size+1));
    obj->mins=(int*)realloc(obj->mins,sizeof(int)*(obj->size+1));//
    obj->data[obj->size]=val;
    if(obj->size==0||obj->mins[obj->size-1]>val)
    {
        obj->mins[obj->size]=val;
    }
    else
    {
        obj->mins[obj->size]=obj->mins[obj->size-1];
        

    }
    obj->size++;
    
}

void minStackPop(MinStack* obj) {
    obj->size--;
    
}

int minStackTop(MinStack* obj) {
    return obj->data[obj->size-1];
    
}

int minStackGetMin(MinStack* obj) {
    return obj->mins[obj->size-1];
   // return 0;
    
}

void minStackFree(MinStack* obj) {
    free(obj->data);
    free(obj->mins);
    obj->size=0;
    free(obj);
    
}

在这里插入图片描述

补充：栈的使用

例子


#include <string.h>

#include <stdio.h>

typedef struct{
    int data[100];
    int size;

}Stack1;
void Push(Stack1 t,int val)//只能修改传递过来的值
{
    t.data[t.size]=val;
    t.size++;
}
void Pop(Stack1 t)
{
    t.size--;
}
void StackPrint(Stack1 t)
{
    int len=t.size;
    int i;
    for(i=0;i<len;i++)
    {
        printf("t.data[%d]=%d\n",i,t.data[i]);
    }
}
int main()
{
    Stack1 t;
    t.size=0;
    memset(t.data,100,0);


    Push(t,10);//无法修改
    Push(t,20);
    StackPrint(t);


    return 0;
}
//输出空
//未使用指针，无法修改值

优化：传递指针

#include <string.h>

#include <stdio.h>

typedef struct{
    int data[100];
    int size;

}Stack1;
void Push(Stack1* t,int val)
{
    t->data[t->size]=val;
    t->size++;
}
void Pop(Stack1* t)
{
    t->size--;
}
void StackPrint(Stack1 t)
{
    int len=t.size;
    int i;
    for(i=0;i<len;i++)
    {
        printf("t.data[%d]=%d\n",i,t.data[i]);
    }
}
int main()
{
    Stack1 t;
    t.size=0;
    memset(t.data,100,0);


    Push(&t,10);
    Push(&t,20);
    Push(&t,30);
    Pop(&t);
    StackPrint(t);


    return 0;
}
/*
t.data[0]=10
t.data[1]=20

*/

优化：初始化、动态分配、释放

#include <string.h>

#include <stdio.h>
#include <malloc.h>

typedef struct{
    int *data;//data[100]
    int size;

}Stack1;
Stack1* create()
{
    Stack1* obj=(Stack1*)malloc(sizeof(Stack1));
    obj->data=NULL;
    obj->size=0;
    return obj;


}
void Push(Stack1* t,int val)
{
    t->data=(int*)realloc(t->data,sizeof(int)*(t->size+1));
    t->data[t->size]=val;
    t->size++;
}
void Pop(Stack1* t)
{
    t->size--;
}
void freestack1(Stack1* t)
{
    free(t->data);
    t->size=0;
    free(t);
    //t=NULL;

    //t->size--;
}
void StackPrint(Stack1 t)
{
    int len=t.size;
    int i;
    for(i=0;i<len;i++)
    {
        printf("t.data[%d]=%d\n",i,t.data[i]);
    }
}
int main()
{
//    Stack1 t;
//    t.size=0;
//    memset(t.data,100,0);
    Stack1 * t=create();


    Push(t,10);//
    Push(t,20);
    Push(t,30);
    Pop(t);
    StackPrint(*t);
	freestack1(t);

    return 0;
}
/*
t.data[0]=10
t.data[1]=20

*/