一、数字重排为偶数
题目描述
给定 q 组数据，每组输入一个正整数 x。要求重排 x 的数位，使其变为偶数并返回结果。若 x 本身已是偶数则直接返回；若无法通过重排得到偶数，返回 -1。
解题思路
判断一个数是否为偶数，只需看其个位数字。我们将输入视为字符串处理更为方便。
- 检查最后一位是否为偶数，若是则直接返回原串。
- 若否，从前往后遍历寻找第一个偶数位，将其交换至末尾。
- 若遍历结束仍未找到偶数位，说明无解，返回 -1。
#include <iostream>
using namespace std;
string solve() {
string str;
cin >> str;
int n = str.size();
// 检查最后一位是否为偶数
if ((str[n - 1] - '0') % 2 == 0) return str;
// 寻找第一个偶数位并交换到末尾
for (int i = 0; i < n - 1; i++) {
if ((str[i] - '0') % 2 == 0) {
swap(str[i], str[n - 1]);
return str;
}
}
return "-1";
}
int main() {
int q;
cin >> q;
while (q--) {
cout << solve() << endl;
}
return 0;
}
二、体操队形排列方案
题目描述
有 n 名队员（编号 1~n），每人有一个诉求 a[i]，表示 i 号队员必须排在 a[i] 的前面。若 a[i] == i 则表示无特殊要求。求满足所有条件的排队方案总数。
解题思路
这是一个典型的回溯问题。我们需要按位置依次填入队员，同时维护已使用状态和约束条件。
- 使用
vis数组记录队员是否已被安排。 - 递归尝试将每个未使用的队员放入当前空位。
- 关键剪枝：如果当前队员 i 的诉求对象 arr[i] 已经被安排了，那么 i 必须排在 arr[i] 前面，这会导致冲突，因为 arr[i] 已经在前面了。此时该分支无效，直接回溯。
- 当填满所有位置时，方案数加一。
#include <iostream>
using namespace std;
int arr[11]; // 每个队员的诉求
bool vis[11]; // 记录队员是否被排过
int ret = 0; // 最终结果
int n;
void dfs(int pos) {
if (pos == n + 1) {
ret++;
return;
}
for (int i = 1; i <= n; i++) {
if (vis[i]) continue; // 队员已用过
// 如果该队员的诉求对象已经排过了，说明无法满足 i 在 arr[i] 前面的条件
if (vis[arr[i]]) return;
vis[i] = true;
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;
}
三、二叉树中的最大路径和
题目描述
给定一棵二叉树，求任意路径的最大路径和。路径定义为从任意节点出发，到达任意节点的序列，节点可向上或向下移动，但同一节点只能经过一次。路径至少包含一个节点。
解题思路
此题适合使用后序遍历（DFS）。对于每个节点，我们需要计算两个值：
- 单侧最大路径和：以当前节点为起点，向左或向右延伸的最大路径和（用于返回给父节点）。
- 全局最大路径和：以当前节点为转折点（即路径经过当前节点，连接左右子树）的最大和。
关键点在于处理负数。如果某条子路径的和小于 0，不如不选（相当于截断），因此取 max(0, 子路径和)。
更新全局最大值时，考虑左子树贡献 + 右子树贡献 + 当前节点值。
返回值时，只返回当前节点值 + max(左，右)，保证是单侧路径。
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
int ret = -1010;
int dfs(TreeNode* root) {
if (root == nullptr) return 0;
// 获取左右子树的最大贡献值，若为负则取 0
int left = max(dfs(root->left), 0);
int right = max(dfs(root->right), 0);
// 更新全局最大路径和（以当前节点为最高点的路径）
ret = max(ret, root->val + left + right);
// 返回当前节点能提供的最大单侧路径和
return root->val + max(left, right);
}
int maxPathSum(TreeNode* root) {
dfs(root);
return ret;
}
};
