LeetCode第76场双周赛前四题题解

- 本人的LeetCode账号：魔术师的徒弟，欢迎关注获取每日一题题解，快来一起刷题呀~

• 本人Gitee账号：路由器，欢迎关注获取博客内容源码。
  文章目录
  • 一、找到最接近 0 的数字
  • 二、买钢笔和铅笔的方案数
  • 三、设计一个ATM机
  • 四、节点序列的最大得分
  • 五、扯淡

一、找到最接近 0 的数字

2239. 找到最接近 0 的数字

  利用绝对值函数abs，简单模拟即可。

class Solution {
public:
    int findClosestNumber(vector<int>& nums) 
    {
        int res = 0x3f3f3f3f;
        for (int p : nums)
        {
            if (abs(p) <= abs(res))
            {
                if (abs(p) < abs(res))
                {
                    res = p;
                }
                else 
                {
                    res = max(res, p);
                }
            }
        }
        return res;    
    }
};

二、买钢笔和铅笔的方案数

2240. 买钢笔和铅笔的方案数

  思路，枚举cost1的数量，每次都获得cost2的可能数量即可。

class Solution {
public:
    typedef long long LL;
    long long waysToBuyPensPencils(int total, int cost1, int cost2) 
    {
        LL res = 0;
        for (int i = 0; i * cost1 <= total; ++i)
        {
            res += (total - i * cost1) / cost2 + 1;
        }    
        return res;
    }
};

三、设计一个ATM机

2241. 设计一个 ATM 机器

  用一个map，第一个关键字是面额，第二个关键字是数量，每次都从大的取钱即可，如果取不出来，返回{-1}。

class ATM {
public:
    typedef long long LL;
    ATM() 
    {}
    
    void deposit(vector<int> banknotesCount) 
    {
        // 存钱
        for (int i = 0; i < 5; ++i)
        {
            if (i == 0) myhash[20] += banknotesCount[i];
            else if (i == 1) myhash[50] += banknotesCount[i];
            else if (i == 2) myhash[100] += banknotesCount[i];
            else if (i == 3) myhash[200] += banknotesCount[i];
            else myhash[500] += banknotesCount[i];
        }
    }
    
    vector<int> withdraw(int amount) 
    {
        vector<int> ans(5);
        int k = 4;
        // 翻墙迭代器取钱
        auto rit = myhash.rbegin();
        while (amount > 0 && rit != myhash.rend())
        {
            if (amount >= (*rit).first && (*rit).second != 0)
            {
                int cnt = amount / (*rit).first;
                amount -= (*rit).first * min((*rit).second, (LL)cnt);
                ans[k] = min((*rit).second, (LL)cnt);
            }
            ++rit;
            --k;
        }
        if (amount != 0) return { -1 };
        auto it = myhash.begin();
        for (int i = 0; i < 5; ++i)
        {
            (*it).second -= ans[i];
            ++it;
        }
        return ans;
    }
private:
    map<int, LL> myhash = {{20, 0}, {50, 0}, {100, 0}, {200, 0}, {500, 0}};
};

四、节点序列的最大得分

2242. 节点序列的最大得分

  本题其实是一个脑筋急转弯题，要找一个长度为4的最长序列，我们可以枚举每条中间边，为了获得最长的序列，我们可以枚举与两个端点相连的值最大的点，为了避免这两个点重复，我们要枚举最大的点和次大的点，其余就是一些细节处理，见代码。

class Solution {
public:
    int maximumScore(vector<int>& scores, vector<vector<int>>& edges) 
    {
        // 贪心:这个长度为4的链可以看为三个边 我们不妨枚举中间那条边(x, y)
        // 然后让旁边两个点往外找 x找与自己相连的不是y的最大点 y找与自己相连的不是x的最大点
        // 这时这两点可能会重复 所以为了避免这个情况 我们再存一个次高边
        // 一旦冲突 取大
        // 邻接表建图
        vector<vector<int>> adj(scores.size());
        for (auto& e : edges)
        {
            int x = e[0], y = e[1];
            adj[x].push_back(y);
            adj[y].push_back(x);
        }   
        // 按照分数由大到小排序
        for (auto& g : adj)
        {
            sort(g.begin(), g.end(), 
            [&](int a, int b)
            {
                return scores[a] > scores[b];
            });
        }
        // 遍历中间边
        int res = -1;
        for (auto& e : edges)
        {
            int x = e[0], y = e[1];
            int sum = scores[x] + scores[y];
            // 找与x相连的且不为y的最大的两个点
            // 找与y相连的且不为x的最大的两个点
            vector<int> next_to_x;
            for (int i = 0; i < adj[x].size() && next_to_x.size() < 2; ++i)
            {
                int k = adj[x][i];
                if (k != y) next_to_x.push_back(k);
            }
            vector<int> next_to_y;
            for (int i = 0; i < adj[y].size() && next_to_y.size() < 2; ++i)
            {
                int k = adj[y][i];
                if (k != x) next_to_y.push_back(k);
            }
            // 找不到相邻边
            if (next_to_x.empty() || next_to_y.empty()) continue;
            int m1 = next_to_x[0], m2 = next_to_y[0];
            // 如果这两点不同
            if (m1 != m2)
            {
                res = max(res, sum + scores[m1] + scores[m2]);
            }
            else 
            {
                // 相同 则以后面那个点取小
                if (next_to_x.size() == 2)
                {
                    int tmpx = next_to_x[1];
                    res = max(res, sum + scores[tmpx] + scores[m2]);
                }
                if (next_to_y.size() == 2)
                {
                    int tmpy = next_to_y[1];
                    res = max(res, sum + scores[tmpy] + scores[m1]);
                }
            }
        }
        return res;
    }
};

五、扯淡

  脑筋急转弯没做出来，不然有机会AK的。。。