华为机试题——函数调用栈【java实现】

题目描述

栈区（stack)，由编译器自动分配和释放，存放函数的参数值，局部变量的值等。

操作方式类似于数据结构中的栈。函数调用链栈总和为调用链中各个函数栈大小的总和，

例如：入口函数A，分配100个字节的栈空间，A调用函数B，B分配50个字节的栈空间， B调用函数C，C分配120个字节的栈空间，则A->B->C函数调用链的栈总和为

100+50+120=270。

输入描述

 




输入
 
输入内容描述：
第1行：调用关系总组数n 第1组被调函数个数 第2组被调函数个数 ... 第n组被调函数个数
第2行：调用函数1 函数1栈大小  被调函数1...被调函数m
...
第n+1行：调用函数n 函数n栈大小  被调函数1...被调函数k
最多100行
5 2 3 1 0 0  //5组调用 第一组调用2个函数，第二组调用3个函数，第三组调用1个函数，第五组无函数调用，第四组无函数调用
1 20 2 3     //函数1，栈大小为20，调用函数2、3
2 30 3 4 5   //函数2，栈大小为30，调用函数3、4、5
3 50 4
4 60
5 80

输出描述：

 
所有调用链中栈总和的最大值，注意输入之中的入口函数可能不唯一，比如可能存在1调用函数2、3,5调用6,6调用7，则有
1->2，1->3，5->6->7三个调用链，有两个入口函数1和5。
所有调用链中只要存在一个递归调用（即直接或间接调用自己，比如1->2->3->1即为递归调用，则输出R
如果调用链中有函数未给出调用栈大小，则输出NA

示例1

输入

输出

160

说明

- 函数调用链：
- 1->2->3->4 调用链栈总和为20+30+50+60=160
- 1->2->4 调用链栈总和为20+30+60=110
- 1->2->5 调用链栈总和为20+30+80=130
- 1->3->4 调用链栈总和为20+50+60=130
- 所有调用链中 栈总和最大的是1->2->3->4，最大值为160，所以输出为160

代码实现：

import java.util.*;

/**
 * Author: chaoyou
 * CSDN：https://blog.csdn.net/qq_41910568
 * Date: 23:15 2021/12/2
 * Content：
 */
public class 函数调用栈 {

    /**
     *题目描述
     *
     * 栈区（stack)，由编译器自动分配和释放，存放函数的参数值，局部变量的值等。
     *
     * 操作方式类似于数据结构中的栈。函数调用链栈总和为调用链中各个函数栈大小的总和，
     *
     * 例如：入口函数A，分配100个字节的栈空间，A调用函数B，B分配50个字节的栈空间， B调用函数C，C分配120个字节的栈空间，则A->B->C函数调用链的栈总和为
     *
     * 100+50+120=270。
     *
     * 输入描述
     *
     * 输入
     *
     * 输入内容描述：
     * 第1行：调用关系总组数n 第1组被调函数个数 第2组被调函数个数 ... 第n组被调函数个数
     * 第2行：调用函数1 函数1栈大小  被调函数1...被调函数m
     * ...
     * 第n+1行：调用函数n 函数n栈大小  被调函数1...被调函数k
     * 最多100行
     * 5 2 3 1 0 0  //5组调用 第一组调用2个函数，第二组调用3个函数，第三组调用1个函数，第五组无函数调用，第四组无函数调用
     * 1 20 2 3     //函数1，栈大小为20，调用函数2、3
     * 2 30 3 4 5   //函数2，栈大小为30，调用函数3、4、5
     * 3 50 4
     * 4 60
     * 5 80
     * 输出描述：
     *
     * 1.所有调用链中栈总和的最大值，注意输入之中的入口函数可能不唯一，比如可能存在1调用函数2、3,5调用6,6调用7，则有
     * 1->2，1->3，5->6->7三个调用链，有两个入口函数1和5。
     * 2.所有调用链中只要存在一个递归调用（即直接或间接调用自己，比如1->2->3->1即为递归调用，则输出R
     * 3.如果调用链中有函数未给出调用栈大小，则输出NA
     *
     * 示例1
     *
     * 输入
     * 5 2 3 1 0 0
     * 1 20 2 3
     * 2 30 3 4 5
     * 3 50 4
     * 4 60
     * 5 80
     *
     * 输出
     * 160
     *
     * 说明
     *
     * - 函数调用链：
     * - 1->2->3->4 调用链栈总和为20+30+50+60=160
     * - 1->2->4 调用链栈总和为20+30+60=110
     * - 1->2->5 调用链栈总和为20+30+80=130
     * - 1->3->4 调用链栈总和为20+50+60=130
     * - 所有调用链中 栈总和最大的是1->2->3->4，最大值为160，所以输出为160
     *
     * 解题思路：
     *     1、先把所有函数栈构造成一棵多杈树
     *     1.1、每个节点保存三个变量：字节大小、函数编号、子节点列表
     *     2、利用递归的方式深度遍历多杈树的每一条路径
     *     2.1、每到一条路径都要累加这个节点的字节大小
     *     2.2、每条路径走到叶子节点结束(即递归出口)
     *     2.3、用一个list收集字节节点的字节累加值
     *     3、倒叙list取第一个值作为结果返回
     *
     * @param strArr
     * @return
     */

