数据结构刷题

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

递归为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);
    }
    else
        QueuePush(&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);
    }
    else
    return 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);
}

用栈实现队列

思路:两个栈，一个负责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);
}

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/155337.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

【AI视野·今日Robot 机器人论文速览 第六十三期】Thu, 26 Oct 2023

【AI视野·今日Robot 机器人论文速览 第六十三期】Thu, 26 Oct 2023

AI视野今日CS.Robotics 机器人学论文速览 Fri, 27 Oct 2023 Totally 27 papers &#x1f449;上期速览✈更多精彩请移步主页 Daily Robotics Papers 6-DoF Stability Field via Diffusion Models Authors Takuma Yoneda, Tianchong Jiang, Gregory Shakhnarovich, Matthew R. …
阅读更多...
JVM虚拟机：垃圾回收器ZGC和Shenandoah算法

JVM虚拟机：垃圾回收器ZGC和Shenandoah算法

随着计算机技术的不断发展，内存管理成为了一个重要的话题。垃圾回收是一种自动内存管理技术，它可以自动地回收不再使用的内存，从而减少内存泄漏和程序崩溃的风险。在Java等高级编程语言中，垃圾回收器是必不可少的组件。近年来，ZGC和Shenandoah算法作为新一代的垃圾回收器，…
阅读更多...
C++ 基础二

C++ 基础二

文章目录 四、流程控制语句4.1 选择结构4.1.1 if语句 4.1.2 三目运算符4.1.3 switch语句注意事项 4.1.4 if和switch的区别【CHAT】4.2 循环结构4.2.1 while循环语句4.2.2 do...while循环语句 4.2.3 for循环语句九九乘法表 4.3 跳转语句4.3.1 break语句4.3.2 continue语句4.3.3 …
阅读更多...
扩散模型实战（九）：使用CLIP模型引导和控制扩散模型

扩散模型实战（九）：使用CLIP模型引导和控制扩散模型

推荐阅读列表&#xff1a; 扩散模型实战&#xff08;一&#xff09;&#xff1a;基本原理介绍 扩散模型实战&#xff08;二&#xff09;&#xff1a;扩散模型的发展 扩散模型实战&#xff08;三&#xff09;&#xff1a;扩散模型的应用 扩散模型实战&#xff08;四&#xff…
阅读更多...
Dubbo协议详解

Dubbo协议详解

前言特点应用场景Dubbo协议示例Dubbo协议的不足拓展 前言 Dubbo协议是一种高性能、轻量级的开源RPC框架&#xff0c;主要设计目的是解决分布式系统中服务调用的一些常见问题&#xff0c;例如服务负载均衡、服务注册中心、服务的远程调用等。它支持多种语言&#xff0c;例如Jav…
阅读更多...
LeetCode（26）判断子序列【双指针】【简单】

LeetCode（26）判断子序列【双指针】【简单】

目录 1.题目2.答案3.提交结果截图 链接&#xff1a; 判断子序列 1.题目 给定字符串 s 和 t &#xff0c;判断 s 是否为 t 的子序列。 字符串的一个子序列是原始字符串删除一些&#xff08;也可以不删除&#xff09;字符而不改变剩余字符相对位置形成的新字符串。&#xff08;…
阅读更多...
centos搭建docker镜像Harbor仓库的简明方法

centos搭建docker镜像Harbor仓库的简明方法

在kubernetes集群中如果要部署springcloud这样的应用&#xff0c;就必须有一个自建的docker镜像中心仓库。 它的目的有两点&#xff1a; 1. 镜像拉取速度快 2. 开发好维护 而Harbor是一个非常好用的docker本地仓库 所以本篇文章来讲讲如何在部署Harbor仓库 首先系统版本最…
阅读更多...
此芯科技加入绿色计算产业联盟，参编绿色计算产业发展白皮书

此芯科技加入绿色计算产业联盟，参编绿色计算产业发展白皮书

近日&#xff0c;此芯科技正式加入绿色计算产业联盟&#xff08;Green Computing Consortium&#xff0c;简称GCC&#xff09;&#xff0c;以Arm架构通用智能CPU芯片及高能效的Arm PC计算解决方案加速构建软硬协同的绿色计算生态体系&#xff0c;推动绿色计算产业加速发展。 继…
阅读更多...
Linux_系统信息_uname查看内核版本、内核建立时间、处理器类型、顺便得到操作系统位数等

Linux_系统信息_uname查看内核版本、内核建立时间、处理器类型、顺便得到操作系统位数等

1、uname --help 使用uname --help查看uname命令的帮助信息 2、uname -a 通过上面的help就知道-a选项显示全部内容时的含义了。 内核名是Linux主机名是lubancat&#xff0c;如果想看主机名可以使用命令hostname&#xff1b;内核版本是Linux 4.19.232&#xff0c;建立时间为2…
阅读更多...
全栈工程师必须要掌握的前端Html技能

全栈工程师必须要掌握的前端Html技能

作为一名全栈工程师&#xff0c;在日常的工作中&#xff0c;可能更侧重于后端开发&#xff0c;如&#xff1a;C#&#xff0c;Java&#xff0c;SQL &#xff0c;Python等&#xff0c;对前端的知识则不太精通。在一些比较完善的公司或者项目中&#xff0c;一般会搭配前端工程师&a…
阅读更多...
【二分法】

