计算机考研408的算法题详解 |
您所在的位置：网站首页 › 408数据结构有几道大题和小题 › 计算机考研408的算法题详解 |
|
2019年真题
题目：设线性表L=（a1，a2，a3,......,a(n-2)，a(n-1)，a(n)），采用带头结点的单链表保存，链表中的结点定义如下。请设计一个空间复杂度为O(1)且时间上尽可能高效的算法，重新排列L中的各结点，得到新线性表L'=（a1，a(n)，a2，a(n-1)，a3，a(n-2),......）。 typedef struct node { int data; struct node *next; } NODE;思路分析：①先找到链表的中心结点，使用两个指针p，每次p走一步，q走两步，当q到链表尾时，p正好在链表中心结点。②将链表后半段原地逆置。③将单链表前后两段中依次各取一个结点，进行重排。 NODE *reverseList(NODE *head) { //将指针全部反转 NODE* pre = NULL; NODE* cur = head; NODE* tmp = NULL;//记录cur的下一个结点 while(cur != NULL) { //记录当前节点的下一个节点 tmp = cur->next; //然后将当前节点指向pre cur->next = pre; //pre和cur节点都前进一位 pre = cur; cur = tmp; } return pre; } void changeList(NODE *head) { NODE *p, *q, *temp; p = q = head; //1、找到中间结点 while(q->next != NULL) { p = p->next; q = q->next; if(q->next != NULL) {//q走两步。用if再判断一次是为了防止走一步后就已到队尾，出现NULL->next异常 q = q->next; } } //此时p指向链表L的中心结点 n/2，向下取整。 //2、后半段链表反转。 NODE *back = reverseList(p-next);//将后半段链表逆置，back指向后半段链表的第一个节点。 NODE *pre = head->next; //pre指向前半段链表的第一个节点。 //3、前半段链表和后半段链表依次各取一个结点。 while(e != NULL) { temp = back->next;//用于back指针后移 back->next = pre->next; pre->next = back; pre = back->next;//pre指针后移 back = temp; //back指针后移 } }链表的算法题一定要手动模拟一遍。其中链表反转部分参考力扣：https://leetcode-cn.com/problems/reverse-linked-list/solution/dong-hua-yan-shi-206-fan-zhuan-lian-biao-by-user74/ 2018年真题 题目：给定一个含n（n>=1）个整数的数组，请设计一个在时间上尽可能高效的算法，找出数组中未出现的最小正整数。例如，数组{-5,3,2,3}中未出现的最小正整数是1；数组{1,2,3}中未出现的最小正整数是4。 思路分析：基于map的思想，创建一个和数组等长的map，遍历数组，对map[i]++；再遍历一次map，对第一次出现的map[i]!=0时的键i输出，即为最小正整数。但408不让用STL，因此用数组来代替map。 1、创建动态数组： 在堆中开辟一块大小为n*sizeof(int)的一块内存空间（因为int是32位，因而此处开辟了n*4Bit的存储空间）； 指针B指向这块内存空间的起始地址（即数组的第一个元素）； malloc前面的（int*）用于强制类型转换，表示这块空间用来存储int型数组。 int *B = (int *)malloc(n*sizeof(int)); free(B); void* malloc(size_t size); //其中参数size_t size表示动态内存分配空间的大小，以字节为单位。malloc返回值是一个指针。 void free(void *ptr); //当不在使用malloc()函数申请的空间之后，应释放掉这个内存空间：2、批量赋初值：对数组B中的n个元素均赋值为0。 memset(B,0,n*sizeof(int)); void *memset(void *s, int v, size_t n); //这里s可以是数组名，也可以是指向某一内在空间的指针； //v为要填充的值； //n为要填充的字节数；完整代码： #include #include using namespace std; /*数组中未出现的最小正整数*/ int findMissMin(int A[], int n){ int *B = (int *)malloc(n*sizeof(int)); //创建动态数组并分配存储空间 memset(B,0,n*sizeof(int)); //赋初值 int i; for(i = 0; i < n; ++i) { if(A[i] > 0 && A[i] < n){// 仅对数组A中的值为1~n的元素进行处理 B[ A[i]- 1 ]++; } } for(i = 0; i < n; ++i) { if(B[i] == 0){ break; } } free(B); return i + 1; } int main(){ int a[3] = {1,2,3}, c[4] = {-5,3,2,3}; cout |
今日新闻 |
点击排行 |
|
推荐新闻 |
图片新闻 |
|
专题文章 |
| CopyRight 2018-2019 实验室设备网 版权所有 win10的实时保护怎么永久关闭 |