第226次周赛题 ｜ 2021-1-31

T2

5665. 从相邻元素对还原数组

难度中等2
存在一个由 n 个不同元素组成的整数数组 nums ，但你已经记不清具体内容。好在你还记得 nums 中的每一对相邻元素。
给你一个二维整数数组 adjacentPairs ，大小为 n - 1 ，其中每个 adjacentPairs[i] = [u, v] 表示元素 u 和 v 在 nums 中相邻。
题目数据保证所有由元素 nums[i] 和 nums[i+1] 组成的相邻元素对都存在于 adjacentPairs 中，存在形式可能是 [nums[i], nums[i+1]] ，也可能是 [nums[i+1], nums[i]] 。这些相邻元素对可以 按任意顺序 出现。
返回 原始数组 nums 。如果存在多种解答，返回 其中任意一个 即可。

比赛时：思路是想使用并查集，题还是刷少了，不太直到什么题用什么模型，并查集比较好处理连通性以及对于元素本身不是很重视的问题（就是说不用把图中元素本身的性质再返回这种），但是本题并查集着实有些麻烦。
然后想着构造图进行遍历，又不大清楚邻接表怎么构造比较好，应该用map构造。
正确思路：
用map构造领接表
同时我们需要确定起点或终点，所以在用一个map2来统计每个数字出现的次数，若为1则为端点
最后用一个vector来记录遍历的过程
DFS+哈希表，这里的DFS实现比较简便

class Solution {
    //邻接表构造
    unordered_map<int, vector<int> > edges;
    vector<int> path;
public:
    void DFS(int i, int father)
    {
        //father是用来保证不会往回遍历
        //这似乎是DFS的一种简单写法 适用于无向图 和 有向图？
        path.push_back(i);
        for(auto x : edges[i])
        {
            if(x != father)
                DFS(x, i);
        }
    }
    vector<int> restoreArray(vector<vector<int>>& adjacentPairs) {
        //统计下来出现1次的两个点分别是端点
        unordered_map<int, int> number;
        for(auto& c: adjacentPairs)
        {
            int a = c[0], b = c[1];
            //有向图两边都要入的
            edges[a].push_back(b);
            edges[b].push_back(a);
            number[a] ++, number[b] ++;
        }
        int root = 0;
        //对构造的开始遍历，构造出一条链
        for(auto [k, v]: number)
        {
            if(v == 1){
                //起点
                root = k;
                break;
            }
        }
        DFS(root, -1);
        return path;
    }
};

T3

5667. 你能在你最喜欢的那天吃到你最喜欢的糖果吗？

难度中等2
给你一个下标从 0 开始的正整数数组 candiesCount ，其中 candiesCount[i] 表示你拥有的第 i 类糖果的数目。同时给你一个二维数组 queries ，其中 queries[i] = [favoriteType, favoriteDay, dailyCap] 。
你按照如下规则进行一场游戏：

• 你从第 **0** 天开始吃糖果。
• 你在吃完 所有 第 i - 1 类糖果之前，不能 吃任何一颗第 i 类糖果。
• 在吃完所有糖果之前，你必须每天 至少 吃 一颗 糖果。

请你构建一个布尔型数组 answer ，满足 answer.length == queries.length 。answer[i] 为 true 的条件是：在每天吃 不超过 dailyCap颗糖果的前提下，你可以在第 favoriteDay 天吃到第 favoriteType 类糖果；否则 answer[i] 为 false 。注意，只要满足上面 3 条规则中的第二条规则，你就可以在同一天吃不同类型的糖果。
请你返回得到的数组 answer 。

示例 1：
输入：candiesCount = [7,4,5,3,8], queries = [[0,2,2],[4,2,4],[2,13,1000000000]]
输出：[true,false,true]
提示：
1- 在第 0 天吃 2 颗糖果(类型 0），第 1 天吃 2 颗糖果（类型 0），第 2 天你可以吃到类型 0 的糖果。
2- 每天你最多吃 4 颗糖果。即使第 0 天吃 4 颗糖果（类型 0），第 1 天吃 4 颗糖果（类型 0 和类型 1），你也没办法在第 2 天吃到类型 4 的糖果。换言之，你没法在每天吃 4 颗糖果的限制下在第 2 天吃到第 4 类糖果。
3- 如果你每天吃 1 颗糖果，你可以在第 13 天吃到类型 2 的糖果。

示例 2：
输入：candiesCount = [5,2,6,4,1], queries = [[3,1,2],[4,10,3],[3,10,100],[4,100,30],[1,3,1]]
输出：[false,true,true,false,false]

提示：

• 1 <= candiesCount.length <= 10
• 1 <= candiesCount[i] <= 10
• 1 <= queries.length <= 10
• queries[i].length == 3
• 0 <= favoriteType < candiesCount.length
• 0 <= favoriteDay <= 10
• 1 <= dailyCap <= 10

注意点：数据范围,有点坑的，3个地方都要用LL（long long）
1.前缀和数组元素类型LL
2.day + 1 这里要LL，因为int 可能不够表示
3.x1,y1 x2,y2要LL

基本思路：利用前缀和转换为区间交集问题，那么如何判断两个区间是否有交集？
比如区间[x1, y1] 和 [x2, y2]。想两个区间有交集，直接判断交集有点复杂，可以反过来考虑两个什么时候没有交集。那么y1 < x2 || x1 > y2的时候就肯定没有交集

typedef long long LL;
class Solution {
public:
    vector<bool> canEat(vector<int>& candiesCount, vector<vector<int>>& queries) {
        //区间题？
        int n = candiesCount.size();
        vector<bool> ans;
        vector<LL> s(n + 1);
        for(int i = 1; i <= n; ++ i)
            s[i] = s[i - 1] + candiesCount[i - 1];
        for(auto& q: queries)
        {
            int type = q[0], day = q[1], cap = q[2];
            //两个条件 天数 * 容量 < 对应类别前缀和
            //(day + 1, (day + 1) * cap)
            //(s[type] + 1, s[type + 1])前面和+1，本和结束
            //s[type]表示的是type前（不包括type）的前缀和
            LL x1 = day + 1, y1 = (LL)(day + 1) * cap;
            LL x2 = s[type] + 1, y2 = s[type + 1];
            if(y1 < x2 || x1 > y2)
                ans.push_back(false);
            else
                ans.push_back(true);
        }
        return ans;
    }
};