数据结构刷题

空间复杂度：临时开辟的空间、空间是可以重复利用的

递归为O(n)

时间复杂度：程序执行次数

消失的数字

力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

思路1：利用连续的特点求等差和然后减去所有元素得到的就是消失的数字

时间复杂度：O(n)     空间复杂度：O(1)

思路2：将给定数组的元素和连续的元素进行异或（异或与顺序无关），相同元素异或结果为0。会得到有一个落单的数字与0异或就是这个数字。

时间复杂度：O(n)     空间复杂度：O(1)

第一种方法大家自行实现，我们可以实现一下不常见的第二种方法：

int missingNumber(int* nums, int numsSize){int x = 0;//0与任何数异或为该数for(int i = 0;i<numsSize;i++){x ^= nums[i];}for(int i = 0;i<=numsSize;i++){x ^= i;}return x;
}

轮转数组

力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

c语言阶段曾实现了两种方法，一种是依次移动,移动M次。一种是局部逆置和整体逆置。前者时间复杂度为O(N*M),后者为O(N)

空间换时间：创建一个临时数组，前面放需要旋转的数据，后面放没有旋转的数据即可。 

不完整代码： 

void rotate(int* nums, int numsSize, int k){int tmp[numsSize];k %= numsSize;//循环次数不必多于元素个数int i = 0;int j = 0;for(i=numsSize-k;i<numsSize;i++){tmp[j] = nums[i];j++;}for(i = 0;i<numsSize-k;i++){tmp[j] = nums[i];
}
for//打印
}

有效的括号

力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

思路：让左括号依次入栈，与右括号匹配。

匹配前：判断栈是否为空，为空说明无左括号。返回false。

匹配中：匹配涉及多次如 " () {} (())",记录指针位置与栈顶比较，然后出栈，不匹配返回false。

匹配结束：栈空为匹配成功，否则匹配失败。

注意返回前都需进行销毁操作。

