途游25届秋招笔试-开发岗位-0908

途游25届秋招笔试-开发岗位-0908

时间：2024-09-08 21:40

选择

编程

1

// Description: 途游25届秋招笔试-开发岗位-0906-编程第一题
// Accept: 100%
// Date: 2024/09/08

#include <iostream>
#include <vector>

using namespace std;

int maxPoints(const std::string& s, int k) {
    int n = s.size();
    std::vector<int> points(n);

    // 将字符转换为对应的积分
    for (int i = 0; i < n; ++i) {
        switch (s[i]) {
            case 'H': points[i] = 1; break;
            case 'S': points[i] = 2; break;
            case 'D': points[i] = 3; break;
            case 'C': points[i] = 4; break;
        }
    }

    // 计算从最左端抽取 k 张卡牌的积分
    int left_sum = 0;
    for (int i = 0; i < k; ++i) {
        left_sum += points[i];
    }

    // 滑动窗口计算最大积分
    int max_sum = left_sum;
    for (int i = 1; i <= k; ++i) {
        left_sum -= points[k - i];
        left_sum += points[n - i];
        max_sum = std::max(max_sum, left_sum);
    }

    return max_sum;
}

int main() {
    string s;
    int k;
    while (cin >> s) {
        cin >> k;
        cout << maxPoints(s, k) << endl;
    }
    return 0;
}

2

// Description: 途游25届秋招笔试-开发岗位-0906-编程第二题
// Accept: 100%
// Date: 2024/09/08

#include <iostream>
#include <vector>

using namespace std;

int charIndex(char c) {
    if (c >= 'A' && c <= 'Z') {
        return c - '7';
    } else if (c >= '0' && c <= '9') {
        return c - '0';
    }
    return 0;
}

int characterReplacement(const string &s, int k) {
    vector<int> count(36, 0);  // 字符频率数组
    int max_count = 0;  // 当前窗口中字符的最大频率
    int max_char = 0; // 当前窗口中最大频率的字符
    int left = 0;  // 窗口的左边界
    int max_length = 0;  // 记录最长子串长度

    for (int right = 0; right < s.size(); ++right) {
        int c = charIndex(s[right]);

        // 更新窗口内字符的频率
        ++count[c];
        if (count[c] > max_count) {
            max_count = count[c];
            max_char = c;
        }

        // 当前窗口的长度
        int window_length = right - left + 1;

        // 计算需要的变换次数
        if (window_length - max_count > k) {
            // 如果变换次数超过 k，缩小窗口
            int left_char = charIndex(s[left]);
            --count[left_char];
            if (left_char == max_char) {
                --max_count;
            }
            left++;
        }

        // 更新最大长度
        max_length = max(max_length, right - left + 1);
    }

    return max_length;
}

int main() {
    int n, k;
    string s;
    while (cin >> n >> k) {
        cin >> s;
        cout << characterReplacement(s, k) << endl;
    }
    return 0;
}

/*
7 1
AABABBA
 */

3

// Description: 途游25届秋招笔试-开发岗位-0906-编程第三题
// Accept: 100%
// Date: 2024/09/08

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <unordered_map>
#include <iomanip>

using namespace std;

class Solution {
public:
    priority_queue<int> small;
    priority_queue<int, vector<int>, greater<int> > big;
    unordered_map<int, int> mp;

    double get(int &k) const {
        if (k % 2) return small.top();
        else return ((long long) small.top() + big.top()) * 0.5;
    }

    vector<double> medianSlidingWindow(vector<int> &nums, int k) {
        for (int i = 0; i < k; i++) { small.push(nums[i]); };
        for (int i = 0; i < k / 2; i++) {
            big.push(small.top());
            small.pop();
        }
        vector<double> ans{get(k)};
        for (int i = k; i < nums.size(); i++) {
            int balance = 0;
            int l = nums[i - k];
            mp[l]++;
            if (!small.empty() && l <= small.top()) { balance--; }
            else { balance++; }
            if (!small.empty() && nums[i] <= small.top()) {
                small.push(nums[i]);
                balance++;
            } else {
                big.push(nums[i]);
                balance--;
            }
            if (balance > 0) {
                big.push(small.top());
                small.pop();
            }
            if (balance < 0) {
                small.push(big.top());
                big.pop();
            }
            while (!small.empty() && mp[small.top()] > 0) {
                mp[small.top()]--;
                small.pop();
            }
            while (!big.empty() && mp[big.top()] > 0) {
                mp[big.top()]--;
                big.pop();
            }
            ans.push_back(get(k));

        }
        return ans;
    }
};

void print(double num) {
    if (num == static_cast<int>(num)) {
        // 输出整数
        std::cout << static_cast<int>(num);
    } else {
        // 输出小数，保留一位小数
        std::cout << std::fixed << std::setprecision(1) << num;
    }
}

int main() {
    int n, k;
    while (cin >> n >> k) {
        vector<int> a(n);
        for (int i = 0; i < n; ++i) {
            cin >> a[i];
        }
        Solution s;
        std::vector<double> res = s.medianSlidingWindow(a, k);
        for (int i = 0; i < res.size() - 1; ++i) {
            print(res[i]);
            cout << " ";
        }
        print(res[res.size() - 1]);
        cout << endl;
    }
    return 0;
}