门户网站分类,上海市500强企业名单,视频网站用php做,天津做网站推广的公司空间复杂度#xff1a;临时开辟的空间、空间是可以重复利用的
递归为O(n)
时间复杂度#xff1a;程序执行次数 消失的数字
力扣#xff08;LeetCode#xff09;官网 - 全球极客挚爱的技术成长平台 思路1#xff1a;利用连续的特点求等差和然后减去所有元素得到的就是消…空间复杂度临时开辟的空间、空间是可以重复利用的
递归为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;inumsSize;i){x ^ nums[i];}for(int i 0;inumsSize;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(inumsSize-k;inumsSize;i){tmp[j] nums[i];j;}for(i 0;inumsSize-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-top0)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.htypedef 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-top0)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);
}