#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
typedef char STDatatype;
typedef struct Stack
{STDatatype* a;int capacity;int top;
}ST;
void check_capacity(ST* ps)
{if(ps->capacity == ps->top){int newCapacity = 0 ? 4:ps->capacity*2;char* tmp;tmp = (STDatatype*)realloc(ps->a,sizeof(STDatatype) * newCapacity);if (tmp == NULL){perror("malloc");exit(-1);}ps->a = tmp;ps->capacity = newCapacity;}
}
bool StackEmpty(ST* ps)//判空
{assert(ps);return ps->top == 0;
}
STDatatype StackTop(ST* ps)
{assert(ps);assert(!StackEmpty(ps));return ps->a[ps->top-1];//top为最后一个元素的下一个
}
void StackDestroy(ST* ps)
{assert(ps);free(ps->a);ps->a = NULL;ps->top = ps->capacity = 0;
}
void StackInit(ST* ps)
{/*ps->a = NULL;ps->top = 0;ps->capacity = 0;*///初始化空间ps->a = (STDatatype*)malloc(sizeof(STDatatype) * 4);if (ps->a == NULL){perror("malloc");exit(-1);}ps->top = 0;ps->capacity = 4;
}
void StackPop(ST* ps)//出栈
{assert(ps);//if(ps->top>0)assert(!StackEmpty(ps));ps->top--;
}
void StackPush(ST* ps, STDatatype x)
{assert(ps);check_capacity(ps);ps->a[ps->top] = x;ps->top++;//指向下一个
}
bool isValid(char* s) {ST ps;StackInit(&ps); 
while(*s)
{if(*s == '(' || *s == '[' ||*s == '{' ){StackPush(&ps,*s);s++;}else{if(StackEmpty(&ps))//如果没有左括号，栈顶没有元素{StackDestroy(&ps);//注意返回前都要手动释放空间return false;}char top = StackTop(&ps);if((*s == ')' && top != '(') || (*s == ']' && top != '[') ||(*s == '}' && top != '{'))//{StackDestroy(&ps);return false;}else{StackPop(&ps);s++;}}
}
bool ret = StackEmpty(&ps);
StackDestroy(&ps);
return ret;
}

用队列实现栈

力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

先导入我们实现过的队列：

#pragma once
#include <stdbool.h>
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
typedef int QDataType;
typedef struct QueueNode
{QDataType data;struct QueueNode* next;
}QNode;
struct Queue
{QNode* head;QNode* tail;int size;
};
void QueueInit(Queue* pq);
void QueueDestroy(Queue* pq);
void QueuePush(Queue* pq, QDataType x);
void QueuePop(Queue* pq);
QDataType QueueFront(Queue* pq);
QDataType QueueBack(Queue* pq);
bool QueueEmpty(Queue* pq);
int QueueSize(Queue* pq);void QueueDestroy(Queue* pq)
{assert(pq);QNode* cur = pq->head;while (cur){QNode* Next =cur->next;free(cur);cur = Next;}pq->head = pq->tail = NULL;//避免野指针pq->size = 0;
}
void QueuePush(Queue* pq, QDataType x)
{assert(pq);QNode* newnode = (QNode*)malloc(sizeof(QNode));if (newnode == NULL){perror("malloc fail");exit(-1);}   newnode->data = x;newnode->next = NULL;pq->size++;if (pq->head == NULL){pq->head = pq->tail = newnode;}else{pq->tail->next = newnode;pq->tail = newnode;}
}
void QueuePop(Queue* pq)
{//出队头删assert(pq);assert(pq->head);QNode* del = pq->head;pq->head = pq->head->next;free(del);if (pq->head == NULL)pq->tail = NULL;pq->size--;}
void QueueInit(Queue* pq)
{assert(pq);pq->head = NULL;pq->tail = NULL;pq->size = 0;
}
bool QueueEmpty(Queue* pq)
{assert(pq);return pq->head == NULL && pq->tail == NULL;
}
int QueueSize(Queue* pq)
{assert(pq);return pq->size;
}
QDataType QueueFront(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq->head->data;
}
QDataType QueueBack(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq->tail->data;
}

 两个队列

将两个队列封装在一个结构体中。

typedef struct Queue
{QNode* head;QNode* tail;int size;
}Queue;//简写

创建并初始化链表(栈）

注意要想保证我们创建的结构体生命周期能够贯彻整个工程，必须在堆上申请空间。

MyStack* myStackCreate() {//创建并初始化链表MyStack* obj = (MyStack*)malloc(sizeof(MyStack));//堆区QueueInit(&obj->q1);QueueInit(&obj->q2);return obj;
}

模拟入栈

选择非空队列插入即可。

void myStackPush(MyStack* obj, int x) {if(!QueueEmpty(&obj->q1))//非空队列插入{QueuePush(&obj->q1,x);}elseQueuePush(&obj->q2,x);
}

模拟出栈

出栈是在队尾进行出(后进先出)，我们将非空队列进行出队只剩下最后一个元素即是栈顶的元素，然后将其保存后出栈避免造成内存泄露，然后返回。

nt myStackPop(MyStack* obj) {//假定一方不为空Queue* empty = &obj->q1;Queue* nonempty = &obj->q2;if(!QueueEmpty(empty)){empty = &obj->q2;nonempty = &obj->q1;}while(QueueSize(nonempty) > 1)//O(1)导入空来链表{QueuePush(empty,QueueFront(nonempty));//非空取队头插入空 QueuePop(nonempty);}//保证原链表返回为空int top = QueueFront(nonempty);QueuePop(nonempty);//出栈return top;
}

模拟栈顶

直接返回队尾元素即可。

int myStackTop(MyStack* obj) {//返回队尾if(!QueueEmpty(&obj->q1)){return QueueBack(&obj->q1);}elsereturn QueueBack(&obj->q2);	
}

模拟栈判空

bool myStackEmpty(MyStack* obj) {return QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2);
}

模拟栈销毁

除了释放队列指针组合的结构体外，还要将每个队列里的元素释放。

void myStackFree(MyStack* obj) {QueueDestroy(&obj->q1);QueueDestroy(&obj->q2);free(obj);
}

用栈实现队列

力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

思路:两个栈，一个负责push数据，一个负责pop数据，在pop数据时，判断pop栈中是否有数据，没有则将push栈的数据全部导入，此时数据顺序反过来后再pop栈里出栈就可以实现先进先出这一特性了。

导入实现好的栈：

#include <stdbool.h>
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>typedef int STDatatype;
typedef struct Stack
{STDatatype* a;int capacity;int top;
}ST;void StackInit(ST* ps);
void StackDestroy(ST* ps);
void StackPush(ST* ps, STDatatype x);
void StackPop(ST* ps);//出栈
STDatatype StackTop(ST* ps);bool StackEmpty(ST* ps);
int StackSize(ST* ps);void StackInit(ST* ps)
{/*ps->a = NULL;ps->top = 0;ps->capacity = 0;*///初始化空间ps->a = (STDatatype*)malloc(sizeof(STDatatype) * 4);if (ps->a == NULL){perror("malloc");exit(-1);}ps->top = 0;ps->capacity = 4;
}static void check_capacity(ST* ps)
{if (ps->top == ps->capacity){int newCapacity = ps->capacity * 2;STDatatype* tmp = (STDatatype*)realloc(ps->a, newCapacity *sizeof(STDatatype));if (tmp == NULL){perror("realloc");exit(-1);}else{ps->a = tmp;ps->capacity == newCapacity;}}
}
void StackPush(ST* ps, STDatatype x)
{assert(ps);check_capacity(ps);ps->a[ps->top] = x;ps->top++;//指向下一个
}
void StackPop(ST* ps)//出栈
{assert(ps);//if(ps->top>0)assert(!StackEmpty(ps));ps->top--;
}STDatatype StackTop(ST* ps)
{assert(ps);assert(!StackEmpty(ps));return ps->a[ps->top-1];//top为最后一个元素的下一个
}
void StackDestroy(ST* ps)
{assert(ps);free(ps->a);ps->a = NULL;ps->top = ps->capacity = 0;
}
bool StackEmpty(ST* ps)//判空
{assert(ps);return ps->top == 0;
}
int StackSize(ST* ps)
{assert(ps);return ps->top;
}

两个栈

typedef struct {ST pushst;//入队ST popst;//出队
} MyQueue;

Create

MyQueue* myQueueCreate() {//初始化+开空间MyQueue* st = (MyQueue*)malloc(sizeof(MyQueue));StackInit(&st->pushst);StackInit(&st->popst);return st;
}

Push

void myQueuePush(MyQueue* obj, int x) {assert(obj);StackPush(&obj->pushst,x);
}

判空 

bool myQueueEmpty(MyQueue* obj) {assert(obj);return StackEmpty(&obj->pushst) && StackEmpty(&obj->popst);
}

查看队头

由于popst的栈顶为队头，如果该栈为空，需要导入pushst的数据。

int myQueuePeek(MyQueue* obj) {assert(obj);assert(!myQueueEmpty(obj)); //双栈判空if(StackEmpty(&obj->popst)){while(!StackEmpty(&obj->pushst))//导数据{StackPush(&obj->popst,StackTop(&obj->pushst));StackPop(&obj->pushst);}}return StackTop(&obj->popst);
}

Pop

同样涉及判空和调用队头元素，通过调用peek函数判断并完成对数据的导入并接收其返回值，

int myQueuePop(MyQueue* obj) {int qhead = myQueuePeek(obj);StackPop(&obj->popst);//出队return qhead;
}

释放

void myQueueFree(MyQueue* obj) {assert(obj);StackDestroy(&obj->pushst);StackDestroy(&obj->popst);free(obj);
}