首页 > 字节跳动06月20号 ES部门笔试
头像
秃秃秃
编辑于 2020-06-23 14:38
+ 关注

字节跳动06月20号 ES部门笔试

字节跳动06月20号 ES部门笔试  第五题猜数游戏: n个棋子(相当于n个坐标点) 是否存在x=a 或者 y=b直线  使所有的坐标点位于这俩直线上(满足一条直线就行)
用的回溯法 , 笔试时候AC80%
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

//判断这个a b值是否满足条件1
bool is_valid(int a,int b,vector<vector<int> > &points)
{
    int n = points.size();
    for(int i=0;i<n;i++)
    {
        if(points[i][0]!=a && points[i][1]!=b)
        {
            return false;
        }
    }
    return true;
}
//回溯  递归
void helper(int x,int y,vector<vector<int> > &res,int &n,vector<vector<int> > &points)
{
    if(x>=n || y>=n)
    {
        return;
    }
    if(is_valid(points[x][0],points[y][1],points))
    {
        vector<int> temp0;
        temp0.push_back(points[x][0]);
        temp0.push_back(points[y][1]);
        res.push_back(temp0);
        helper(x,y+1,res,n,points);
        //return;
    }
    else
    {
        helper(x,y+1,res,n,points);
    }
    return;
}
// 对满足条件的 a  b 进行排序 选出  a*1000+b最小的
bool cmp(const vector<int>& a,const vector<int>& b)
{
    return a[2] < b[2];
}
int main()
{
    int n;
    cin>>n;
    vector<vector<int> >points(n,vector<int>(2,0));
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<2;j++)
        {
            cin>>points[i][j];
            if (cin.peek() == ',')     
			{
				cin.get();               
			}
			if (cin.peek() == '\n')       
			{
				break;
			}
        }
    }
    vector<vector<int> > res;
    for(int i=0;i<n;i++)
    {
        helper(i,0,res,n,points);

    }
    if(res.empty())
    {
        cout<<-1<<','<<" "<< -1<<endl;
        return 0;
    }
    for(int i=0;i<res.size();i++)
    {
        int min_val = res[i][0]*1000+res[i][1];
        res[i].push_back(min_val);
    }
    sort(res.begin(),res.end(),cmp);
    cout<<res[0][0]<<','<<" "<<res[0][1]<<endl;
    return 0;

}



全部评论

(4) 回帖
加载中...
话题 回帖

推荐话题

相关热帖

历年真题 真题热练榜 24小时
技术(软件)/信息技术类
查看全部

近期精华帖

热门推荐