NC333. 加分二叉树
描述
设一个n个节点的二叉树tree的中序遍历为（l,2,3,…,n），其中数字1,2,3,…,n为节点编号。每个节点都有一个分数（均为正整数），记第j个节点的分数为di，tree及它的每个子树都有一个加分，任一棵子树subtree（也包含tree本身）的加分计算方法如下：
subtree的左子树的加分× subtree的右子树的加分＋subtree的根的分数
（1）tree的最高加分
示例1
输入:
[5,7,1,2,10]
输出:
[[145],[3,1,2,4,5]]
C 解法, 执行用时: 4ms, 内存消耗: 412KB, 提交时间: 2022-06-23
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param scores int整型一维数组
* @param scoresLen int scores数组长度
* @return int整型二维数组
* @return int* returnSize 返回数组行数
* @return int** returnColumnSizes 返回数组列数
*
* C语言声明定义全局变量请加上static，防止重复定义
*/
#include <stdio.h>
#include <stdbool.h>
void printPreOrder(int start, int end, int **select, int *result, int *resultLen) {
if (start <= end) {
int v = select[start][end];
result[(*resultLen)++] = v;
printPreOrder(start, v-1, select, result, resultLen);
printPreOrder(v+1, end, select, result, resultLen);
}
}
int** scoreTree(int* scores, int scoresLen, int* returnSize, int** returnColumnSizes ) {
int n = scoresLen;
int nums[n];
for(int i = 0; i < n; i++) {
nums[i] = scores[i];
}
int **dp = (int **)malloc(sizeof(int *) * (n + 1));
int **select = (int **)malloc(sizeof(int *) * (n + 1));
for (int i = 0; i < n + 1; i++) {
dp[i] = (int *)malloc(sizeof(int) * (n + 1));
select[i] = (int *)malloc(sizeof(int) * (n + 1));
dp[i][i] = nums[i-1];
select[i][i] = i;
}
int maxDp, maxDpIndex, left, right, total;
for (int d = 1; d < n; d++) {
for (int i = 1; i <= n - d; i++) {
maxDp = 0;
maxDpIndex = 0;
for (int k = i; k <= i + d; k++) {
if (k == i) {
left = 1;
} else {
left = dp[i][k-1];
}
if (k == i + d) {
right = 1;
} else {
right = dp[k+1][i+d];
}
total = nums[k-1] + left * right;
if (total > maxDp) {
maxDp = total;
maxDpIndex = k;
}
}
dp[i][i+d] = maxDp;
select[i][i+d] = maxDpIndex;
}
}
*returnSize = 2;
int **result = (int **)malloc(sizeof(int *) * 2);
*returnColumnSizes = (int *)malloc(sizeof(int) * 2);
(*returnColumnSizes)[0] = 1;
int *maxScore = (int *)malloc(sizeof(int));
maxScore[0] = dp[1][n];
result[0] = maxScore;
int *preOrder = (int *)malloc(sizeof(int) * n);
int preOrderLen = 0;
printPreOrder(1, n, select, preOrder, &preOrderLen);
result[1] = preOrder;
(*returnColumnSizes)[1] = preOrderLen;
for (int i = 0; i < n + 1; i++) {
free(dp[i]);
free(select[i]);
}
free(dp);
free(select);
return result;
}
C 解法, 执行用时: 5ms, 内存消耗: 424KB, 提交时间: 2022-06-24
void printPreOrder(int start, int end, int** select, int* result,
int* resultLen) {
if (start <= end) {
int v = select[start][end];
result[(*resultLen)++] = v;
printPreOrder(start, v - 1, select, result, resultLen);
printPreOrder(v + 1, end, select, result, resultLen);
}
}
int** scoreTree(int* scores, int scoresLen, int* returnSize,
int** returnColumnSizes ) {
int n = scoresLen;
int nums[n];
for (int i = 0; i < n; i++) {
nums[i] = scores[i];
}
int** dp = (int**)malloc(sizeof(int*) * (n + 1));
int** select = (int**)malloc(sizeof(int*) * (n + 1));
for (int i = 0; i < n + 1; i++) {
dp[i] = (int*)malloc(sizeof(int) * (n + 1));
select[i] = (int*)malloc(sizeof(int) * (n + 1));
dp[i][i] = nums[i - 1];
select[i][i] = i;
}
int maxDp, maxDpIndex, left, right, total;
for (int d = 1; d < n; d++) {
for (int i = 1; i <= n - d; i++) {
maxDp = 0;
maxDpIndex = 0;
for (int k = i; k <= i + d; k++) {
if (k == i) {
left = 1;
} else {
left = dp[i][k - 1];
}
if (k == i + d) {
right = 1;
} else {
right = dp[k + 1][i + d];
}
total = nums[k - 1] + left * right;
if (total > maxDp) {
maxDp = total;
maxDpIndex = k;
}
}
dp[i][i + d] = maxDp;
select[i][i + d] = maxDpIndex;
}
}
*returnSize = 2;
int** result = (int**)malloc(sizeof(int*) * 2);
*returnColumnSizes = (int*)malloc(sizeof(int) * 2);
(*returnColumnSizes)[0] = 1;
int* maxScore = (int*)malloc(sizeof(int));
maxScore[0] = dp[1][n];
result[0] = maxScore;
int* preOrder = (int*)malloc(sizeof(int) * n);
int preOrderLen = 0;
printPreOrder(1, n, select, preOrder, &preOrderLen);
result[1] = preOrder;
(*returnColumnSizes)[1] = preOrderLen;
for (int i = 0; i < n + 1; i++) {
free(dp[i]);
free(select[i]);
}
free(dp);
free(select);
return result;
}
Java 解法, 执行用时: 20ms, 内存消耗: 9800KB, 提交时间: 2022-06-24
import java.util.*;
public class Solution {
public ArrayList<ArrayList<Integer>> scoreTree (ArrayList<Integer> scores) {
ArrayList<ArrayList<Integer>> scoreTree = new ArrayList<>();
int[][] d = new int[scores.size() + 1][scores.size() + 1];
int[][] head = new int[scores.size() + 1][scores.size() + 1];
for (int h = 0; h < scores.size(); h++) {
for (int i = 1; i <= scores.size(); i++) {
int left = i;
int right = i + h;
if (i + h > scores.size()) {
break;
}
int max = 0;
for (int j = left; j <= right; j++) {
int sum;
int leftValue = (j - 1 < left) ? 1 : d[left][j - 1];
int rightValue = (j + 1 > right) ? 1 : d[j + 1][right];
if ((j - 1 < left) && (j + 1 > right)) {
sum = scores.get(j - 1);
} else {
sum = scores.get(j - 1) + leftValue * rightValue;
}
if (sum > max) {
head[left][right] = j;
max = sum;
}
}
d[left][right] = max;
}
}
Recursion(head, 1, scores.size());
ArrayList<Integer> y = new ArrayList<>();
y.add(d[1][scores.size()]);
scoreTree.add(y);
scoreTree.add(x);
return scoreTree;
}
ArrayList<Integer> x = new ArrayList<>();
public void Recursion(int[][] head, int left, int right) {
if (left > right) {
return;
}
x.add(head[left][right]);
Recursion(head, left, head[left][right] - 1);
Recursion(head, head[left][right] + 1, right);
}
}
Java 解法, 执行用时: 20ms, 内存消耗: 9868KB, 提交时间: 2022-06-29
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param scores int整型ArrayList
* @return int整型ArrayList<ArrayList<>>
*/
ArrayList<Integer> list = new ArrayList<>();
public ArrayList<ArrayList<Integer>> scoreTree (ArrayList<Integer> scores) {
// write code here
int n = scores.size();
int[][] dp = new int[n][n];
int max_score = 0;
for(int i = n-1;i>=0;i--){
dp[i][i] = scores.get(i);
max_score = Math.max(max_score,dp[i][i]);
for(int j=i+1;j<n;j++){
for(int k=i;k<=j;k++){
if(k==i){
dp[i][j] = Math.max(dp[i][j],scores.get(k)+dp[k+1][j]);
}else if(k==j){
dp[i][j] = Math.max(dp[i][j],dp[i][k-1]+scores.get(k));
}else {
dp[i][j] = Math.max(dp[i][j],dp[i][k-1]*dp[k+1][j]+scores.get(k));
}
max_score = Math.max(max_score,dp[i][j]);
}
}
}
// for(int i=0;i<dp.length;i++) System.out.println(Arrays.toString(dp[i]));
getRes(dp,0,n-1,0);
ArrayList<ArrayList<Integer>> res = new ArrayList<>();
ArrayList<Integer> temp = new ArrayList<>();
temp.add(max_score);
res.add(temp);
res.add(list);
return res;
}
public void getRes(int[][] dp,int x,int y_max,int y_min){
if(y_max-y_min<0||list.size()==dp.length) return;
if(y_max==y_min) {
list.add(y_max+1);
return;
}
int index = y_min;
for(int i=y_min;i<=y_max;i++) {
if ((i==y_min&&dp[i+1][y_max]+dp[i][i]==dp[x][y_max])||
(i==y_max&&dp[x][i-1]+dp[i][i]==dp[x][y_max])||
(i>y_min&& i<y_max&& dp[x][i-1]*dp[i+1][y_max]+dp[i][i]==dp[x][y_max])){
index = i;
break;
}
}
list.add(index+1);
getRes(dp,x,index-1,y_min);
getRes(dp,index+1,y_max,index+1);
}
}
Java 解法, 执行用时: 20ms, 内存消耗: 11224KB, 提交时间: 2022-05-09
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param scores int整型ArrayList
* @return int整型ArrayList<ArrayList<>>
*/
public ArrayList<ArrayList<Integer>> scoreTree (ArrayList<Integer> scores) {
// write code here
ArrayList<ArrayList<Integer>> scoreTree = new ArrayList<>();
int[][] ints = new int[scores.size()+1][scores.size()+1];
int[][] head = new int[scores.size()+1][scores.size()+1];
for(int length = 0;length<scores.size();length++){
for(int i=1;i<=scores.size();i++){
int left = i;
int right = i+length;
if(i+length>scores.size()){
break;
}
int max = 0;
for(int j=left;j<=right;j++){
int sum;
int leftValue = (j-1<left)?1:ints[left][j-1];
int rightValue = (j+1>right)?1:ints[j+1][right];
if((j-1<left)&&(j+1>right)){
sum = scores.get(j-1);
}else {
sum = scores.get(j-1)+leftValue*rightValue;
}
if(sum>max){
head[left][right] = j;
max=sum;
}
}
ints[left][right] = max;
}
}
digui(head,1,scores.size());
ArrayList<Integer> integers1 = new ArrayList<>();
integers1.add(ints[1][scores.size()]);
scoreTree.add(integers1);
scoreTree.add(integers);
return scoreTree;
}
ArrayList<Integer> integers = new ArrayList<>();
public void digui(int[][] head,int left,int right){
if(left>right){
return;
}
integers.add(head[left][right]);
digui(head,left,head[left][right]-1);
digui(head,head[left][right]+1,right);
}
}