C++ 笔试刷题实战：偶数重组、排队方案与二叉树路径和

一、重组偶数

题目描述

给定一组数据，每次输入一个正整数 x。要求将其重排成一个偶数并返回；如果 x 本身是偶数则直接返回。若无法通过重排得到偶数，则输出 -1。

解题思路

对于正整数 x，我们可以将其视为字符串处理，这样能更方便地操作每一位数字。判断一个数是否为偶数，只需看其最低位（末位）是否为偶数。

具体策略如下：

1. 检查字符串最后一位，如果是偶数，直接返回原串。
2. 如果不是，从前往后遍历寻找第一个偶数位，将其交换到末尾。
3. 若遍历结束仍未找到偶数位，说明该数全由奇数组成，无法重排为偶数，返回 -1。

#include <iostream>
#include <string>
#include <algorithm>
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 名同学进行排队。第 i 号队员有一个诉求 a[i]，表示 i 必须排在 a[i] 的前面。若 a[i] == i，则表示无特殊要求。求一共有多少种合法的排队方案。

解题思路

这是一个典型的回溯问题。我们需要依次确定每个位置的人选，同时满足前驱约束条件。

核心逻辑在于：当尝试将队员 i 放入当前空位时，需要检查两个条件：

1. 队员 i 是否已经被安排过？
2. 队员 i 的诉求对象 a[i] 是否已经排好队了？如果 a[i] 已排且不在 i 之前，则此路不通。

我们使用一个 vis 数组记录已排人员，递归尝试填充每一个位置。当所有位置填满时，方案数加一。

#include <iostream>
using namespace std;

int arr[11];      // 存储每个队员的诉求
bool vis[11];     // 标记队员是否已排
int ret = 0;      // 记录合法方案数
int n;

// pos: 当前要填充的位置索引
void dfs(int pos) {
    if (pos == n + 1) {
        ret++;
        return;
    }

    for (int i = 1; i <= n; i++) {
        if (vis[i]) continue; // 该队员已排过
        
        // 如果该队员的诉求对象已排过，但不在该队员前面，则不满足条件
        // 注意：这里假设 a[i] 是 i 必须排在它前面的那个人
        if (arr[i] != i && 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;
}

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

题目描述

给定一棵二叉树，找出任意路径的最大路径和。路径定义为从任意节点出发，到达任意节点的序列，同一节点在路径中最多出现一次。路径至少包含一个节点，不一定经过根节点。

解题思路

这道题是经典的树形 DP 或 DFS 问题。关键在于理解'路径'的定义：它可以是单向的（如左子树 -> 根），也可以是分叉的（左子树 -> 根 -> 右子树）。

我们在遍历每个节点时，需要计算两个值：

1. 以当前节点为最高点的路径和：即 left_max + root->val + right_max。这用于更新全局最大值 ret。
2. 从当前节点向下延伸的单侧最大路径和：即 root->val + max(left_max, right_max)。这是递归返回值，供父节点使用。

注意：如果某棵子树的最大单路径和小于 0，说明该子树对总和有负贡献，此时应视为 0（即不选择该子树）。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int ret = -100000000;

    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;
    }
};