2019 年机考试题 试读

1、给一个日期，输出与 20190218 之间相差的天数

#include <iostream>

using namespace std;

int days[2][13] = { {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31},
                    {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31} };
bool isLeapYear(int year) {
    return year % 400 == 0 || year % 4 == 0 && year % 100 != 0;
}

int calDay(int year, int month, int day) {
    int cnt = day;
    if (isLeapYear(year)) {
        for (int i = 1; i < month; i++)
            cnt += days[1][i];
    }
    else {
        for (int i = 1; i < month; i++)
            cnt += days[0][i];
    }
    return cnt;
}
int difference(string date1, string date2) {
    int year1 = 0, month1 = 0, day1 = 0;
    int year2 = 0, month2 = 0, day2 = 0;
    if (date1 > date2) swap(date1, date2);
    // 取出来年月日
    for (int i = 0; i < 4; i ++) {
        year1 = year1 * 10 + date1[i] - '0';
        year2 = year2 * 10 + date2[i] - '0';
    }
    for (int i = 4; i < 6; i ++) {
        month1 = month1 * 10 + date1[i] - '0';
        month2 = month2 * 10 + date2[i] - '0';
    }
    for (int i = 6; i < 8; i ++) {
        day1 = day1 * 10 + date1[i] - '0';
        day2 = day2 * 10 + date2[i] - '0';
    }
    int differ = 0;
    for (int i = year1; i < year2; i++) {
        if (isLeapYear(i)) differ += 366;
        else differ += 365;
    }
    differ -= calDay(year1, month1, day1);
    differ += calDay(year2, month2, day2);
    return differ;
}
int main(){
    string date = "20190218", date2;
    cin >> date2;
    cout << difference(date, date2) << endl;
    return 0;
}

2、最大连续子序列和

dp[i] 代表以 nums[i] 结尾的最大子序列和，dp[i] = max(nums[i], dp[i - 1] + nums[i])

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

using namespace std;

int main(){
    int n;
    cin >> n;
    vector<int> nums(n);
    for (int i = 0; i < n; i++)
        cin >> nums[i];
    int ans = nums[0];
    int dp = nums[0];
    for (int i = 1; i < n; i++) {
        dp = dp > 0 ? dp + nums[i] : nums[i];
        ans = max(ans, dp);
    }
    cout << ans << endl;
    return 0;
}

3、给一个数（范围是好像是2到1000）表示二叉树由多少个节点，让输出有多少个二叉树的形态

卡特兰数

https://leetcode-cn.com/circle/article/lWYCzv/

#include <iostream>

using namespace std;

int main(){
    int n;
    cin >> n;
    int num1 = 1, num2 = 1;
    for (int i = n + 2; i <= 2 * n; i++)
        num1 *= i;
    for (int i = 2; i <= n; i++)
        num2 *= i;
    cout << num1 / num2 << endl;
    return 0;
}