字节跳动ZJ13->最大点集

最大点集

http://www.nowcoder.com/questionTerminal/089dbc5ec7ac468589ce143d43248949

1. 思路

  1. 想法是反向思考 把不符合条件的都去掉就好了,emmm但是不太好整(原思路:找出最大的x,将y小于他的全部去掉。然后找出y最大的,再将x<他的全去掉)emmmm跑出来发现不中 哈哈哈,但是这边结构体和sort排序挺好的
  2. 排序用法:自己指定一个比较函数。通过sort的第三个参数传进去。

2.初级代码

#include <bits/stdc++.h>
using namespace std;

    struct P{
        int x=0, y=0,flag=1;

    }; 
    bool comparex(const P &a, const P &b) {//让x从小到大排序 
        return a.x < b.x;
    }
     bool comparey(const P &a, const P &b) {//让x从小到大排序 
        return a.y < b.y;
    }
    int main(){
    int n, x, y, Max=0;
    scanf("%d", &n);
    P p[n];
    for(int i=0;i<n;i++)
        cin>> p[i].x>> p[i].y;
    sort(p, p+n,comparey);//x 
    for(int i=0;i<n-1;i++){
        if(p[i].x < p[n-1].x)
            p[i].flag=0;
    }
        sort(p, p+n,comparex);//x 
    for(int i=0;i<n-1;i++){
        if(p[i].y < p[n-1].y)
            p[i].flag=0;
    }
    for(int i=0;i<n-1;i++){
        if(p[i].flag==1)
            cout<<p[i].x<<" "<<p[i].y<<endl;
    }
    return 0;
}

3. 正解参考

1) 思路是先将y从大到小排序
2) y定好了之后,由于y牟定了高度,只要下一个x不比出现过的x小就绝对没问题,所以设立一个Max=0;进行控制。而且也能使x递增。非常好用。

#include <bits/stdc++.h>
using namespace std;
    struct P{
        int x=0, y=0;

    }; 
     bool comparey(const P &a, const P &b) {//让y从大到小排序 
        return a.y > b.y;
    }
    int main(){
    int n, x, y, Max=0;
    cin>>n;
    P p[n];
    for(int i=0;i<n;i++)
        cin>> p[i].x>> p[i].y;
    sort(p, p+n,comparey);//x 
    for(int i=0;i<n;i++){
            if(p[i].x>Max){
                Max=p[i].x;
                cout<<p[i].x<<" "<<p[i].y<<endl;
            }
        }
        return 0;
    }


全部评论

相关推荐

東大沒有派對:这是好事啊(峰哥脸
我的秋招日记
点赞 评论 收藏
分享
10-19 10:28
已编辑
成都理工大学 后端工程师
团孝子已上线feeling:面了很多家公司,能感受到目前只有小公司+外包喜欢问八股。大厂虽然也问八股,但是是从实习、项目中进行提问,并且大厂会问很深,面试官也会对你的回答进行思考➕追问,所以准备大厂面试前一定要备好相关资料。对于算法,我做的是codetop前100+力扣hot100+力扣高频150,面试中实感hot100就足够,基本上只要是hot100就秒答。对于项目和八股,我做的也是烂大街的星球项目,八股则是看小林和问ai,自己也写了很多技术博客和画了很多思维导图,并且自己也尝试用嘴巴说出来,不只停留于纸面。运气也很重要,必须要让面试官/HR看到简历才行,所以建议投递时间是下午两点。tl:第一岗位9.9&nbsp;投递9.10&nbsp;一面(一面评价:最近见过最强的大三,结束五分钟后约二面,都晚上九点了不下班吗)9.11&nbsp;二面(三道算法a出两道,反问评价:经验不够等横向,我实习生要啥经验)9.21挂(实习时间过短+其他原因,想要一年实习的,为什么不招个正职)第二岗位10.10投递10.11约面(主管打电话,说看到我之前投递记录了想要我挂qa职进去干后端,同意)10.14&nbsp;一面(无八股,主动说确实很强,意愿很强)10.16&nbsp;oc其余,友邦,东软,东华,惠择,用友oc已拒京东测开一面挂(投后端被测开捞)腾讯测试已拒(投后端被测开捞)ps:表扬惠择的主管面,没怎么问技术(可能是一面面试官沟通过了),全程一起讲大道理,解答了心中很多疑惑,也告诉我以面试官角度来看怎么选候选人,如果可以下次一定选惠择
HeaoDng:美团好像可以触发一面通
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务