【二分法】

二分法可以在有序排列中&#xff0c;通过不断对半切割数据&#xff0c;提高数据查找效率。 lst [1,4,6,7,45,66,345,767,788,999] n 66 left 0 right len(lst)-1 while left < right: #边界&#xff0c;当右边比左边还小的时候退出循环 mid (left right)//2 …
阅读更多...
JVM虚拟机-虚拟机执行子系统-第6章 类文件结构

JVM虚拟机-虚拟机执行子系统-第6章 类文件结构

各种不同平台的Java虚拟机&#xff0c;以及所有平台都统一支持的程序存储格式——字节码&#xff08;Byte Code&#xff09;是构成平台无关性的基石 Class类文件的结构 字节码指令&#xff1a;操作码 操作数 任何一个Class文件都对应着唯一的一个类或接口的定义信息 Class文件…
阅读更多...
C/C++输出整数部分 2021年12月电子学会青少年软件编程（C/C++）等级考试一级真题答案解析

C/C++输出整数部分 2021年12月电子学会青少年软件编程（C/C++）等级考试一级真题答案解析

目录 C/C输出整数部分 一、题目要求 1、编程实现 2、输入输出 二、算法分析 三、程序编写 四、程序说明 五、运行结果 六、考点分析 C/C输出整数部分 2021年12月 C/C编程等级考试一级编程题 一、题目要求 1、编程实现 输入一个双精度浮点数f&#xff0c; 输出其整…
阅读更多...
C++打怪升级（十一）- STL之list

C++打怪升级（十一）- STL之list

~~~~ 前言1. list是什么2. list接口函数的使用1. 构造相关默认构造n个val构造迭代器范围构造拷贝构造 2 赋值运算符重载函数2 析构函数3 迭代器相关begin 和 endrbegin 和rend 4 容量相关emptysize 5 元素访问相关frontback 6 修改相关push_backpop_backpush_frontpop_frontins…
阅读更多...
【OJ比赛日历】快周末了，不来一场比赛吗？ #11.18-11.24 #15场

【OJ比赛日历】快周末了，不来一场比赛吗？ #11.18-11.24 #15场

CompHub[1] 实时聚合多平台的数据类(Kaggle、天池…)和OJ类(Leetcode、牛客…&#xff09;比赛。本账号会推送最新的比赛消息&#xff0c;欢迎关注&#xff01; 以下信息仅供参考&#xff0c;以比赛官网为准 目录 2023-11-18&#xff08;周六&#xff09; #5场比赛2023-11-19…
阅读更多...
受电诱骗快充取电芯片XSP08：PD+QC+华为+三星多种协议9V12V15V20V

受电诱骗快充取电芯片XSP08：PD+QC+华为+三星多种协议9V12V15V20V

目前市面上很多家的快充充电器&#xff0c;都有自己的私有快充协议&#xff0c;如PD协议、QC协议、华为快充协议、三星快充协议、OPPO快充协议等待&#xff0c;为了让它们都能输出快充电压&#xff0c;就需要在受电端也增加快充协议取电芯片XSP08&#xff0c;它可以和充电器通讯…
阅读更多...
我记不住的getopt_long的那些参数和返回值

我记不住的getopt_long的那些参数和返回值

前言&#xff1a;最近在学习面向Linux系统进行C语言的编程&#xff0c;通过查询man手册和查看网络上的各种文章来获取一点点的知识&#xff0c;重点是看完手册还是一脸懵逼&#xff0c;搞不懂手册里面再说啥&#xff0c;而本篇文章将记录一下学习getopt_long的那些参数和返回值…
阅读更多...
IDEA无法查看源码是.class,而不是.java解决方案？

IDEA无法查看源码是.class,而不是.java解决方案？

问题&#xff1a;在idea中&#xff0c;ctrl鼠标左键进入源码&#xff0c;但是有时候会出现无法查看反编译的源码&#xff0c;如图&#xff01; 而我们需要的是方法1: mvn dependency:resolve -Dclassifiersources 注意&#xff1a;需要该模块的目录下&#xff0c;不是该文件目…
阅读更多...
计算机毕业设计选题推荐-幼儿园管理微信小程序/安卓APP-项目实战

计算机毕业设计选题推荐-幼儿园管理微信小程序/安卓APP-项目实战

✨作者主页&#xff1a;IT毕设梦工厂✨ 个人简介&#xff1a;曾从事计算机专业培训教学&#xff0c;擅长Java、Python、微信小程序、Golang、安卓Android等项目实战。接项目定制开发、代码讲解、答辩教学、文档编写、降重等。 ☑文末获取源码☑ 精彩专栏推荐⬇⬇⬇ Java项目 Py…
阅读更多...
LeetCode（24）文本左右对齐【数组/字符串】【困难】

LeetCode（24）文本左右对齐【数组/字符串】【困难】

目录 1.题目2.答案3.提交结果截图 链接&#xff1a; 文本左右对齐 1.题目 给定一个单词数组 words 和一个长度 maxWidth &#xff0c;重新排版单词&#xff0c;使其成为每行恰好有 maxWidth 个字符&#xff0c;且左右两端对齐的文本。 你应该使用 “贪心算法” 来放置给定的单…
阅读更多...
最新文章

Copyright @ 2022~2023