2018秋招-阿裡内推程式設計題

阿裡巴巴的ODPS大資料處理平台可以啟動一系列并發的作業，每個作業中存在一系列存在父子關系的任務。每個任務用一個三元組表示–（任務id，父任務id，執行開銷），其中任務id是一個正整數（>0）；父任務id為0表示根任務，每個作業存在一個唯一的根任務，并且所有的任務，如果其父任務id不為0，那麼必然是一個已經存在的根任務id；執行開銷是一個正整數（>0）。系統中至少存在一個作業。

舉例如下：

(1, 0, 2) (2, 0, 3) (3, 1, 2) (4, 1, 3)

對應的任務關系是：

1(2) 2(3)

/ \

3(2) 4(3)

注：括号内的數字表示任務開銷。

很容易看出來，這些任務樹構成了一個森林。每顆任務樹有若幹個葉子節點，從根節點到葉子結點的路徑上所有的執行開銷，稱作葉子節點對應任務的總開銷。例如上面一共有3個葉子節點任務，分别是任務3, 4和2，對應的總開銷分别是4, 5和3。總開銷最大的葉子節點任務是4，對應的總開銷是5。

現在需要編寫程式，針對輸入的任務資料，找到總開銷最大的葉子節點任務對應的總開銷，比如針對上面例子，輸出5。

示例輸入：

1 0 2

2 0 3

3 1 2

4 1 3

示例輸出：

5

//定義樹的結點
class TreeNode{
    private Integer id;
    private Integer parentId;
    private int cost;
    private Map<Integer,TreeNode> childs = new HashMap<Integer,TreeNode>();//存放所有子結點 <子結點Id，子結點>
    public Integer getId() {
        return id;
    }
    public void setId(Integer id) {
        this.id = id;
    }
    public Integer getParentId() {
        return parentId;
    }
    public void setParentId(Integer parentId) {
        this.parentId = parentId;
    }
    public int getCost() {
        return cost;
    }
    public void setCost(int cost) {
        this.cost = cost;
    }
    public Map<Integer, TreeNode> getChilds() {
        return childs;
    }
    public void setChilds(Map<Integer, TreeNode> childs) {
        this.childs = childs;
    }
}


public class Main{


    public static void main(String[] args) {

        ArrayList<Integer> _ids = new ArrayList<Integer>();
        ArrayList<Integer> _parents = new ArrayList<Integer>();
        ArrayList<Integer> _costs = new ArrayList<Integer>();

        Scanner in = new Scanner(System.in);
        String line = in.nextLine();

        while(line != null && !line.isEmpty()) {
            if(line.trim().equals("0")) break;
            String []values = line.trim().split(" ");
            if(values.length != ) {
                break;
            }
            _ids.add(Integer.parseInt(values[]));
            _parents.add(Integer.parseInt(values[]));
            _costs.add(Integer.parseInt(values[]));
            line = in.nextLine();
        }
        int res = resolve(_ids, _parents, _costs);

        System.out.println(String.valueOf(res));
    }

         // write your code here
    public static int resolve(ArrayList<Integer> ids, ArrayList<Integer> parents, ArrayList<Integer> costs) {
        TreeNode root = creatTree(ids, parents, costs);
        IteratorTree(root, );

        //擷取ArrayList中最大值
        int max = pathValueList.get();
        for(int i = ; i < pathValueList.size(); i++){
            if(pathValueList.get(i) > max){
                max = pathValueList.get(i);
            }
        }
        return max;
    }

  //建構一棵多叉樹
    public static TreeNode creatTree(ArrayList<Integer> ids, ArrayList<Integer> parents, ArrayList<Integer> costs){
        //建立根節點
        TreeNode root = new TreeNode();
        Map<Integer, TreeNode> maps = new HashMap<Integer, TreeNode>();
        //周遊所有結點資訊，将所有結點相關資訊放入maps中
        for(int i = ; i < ids.size(); i++){
            TreeNode node = new TreeNode();
            node.setId(ids.get(i));
            node.setParentId(parents.get(i));
            node.setCost(costs.get(i));
            maps.put(ids.get(i), node);
        }
        //周遊map，将父結點為0的結點放到根結點下，否則在相應父節點下添加子結點
        for(Map.Entry<Integer, TreeNode> entry : maps.entrySet()){
            TreeNode node = entry.getValue();
            Integer partentId = node.getParentId();
            if(partentId == ){
                root.getChilds().put(node.getId(), node);//node.getId()等價于node.getKey()
            }else{
                TreeNode pNode = maps.get(partentId);
                pNode.getChilds().put(node.getId(), node);
            }
        }
        return root;
    }

    //周遊多叉樹，尋找最優解
    private static List<Integer> pathValueList = new ArrayList<Integer>();
    public static void IteratorTree(TreeNode root, int sum){

        int tmp = sum;
        if(root != null){
            for(Map.Entry<Integer, TreeNode> entry : root.getChilds().entrySet()){

                sum = tmp;
                sum += entry.getValue().getCost();

                if(entry.getValue().getChilds() != null && entry.getValue().getChilds().size() > ){
                    IteratorTree(entry.getValue(), sum);
                }else{
                    pathValueList.add(sum);//周遊完一條路徑，将這條路徑和記錄下來
                }
            }
        }
    }

}
           

如有錯誤，歡迎指正！