题目描述
栈区（stack)，由编译器自动分配和释放，存放函数的参数值，局部变量的值等。
操作方式类似于数据结构中的栈。函数调用链栈总和为调用链中各个函数栈大小的总和，
例如：入口函数A，分配100个字节的栈空间，A调用函数B，B分配50个字节的栈空间， B调用函数C，C分配120个字节的栈空间，则A->B->C函数调用链的栈总和为
100+50+120=270。
输入描述
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
输入
输入内容描述：
第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 4 |
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
输入
| 1 2 3 4 5 6 |
5 2 3 1 0 0
1 20 2 3
2 30 3 4 5
3 50 4
4 60
5 80
|
输出
| 1 |
160
|
说明
| 1 2 3 4 5 6 |
- 函数调用链：
- 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);
}
}