    public static String tree(List<String> strArr){
        if (null == strArr || strArr.size() < 1){
            return "NA";
        }
        // 获取函数组信息
        String one = strArr.get(0);
        String[] ones = one.split(" ");
        int methods = Integer.parseInt(ones[0]);

        /**
         * 构造多杈树
         */
        // 第一步：先构造出所有节点的信息：函数编号、子节大小
        Map<String, Map<String, Object>> nodeMap = new HashMap<>();
        for (int i=1; i<=methods; i++){
            Map<String, Object> node = new HashMap<>();
            String temp = strArr.get(i);
            String[] tempList = temp.split(" ");
            if (tempList.length < 2){
                return "NA";
            }
            node.put("methodNo", tempList[0]);
            node.put("byte", tempList[1]);
            nodeMap.put(i+"", node);
        }

        // 开始构造树：把完善各个节点的孩子节点逻辑
        String root = "";
        for (int i=1; i<=methods; i++){
            String temp = strArr.get(i);
            String[] tempList = temp.split(" ");
            if (i == 1){
                // 初始化根节点函数编号
                root = tempList[0];
            }
            // 根据指定的函数编号取出该节点
            Map<String, Object> node = nodeMap.get(tempList[0]);

            // 初始化子节点列表
            List<Map<String, Object>> sunList = new ArrayList<>();
            for (int j=2; j<tempList.length; j++){
                Map<String, Object> sunNode = nodeMap.get(tempList[j]);
                sunList.add(sunNode);
            }
            // 子节点列表关联上父节点
            node.put("sunList", sunList);
            nodeMap.put(i+"", node);
        }
        List<Long> resultList = new ArrayList<>();
        recursion(nodeMap.get(root), 0, resultList);
        resultList.sort(new Comparator<Long>() {
            @Override
            public int compare(Long o1, Long o2) {
                return o2.compareTo(o1);
            }
        });
        System.out.println(resultList);
        return resultList.get(0)+"";
    }

    /**
     * 递归方式深度遍历多杈树
     * @param treeMap
     * @param bytes
     * @param result
     */
    public static void recursion(Map<String, Object> treeMap, long bytes, List<Long> result){
        if (null == treeMap || treeMap.isEmpty() || null == result){
            return;
        }
        // 获取子节点列表
        List<Map<String, Object>> sunList = (List<Map<String, Object>>) treeMap.get("sunList");
        // 获取当前节点的字节大小，并且进行累加
        bytes += Long.parseLong(treeMap.get("byte")+"");

        // 判断当前节点是否为叶子节点
        if (sunList.size() < 1){
            // 如果是叶子节点则保存该路径的字节累加值
            result.add(bytes);
            // 递归出口
            return;
        }

        // 递归进入子节点
        for (Map<String, Object> sunNode: sunList){
            recursion(sunNode, bytes, result);
        }
    }

    public static void main(String[] args) {
        List<String> data = new ArrayList<>();
        data.add("5 2 3 1 0 0");
        data.add("1 20 2 3");
        data.add("2 30 3 4 5");
        data.add("3 50 4");
        data.add("4 60");
        data.add("5 80");
        String tree = tree(data);
        System.out.println(tree);
    }
}