2021

第一题

题目描述：给定一颗二叉树，树的每个节点的值为一个正整数。如果从根节点到节点N的路径上不存在比节点N的值大的节点，那么节点N被认为是树上的关键节点。求树上所有的关键节点的个数。请写出程序，并解释解题思路。

输入
3, 1, 4, 3, null, 1, 5
输出
4

方法: DFS

class Solution {
public:
    int res = 0;
    int goodNodes(TreeNode* root) {
        goodNodesFind(root, INT_MIN);
        return res;
    }
    void goodNodesFind(TreeNode* root, int max){
        if (!root) return;
        if (root->val >= max)
        {
            res ++;
            max = root->val;
        }
        goodNodesFind(root->left, max);
        goodNodesFind(root->right, max);
    }
};

第二题

题目描述：训练场上有一个台阶，总共有n级。一个运动员可以跳1级，也可以跳2级。求运动员有多少种跳法。请写出程序，并解释解题思路。

方法: dp

class Solution {
public:
    const int  mod = 1e9 + 7;

    int numWays(int n) {
        if (n <= 1) return 1;
        int dp[n + 1];
        dp[0] = 1;
        dp[1] = 1;
        for (int i = 2; i <= n; i ++) 
            dp[i] = (dp[i - 1] + dp[i - 2]) % mod;
        return dp[n];
    }
};

第三题

题目描述：给定一个非负整数序列$x_1,x_2,......,x_n$,可以给每一个整数取负数或者取原值,有多少种取法使得这些整数的和等于期望值$E$.

输入
1, 1, 1, 1, 1, 3
输出
5
explain:
-1+1+1+1+1 = 3
1-1+1+1+1 = 3
1+1-1+1+1 = 3
1+1+1-1+1 = 3
1+1+1+1-1 = 3

方法一:回溯

class Solution {
public:
    int res = 0;
    int findTargetSumWays(vector<int>& nums, int target) {
        backtrack(nums, target, 0, 0);
        return res;
    }
    void backtrack(vector<int>& nums, int target, int index, int sum)
    {
        if (index == nums.size())
        {
            if (sum == target)
                res ++;
        }
        else{
            backtrack(nums, target, index + 1, sum + nums[index]);
            backtrack(nums, target, index + 1, sum - nums[index]);
        }
    }
};

方法二:dp

解题思路：记数组的元素和为sum，添加-号的元素之和为neg，则其余添加+的元素之和为sum - neg，得到的表达式的结果为
(sum − neg) − neg = sum − 2neg = target
neg = (sum - target) / 2
由于数组nums中的元素都是非负整数,neg也必须是非负整数，所以上式成立的前提是sum−target是非负偶数。若不符合该条件可直接返回0。
定义二维数组dp，其中dp[i][j]表示在数组nums的前i个数中选取元素，使得这些元素之和等于j的方案数。假设数组nums的长度为len，则最终答案为dp[len][neg]。
当没有任何元素可以选取时，元素和只能是0，对应的方案数是1，因此动态规划的边界条件是：dp[0][0] = 1。
状态转移方程：
j < num时： dp[i][j] = dp[i - 1][j]
j >= num时：dp[i][j] = dp[i - 1][j] + dp[i - 1][j - num]
采用滚动数组得状态转移方程：
dp[j] += dp[j - num]

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        int sum = 0;
        for (int num: nums) sum +=num;
        int diff = sum - target;
        if (diff < 0 || diff % 2 != 0) return 0;
        int len = nums.size(), neg = diff / 2;
        vector<int> dp(neg + 1);
        dp[0] = 1;
        for (int num: nums)
            for (int j = neg; j >= num; j --)
                dp[j] += dp[j - num];
        return dp[neg];
    }
};

2020

第一题

题目描述：给定五个0-9范围内的整数$a_1,a_2,a_3,a_4,a_5$。如果能从五个整数中选出三个并且这三个整数的和为10的倍数（包括0），那么这五个整数的权值即为剩下两个没被选出来的整数的和对10取余的结果，显然如果有多个三元组满⾜和是10的倍数，剩下两个数之和对10取余的结果都是相同的；如果选不出这样三个整数，则这五个整数的权值为-1。
现在给定T组数据，每组数据包含五个0-9范围内的整数，分别求这T组数据中五个整数的权值。
输⼊格式 第⼀⾏⼀个整数T(1<=T<=1000)，表⽰数据组数。 接下来T⾏，每⾏5个0~9的整数，表⽰⼀组数据。
输出格式 输出T⾏，每⾏⼀个整数，表⽰每组数据中五个整数的权值。

输入
4
1 0 0 1 0
1 0 0 8 6
3 4 5 6 7
4 5 6 7 8
输出
2
-1
-1
0

#include <iostream>

using namespace std;

int main()
{
    int t;
    cin >> t;
    while(t --)
    {
        int a[5];
        int sum = 0, res = -1;
        for (int i = 0; i < 5; i ++)
        {
            cin >> a[i];
            sum += a[i];
        }
        for (int i = 0; i < 4; i ++)
            for (int j = i + 1; j < 5; j ++)
            {
                int x = sum - a[i] - a[j];
                if (x % 10 == 0)
                {
                    res = (a[i] + a[j]) % 10;
                    break;
                }
            }
        if (res == -1) cout << "-1" << endl;
        else cout << res << endl;
    }
    return 0;
}

第二题

