当前位置:网站首页>派对的最大快乐值
派对的最大快乐值
2022-07-05 22:50:00 【明朗晨光】
1、题目
员工的信息定义如下:
class Employee {
public int happy; //这名员工可以带来的快乐值
List<Employee> subordinates; //这名员工有哪些直接下级
};
公司的每个员工都符合 Employee
类的描述,整个公司的人员结构可以看做是一棵标准的、没有环的多叉树。树的根节点是公司唯一的老板。除老板之外的每个员工都有唯一的直接上级。叶节点是没有任何下属的基层员工(subordinates
列表为空),除基层员工外,每个员工都有一个或多个直接下级。
这个公司现在要办 party,你可以决定哪些员工来,哪些员工不来,规则:
- 如果某个员工来了,那么这个员工的所有直接下级都不能来;
- 排队的整体快乐值是所有到场员工快乐值的累加;
- 你的目标是让排队的整体快乐值尽量大。
给定一棵多叉树的根节点 boss
,请返回排队的最大快乐值。
2、分析
使用二叉树的递归套路:
①目标:以 X 为根的整棵树获得最大 happy 值
②可能性:
1)X 来的情况:假设 X 的直接下级是 a,b,c,那么快乐值 = X.happy + a 不来的 max + b 不来的max + c不来的max;
2)X 不来的情况:快乐值 = 0 + max{a来,a不来} + max{b来,b不来} + max{c来,c不来}
整理可得,需要向左右子树获得信息是:①节点不来的最大happy值;②节点来的最大happy值。
3、实现
C++ 版
/************************************************************************* > File Name: 042.派对最大快乐值.cpp > Author: Maureen > Mail: [email protected] > Created Time: 二 7/ 5 14:59:05 2022 ************************************************************************/
#include <iostream>
#include <vector>
#include <ctime>
using namespace std;
class Employee {
public:
int happy;
vector<Employee*> subordinates;
Employee(int h) : happy(h) {
}
};
//当前来到的节点叫做cur
//参数up表示cur的上级是否来
//函数的意义:
// up为true, 表示cur的上级确定要来的情况,cur 整棵树能提供的最大happy值
// up为false,表示cur的上级确定不来的情况,cur 整棵树能提供的最大happy值
int process1(Employee *cur, bool up) {
if (up) {
int ans = 0;
for (Employee *next : cur->subordinates) {
ans += process1(next, false);
}
return ans;
} else {
int p1 = cur->happy;
int p2 = 0;
for (Employee *next : cur->subordinates) {
p1 += process1(next, true);
p2 += process1(next, false);
}
return max(p1, p2);
}
}
int maxHappy1(Employee *boss) {
if (boss == nullptr)
return 0;
return process1(boss, false);
}
//方法二:
class Info {
public:
int no; //根节点不来的情况最大happy值
int yes; //根节点来的情况最大happy值
Info (int n, int y) : no(n), yes(y) {
}
};
Info *process(Employee *x) {
if (x == nullptr) {
return new Info(0, 0);
}
int no = 0;
int yes = x->happy;
for (Employee *next : x->subordinates) {
Info *nextInfo = process(next);
//x不来的时候,子孩子可来可不来
no += max(nextInfo->no, nextInfo->yes);
//x来的时候,子孩子不能来
yes += nextInfo->no;
}
return new Info(no, yes);
}
int maxHappy2(Employee *boss) {
Info *allInfo = process(boss);
return max(allInfo->no, allInfo->yes);
}
//for test
void generateNexts(Employee *e, int level, int maxLevel, int maxNexts, int maxHappy) {
if (level > maxLevel) return ;
int nextsSize = rand() % (maxNexts + 1);
for (int i = 0; i < nextsSize; i++) {
Employee *next = new Employee(rand() % (maxHappy + 1));
e->subordinates.push_back(next);
generateNexts(next, level + 1, maxLevel, maxNexts, maxHappy);
}
}
Employee *generateBoss(int maxLevel, int maxNexts, int maxHappy) {
if ((rand() % 100 / (double)101) < 0.02) return nullptr;
Employee *boss = new Employee(rand() % (maxHappy + 1));
generateNexts(boss, 1, maxLevel, maxNexts, maxHappy);
return boss;
}
int main() {
srand(time(0));
int maxLevel = 4;
int maxNexts = 7;
int maxHappy = 100;
int testTimes = 100000;
for (int i = 0; i < testTimes + 1; i++) {
Employee *boss = generateBoss(maxLevel, maxNexts, maxHappy);
if (maxHappy1(boss) != maxHappy2(boss)) {
cout << "Failed!" << endl;
return 0;
}
if (i && i % 1000 == 0) cout << i << " cases passed!" << endl;
}
cout << "Success!" << endl;
return 0;
}
Java 版
import java.util.ArrayList;
import java.util.List;
public class MaxHappy {
public static class Employee {
public int happy;
public List<Employee> nexts;
public Employee(int h) {
happy = h;
nexts = new ArrayList<>();
}
}
//方法一:
public static int maxHappy1(Employee boss) {
if (boss == null) {
return 0;
}
return process1(boss, false);
}
// 当前来到的节点叫cur,
// up表示cur的上级是否来,
// 该函数含义:
// 如果up为true,表示在cur上级已经确定来,的情况下,cur整棵树能够提供最大的快乐值是多少?
// 如果up为false,表示在cur上级已经确定不来,的情况下,cur整棵树能够提供最大的快乐值是多少?
public static int process1(Employee cur, boolean up) {
if (up) {
// 如果cur的上级来的话,cur没得选,只能不来
int ans = 0;
for (Employee next : cur.nexts) {
ans += process1(next, false);
}
return ans;
} else {
// 如果cur的上级不来的话,cur可以选,可以来也可以不来
int p1 = cur.happy;
int p2 = 0;
for (Employee next : cur.nexts) {
p1 += process1(next, true);
p2 += process1(next, false);
}
return Math.max(p1, p2);
}
}
//方法二:
public static int maxHappy2(Employee head) {
Info allInfo = process(head);
return Math.max(allInfo.no, allInfo.yes); //最大老板来的最大收益,和最大老板不来的最大收益
}
public static class Info {
public int no; //根节点不来的情况下的最大happy值
public int yes;//根节点来的情况下的最大happy值
public Info(int n, int y) {
no = n;
yes = y;
}
}
public static Info process(Employee x) {
if (x == null) {
return new Info(0, 0); //快乐值为0
}
int no = 0;
int yes = x.happy;
for (Employee next : x.nexts) {
Info nextInfo = process(next);
no += Math.max(nextInfo.no, nextInfo.yes); //x不来的时候,子孩子可以来,也可以不来,求二者的最大值
yes += nextInfo.no;//子孩子不能来
}
return new Info(no, yes);
}
// for test
public static Employee genarateBoss(int maxLevel, int maxNexts, int maxHappy) {
if (Math.random() < 0.02) {
return null;
}
Employee boss = new Employee((int) (Math.random() * (maxHappy + 1)));
genarateNexts(boss, 1, maxLevel, maxNexts, maxHappy);
return boss;
}
// for test
public static void genarateNexts(Employee e, int level, int maxLevel, int maxNexts, int maxHappy) {
if (level > maxLevel) {
return;
}
int nextsSize = (int) (Math.random() * (maxNexts + 1));
for (int i = 0; i < nextsSize; i++) {
Employee next = new Employee((int) (Math.random() * (maxHappy + 1)));
e.nexts.add(next);
genarateNexts(next, level + 1, maxLevel, maxNexts, maxHappy);
}
}
public static void main(String[] args) {
int maxLevel = 4;
int maxNexts = 7;
int maxHappy = 100;
int testTimes = 100000;
for (int i = 0; i < testTimes; i++) {
Employee boss = genarateBoss(maxLevel, maxNexts, maxHappy);
if (maxHappy1(boss) != maxHappy2(boss)) {
System.out.println("Oops!");
}
}
System.out.println("finish!");
}
}
边栏推荐
- [untitled]
- Three.js-01 入门
- CJ mccullem autograph: to dear Portland
- Arduino 测量交流电流
- Post-90s tester: "after joining Ali, this time, I decided not to change jobs."
- Double pointeur de liste liée (pointeur rapide et lent, pointeur séquentiel, pointeur de tête et de queue)
- d3dx9_ What if 29.dll is missing? System missing d3dx9_ Solution of 29.dll file
- Nacos 的安装与服务的注册
- 利用LNMP实现wordpress站点搭建
- 我对新中台模型的一些经验思考总结
猜你喜欢
LeetCode102. Sequence traversal of binary tree (output by layer and unified output)
Metasploit(msf)利用ms17_010(永恒之蓝)出现Encoding::UndefinedConversionError问题
利用LNMP实现wordpress站点搭建
[untitled]
Overview of Fourier analysis
Element operation and element waiting in Web Automation
Simple and beautiful method of PPT color matching
Finally understand what dynamic planning is
Business introduction of Zhengda international futures company
一文搞定class的微观结构和指令
随机推荐
Google Maps case
Unity Max and min constraint adjustment
Ultrasonic sensor flash | LEGO eV3 Teaching
[digital signal denoising] improved wavelet modulus maxima digital signal denoising based on MATLAB [including Matlab source code 1710]
Business introduction of Zhengda international futures company
Nangou Gili hard Kai font TTF Download with installation tutorial
Getting started stm32--gpio (running lantern) (nanny level)
Request preview display of binary data and Base64 format data
The countdown to the launch of metaverse ape is hot
Error when LabVIEW opens Ni instance finder
Event trigger requirements of the function called by the event trigger
openresty ngx_lua正则表达式
The introduction to go language is very simple: String
d3dx9_ What if 29.dll is missing? System missing d3dx9_ Solution of 29.dll file
Hcip day 11 (BGP agreement)
Openresty ngx Lua regular expression
Double pointer of linked list (fast and slow pointer, sequential pointer, head and tail pointer)
Metasploit (MSF) uses MS17_ 010 (eternal blue) encoding:: undefined conversionerror problem
Arduino 测量交流电流
Distributed resource management and task scheduling framework yarn