数据结构解题报告
重复计数 在一个有限的正整数序列中，有些数会多次重复出现。请你统计每个数的出现次数，然后按数字在序列中第一次出现的位置顺序输出数及其次数。 输入格式 第1行，1个整数N，表示整数的个数，(1≤N≤50000)。 第2行，N个正整数，每个整数x 都满足 1 ≤ x ≤2000000000。 输出格式 若干行，每行两个用一个空格隔开的数，第一个是数列中出现的数，第二个是该数在序列中出现的次数。 输入样例 在这里给出一组输入。例如: 1 2 12 8 2 8 2 2 11 1 1 8 1 13 13 输出样例 在这里给出相应的输出。例如: 1 2 3 4 5 8 3 2 3 11 1 1 3 13 2 题目解析 方法一:暴力法 这个方法非常简单啊，一波暴力，直接将遍历现有的数组去查找然后有的增加计数，没有的就直接添加 代码实现 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 #include<iostream> #include<algorithm> #include<vector> using namespace std; int main(int argc, char const *argv[]) { vector<pair<int,int>> list; int n=0; scanf("%d",&n); getchar(); int itemp=0; int t=0; for(int i=0;i<n;++i){ scanf("%d",&itemp); getchar(); //搜索 int target=-1; //置为-1用作标记是否存在 for(int j=0;j<list.size();++j){ if(list[j].first==itemp){ target=j; } } if(target){ list[target].second+=1; }else{ list.push_back(pair<int,int>(itemp,1)); } } for (int i = 0; i < list.size(); ++i) { printf("%d %d",list[i].first,list[i].second); if(i<list.size()-1)printf("\n"); } return 0; } 分析 显然的，这个时间复杂度是O($n^2$)的，非常低效，数据种类一多，就会被卡时间。那有没有优化的方法呢？显然是有的啦 这不是废话 方法二：使用Map优化的统计法 在暴力法中，查找数字花费了大量的时间，为了加速查找，使用STL中的Map是一个不错的选择，所以代码可以优化成这样 代码实现 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 #include<iostream> #include<algorithm> #include<vector> #include<map> using namespace std; int main(int argc, char const *argv[]) { vector<pair<int,int>> list; map<int,int> tofind; int n=0; scanf("%d",&n); getchar(); int itemp=0; int t=0; for(int i=0;i<n;++i){ scanf("%d",&itemp); getchar(); auto iter=tofind.find(itemp); //使用Map来加速查找 if(iter==tofind.end()){ tofind.insert(pair<int,int>(itemp,t)); list.push_back(pair<int,int>(itemp,1)); ++t; }else{ list[iter->second].second+=1; } } for (int i = 0; i < list.size(); ++i) { printf("%d %d",list[i].first,list[i].second); if(i<list.size()-1)printf("\n"); } return 0; } 方法三:使用Multiset(集合) 使用Multiset的方法其实与Map相差不大，可以用加入标记并重载排序函数来实现输入时顺序,其实Map也可以用同样的方式来排序 我是伞兵 此处就不在赘述。 方法四:使用排序和查找 主要思路就是运用相同数字排序后会形成一个区间，从而只要以区间上界减去下界即可得到个数 对于排序可以使用sort方法，而对于上下界也可以使用系统提供的lower*bound和upper_bound来获取，使用方法及代码请读者自行解决了，此处就提供一个思路就是懒 报数游戏 n个人围成一圈，从1开始依次编号，做报数游戏。 现指定从第1个人开始报数，报数到第m个人时，该人出圈，然后从其下一个人重新开始报数，仍是报数到第m个人出圈，如此重复下去，直到所有人都出圈。总人数不足m时将循环报数。请输出所有人出圈的顺序。 输入格式 一行，两个整数n和m。n表示游戏的人数，m表示报数出圈的数字，1≤n≤50000，1≤m≤100. 输出格式 一行，n个用空格分隔的整数，表示所有人出圈的顺序 输入样例 1 5 2 输出样例 1 2 4 1 5 3 题目解析 从本质上来说，这就是约瑟夫问题，对于约瑟夫问题使用循环链表来解决是一个很好的方法。但是使用循环数组也可以实现，但是考虑到数组维护的复杂度还不如手撸一个链表来的快😅 方法一：循环链表(数组) 代码实现 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 //建立循环链表 #include<stdio.h> #include<stdlib.h> typedef struct Node{ int num; struct Node * next; }Person; //创建循环链表 Person* initLink(int n){ int i=0; Person* head=NULL,*cyclic=NULL; head=(Person*)malloc(sizeof(Person)); head->num=1; head->next=NULL; cyclic=head; //建立n个节点的循环链表 for(int i=2;i<=n;i++){ Person* body=(Person*)malloc(sizeof(Person)); body->num=i; body->next=NULL; cyclic->next=body; cyclic=cyclic->next; } cyclic->next=head;//首尾相连 return head; } //删去报到的人 void findAndDel(Person* head,int s,int m){ Person* point=NULL; Person* tail=head; //找到上一个节点 while(tail->next!=head){ tail=tail->next; } //从头开始 point=head; //找到编号为s的人 while(point->num!=s){ tail=point; point=point->next;//将point移动到下一个链表元素 } //从编号为s的人开始 只有符合point->next==point时,说明处P外全出列了 while(point->next!=point){ int i=0; //从point所指的人开始报数,找到报m-1的人,方便删除 for(i=1;i<m;i++){ tail=point; point=point->next; } //此时point所指的即为要杀死的人,摘除这个节点 tail->next=point->next; printf("%d " ,point->num); //释放空间 free(point); //将point指向下一个人 point=tail->next; } //最后只剩下一个人 printf("%d",point->num); free(point); } int main(int argc, char const *argv[]) { int n=0,s=1,m=0; Person* head=NULL; scanf("%d %d",&n,&m); head=initLink(n); findAndDel(head,s,m); printf("\n"); return 0; } 分析 总的来说，算是链表构建的时间，时间复杂度是O(n)的，当然用数组实现也是一样的。还是很nice 的 算术表达式计算 任务: 计算算术表达式的值。 算术表达式按中缀给出，以=号结束，包括+,-,,/四种运算和(、)分隔符。运算数的范围是非负整数，没有正负符号，小于等于109 。 计算过程中,如果出现除数为0的情况,表达式的结果为”NaN” ; 如果中间结果超出32位有符号整型范围,仍按整型计算，不必特殊处理。 输入保证表达式正确。 输入格式 一行，包括1个算术表达式。算术表达式的长度小于等于1000。 输出格式 一行，算术表达式的值 。 输入样例 1 (1+30)/3= 输出样例 1 10 题目解析 显然的对于这种题目，关键点就是前缀表达式转化为后缀表达式进行计算。可以先求后缀式，再求结果但是也可以结合起来，节省时间。 代码实现 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 #include <iostream> #include <stack> using namespace std; stack<int> num; stack<int> oper; bool cmpPriority(char a, char b) { if (b == '*' || b == '/') { if (a == '+' || a == '-' || a == '(') { return true; } else { return false; } } if (b == '+' || b == '-') { if (a == '*' || a == '/') { return false; } else { if (a == '(') { return true; } else { return false; } } } if (a == '(') { return true; } return true; } void poponeOpe(char ope) { int a = 0; int b = 0; switch (ope) { case '+': a = num.top(); num.pop(); b = num.top(); num.pop(); num.push(b + a); break; case '-': a = num.top(); num.pop(); b = num.top(); num.pop(); num.push(b - a); break; case '*': a = num.top(); num.pop(); b = num.top(); num.pop(); num.push(a * b); break; case '/': a = num.top(); num.pop(); b = num.top(); num.pop(); if (a == 0) { printf("NaN"); exit(0); } num.push(b / a); break; break; default: break; } } int main(int argc, char const *argv[]) { stack<int> &tosee = num; stack<int> &app = oper; char ctemp = 0; char ope = 0; int res = 0; int itemp = 0; bool flag = true; while (flag) { res = -1; itemp = 0; while (1) { ctemp = getchar(); if (ctemp >= '0' && ctemp <= '9') { itemp = itemp * 10 + int(ctemp - 48); res = itemp; } else { if (ctemp == '=') { flag = false; } break; } } if (res > -1) { num.push(res); } if (oper.empty()) { oper.push(ctemp); } else { if (ctemp == '(') { oper.push(ctemp); } else if (ctemp == ')') { while ('(' != oper.top()) { ope = oper.top(); poponeOpe(ope); oper.pop(); } oper.pop(); } else if (cmpPriority(oper.top(), ctemp)) { oper.push(ctemp); } else if (!cmpPriority(oper.top(), ctemp)) { while (!cmpPriority(oper.top(), ctemp)) { ope = oper.top(); poponeOpe(ope); oper.pop(); if (oper.empty()) break; } oper.push(ctemp); } } } while (!oper.empty()) { ope = oper.top(); poponeOpe(ope); oper.pop(); } printf("%d", num.top()); return 0; } 分析 总体来说，只是将整个字符串扫描了一遍，设字符串长度为n，时间复杂度为O(n)的。 最喜爱的序列 小唐这段时间在研究序列。拿来N个整数的序列，他给序列中的每个整数都赋予一个喜爱值。喜爱值也是整数，有正有负，越大表明越喜欢。他想知道，如何从序列中连续取最多m个数，他获得喜爱值最大。1≤N≤500000，1≤m≤N。 输入格式 第一行是两个整数N,m。分别代表序列中数的个数以及能取的最多个数。 第二行用空格隔开的N个整数，第i个整数Li代表他对第i个数的喜爱值。│Li│≤1000 输出格式 一行，三个数，表示获得最大喜爱值，及第一个取最大喜爱值的区间。 输入样例 1 2 5 2 1 4 5 2 3 输出样例 1 9 2 3 ...