【刷题汇总 -- 游游的重组偶数、体操队形、二叉树中的最大路径和】 ...

今日刷题汇总 - day028

1、游游的重组偶数

1.1、标题

1.2、思路

读完题，知道让处置惩罚q组数据，让其重新排位，让这个数酿成偶数，且不能有前导零，且重排后可与原数相称，如果重排后能成为偶数则输出，若无法成为偶数，则输出-1即可。那么，这个问题就成为怎样判断偶数的问题，第一个方式就是判断这个数可以或许被2整除，第二个方法判断个位上的数是不是偶数即可。此外，由于我们老实的输入数字去摸得到每一位上的数比较贫苦，所以这里就利用string转数字提取每一位即可，再然后还有一些细节须要留意处置惩罚，那么接下来，就是步伐实现。
1.3、步伐实现

首先，按照思路和标题要求利用string输入每一组的数据number，然后遍历字符串如果是偶数就与最后的和个位互换，然后如果互换成功最后一位就是偶数，则满足条件，如果遍历完都没有实行互换说明就不是偶数，则输出-1。此中值得留意的细节就是，遍历选择从末尾开始遍历办理，这个数自己就是偶数如24时，然后如果从前遍历也会互换酿成42，输出42与标题输出不匹配通过不了。所以就直接采用从末尾判断互换即可。

1. #include <iostream>
2. #include <string>
3. using namespace std;
5. int main()
6. {
7.     int q;
8.     cin >> q;
9.     string number;
11.     while (q--)
12.     {
13.         cin >> number;
14.         int len = number.size();
15.         int flag = 0;
16.         for(int i = len - 1;i >= 0;i--)
17.         {
18.             if((number[i]-'0') % 2 == 0)
19.             {
20.                 swap(number[i],number[len-1]);
21.                 flag = 1;
22.                 break;
23.             }
24.         }
25.         if(flag)
26.             cout << number << endl;
27.         else
28.             cout << -1 << endl;
29.     }
30.     return 0;
31. }

复制代码

2、体操队形

2.1、标题

2.2、思路

读完题知道，就是让处置惩罚体操队员的列队问题，须要满足位置与队员需求，此中对于第 i 个队员的需求a表示想要排在a队员位置的前面，比如2号队员的须要a[3]表示想要排在a[2]位置，如果2号需求恰好就是a[2]那么表示该队员没有位置需求，可恣意分配即可。最后求满足所有队员的列队的方案有多少种？那么为了直观的明白画个图：

综上所述就是：根据标题中的队员位置需求与位置是否被占举行递归减治策略，采用dfs依次搜索合法位置就入队，知道所有队员全部放入即可。那么，接下来就是步伐实现。
2.3、步伐实现 – 递归(dfs) + 剪枝

根据思路分析的递归思想和减治策略实现，首先按照标题要求输入这里采用全局方便使用和输出结果，然后主要是完善dfs，这里同样是利用全局的特性，可以明白为直接一位一位的判断处置惩罚，所以主函数直接给第一个位置即可，然后dfs函数体中，如果当前位置越界那么就直接返回输出ret即可。此中标题中2 <= n <= 10;接着，遍历递归剩余位置，且利用bool vis数组判断队员是否已入队，且判断vis[arr]队员的需求是否已经被满足了，如对于上图中第二个情况的第四组情况中，4号要求在2号前面，但是2号已经入队了就不满足，则都采用剪枝减去多余重复的利用，最后是合法的就进入标记，继承第二个位置递归。值得留意的是，实行恢复现场，由于上图思路分析中对于情况二发现到后面属于都不满足条件，无法有方案的，所以须要恢复到情况3的形式继承递归判断，搜索是否具有合法方案。

1. #include <iostream>
2. using namespace std;
4. const int N = 15;
5. int n,ret;
6. int arr[N];
7. bool vis[N];
9. void dfs(int pos)
10. {
11.     if(pos == n+1)//说明遍历完，所有队员都合法入队
12.     {
13.         ret++;//方案+1
14.         return;
15.     }
16.     for(int i = 1;i <= n;i++)
17.     {
18.         //剪枝
19.         if(vis[i])//当前队员已入队了
20.             continue;
21.         if(vis[arr[i]])//当前队员的需求不满足，因为vis说明arr[i]需求的队员已经入队。
22.             return;
23.         //说明当前合法,则进行标记
24.         vis[i] = true;
25.         dfs(pos + 1);//继续下个位置
26.         //注意：恢复现场,因为当前位置不合法时，需要将当前位置腾出来，才能让下一个队员进行递归判断
27.         vis[i] = false;
28.     }
29. }
31. int main()
32. {
33.     cin >> n;
34.     for(int i = 1;i <= n;i++)
35.         cin >> arr[i];
36.    
37.     dfs(1);
38.    
39.     cout << ret << endl;
40.     return 0;
41. }

复制代码

3、二叉树中的最大路径和

3.1、标题

3.2、思路

读完题知道，二叉树内里的路径被界说为:从该树的恣意节点出发，颠末父=>子大概子=>父的连接，达到恣意节点的序列。
留意:
1.同一个节点在一条二叉树路径里中最多出现一次
2.一条路径至少包含一个节点，且不一定颠末根节点
那么给定一个二叉树的根节点root，请你盘算它的最大路径和。
通过标题和示例分析，总结标题的概念就是一句话，就是将这棵树中画一条不会回溯的路线，求路线中最大路径和。如图：

那么由于路径是不定长且存在负数的情况，思考和分析以下几个要点：
(1)、要明白怎样遍历树更适用？采用后序遍历，由左右子树汇集根节点更方便统计；
(2)、由于不不能回溯的所以这里的左右子树的路径和，实际上是一条单链和；
(3)、返回分为四种情况：
a、左右子树都是正数，则左+右+根的总和为最大路径和；
b、左子树和为负数，右子树和为正数，则返回右子树的和 + 根的和与只要右子树的路径相比的最大值，即max(右+根，右)；由于根结点的值可能为负数；
c、同理，左子树和为正数数，右子树和为负数，则max(左+根，左)；
d、左右子树都为负数，则返回与根结点的比较，max(根，max(左，右));
接下来，就是步伐实现。
3.3、步伐实现 – 递归+树形dp

综上所述总结为树形dp：
a. 左⼦树收集：以左⼦树为起点的最⼤单链和；
b. 右⼦树收集：以右⼦树为起点的最⼤单链和；
c. 根节点要做的事情：整合左右⼦树的信息，得到颠末根节点的最⼤路径和；
d. 向上返回：以根节点为起点的最⼤单链和

1. class Solution
2. {
3.   public:
4.     int ret = -1010;
5.     int dfs(TreeNode* root)
6.     {
7.         if (root == nullptr)
8.             return 0;
9.         int left = max(0, dfs(root->left));// 左⼦树的最⼤单链和,max 0去除负数
10.         int right = max(0, dfs(root->right)); // 右⼦树的最⼤单链和
11.         // 经过root的最⼤路径和
12.         ret = max(ret, root->val + left + right);
13.         return root->val + max(left, right);
14.     }
15.     int maxPathSum(TreeNode* root)
16.     {
17.         dfs(root);
18.         return ret;
19.     }
20. };

复制代码

4、标题链接