【c++笔试强训】（第四十一篇）
目录
体操队形（DFS+枚举）
题目解析
讲解算法原理
编写代码
⼆叉树中的最⼤路径和（树形dp）
题目解析
讲解算法原理
编写代码
体操队形（DFS+枚举）
题目解析
1.题目链接：登录—专业IT笔试面试备考平台_牛客网
2.题目描述
题目描述
dddddd作为体操队队长，在给队员们排队形，体操队形为一个单独的纵列，体操队有nnn个同学，标号为1∼n1\sim n1∼n，对于i(1≤i≤n)i(1≤i≤n)i(1≤i≤n)号队员，会有一个诉求(1≤a[i]≤n)(1≤a[i]≤n)(1≤a[i]≤n)，表示他想排在a[i]a[i]a[i]号队员前面，当a[i]=ia[i]=ia[i]=i时，我们认为他没有位置需求，随便排哪儿都行，dddddd想知道有多少种队形方案，可以满足所有队员的要求。
输入描述:
读入第一行一个数字n(2≤n≤10)
第二行n个数字，表示a[i],保证1≤a[i]≤n输出描述:
输出一行，表示方案数
示例1
输入
3 1 1 2
3
1 1 2输出
1
1
讲解算法原理
解法：
算法思路：
画出决策树，注意剪枝策略~
编写代码
c++算法代码：
#include <iostream>
using namespace std;
const int N = 15;
int ret;
int n;
bool vis[N];
int arr[N];
void dfs(int pos)
{
if(pos == n + 1) // 找到⼀种合法⽅案 {
ret++;
return;
}
for(int i = 1; i <= n; i++)
{
if(vis[i]) continue; // 当前 i 已经放过了 - 剪枝
if(vis[arr[i]]) return; // 剪枝
vis[i] = true; // 相当于放上 i 号队员 dfs(pos + 1);
vis[i] = false; // 回溯- 还原现场 }
}
int main()
{
cin >> n;
for(int i = 1; i <= n; i++) cin >> arr[i];
dfs(1);
cout << ret << endl;
return 0;
}java算法代码：
mport java.util.*;
public class Main
{
public static int N = 15; public static int n, ret; public static boolean[] vis = new boolean[N]; public static int[] arr = new int[N]; public static void dfs(int pos) {
if(pos == n + 1) // 找到⼀种合法情况 {
ret++;
return;
}
for(int i = 1; i <= n; i++)
{
if(vis[i] == true) continue; // 剪枝 - i 号队员已经放过了
if(vis[arr[i]]) return; // 剪枝
vis[i] = true; // 相当于已经放上 i 号队员 dfs(pos + 1);
vis[i] = false; // 回溯 - 恢复现场 } }
public static void main(String[] args)
{
Scanner in = new Scanner(System.in); n = in.nextInt(); for(int i = 1; i <= n; i++)
{
arr[i] = in.nextInt();
}
dfs(1);
System.out.println(ret);
}
}⼆叉树中的最⼤路径和（树形dp）
题目解析
1.题目链接：二叉树中的最大路径和_牛客题霸_牛客网
2.题目描述
描述
二叉树里面的路径被定义为:从该树的任意节点出发，经过父=>子或者子=>父的连接，达到任意节点的序列。
注意:
1.同一个节点在一条二叉树路径里中最多出现一次
2.一条路径至少包含一个节点，且不一定经过根节点
给定一个二叉树的根节点root，请你计算它的最大路径和
例如：
给出以下的二叉树，
最优路径是:2=>1=>3，或者3=>1=>2，最大路径和=2+1+3=6数据范围：节点数满足 1 \le n \le 10^51≤n≤105 ，节点上的值满足 |val| \le 1000∣val∣≤1000
要求：空间复杂度 O(1)O(1)，时间复杂度 O(n)O(n)
示例1
输入：
{1,2,3}
复制返回值：
6
复制
示例2
输入：
{-20,8,20,#,#,15,6}
复制返回值：
41
复制说明：
其中一条最大路径为:15=>20=>6，路径和为15+20+6=41
示例3
输入：
{-2,#,-3}
返回值：
-2
讲解算法原理
解法：
算法思路：
树形dp：
a. 左⼦树收集：以左⼦树为起点的最⼤单链和；b. 右⼦树收集：以右⼦树为起点的最⼤单链和；
c. 根节点要做的事情：整合左右⼦树的信息，得到经过根节点的最⼤路径和；
d. 向上返回：以根节点为起点的最⼤单链和
编写代码
c++算法代码：
class Solution
{
public:
int ret = -1010;
int maxPathSum(TreeNode* root)
{
dfs(root);
return ret;
}
int dfs(TreeNode* root)
{
if(root == nullptr) return 0;
int l = max(0, dfs(root->left));// 左⼦树的最⼤单链和 int r = max(0, dfs(root->right)); // 右⼦树的最⼤单链和 // 经过root的最⼤路径和
ret = max(ret, root->val + l + r);
return root->val + max(l, r);
}
};java算法代码：
import java.util.*;
/*
* public class TreeNode {
* int val = 0;
* TreeNode left = null;
* TreeNode right = null;
* public TreeNode(int val) {
* this.val = val;
* }
* }
*/
public class Solution
{
int ret = -1010;
public int maxPathSum (TreeNode root)
{
dfs(root);
return ret;
}
int dfs(TreeNode root)
{
if(root == null) return 0;
int l = Math.max(0, dfs(root.left)); // 左⼦树为根的最⼤单链和 int r = Math.max(0, dfs(root.right)); // 右⼦树为根的最⼤单链和 // 经过root的最⼤路径和
ret = Math.max(ret, root.val + l + r);
return root.val + Math.max(l, r);
}
}