当前位置：首页 > news >正文

【今日三题】游游的重组偶数(模拟) / 体操队形(回溯) / 二叉树中的最大路径和(树形dp)

news 2025/5/4 11:17:41

⭐️个人主页：@小羊 ⭐️所属专栏：每日两三题很荣幸您能阅读我的文章，诚请评论指点，欢迎欢迎 ~

动图描述

游游的重组偶数(模拟)

游游的重组偶数

在这里插入图片描述

如果需要操作整数的位，可以将这个整数作为字符串读入，方便操作。
首先判断读入整数是否本来就是偶数，如果不是再从头遍历找有没有哪一位是偶数，如果存在则和最后一位交换，然后返回。

#include <iostream>
#include <string>
using namespace std;int func(string s)
{int n = s.size();if ((s[n - 1] - '0') % 2 == 0) return stoi(s);for (int i = 0; i < n; i++){if ((s[i] - '0') % 2 == 0){swap(s[i], s[n - 1]);return stoi(s);}}return -1;
}int main()
{int q;cin >> q;while (q--){string x;cin >> x;cout << func(x) << endl;}return 0;
}

体操队形(回溯)

体操队形

在这里插入图片描述

枚举每个位置的情况，画出决策树，一切都好办。

#include <iostream>
using namespace std;int n, arr[11], res;
bool used[11];void dfs(int pos)
{if (pos == n + 1){res++;return;}for (int i = 1; i <= n; i++){if (used[i]) continue;if (used[arr[i]]) return; // 剪枝used[i] = true;dfs(pos + 1);used[i] = false;}
}int main()
{cin >> n;for (int i = 1; i <= n; i++) cin >> arr[i];dfs(1);cout << res << endl;return 0;
}

二叉树中的最大路径和(树形dp)

二叉树中的最大路径和

在这里插入图片描述

最大路径和 = 当前节点值 + 左子树最大单链和 + 右子树最大单链和。

class Solution {
public:int res = -0x3f3f3f3f;int maxPathSum(TreeNode* root) {dfs(root);return res;}int dfs(TreeNode *root){if (root == nullptr) return 0;int l = max(0, dfs(root->left));  // 左子树最大单链和int r = max(0, dfs(root->right)); // 右子树最大单链和res = max(res, root->val + l + r); // 当前节点最大路径和return root->val + max(l, r); // 返回当前最大单链和}
};