今日头条2019春招笔试题

1

[AC]动态规划。

#include <iostream>
#include <vector>
#include <limits>
#include <algorithm>
#include <numeric>
using namespace std;

int main()
{
    int n;
    cin >> n;
    n = 1024 - n;

    vector<int> coins{ 1,4,16,64 };
    vector<int> dp(n + 1, INT_MAX);
    dp[0] = 0;

    for (int i = 1; i <= n; ++i) {
        for (auto coin : coins) {
            if (i >= coin) {
                dp[i] = min(dp[i - coin] + 1, dp[i]);
            }
        }
    }
    std::cout << dp[n] << endl;
}

---

2

[AC].

#include<cmath>
#include<string>
#include<iostream>
#include<algorithm>
using namespace std;

int main()
{
    int n;
    cin>>n;
    while(n--)
    {
        string str;
        cin>>str;
        string str1 = "";
        char last = str[0];
        int count = 0;
        for (int i = 0; i < str.length(); i++)
        {
            if (str[i] == last)
            {
                count++;
            }
            else
            {
                str1 += last;
                str1 += to_string(count);
                count = 1;
                last = str[i];
            }
        }
        str1 += last;
        str1 += to_string(count);

        for (int i = 1; i < str1.size(); i+=2)
        {
            if (str1[i]-'0' >= 3)
                str1[i] = '2';
        }
        for (int i = 1, j = 3; i<str1.size()&&j < str1.size(); j+=2,i+=2)
        {
            if (str1[i]-'0' == 2 && str1[j]-'0' == 2)
                str1[j] = '1';
        }
        //cout << str1 << endl;

        string s = "";
        for (int i = 1; i < str1.size(); i += 2)
        {
            int count = str1[i] - '0';
            char c = str1[i - 1];

            for (int j = 0; j < count; j++)
                s += c;
        }
        cout << s << endl;
    }
}

---

3

[AC].找到最小的值所在的位置，然后先往左扫一遍，再往右扫一遍，类似是个环。

#include <iostream>
#include <vector>
#include <limits>
#include <algorithm>
#include <numeric>
using namespace std;

int main() {
    int example;
    cin >> example;
    while (example--) {
        int n;
        cin >> n;
        vector<int> nums(n);
        int i = 0;
        while (i < n && cin >> nums[i]) {
            ++i;
        }

        auto iter = min_element(nums.begin(), nums.end());
        int index = iter - nums.begin();

        vector<int> nums_sort(nums.begin() + index, nums.end());

        for (int i = 0; i < index; ++i) {
            nums_sort.push_back(nums[i]);
        }

        vector<int> dp(n, 1);
        for (int i = 1; i < nums_sort.size(); ++i) {
            if (nums_sort[i] > nums_sort[i - 1]) {
                dp[i] = dp[i - 1] + 1;
            }
        }

        vector<int> dp2(n,1);
         int tmp = nums_sort[0];
        for (int i = 0; i < nums_sort.size() - 1; ++i) {
            nums_sort[i] = nums_sort[i + 1];
        }
        nums_sort[nums_sort.size() - 1] = tmp;

        for (int i = nums_sort.size() - 2; i >= 0; --i) {
            if (nums_sort[i] > nums_sort[i + 1])
                dp2[i] = dp2[i + 1]+1;
        }

        int tmp2 = dp2.back();
        for (int i = dp2.size()-2; i >= 0; --i) {
            dp2[i+1] = dp2[i];
        }
        dp2[0] = tmp2;

        for (int i = 0; i < dp.size(); ++i) {
            dp[i] = max(dp[i], dp2[i]);
        }
        int res = accumulate(dp.begin(), dp.end(), 0);
        cout << res << endl;
    }
}

---

4

二分查找。

注：第四题答案对应的图片为牛客网上牛友分享的，侵删。