数据结构，前几天上了解题分享。第一次的作业总体上比较简单的，要小心会超时。在没有上分享课之前，我对那两道题的解题思路还停留在初始的状态，听了其他人的思路，对那两道题加深了理解，的确要听取其他人的意见，思路才会打开。
第一道题
题目描述
顾名思义，互质序列是满足序列元素的gcd为1的序列。比如，[1， 2， 3]，[4， 7， 8]，都是互质序列。[3， 6， 9]不是互质序列。现在并不要求你找出一个互质序列，那样太简单了！真正的问题描述是：给定一个序列，删除其中一个元素使得剩下元素的gcd最大，输出这个gcd.
数据输入
输入第一行为一个正整数n。第二行为n个正整数ai(1 <= ai <= 10^9).
数据输出
输出一个正整数，表示最大的gcd.
| 输入示例 | 输出示例 |
|---|---|
| 3 | 1 |
| 1 1 1 |
解题思路
用两个数组储存从左到右、从右到左的gcd，在从头开始遍历，直接在两个数组对应的数据再求一次gcd即可。
下面是一个评优代码：
#include<stdio.h>
int gcd(int a,int b)
{
int t = 0;
while(b != 0)
{
t = b;
b = a % b;
a = t;
}
return a;
}
int a[100000],b[100000],c[100000];
int main()
{
int n;
scanf("%d",&n);
int i,j;
for(i = 1;i <= n;i++)
{
scanf("%d",&a[i]);
}
b[1] = a[1];
c[n] = a[n];
for(i = 2;i <= n;i++)
{
b[i] = gcd(b[i-1],a[i]);
}
for(i = n-1;i>1;i--)
{
c[i] = gcd(c[i+1],a[i]);
}
int max = 0;
if(b[n-1] >= c[2]) max = b[n-1];
else max = c[2];
for(i = 2;i < n;i++)
{
if(gcd(b[i-1],c[i+1])>max)
{
max = gcd(b[i-1],c[i+1]);
}
}
printf("%d",max);
return 0;
}
第二道题
题目描述
给出两个已按升序排列的数组，a[1,...,n], b[1,...,m],如果存在i、j,使得a[i] + b[j] = k, 我们便说已找到幸运值。请你判断能不能找到幸运值。
数据输入
输入第一行为正整数n, m, k(1 <= k <= 10^9)；
第二行为n个正整数a[1,...,n] (1 <= ai <= 10^9); 第三行为m个正整数b[1,...,m] (1 <= bi <= 10^9)。
数据输出
如果能找到幸运值，输出yes,否则输出no。
解题思路
1.暴力，两层循环，时间复杂度是O(n^2)
2.使用STL库函数lower_bound()
3.两个指针，一个指针指向a数组的头，一个指针指向b数组的尾，遍历即可。
下面是第三个思路的代码：
#include<algorithm>
#include<stdlib.h>
#include<iostream>
using namespace std;
int i,j,k,m,n,l,a[100000],b[100000];
int main()
{
cin>>m>>n>>k;
for(i=0;i<n;i++)
{
scanf("%d",&a[i]);
}
for(i=0;i<m;i++)
{
scanf("%d",&b[i]);
}
for(i=0;;)
{
if(a[i]+b[m-1]==k)
{
cout<<"yes";
break;
}
if(a[i]+b[m-1]<k)
{
i++;
}
if(a[i]+b[m-1]>k)
{
m--;
}
if(m==0||i==n)
{
cout<<"no";
break;
}
}
return 0;
}和其他人交流思想的确可以学到很多东西，我的第二题的思路就只停留在lower_bound()，时间复杂度的确比两个指针的更慢。