2019杭电计算机复试笔试回忆版_杭州电子科技大学 计算机复试笔试 知乎

1.大家去电影院看电影，总共有n人来看电影，其中年龄不低于18岁的成年人的座位号为奇数，不满18岁的未成年人的座位号为偶数。现在请统计成年人与未成年的数目，以及他们在总人数里的比例。n<=1000。

样例输入：5 2 3 6 7 11

样例输出：3 0.60 2 0.40

#include<cstdio>
using namespace std;
int n,man,child;
double a1,a2;
int main()
{
    while(scanf("%d",&n)!=EOF&&n&&n<=1000)
    {
        man=0,child=0;
        for(int i=0;i<n;i++)
        {
            int m;
            scanf("%d",&m);
            if(m%2!=0)
                man++;
            else
                child++;
        }
        a1=(double)man/n;
        a2=(double)child/n;
        printf("%d %.2f %d %.2f\n",man,a1,child,a2);
    }
    return 0;
}

2.leetcode011

给定 n 个非负整数 a1，a2，...，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

说明：你不能倾斜容器，且 n 的值至少为 2。

图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。

 

示例:

输入: [1,8,6,2,5,4,8,3,7](考试的时候给了数量n，n<=1000)
输出: 49

这题考试的时候没多想直接暴力了 后面看到还有双指针的办法 确实巧妙很多

暴力：时间复杂度高

#include<cstdio>
#include<algorithm>
using namespace std;
int n,a[1001];
int main()
{
        scanf("%d",&n);
        for(int i=0;i<n;i++)
        {
            scanf("%d",&a[i]);
        }
        int v=-1;
        for(int i=0;i<n;i++)
            for(int j=n-1;j>i;j--)
        {
            int temp=min(a[i],a[j]);
            v=max(v,(j-i)*temp);
        }
        printf("%d\n",v);
    return 0;
}

双指针法:

#include<cstdio>
#include<algorithm>
using namespace std;
int n,a[1001];
int main()
{
        scanf("%d",&n);
        for(int i=0;i<n;i++)
        {
            scanf("%d",&a[i]);
        }
        int i=0;
        int j=n-1;
        int v=(n-1)*min(a[i],a[j]);
        while(i<j)
        {
            v=max(v,(j-i)*min(a[i],a[j]));
            if(a[i]<a[j])
                i++;
            else
                j--;
        }
        printf("%d\n",v);
    return 0;
}

4.LeetCode547 Friend Circles 原题为英文

有个班级，里面有N个学生，他们之中有些是朋友有些不是，比如如果A是B的朋友，B是C的朋友，那么A就是C的间接朋友，我们定义所谓的朋友圈就是由直系和间接朋友所组成的群体。N的范围为 [1,200].

例子 1:

输入:

3
1 1 0
1 1 0
0 0 1
输出: 2

解释：第0个和第1个学生是直系朋友，所以记为1个朋友圈。第2个学生他没什么朋友也要算一个朋友圈，所以结果为2.

例子 2:

输入:

3
 1 1 0
 1 1 1
 0 1 1
输出: 1

解释：第0个和第1个学生是直系朋友，第1和第2个也是，所以第0和第2个学生是间接朋友，三个学生都在同个朋友圈里，返回1.

并查集：

#include<cstdio>
#include<cstring>
using namespace std;
int n,map[201][201],pre[201];//pre数组记录朋友圈中心,类比根节点
int find(int x)//找根节点，并路径压缩
{
    int p=x,temp;
    while(x!=pre[x])
        x=pre[x];
    while(p!=x)
    {
        temp=pre[p];
        pre[p]=x;
        p=temp;
    }
    return x;
}
int main()
{
    while(scanf("%d",&n)!=EOF&&n)
    {
    memset(map,0,sizeof(map));//初始化矩阵数组
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
    {
        pre[i]=i;//初始化根节点数组
        scanf("%d",&map[i][j]);
    }
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
        {
            int a,b;
            if(i<j&&map[i][j]==1)//并集
            {
                a=find(i);
                b=find(j);
                if(a!=b)
                    pre[a]=b;
            }
        }
        int cnt=0;
        for(int i=0;i<n;i++)//统计根节点未改变的结点的数目
        {
            if(pre[i]==i)
                cnt++;
        }
        printf("%d\n",cnt);
        return 0;
        }
}

第三题的话因为篇幅长，有很多图，最重要的是我不会，嘿嘿，有点尴尬，就没在这里写出来，如果有大佬知道的话可以留言，我也希望能交流学习一下。

以后我会把之前做过的11页的题目和一些我特意准备过的题目陆续发出来。