力扣竞赛周赛320场_力扣周赛 题目

有一段时间没有发力扣竞赛CSDN了，今天抽空记录一下320周力扣周赛。

---

6241. 数组中不等三元组的数目 - 力扣（Leetcode）

给你一个下标从 0 开始的正整数数组 nums 。请你找出并统计满足下述条件的三元组 (i, j, k) 的数目：

• 0 <= i < j < k < nums.length
• nums[i]、nums[j] 和 nums[k] 两两不同 。
  • 换句话说：nums[i] != nums[j]、nums[i] != nums[k] 且 nums[j] != nums[k] 。

返回满足上述条件三元组的数目。

提示：

• 3 <= nums.length <= 100
• 1 <= nums[i] <= 1000

对于力扣第一道简单题都是可以暴力的，这里就不写暴力的做法了 

我们可以使用一种时间复杂度为O(N)的方法：

通过三元组我们可以思考此题就是求一个数组中三个不同元素的组合，我们可以想到如下原理：

看到图中有三个框 a b c ，此时b是活动的，而a是b框左边的所有数同时a框中所有的数与b不同，a表示所有数的数量大小，而b框每次只有一个数，从数组的第二个位置开始遍历到数组的倒数第二个位置，c框同a框类似，于是我们可以用 a * b来就计算此时以b为中心数的这种情况下所有的组合种数，以此类推求得最终的结果，这个时候我们就会发现这样必须保证数组是有序的。

我们可以看到题目中给的数组并不是一个有序数组，要使一个数组有序很简单，排序即可，于是最终的代码如下：

class Solution {
public:
    int unequalTriplets(vector<int>& nums) {
        int res=0;
        int n=nums.size();
        sort(nums.begin(),nums.end());
        for(int i=1;i<n-1;++i){
            int cur=nums[i];
            if(cur==nums[0] || cur==nums[n-1]) continue;
            auto it1 = lower_bound(nums.begin(),nums.end(),cur);
            if(it1 == nums.begin()) continue;
            auto it2 = upper_bound(nums.begin(),nums.end(),cur);
            if(it2 == nums.end()) continue;
            res+=(it1-nums.begin()) * (nums.end()-it2);
            cout << it1-nums.begin() << endl;
        }
        return res;
    }
};

---

2476. 二叉搜索树最近节点查询 - 力扣（Leetcode）

给你一个 二叉搜索树 的根节点 root ，和一个由正整数组成、长度为 n 的数组 queries 。

请你找出一个长度为 n 的 二维 答案数组 answer ，其中 answer[i] = [mini, maxi] ：

• mini 是树中小于等于 queries[i] 的 最大值 。如果不存在这样的值，则使用 -1 代替。
• maxi 是树中大于等于 queries[i] 的 最小值 。如果不存在这样的值，则使用 -1 代替。

返回数组 answer 。

示例 1 ：

输入：root = [6,2,13,1,4,9,15,null,null,null,null,null,null,14], queries = [2,5,16]
输出：[[2,2],[4,6],[15,-1]]
解释：按下面的描述找出并返回查询的答案：
- 树中小于等于 2 的最大值是 2 ，且大于等于 2 的最小值也是 2 。所以第一个查询的答案是 [2,2] 。
- 树中小于等于 5 的最大值是 4 ，且大于等于 5 的最小值是 6 。所以第二个查询的答案是 [4,6] 。
- 树中小于等于 16 的最大值是 15 ，且大于等于 16 的最小值不存在。所以第三个查询的答案是 [15,-1] 。

我一开始看到题目想都没想，这不直接树上搜索嘛，logn 的搜索时间复杂度加上 n 的遍历时间复杂度，然后提交！超时！！！思考了一会我明白了：题目所给的树并非平衡树，所以当出现很大的数据或者很特殊的大数据时，几乎达到了 n 的时间复杂度，于是得换方法了。既然二叉树无法达到logn 的时间复杂度那么我们肯定下意识的想到了二分查找，题目所给的是二叉搜索树很容易便能将题目中的二叉搜索树转换成一个有序数组。于是本题就迎刃而解了，代码如下： 

class Solution {
public:
    vector<vector<int>> closestNodes(TreeNode* root, vector<int>& queries) {
        multiset<int> ms;
        function<void(TreeNode*)> dfs=[&](TreeNode* root){
            if(!root) return;
            ms.insert(root->val);
            dfs(root->left);
            dfs(root->right);
        };
        dfs(root);
        vector<vector<int>> ans;
        for(int q:queries){
            auto it=ms.upper_bound(q);
            int minq;
            if(it==ms.begin()) minq=-1;
            else minq=*prev(it);
            int maxq;
            it=ms.lower_bound(q);
            if(it==ms.end()) maxq=-1;
            else maxq=*it; 
            ans.push_back({minq,maxq});
        }
        return ans;
    }
};

---

2477. 到达首都的最少油耗 - 力扣（Leetcode）

给你一棵 n 个节点的树（一个无向、连通、无环图），每个节点表示一个城市，编号从 0 到 n - 1 ，且恰好有 n - 1 条路。0 是首都。给你一个二维整数数组 roads ，其中 roads[i] = [ai, bi] ，表示城市 ai 和 bi 之间有一条 双向路 。

每个城市里有一个代表，他们都要去首都参加一个会议。

每座城市里有一辆车。给你一个整数 seats 表示每辆车里面座位的数目。

城市里的代表可以选择乘坐所在城市的车，或者乘坐其他城市的车。相邻城市之间一辆车的油耗是一升汽油。

请你返回到达首都最少需要多少升汽油。

示例 1：

 

输入：roads = [[0,1],[0,2],[0,3]], seats = 5
输出：3
解释：
- 代表 1 直接到达首都，消耗 1 升汽油。
- 代表 2 直接到达首都，消耗 1 升汽油。
- 代表 3 直接到达首都，消耗 1 升汽油。
最少消耗 3 升汽油。

这题当时并未写出来，之后看到各路大佬思路才写出来，对于此题的题解列出以下几个步骤：

1. 此题其实并不需要考虑车的数量，我们可以计算1-n个节点一共只需要 n / seats 辆车所以最终停在0 点的只有这些车，所以此题最大的限制不是车的数量，而是seats的大小
2. 于是我们可以从0点向子树遍历然后利用回溯算得到达此根节点的子树的大小，然后对此根节点的所有子树对根节点贡献值求和，其贡献值就是所有子树到达该根节点所需要的汽油量，需要注意的是汽油的数量如果不是整数必须向上取整。

具体代码如下：

class Solution {
public:
    long long minimumFuelCost(vector<vector<int>>& roads, int seats) {
        //建图
        int n=roads.size()+1;
        vector<int> edge[n];
        for(auto road:roads){
            edge[road[0]].push_back(road[1]);
            edge[road[1]].push_back(road[0]);
        }
        long long res=0; 
        function<int(int, int)> dfs=[&](int sn,int fa){
            int ret=1;
            for(int fn:edge[sn]){
                if(fn!=fa){
                    int t=dfs(fn,sn);
                    res+=(t+seats-1)/seats;
                    ret+=t;
                }
            }
            return ret;
        };
        dfs(0,-1);
        return res; 
    }
};