题目描述：给定n个整数$a_1,a_2,......,a_n$和⼀个d，你需要选出若⼲个整数，使得将这些整数从⼩到⼤排好序之后，任意两个相邻的数之差都不⼩于给定的d，问最多能选多少个数出来。
输⼊格式 第⼀⾏两个整数n,d(1<=n<=10^5,0<=d<=10^9)，分别表⽰整数个数和相邻整数差的下界。第⼆⾏n个整数$a_1,a_2, …,a_n$ (1<=$a_i$<=10^9, 1<=i<=n)，表⽰给定的n个整数。
输出格式 仅⼀⾏⼀个整数，表⽰答案。

输入
6 2
1 4 2 8 5 7
输出
3

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

using namespace std;

int main()
{
    int n, d;
    scanf("%d%d", &n, &d);
    vector<int> a(n + 1);
    for (int i = 0; i < n; i ++) scanf("%d", &a[i]);
    sort(a.begin(), a.end());
    int res = 0;
    int i = 0, j = 1;
    while (j < n)
    {
        if (a[j] - a[i] >= d)
        {
            res ++;
            i = j;
            j ++;
        }
        else j ++;
    }
    cout << res << endl;
    return 0;
}

第三题

题目描述：下课了，有n位同学陆续赶到⻝堂进⾏排队打饭，其中第i位同学的到达时间为$a_i$，打饭耗时为$t_i$，等待时间上限为$b_i$，即如果其在第$a_i+b_i$秒的时刻仍然没有轮到他开始打饭，那么他将离开打饭队列，另寻吃饭的地⽅。问每位同学的开始打饭时间，或者指出其提前离开了队伍（如果这样则输出 -1）。

输⼊格式 第⼀⾏⼀个整数n(1<=n<=10^5)，表⽰来打饭的同学数量。 接下来n⾏，每⾏三个整数$a_i,t_i,b_i$(1<=$a_i$,$t_i$,$b_i$<=10^9, 1<=i<=n)，分别表⽰每位同学的到达时间、打饭耗时、等待时间上限。保证$a_1$<$a_2$<…<$a_n$

输出格式 ⼀⾏n个整数，表⽰每位同学的开始打饭时间或者 -1（如果该同学提前离开了队伍）。

输入
4
1 3 3
2 2 2
3 9 1
4 3 2
输出
1 4 -1 6

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 10010;
int a[N], t[N], b[N], res[N];

int main()
{
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i ++) scanf("%d%d%d", &a[i], &t[i], &b[i]);
    int endtime = a[0] + t[0];
    res[0] = a[0];
    for (int i = 1; i < n; i ++)
    {
        if (a[i] + b[i] >= endtime)
        {
            res[i] = endtime;
            endtime += t[i];
        }
        else res[i] = -1;
    }
    for (int i = 0; i < n; i ++)
        cout << res[i] << ' ';
    return 0;
}

第四题

题目描述：给定⼀个1~n的排列P，即⻓度为n，且1~n中所有数字都恰好出现⼀次的序列。现在按顺序将排列中的元素⼀⼀插⼊到初始为空的⼆叉搜索树中（左小右大），问最后每个节点的⽗亲节点的元素是什么。特别地，根节点的⽗亲节点元素视为0。

输⼊格式 第⼀⾏⼀个整数n(1<=n<=10^5)，表⽰排列P中的元素个数。
第⼆⾏n个整数$p_1,p_2,…,p_n$(1<=pi<=n, 1<=i<=n)，表⽰给定的排列。
输出格式 ⼀⾏n个整数，其中第i个整数$a_i$表⽰元素i对应节点的⽗亲节点的元素。特别地，根节点的⽗亲节点元素视为 0。

输入
5
2 3 5 1 4
输出
2 0 2 5 3

2019

第一题

题目描述：相隔天数：输入日期格式：YYYYMMDD，求与20190205相隔的天数。

输入
20190208
输出
3

#include <iostream>
#include <algorithm>

using namespace std;

int month[13] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};

bool isLeapYear(int n)
{
    if ((n % 100 != 0 && n % 4 == 0) || n % 400 == 0) return true;
    else return false;
}

int days(int x)
{
    int d = x % 100, m = (x / 100) % 100, y = x / 10000;
    if (isLeapYear(y)) month[2] = 29;
    while (y --)
    {
        if (isLeapYear(y)) d += 366;
        else d += 365;
    }
    while (m --)
        d += month[m];
    return d;
}

int main()
{
    int date;
    cin >> date;
    cout << abs(days(20190205) - days(date)) << endl;
    return 0;
}

第二题

题目描述：给定一个数字序列$A_1,A_2…A_n$，求i,j(1<=i<=j<=n)，使得$A_i+…+A_j$最大，输出这个最大和。

输入
6
-2 11 -4 13 -5 -2
输出
20

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

using namespace std;

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

第三题

题目描述：求N个结点能够组成的二叉树的个数。

输入
3
输出
5

#include <iostream>

using namespace std;

int main()
{
    int n;
    cin >> n;
    long long dp[n + 1];
    dp[0] = 1;
    dp[1] = 1;
    for (int i = 2; i <= n; i ++)
    {
        long long res = 0;
        for (int j = 0; j <= i - 1; j ++)
            res = res + dp[j] * dp[i - j - 1];
        dp[i] = res;
    }
    cout << dp[n] << endl;
}