数据结构与算法A 查找
2021/11/28 20:42:21
本文主要是介绍数据结构与算法A 查找，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！
题目列表
- 1.电话聊天狂人
- 2.两个有序序列的中位数
- 3.词频统计【未完成】
- 4.集合相似度
- 5.悄悄关注
- 6.单身狗
- 7.词典
- 8.中序遍历树并判断是否为二叉搜索树
1.电话聊天狂人
给定大量手机用户通话记录，找出其中通话次数最多的聊天狂人。
输入格式
输入首先给出正整数N（≤105），为通话记录条数。随后N行，每行给出一条通话记录。简单起见，这里只列出拨出方和接收方的11位数字构成的手机号码，其中以空格分隔。
输出格式
在一行中给出聊天狂人的手机号码及其通话次数，其间以空格分隔。如果这样的人不唯一，则输出狂人中最小的号码及其通话次数，并且附加给出并列狂人的人数。
输入样例
4
13005711862 13588625832
13505711862 13088625832
13588625832 18087925832
15005713862 13588625832
输出样例
13588625832 3
代码1
#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define MAX 200005
char s[MAX][12];
int cmp(const void* a, const void* b)
{
return strcmp((char*)a, (char*)b) > 0 ? 1 : -1;
}
int main()
{
int n;
int max = 0, num = 0;
int d = -1;
char arr[12] = "";
scanf("%d", &n);
for (int i = 0; i < n; i++)
{
scanf("%s%s", s[i * 2], s[i * 2 + 1]);
}
qsort(s, 2 * n, sizeof(s[0]), cmp);
for (int i = 1; i < 2 * n + 1; i++)
{
if (strcmp(s[i], s[i - 1]) == 0)
{
num++;
}
else
{
if (num > max)
{
strcpy(arr, s[i - 1]);
max = num;
d = 1;
}
else if (num == max)
{
d++;
}
num = 1;
}
}
printf("%s %d", arr, max);
if (d > 1)
{
printf(" %d", d);
}
return 0;
}
代码2
#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
typedef struct loca loca;
typedef struct hash hash;
struct loca
{
long long data;
int c;
loca* next;
};
struct hash
{
int hsize;
loca** har;
};
hash* Create(int n)
{
hash* h = (hash*)malloc(sizeof(hash));
h->hsize = n;
h->har = (loca**)malloc(sizeof(loca*) * n);
for (int i = 0; i < h->hsize; i++)
{
h->har[i] = (loca*)malloc(sizeof(loca));
h->har[i]->next = NULL;
}
return h;
}
void insert(long long n, hash* h)
{
int d = n % h->hsize;
loca* pos = h->har[d];
while (pos->next)
{
if (pos->next->data == n)
{
pos->next->c++;
return;
}
pos = pos->next;
}
pos->next = (loca*)malloc(sizeof(loca));
pos->next->data = n;
pos->next->c = 1;
pos->next->next = NULL;
}
void find(hash* h)
{
long long d = 0;
int max = 0, c;
for (int i = 0; i < h->hsize; i++)
{
loca* p = h->har[i]->next;
while (p)
{
if (p->c > max)
{
max = p->c;
d = p->data;
c = 0;
}
else if (p->c == max)
{
c++;
if (p->data < d)
{
d = p->data;
}
}
p = p->next;
}
}
printf("%lld %d", d, max);
if (c)
{
printf(" %d", c + 1);
}
}
int isprime(int n)
{
if (n == 2 || n == 3)
{
return 1;
}
if (n % 6 != 1 && n % 6 != 5)
{
return 0;
}
for (int i = 5; i * i <= n; i += 6)
{
if (n % i == 0 || n % (i + 2) == 0)
{
return 0;
}
}
return 1;
}
int nextprime(int n)
{
if (n % 2 == 0)
{
n++;
}
while (!isprime(n))
{
n += 2;
}
return n;
}
int main()
{
int n;
long long a, b;
scanf("%d", &n);
hash* h = Create(nextprime(n * 2));
for (int i = 0; i < n; i++)
{
scanf("%lld %lld", &a, &b);
insert(a, h);
insert(b, h);
}
find(h);
return 0;
}
2.两个有序序列的中位数
已知有两个等长的非降序序列S1, S2, 设计函数求S1与S2并集的中位数。有序序列A0,A1,⋯,AN−1的中位数指A(N−1)/2的值,即第⌊(N+1)/2⌋个数（A0为第1个数）。
输入格式
输入分三行。第一行给出序列的公共长度N（0<N≤100000），随后每行输入一个序列的信息，即N个非降序排列的整数。数字用空格间隔。
输出格式
在一行中输出两个输入序列的并集序列的中位数。
输入样例1
5
1 3 5 7 9
2 3 4 5 6
输出样例1
4
输入样例2
6
-100 -10 1 1 1 1
-50 0 2 3 4 5
输出样例2
1
代码
#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>
int arr1[100005], arr2[100005];
int n;
int Dw()
{
int i = 0, j = 0;
int m = (2 * n - 1) / 2;
while (i + j < m)
{
if (arr1[i] > arr2[j])
{
j++;
}
else {
i++;
}
}
return arr1[i] > arr2[j] ? arr2[j] : arr1[i];
}
int main()
{
scanf("%d", &n);
for (int i = 0; i < n; i++)
{
scanf("%d", &arr1[i]);
}
for (int i = 0; i < n; i++)
{
scanf("%d", &arr2[i]);
}
printf("%d", Dw());
return 0;
}
3.词频统计【未完成】
请编写程序，对一段英文文本，统计其中所有不同单词的个数，以及词频最大的前10%的单词。
所谓“单词”，是指由不超过80个单词字符组成的连续字符串，但长度超过15的单词将只截取保留前15个单词字符。而合法的“单词字符”为大小写字母、数字和下划线，其它字符均认为是单词分隔符。
输入格式
输入给出一段非空文本，最后以符号#结尾。输入保证存在至少10个不同的单词。
输出格式
在第一行中输出文本中所有不同单词的个数。注意“单词”不区分英文大小写，例如“PAT”和“pat”被认为是同一个单词。
随后按照词频递减的顺序，按照词频:单词的格式输出词频最大的前10%的单词。若有并列，则按递增字典序输出。
输入样例
This is a test.
The word “this” is the word with the highest frequency.
Longlonglonglongword should be cut off, so is considered as the same as longlonglonglonee. But this_8 is different than this, and this, and this…#
this line should be ignored.
输出样例
(注意：虽然单词the也出现了4次，但因为我们只要输出前10%（即23个单词中的前2个）单词，而按照字母序，the排第3位，所以不输出.)
23
5:this
4:is
代码
4.集合相似度
给定两个整数集合，它们的相似度定义为：Nc/Nt×100%。其中Nc是两个集合都有的不相等整数的个数，Nt是两个集合一共有的不相等整数的个数。你的任务就是计算任意一对给定集合的相似度。
输入格式
输入第一行给出一个正整数N（≤50），是集合的个数。随后N行，每行对应一个集合。每个集合首先给出一个正整数M（≤104），是集合中元素的个数；然后跟M个[0,109]区间内的整数。
之后一行给出一个正整数K（≤2000），随后K行，每行对应一对需要计算相似度的集合的编号（集合从1到N编号）。数字间以空格分隔.
输出格式
对每一对需要计算的集合，在一行中输出它们的相似度，为保留小数点后2位的百分比数字。
输入样例
3
3 99 87 101
4 87 101 5 87
7 99 101 18 5 135 18 99
2
1 2
1 3
输出样例
50.00%
33.33%
代码
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<set>
using namespace std;
int main()
{
set<int>st[51];
int n, m;
cin >> n;
for (int i = 1; i <= n; i++)
{
cin >> m;
while (m--)
{
int k;
cin >> k;
st[i].insert(k);
}
}
int l;
cin >> l;
while (l--)
{
int a1, a2;
int s = 0;
cin >> a1 >> a2;
set<int>::iterator it;
for (it = st[a1].begin(); it != st[a1].end(); it++)
{
if (st[a2].count(*it))
{
s++;
}
}
int ans = st[a1].size() + st[a2].size() - s;
printf("%.2lf%%\n", s * 100.0 / ans);
}
return 0;
}
5.悄悄关注
新浪微博上有个“悄悄关注”，一个用户悄悄关注的人，不出现在这个用户的关注列表上，但系统会推送其悄悄关注的人发表的微博给该用户。现在我们来做一回网络侦探，根据某人的关注列表和其对其他用户的点赞情况，扒出有可能被其悄悄关注的人。
输入格式
输入首先在第一行给出某用户的关注列表，格式如下：
人数N 用户1 用户2 …… 用户N
其中N是不超过5000的正整数，每个用户i（i=1, …, N）是被其关注的用户的ID，是长度为4位的由数字和英文字母组成的字符串，各项间以空格分隔。
之后给出该用户点赞的信息：首先给出一个不超过10000的正整数M，随后M行，每行给出一个被其点赞的用户ID和对该用户的点赞次数（不超过1000），以空格分隔。注意：用户ID是一个用户的唯一身份标识。题目保证在关注列表中没有重复用户，在点赞信息中也没有重复用户。
输出格式
我们认为被该用户点赞次数大于其点赞平均数、且不在其关注列表上的人，很可能是其悄悄关注的人。根据这个假设，请你按用户ID字母序的升序输出可能是其悄悄关注的人，每行1个ID。如果其实并没有这样的人，则输出“Bing Mei You”。
输入样例1
10 GAO3 Magi Zha1 Sen1 Quan FaMK LSum Eins FatM LLao
8
Magi 50
Pota 30
LLao 3
Ammy 48
Dave 15
GAO3 31
Zoro 1
Cath 60
输出样例1
Ammy
Cath
Pota
输入样例2
11 GAO3 Magi Zha1 Sen1 Quan FaMK LSum Eins FatM LLao Pota
7
Magi 50
Pota 30
LLao 48
Ammy 3
Dave 15
GAO3 31
Zoro 29
输出样例2
Bing Mei You
代码
#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define MAX 10000
char s1[5000][5];
char s2[MAX][5];
int n2[MAX];
char s3[MAX][5];
int cmp(const void* a, const void* b)
{
return strcmp((char*)a, (char*)b) > 0 ? 1 : -1;
}
int main()
{
int n;
scanf("%d", &n);
for (int i = 0; i < n; i++)
{
scanf("%s", s1[i]);
fflush(stdin);
}
fflush(stdin);
qsort(s1, n, sizeof(s1[0]), cmp);
int m, k;
int sum = 0;
scanf("%d", &m);
for (int i = 0; i < m; i++)
{
scanf("%s", s2[i]);
fflush(stdin);
scanf("%d", &n2[i]);
sum += n2[i];
}
double ave = sum * 1.0 / m;
int cnt = 0;
for (int i = 0; i < m; i++)
{
if (ave < n2[i])
{
strcpy(s3[cnt++], s2[i]);
for (int j = 0; j < n; j++)
{
if (s2[i][0] == s1[j][0])
{
if (strcmp(s2[i], s1[j]) == 0)
{
cnt--;
break;
}
}
}
}
}
qsort(s3, cnt, sizeof(s3[0]), cmp);
if (cnt > 0)
{
for (int i = 0; i < cnt - 1; i++)
{
printf("%s\n", s3[i]);
}
printf("%s", s3[cnt - 1]);
}
else
{
printf("Bing Mei You");
}
return 0;
}
6.单身狗
“单身狗”是中文对于单身人士的一种爱称。本题请你从上万人的大型派对中找出落单的客人，以便给予特殊关爱。
输入格式
输入第一行给出一个正整数 N（≤50000），是已知夫妻/伴侣的对数；随后 N 行，每行给出一对夫妻/伴侣——为方便起见，每人对应一个 ID 号，为 5 位数字（从 00000 到 99999），ID 间以空格分隔；之后给出一个正整数 M（≤10000），为参加派对的总人数；随后一行给出这 M 位客人的 ID，以空格分隔。题目保证无人重婚或脚踩两条船。
输出格式
首先第一行输出落单客人的总人数；随后第二行按 ID 递增顺序列出落单的客人。ID 间用 1 个空格分隔，行的首尾不得有多余空格。
输入样例
3
11111 22222
33333 44444
55555 66666
7
55555 44444 10000 88888 22222 11111 23333
输出样例
5
10000 23333 44444 55555 88888
代码
#include<iostream>
#include<cstdio>
#include<cstdlib>
using namespace std;
const int N = 100005;
int arr[N];
int main()
{
int n;
cin >> n;
for (int i = 0; i < N; i++)
{
arr[i] = -1;
}
for (int i = 0; i < n; i++)
{
int a1, a2;
cin >> a1 >> a2;
arr[a1] = a2;
arr[a2] = a1;
}
int m;
cin >> m;
int cnt = 0;
for (int i = 0; i < m; i++)
{
int k;
cin >> k;
if (arr[k] >= 0)
{
arr[k] = -2;
}
else if (arr[k] != -2)
{
arr[k] = -3;
cnt++;
}
}
for (int i = 0; i < N; i++)
{
if (arr[i] >= 0)
{
if (arr[arr[i]] == -2)
{
arr[arr[i]] = -3;
cnt++;
}
}
}
cout << cnt << endl;
for (int i = 0; i < N; i++)
{
if (arr[i] == -3)
{
printf("%05d", i);
char c = --cnt == 0 ? '\n' : ' ';
cout << c;
}
}
return 0;
}
7.词典
你刚从滑铁卢搬到了一个大城市，这里的人们讲一种难以理解的外语方言。幸运的是，你有一本字典来帮助你理解它们。
输入格式
输入第一行是正整数N和M,后面是N行字典条目（最多10000条），然后是M行要翻译的外语单词（最多10000个）。每一个字典条目都包含一个英语单词，后面跟着一个空格和一个外语单词。 输入中的每个单词都由最多10个小写字母组成。
输出格式
输出翻译后的英文单词，每行一个单词。非词典中的外来词汇输出“eh”。
输入样例
5 3
dog ogday
cat atcay
pig igpay
froot ootfray
loops oopslay
atcay
ittenkay
oopslay
输出样例
cat
eh
loops
代码
#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define MAX 10005
typedef struct
{
char word[11];
char fword[11];
}Enum;
int main()
{
int n, m;
Enum e[MAX];
char tw[11];
scanf("%d %d", &n, &m);
fflush(stdin);
for (int i = 0; i < n; i++)
{
scanf("%s %s", e[i].word, e[i].fword);
fflush(stdin);
}
while (m--)
{
scanf("%s", tw);
fflush(stdin);
int i;
int flag = 0;
for (i = 0; i < n; i++)
{
if (e[i].fword[0] == tw[0])
{
if (strcmp(e[i].fword, tw) == 0)
{
printf("%s\n", e[i].word);
flag = 1;
}
}
}
if (flag == 0)
{
printf("eh\n");
}
}
return 0;
}
8.中序遍历树并判断是否为二叉搜索树
对给定的有N个节点（N>=0）的二叉树，给出中序遍历序列，并判断是否为二叉搜索树。
题目保证二叉树不超过200个节点，节点数值在整型int范围内且各不相同。
输入格式
第一行是一个非负整数N，表示有N个节点
第二行是一个整数k，是树根的元素值
接下来有N-1行，每行是一个新节点，格式为 r d e 三个整数，
r表示该节点的父节点元素值（保证父节点存在）；d是方向，0表示该节点为父节点的左儿子，1表示右儿子；e是该节点的元素值
输出格式
首先输出二叉树的中序遍历序列，每个元素占一行。对于空树，不输出任何内容。
然后如果给定的树是二叉搜索树，输出Yes 否则输出No
输入样例
对于图片中的二叉树：
3
20
20 0 10
20 1 25
输出样例
10
20
25
Yes
代码
#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>
#define MAX 200
int a[205];
int i;
int flag;
int min;
typedef struct
{
int data;
struct Tree* lchild, * rchild;
}Tree;
Tree* init()
{
Tree* T;
T = (Tree*)malloc(sizeof(Tree));
T->data = NULL;
T->lchild = NULL;
T->rchild = NULL;
return T;
}
Tree* find(Tree* T, int r)
{
if (!T)
{
return NULL;
}
if (T->data == r)
{
return T;
}
else
{
Tree* R = find(T->lchild, r);
if (!R)
{
return find(T->rchild, r);
}
return R;
}
}
void insert(Tree* T, int d, int e)
{
Tree* R = init();
R->data = e;
if (d == 0)
{
T->lchild = R;
}
if (d == 1)
{
T->rchild = R;
}
}
void traverse(Tree* T)
{
if (!T)
{
return NULL;
}
else
{
traverse(T->lchild);
printf("%d\n", T->data);
a[i++] = T->data;
traverse(T->rchild);
}
}
int main()
{
int n;
scanf("%d", &n);
if (n == 0)
{
printf("Yes");//好吧，这一步输出我也不知道为什么 = = 没有这一步输出过不了测试点4
return 0;
}
else
{
Tree* T = init();
int k;
scanf("%d", &k);
T->data = k;
for (int j = 0; j < n - 1; j++)
{
int r, d, e;
scanf("%d %d %d", &r, &d, &e);
Tree* R = init();
R = find(T, r);
insert(R, d, e);
}
traverse(T);
min = a[0];
for (int j = 1; j < i; j++)
{
if (min < a[j])
{
min = a[j];
flag = 1;
}
else
{
flag = 0;
break;
}
}
if (flag)
{
printf("Yes");
}
else
{
printf("No");
}
return 0;
}
}
这篇关于数据结构与算法A 查找的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
- 2025-01-09百万架构师第十二课：源码分析：Spring 源码分析：Spring系统概述及IOC实现原理｜JavaGuide
- 2025-01-08如何用关键链方法突破项目管理瓶颈？
- 2025-01-08电商人必看！6 款提升团队协作与客户满意度软件！
- 2025-01-08电商团队管理混乱？快用这 6 款软件优化协作流程！
- 2025-01-08短剧制作效率低？试试这5款任务管理工具
- 2025-01-08高效应对电商高峰，6 款团队协作软件大揭秘！
- 2025-01-08为什么外贸人都爱上了在线协作工具？
- 2025-01-08提升工作效率，从这些任务管理工具开始
- 2025-01-08新年电商订单暴增，必备的 6 款可视化协作办公软件有哪些？
- 2025-01-08短剧制作经理必备技能与工具全解析
