2012 年机考试题

1、1000 个成绩输出前 30%

明显就是用快排思路

#include <iostream>
#include<queue>

using namespace std;

int partition(vector<int>& nums, int left, int right) {
    int pivot = nums[left];
    while (left < right) {
        while (left < right && nums[right] >= pivot) right--;
        nums[left] = nums[right];
        while (left < right && nums[right] <= pivot) left++;
        nums[right] = nums[left];
    }
    nums[left] = pivot;
    return left;
}

void qsort(vector<int>& nums, int left, int right, int target) {
    if (left < right) {
        int p = partition(nums, left, right);
        if (p > target)
            qsort(nums, left, p - 1, target);
        else if (p < target)
            qsort(nums, p + 1, right, target);
    }
}

int main() {
    int n;
    cin >> n;
    vector<int> nums(n);
    for (int i = 0; i < n; i++)
        cin >> nums[i];
    qsort(nums, 0, n - 1, n * 0.3);
    for (int i = 0; i < n * 0.3; i++)
        cout << nums[i] << " ";
    return 0;
}

2、最大叶子间距

其实也就是求二叉树每个结点左右子树的深度之和

https://leetcode-cn.com/problems/diameter-of-binary-tree/solution/er-cha-shu-de-zhi-jing-by-leetcode-solution/

class Solution {
    int ans;
    int depth(TreeNode* rt){
        if (rt == NULL) {
            return 0; // 访问到空节点了，返回0
        }
        int L = depth(rt->left); // 左儿子为根的子树的深度
        int R = depth(rt->right); // 右儿子为根的子树的深度
        ans = max(ans, L + R + 1); // 计算d_node即L+R+1 并更新ans
        return max(L, R) + 1; // 返回该节点为根的子树的深度
    }
public:
    int diameterOfBinaryTree(TreeNode* root) {
        ans = 1;
        depth(root);
        return ans - 1;
    }
};

3、扩展字符串

#include <iostream>

using namespace std;

int main() {
    string s;
    int n;
    cin >> s >> n;
    string ans = "";
    for (char c : s) {
        string temp(n, c);
        ans += temp;
    }
    cout << ans << endl;
    return 0;
}