首页 > 试题广场 >

比较重量

[编程题]比较重量

热度指数：6293 时间限制：C/C++ 3秒，其他语言6秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

小明陪小红去看钻石，他们从一堆钻石中随机抽取两颗并比较她们的重量。这些钻石的重量各不相同。在他们们比较了一段时间后，它们看中了两颗钻石g1和g2。现在请你根据之前比较的信息判断这两颗钻石的哪颗更重。

给定两颗钻石的编号g1,g2，编号从1开始，同时给定关系数组vector,其中元素为一些二元组，第一个元素为一次比较中较重的钻石的编号，第二个元素为较轻的钻石的编号。最后给定之前的比较次数n。请返回这两颗钻石的关系，若g1更重返回1，g2更重返回-1，无法判断返回0。输入数据保证合法，不会有矛盾情况出现。

测试样例：

2,3,[[1,2],[2,4],[1,3],[4,3]],4

返回: 1

算法知识视频讲解

Java

牛客夯先生

import java.util.*;

public class Cmp {
    public int cmp(int g1, int g2, int[][] records, int n) {
        // write code here
        Map<Integer,List<Integer>> map = create_graph(records,n);
        if(helper(g1,g2,map))//g1重于g2
            return 1;
        else if(helper(g2,g1,map))//g1请g2
            return -1;
        return 0;//无法判断
    }
    public boolean helper(int g1,int g2,Map<Integer,List<Integer>> map){//广度优先遍历，判断是否路径点可达
        if (!map.containsKey(g1))//判断是否存在g1，不存在直接pass
            return false;
        Map<Integer,Integer> flag = new HashMap();//记录是否访问过该点
        Set<Integer> set = map.keySet();
        for (Integer i : set)
            flag.put(i, 0);
        Queue<Integer> queue = new LinkedList();
        queue.offer(g1);
        while(!queue.isEmpty()){
            List<Integer> temp = map.get(queue.poll());
            for(int i=0;i<temp.size();i++){
                if(flag.get(temp.get(i))==null)//不存在该点
                    continue;
                if(temp.get(i)==g2)//可达
                    return true;
                if(flag.get(temp.get(i))==0){
                    flag.replace(temp.get(i),1);
                    queue.offer(temp.get(i));
                }
            }
        }
        return false;
    }
    public Map<Integer,List<Integer>> create_graph(int[][] records,int n){//构建邻接表
        Map<Integer,List<Integer>> map = new HashMap();
        for(int i=0;i<n;i++){
            if(map.containsKey(records[i][0]))
                map.get(records[i][0]).add(records[i][1]);
            else{
                List<Integer> list = new ArrayList();
                list.add(records[i][1]);
                map.put(records[i][0],list);
            }
        }
        return map;
    }
}

发表于 2019-08-21 22:26:50 回复(0)

Java

牛客973398号

 //题目相当于是求有向图中的两个节点的可达性，所以解这个题目分为两步，先构造有向图，再求可达性。
public class Cmp {

     private  boolean reachable = false;

    public int cmp(int g1, int g2, int[][] records, int n) {
        // 生成一个有向图
        HashMap<Integer, List<Integer>> map = generateMap(records, n);
        if (map.isEmpty()) {
            return 0;
        }
        depthSearch(g1, g2, map);
        if (reachable) {
            return 1;
        }
        depthSearch(g2, g1, map);
        if (reachable) {
            return -1;
        }
        return 0;
    }

    private void depthSearch(int g1, int g2, HashMap<Integer, List<Integer>> map) {
        if (!map.containsKey(g1)) {
            reachable = false;
        } else {
            List<Integer> values = map.get(g1);
            for (int value : values) {
                if (g2 == value) {
                    reachable = true;
                    return;
                } else {
                    depthSearch(value, g2, map);
                }
            }

        }
    }

    public HashMap<Integer, List<Integer>> generateMap(int[][] records, int n) {
        HashMap<Integer, List<Integer>> map = new HashMap<>();
        for (int i = 0; i < n; i++) {
            int key = records[i][0];
            int value = records[i][1];
            if (map.containsKey(key)) {
                map.get(key).add(value);
            } else {
                List<Integer> list = new ArrayList<>();
                list.add(value);
                map.put(key, list);
            }
        }
        return map;
    }
  
}

编辑于 2016-08-01 20:19:10 回复(9)