2021 年机考试题

1、
在深搜的过程中记录下路径上的最大节点值即可

#include <iostream>
#include<stack>
#include<vector>
#include<algorithm>

using namespace std;

struct TreeNode {
    int val;
    TreeNode* left, * right;
    TreeNode(int v) : val(v), left(NULL), right(NULL) {}
};
// 层次遍历构建二叉树
void createTree(vector<int>& nums, int i, int len, TreeNode*& root) {
    if (nums[0] == -1 || len == 0)
        return;
    if (i >= len)//超过数组长度返回  
        return;
    if (nums[i] == -1) {
        root = NULL;
    }
    else {
        root = new TreeNode(nums[i]);
        createTree(nums, i * 2 + 1, len, root->left); //建立左子树  
        createTree(nums, i * 2 + 2, len, root->right); //建立右子树  
    }
}
// 对二叉树进行深度优先搜索
int dfs(TreeNode* root) {
    // 栈中存储节点 + 路径上的最大值
    stack<pair<TreeNode*, int>> s;
    int ans = 0;
    TreeNode* tmp = root;
    int maxNode = root->val;
    while (!s.empty() || tmp) {
        while (tmp) {
            maxNode = max(maxNode, tmp->val);
            s.push({ tmp, maxNode });
            // 关键节点
            if (tmp->val >= maxNode) {
                ans++;
            }
            tmp = tmp->left;
        }
        auto node = s.top();
        s.pop();
        maxNode = node.second;
        tmp = node.first->right;
    }
    return ans;
}
// 先序遍历
void preOrder(TreeNode* root) {
    if (root == NULL)
        return;
    cout << root->val << " ";
    preOrder(root->left);
    preOrder(root->right);
}

int main() {
    int n;
    cin >> n;
    vector<int> nums(n);
    for (int i = 0; i < n; i++) {
        cin >> nums[i];
    }
    TreeNode* root;
    createTree(nums, 0, n, root);
    cout << "关键节点个数为:" << dfs(root) << endl;
    return 0;
}

2、跳台阶问题
简单的动态规划

#include <iostream>

using namespace std;

int main() {
    int n;
    cin >> n;
    // 初始化只有 1 级台阶和 2 级台阶的情况
    int dp1 = 1, dp2 = 2;
    if (n <= 2) cout << "跳法有: " << n << "种" << endl;
    else {
        // 迭代求解
        for (int i = 3; i <= n; i++) {
            int tmp = dp2;
            dp2 += dp1;
            dp1 = tmp;
        }
        cout << "跳法有: " << dp2 << "种" << endl;
    }
    return 0;
}

3、
这道题可以暴力地进行深搜，也就是每个数字选择或者不选择，时间复杂度为 ，我当时稍微做了一下剪枝，好了一点点

#include <iostream>
#include <vector>

using namespace std;

// k 个数字之和为 sum1
int cnt = 0;
int ans[100] = { 0 };
void kSum(vector<int>& nums, int sum1, int idx, int E) {
    if (idx >= nums.size() || sum1 <= 0) return;
    ans[idx] = 1;
    if (sum1 == nums[idx]) {
        cnt++;
        for (int i = 0; i < nums.size(); i++) {
            if (ans[i] == 0 && i == 0) cout << nums[i];
            else if (ans[i] == 0 && i > 0) cout << "+" << nums[i];
            else cout << "-" << nums[i];
        }
        cout << "=" << E << endl;
    }
    // 取第 idx 个数字
    kSum(nums, sum1 - nums[idx], idx + 1, E);
    ans[idx] = 0;
    // 不取第 idx 个数字
    kSum(nums, sum1, idx + 1, E);
}
int main() {
    int n, sum = 0, E;
    cin >> n;
    vector<int> nums(n, 0);
    for (int i = 0; i < n; i++) {
        cin >> nums[i];
        sum += nums[i];
    }
    cin >> E;
    if ((sum - E) % 2 != 0) cout << "取法有: " << 0 << endl;
    else {
        kSum(nums, (sum - E) / 2, 0, E);
        cout << "取法有: " << cnt << endl;
    }
    return 0;
}