• 数据结构刷题

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

    递归为O(n)

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

    消失的数字

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

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

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

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

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

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

    1. int missingNumber(int* nums, int numsSize){
    2.     int x = 0;//0与任何数异或为该数
    3.     for(int i = 0;i
    4.     {
    5.         x ^= nums[i];
    6.     }
    7.      for(int i = 0;i<=numsSize;i++)
    8.      {
    9.           x ^= i;
    10.      }
    11.      return x;
    12. }

    轮转数组

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

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

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

    不完整代码： 

    1. void rotate(int* nums, int numsSize, int k){
    2.     int tmp[numsSize];
    3.     k %= numsSize;//循环次数不必多于元素个数
    4.     int i = 0;
    5.     int j = 0;
    6.     for(i=numsSize-k;i
    7.     {
    8.         tmp[j] = nums[i];
    9.         j++;
    10.     }
    11.     for(i = 0;i
    12.     {
    13.         tmp[j] = nums[i];
    14. }
    15. for//打印
    16. }

    有效的括号

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

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

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

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

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

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

    1. #include 
    2. #include 
    3. #include 
    4. typedef char STDatatype;
    5. typedef struct Stack
    6. {
    7. 	STDatatype* a;
    8. 	int capacity;
    9. 	int top;
    10. }ST;
    11. void check_capacity(ST* ps)
    12. {
    13.      if(ps->capacity == ps->top)
    14.     {
    15.         int newCapacity = 0 ? 4:ps->capacity*2;
    16.         char* tmp;
    17.         tmp = (STDatatype*)realloc(ps->a,sizeof(STDatatype) * newCapacity);
    18. 	    if (tmp == NULL)
    19. 	    {
    20. 		    perror("malloc");
    21. 		    exit(-1);
    22. 	    }
    23.         ps->a = tmp;
    24. 	    ps->capacity = newCapacity;
    25.     }
    26. }
    27. bool StackEmpty(ST* ps)//判空
    28. {
    29. 	assert(ps);
    30. 	return ps->top == 0;
    31. }
    32. STDatatype StackTop(ST* ps)
    33. {
    34. 	assert(ps);
    35. 	assert(!StackEmpty(ps));
    36. 	return ps->a[ps->top-1];//top为最后一个元素的下一个
    37. }
    38. void StackDestroy(ST* ps)
    39. {
    40. 	assert(ps);
    41.  
    42. 	free(ps->a);
    43. 	ps->a = NULL;
    44. 	ps->top = ps->capacity = 0;
    45. }
    46. void StackInit(ST* ps)
    47. {
    48. 	/*ps->a = NULL;
    49. 	ps->top = 0;
    50. 	ps->capacity = 0;*/
    51. 	//初始化空间
    52. 	ps->a = (STDatatype*)malloc(sizeof(STDatatype) * 4);
    53. 	if (ps->a == NULL)
    54. 	{
    55. 		perror("malloc");
    56. 		exit(-1);
    57. 	}
    58. 	ps->top = 0;
    59. 	ps->capacity = 4;
    60. }
    61. void StackPop(ST* ps)//出栈
    62. {
    63. 	assert(ps);
    64. 	//if(ps->top>0)
    65. 	assert(!StackEmpty(ps));
    66. 		ps->top--;
    67. }
    68. void StackPush(ST* ps, STDatatype x)
    69. {
    70. 	assert(ps);
    71. 	check_capacity(ps);
    72. 	ps->a[ps->top] = x;
    73. 	ps->top++;//指向下一个
    74. }
    75. bool isValid(char* s) {
    76.     ST ps;
    77.     StackInit(&ps); 
    78. while(*s)
    79. {
    80. 	if(*s == '(' || *s == '[' ||*s == '{' )
    81.     {
    82.         StackPush(&ps,*s);
    83.         s++;
    84.     }
    85. 		else
    86. 		{
    87.         if(StackEmpty(&ps))//如果没有左括号，栈顶没有元素
    88.         {
    89.             StackDestroy(&ps);//注意返回前都要手动释放空间
    90.             return false;
    91.         }
    92.         char top = StackTop(&ps);
    93.         if((*s == ')' && top != '(') || (*s == ']' && top != '[') ||
    94.         (*s == '}' && top != '{'))//
    95.         {
    96.             StackDestroy(&ps);
    97.             return false;
    98.         }
    99.         else
    100.         {
    101.             StackPop(&ps);
    102.             s++;
    103.         }
    104. 		}
    105. }
    106. bool ret = StackEmpty(&ps);
    107. StackDestroy(&ps);
    108. return ret;
    109. }

    用队列实现栈

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

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

    1. #pragma once
    2. #include 
    3. #include 
    4. #include 
    5. #include 
    6. typedef int QDataType;
    7. typedef struct QueueNode
    8. {
    9. 	QDataType data;
    10. 	struct QueueNode* next;
    11. }QNode;
    12. struct Queue
    13. {
    14. 	QNode* head;
    15. 	QNode* tail;
    16. 	int size;
    17. };
    18. void QueueInit(Queue* pq);
    19. void QueueDestroy(Queue* pq);
    20. void QueuePush(Queue* pq, QDataType x);
    21. void QueuePop(Queue* pq);
    22. QDataType QueueFront(Queue* pq);
    23. QDataType QueueBack(Queue* pq);
    24. bool QueueEmpty(Queue* pq);
    25. int QueueSize(Queue* pq);
    26.  
    27. void QueueDestroy(Queue* pq)
    28. {
    29. 	assert(pq);
    30. 	QNode* cur = pq->head;
    31. 	while (cur)
    32. 	{
    33. 		QNode* Next =cur->next;
    34. 		free(cur);
    35. 		cur = Next;
    36. 	}
    37. 	pq->head = pq->tail = NULL;//避免野指针
    38. 	pq->size = 0;
    39. }
    40. void QueuePush(Queue* pq, QDataType x)
    41. {
    42. 	assert(pq);
    43.  
    44. 	QNode* newnode = (QNode*)malloc(sizeof(QNode));
    45. 	if (newnode == NULL)
    46. 	{
    47. 		perror("malloc fail");
    48. 		exit(-1);
    49. 	}   
    50. 	newnode->data = x;
    51. 	newnode->next = NULL;
    52. 	pq->size++;
    53.  
    54. 	if (pq->head == NULL)
    55. 	{
    56. 		pq->head = pq->tail = newnode;
    57. 	}
    58. 	else
    59. 	{
    60. 		pq->tail->next = newnode;
    61. 		pq->tail = newnode;
    62. 	}
    63. }
    64. void QueuePop(Queue* pq)
    65. {
    66. 	//出队头删
    67. 	assert(pq);
    68. 	assert(pq->head);
    69. 	QNode* del = pq->head;
    70. 	pq->head = pq->head->next;
    71. 	free(del);
    72. 	if (pq->head == NULL)
    73. 		pq->tail = NULL;
    74. 	pq->size--;
    75. 	 
    76. }
    77. void QueueInit(Queue* pq)
    78. {
    79. 	assert(pq);
    80. 	pq->head = NULL;
    81. 	pq->tail = NULL;
    82. 	pq->size = 0;
    83. }
    84. bool QueueEmpty(Queue* pq)
    85. {
    86. 	assert(pq);
    87. 	return pq->head == NULL && pq->tail == NULL;
    88. }
    89. int QueueSize(Queue* pq)
    90. {
    91. 	assert(pq);
    92. 	return pq->size;
    93. }
    94. QDataType QueueFront(Queue* pq)
    95. {
    96. 	assert(pq);
    97. 	assert(!QueueEmpty(pq));
    98. 	return pq->head->data;
    99. }
    100. QDataType QueueBack(Queue* pq)
    101. {
    102. 	assert(pq);
    103. 	assert(!QueueEmpty(pq));
    104.  
    105. 	return pq->tail->data;
    106. }

     两个队列

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

    1. typedef struct Queue
    2. {
    3. 	QNode* head;
    4. 	QNode* tail;
    5. 	int size;
    6. }Queue;//简写

    创建并初始化链表(栈）

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

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

    模拟入栈

    选择非空队列插入即可。

    1. void myStackPush(MyStack* obj, int x) {
    2.     if(!QueueEmpty(&obj->q1))//非空队列插入
    3.     {
    4.         QueuePush(&obj->q1,x);
    5.     }
    6.     else
    7.         QueuePush(&obj->q2,x);
    8. }

    模拟出栈

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

    1. nt myStackPop(MyStack* obj) {
    2.     //假定一方不为空
    3.     Queue* empty = &obj->q1;
    4.     Queue* nonempty = &obj->q2;
    5.     if(!QueueEmpty(empty))
    6.     {
    7.           empty = &obj->q2;
    8.         nonempty = &obj->q1;
    9.     }
    10.     
    11.     while(QueueSize(nonempty) > 1)//O(1)导入空来链表
    12.     {
    13.         QueuePush(empty,QueueFront(nonempty));//非空取队头插入空 
    14.         QueuePop(nonempty);
    15.     }
    16.     //保证原链表返回为空
    17.     int top = QueueFront(nonempty);
    18.     QueuePop(nonempty);//出栈
    19.     return top;
    20. }

    模拟栈顶

    直接返回队尾元素即可。

    1. int myStackTop(MyStack* obj) {
    2.     //返回队尾
    3.     if(!QueueEmpty(&obj->q1))
    4.     {
    5.         return QueueBack(&obj->q1);
    6.     }
    7.     else
    8.     return QueueBack(&obj->q2);	
    9. }

    模拟栈判空

    1. bool myStackEmpty(MyStack* obj) {
    2.    
    3.     return QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2);
    4. }

    模拟栈销毁

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

    1. void myStackFree(MyStack* obj) {
    2.     QueueDestroy(&obj->q1);
    3.     QueueDestroy(&obj->q2);
    4.     free(obj);
    5. }

    用栈实现队列

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

    导入实现好的栈：

    1.  
    2. #include 
    3. #include 
    4. #include 
    5. #include 
    6.  
    7. typedef int STDatatype;
    8. typedef struct Stack
    9. {
    10. 	STDatatype* a;
    11. 	int capacity;
    12. 	int top;
    13. }ST;
    14.  
    15. void StackInit(ST* ps);
    16. void StackDestroy(ST* ps);
    17. void StackPush(ST* ps, STDatatype x);
    18. void StackPop(ST* ps);//出栈
    19. STDatatype StackTop(ST* ps);
    20.  
    21. bool StackEmpty(ST* ps);
    22. int StackSize(ST* ps);
    23.  
    24. void StackInit(ST* ps)
    25. {
    26. 	/*ps->a = NULL;
    27. 	ps->top = 0;
    28. 	ps->capacity = 0;*/
    29. 	//初始化空间
    30. 	ps->a = (STDatatype*)malloc(sizeof(STDatatype) * 4);
    31. 	if (ps->a == NULL)
    32. 	{
    33. 		perror("malloc");
    34. 		exit(-1);
    35. 	}
    36. 	ps->top = 0;
    37. 	ps->capacity = 4;
    38. }
    39.  
    40. static void check_capacity(ST* ps)
    41. {
    42. 	if (ps->top == ps->capacity)
    43. 	{
    44. 		int newCapacity = ps->capacity * 2;
    45. 		STDatatype* tmp = (STDatatype*)realloc(ps->a, newCapacity *sizeof(STDatatype));
    46. 		if (tmp == NULL)
    47. 		{
    48. 			perror("realloc");
    49. 			exit(-1);
    50. 		}
    51. 		else
    52. 		{
    53. 			ps->a = tmp;
    54. 			ps->capacity == newCapacity;
    55. 		}
    56. 	}
    57. }
    58. void StackPush(ST* ps, STDatatype x)
    59. {
    60. 	assert(ps);
    61. 	check_capacity(ps);
    62. 	ps->a[ps->top] = x;
    63. 	ps->top++;//指向下一个
    64. }
    65. void StackPop(ST* ps)//出栈
    66. {
    67. 	assert(ps);
    68. 	//if(ps->top>0)
    69. 	assert(!StackEmpty(ps));
    70. 		ps->top--;
    71. }
    72.  
    73. STDatatype StackTop(ST* ps)
    74. {
    75. 	assert(ps);
    76. 	assert(!StackEmpty(ps));
    77. 	return ps->a[ps->top-1];//top为最后一个元素的下一个
    78. }
    79. void StackDestroy(ST* ps)
    80. {
    81. 	assert(ps);
    82.  
    83. 	free(ps->a);
    84. 	ps->a = NULL;
    85. 	ps->top = ps->capacity = 0;
    86. }
    87. bool StackEmpty(ST* ps)//判空
    88. {
    89. 	assert(ps);
    90. 	return ps->top == 0;
    91. }
    92. int StackSize(ST* ps)
    93. {
    94. 	assert(ps);
    95. 	return ps->top;
    96. }

    两个栈

    1. typedef struct {
    2.     ST pushst;//入队
    3.     ST popst;//出队
    4. } MyQueue;

    Create

    1.  
    2. MyQueue* myQueueCreate() {
    3.         //初始化+开空间
    4.     MyQueue* st = (MyQueue*)malloc(sizeof(MyQueue));
    5.     StackInit(&st->pushst);
    6.     StackInit(&st->popst);
    7.     return st;
    8. }

    Push

    1. void myQueuePush(MyQueue* obj, int x) {
    2.     assert(obj);
    3.     StackPush(&obj->pushst,x);
    4. }

    判空 

    1. bool myQueueEmpty(MyQueue* obj) {
    2.     assert(obj);
    3.     return StackEmpty(&obj->pushst) && StackEmpty(&obj->popst);
    4. }

    查看队头

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

    1. int myQueuePeek(MyQueue* obj) {
    2.     assert(obj);
    3. 	assert(!myQueueEmpty(obj)); //双栈判空
    4. 		if(StackEmpty(&obj->popst))
    5. 		{
    6. 			while(!StackEmpty(&obj->pushst))//导数据
    7. 			{
    8. 				StackPush(&obj->popst,StackTop(&obj->pushst));
    9.                 StackPop(&obj->pushst);
    10. 			}
    11. 		}
    12.     return StackTop(&obj->popst);
    13. }

    Pop

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

    1. int myQueuePop(MyQueue* obj) {
    2.   
    3.       int qhead = myQueuePeek(obj);
    4.       StackPop(&obj->popst);//出队
    5.       return qhead;
    6. }

    释放

    1. void myQueueFree(MyQueue* obj) {
    2.     assert(obj);
    3.     StackDestroy(&obj->pushst);
    4.     StackDestroy(&obj->popst);
    5.     free(obj);
    6. }

  • 相关阅读:
    MySQL--创建，删除，查找，案例
    发展之路是怎么样？ 防爆机器人的未来发展之路是怎么样
    数字孪生产业园开发公司，VR钢铁效果怎么样?强荐广州华锐互动
    Shell常用的几个正则表达式:[:alnum:], [:alpha:], [:upper:], [:lower:], [:digit:] 认知
    代码随想录笔记_动态规划_139单词拆分
    字符串首尾空格去除问题
    redis
    JMeter 逻辑控制之IF条件控制器
    CLIP 论文逐段精读【论文精读】
    计算机组成原理 | 输入输出系统
  • 原文地址：https://blog.csdn.net/dwededewde/article/details/134082802