第一题：
咋一看，这题目好像很简单，因为题目给的测试用例好像很简单，首先看5 2 3；2 6 7 8，让我们的感觉是从第一行开始搜索根结点，找到根结点之后，再从第二行数据
开始往第三行数据开始找，但是事实不是这样的，这是题目测试用例给我们设置的陷阱，假设我们有下面的测试用例：
5 13 14 16
1 3 4 5
3 6 7 8
5 9 10 12
很显然我们的根结点不在第一行，且这些数据之间都是乱的，所以我们还是要从所有的输入行中逐一寻找根结点；
因为这个题的测试的所有的测试数据的大小为[0,100]，所以所有根结点的大小都在这个范围里面，所以在算法中我们用一个含有101个vector<int>的二维
vector<vector<int>>来记录每个根结点的最近子节点，如果根结点是i，直接将它的所有子节点存入vector<vector<int>>data中编号为i的数组中，这样在后续的取数
操作就会非常方便，直接data[i]就行！！！
代码如下：
#include<iostream>测试用例1：
#include<vector>
#include<map>
#include<sstream>
#include<fstream>
#include<algorithm>
using namespace std;
class solution{
public:
vector<int> BFS(vector<vector<int>>&data){
vector<int>re, tmp;
int count = 0, root = -1;
for (int i = 0; i < data.size(); i++){//统计有多少行
if (data[i].size() != 0 && find(tmp.begin(), tmp.end(), i) == tmp.end())tmp.push_back(i);//tmp记录所有的根节点
}
for (int i = 0; i < data.size(); i++){
if (data[i].size() >1){
for (int j = 1; j < data[i].size(); j++){
for (int k = 0; k < tmp.size(); k++){
if (data[i][j] == tmp[k])tmp[k] = -1;//表示不是根节点
}
}
}
}
//寻找根节点
for (int i = 0; i < tmp.size(); i++){
if (tmp[i] != -1)root = tmp[i];
}
re.push_back(root);
count = 0;
int total = tmp.size();
while (total&&count<re.size()){
if (data[re[count]].size() >1){
for (int i = 1; i < data[re[count]].size(); i++){
re.push_back(data[re[count]][i]);
}
total--;
}
count++;
}
return re;
}
};
int main(){
ifstream fin("C:\\Users\\Dell\\Desktop\\data.txt");
string str;
solution aa;
int size, root, temp;
int num;
vector<int>tmp;
vector<vector<int>>data;
stringstream mystream;
int count = 0;
for (int i = 0; i < 101; i++)data.push_back(tmp);
while (getline(fin, str)){
count = 0;
for (int i = 0; i < str.size(); i++){
if (str[i] == ' ')count++;//多少个整数
}
mystream.clear();
mystream << str;//这里从新定义一个string的流是因为我们是整行读取的，这个题也只能整行读取，那么在后面就要对读取的每一行数据进行切割，把空格 //字符去掉，然后再一个一个取整数，这个时候再把我们的str数据直接传送给流对象mystream，那么流对象mystream就会自动去掉空格，再根据root的类型 //赋值,不得不说c++的流很强大！！！！！！！</span>
mystream >> root;//根结点
data[root].push_back(root);
for (int i = 0; i < count; i++){//除开根结点
mystream >> temp;
data[root].push_back(temp);
}
}
vector<int>re = aa.BFS(data);
for (int i = 0; i < re.size(); i++)cout << re[i] << ' ';
cout << endl;
}
5 13 14 16测试结果：
1 3 4 5
3 6 7 8
4 9 10 12
测试用例2：
1 2 4 5对于这组测试用例，题目要求是第一个数为根结点，后面N个数为子结点，但没有说N不可以等于0,所以在设计的时候要考虑这种特殊情况！！
2
4
5
测试结果：
测试用例2：
1测试结果：
第二题：
这个题也很具有迷惑性，让人一看好像很简单？？？？but，事实不是这样的！！！！
#include<iostream>测试数据：
#include<vector>
#include<map>
#include<sstream>
#include<fstream>
#include<algorithm>
using namespace std;
class solution{
public:
int dynamic_programming(vector<int>&data){
int size = data.size();
int *p = new int[size];
int max_value = 0;
memset(p, 0, sizeof(int)*size);
p[0] = data[0];
p[1] = max(data[0], data[1]);
for (int i = 2; i < size - 1; i++){
p[i] = max(p[i - 2] + data[i], p[i - 1]);
}
max_value = p[size - 2];
memset(p, 0, size*sizeof(int));
p[1] = data[1];
p[2] = data[2];
for (int i = 3; i < size; i++){
p[i] = max(p[i - 2] + data[i], p[i - 1]);
}
max_value = max(max_value, p[size - 1]);
return max_value;
}
};
int main(){
ifstream fin("C:\\Users\\Dell\\Desktop\\data.txt");
int num, count = 0, tmp;;
string str;
vector<int>data;
solution aa;
stringstream mystream;
while (fin >> num){
for (int i = 0; i < num; i++){
fin >> str;
count = 1;
for (int j = 0; j < str.size(); j++){
if (str[j] == ','){
str[j] = ' ';
count++;
}
}
mystream.clear();
mystream << str;
for (int j = 0; j < count; j++){
mystream >> tmp;
data.push_back(tmp);
}
cout << aa.dynamic_programming(data) << endl;
data.clear();
}
}
}
2
1,5,7,10,4,6
1,5,7,4,10,6
测试结果：
在算法中，我们用p数组来保存到目前元素data[i]为止的最大红包数(把data[i]的情况考虑进去，但是此时data[i]可能没有拿走，也有可能拿走)，所以我们知道对于每个红包
有两种结果，要最优子结构p[i]=max{p[i-2]+data[i]，p[i-1]}。我们假设第一个测试用例的情况:
| i | 0 | 1 | 2 | 3 | 4 | 5 |
| data | 1 | 5 | 7 | 10 | 4 | 6 |
| p | 1 | 5 | 8 | 15 | 15 | 21 |
对于每个红包，我们只有两个选择，要么不拿要么不拿，我们用p数组来记录到目前为止的最大红包总金额，我们假设此时算法的i=3，那么对于第三个红包p[i-2]+data[i]表示拿
第i个红包，如果要拿走第i个红包，那么第i-1个红包就不能拿，那么此时我们只能用到p[i-2]目前的红包总金额来加上data[i]，所以在拿data[i]的情况下，它的目前红包总金额
是p[i-2]+data[i]，如果我们不拿data[i]那么p[i]的值就可以直接等于p[i-1]。