周赛补题

leetcode ：  

第一题https://leetcode.cn/problems/number-of-unequal-triplets-in-array/可以直接暴力

class Solution {
public:
    int unequalTriplets(vector<int>& nums) {
        int sum = 0;
        int n = nums.size();
        
        for(int i = 0; i < n; i ++){
            for(int j = i + 1; j < n; j ++){
                for(int k = j + 1; k < n; k ++){
                    if(nums[i] != nums[j] && nums[i] != nums[k] && nums[j] != nums[k])  sum ++;
                }
            }
        }
        
        return sum;
    }
};

第二题https://leetcode.cn/problems/closest-nodes-queries-in-a-binary-search-tree/description/先遍历一遍树，将值存储起来排序，然后用二分查找答案

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vectorint>> ans;
    vector<int> res;
    
    vectorint>> closestNodes(TreeNode* root, vector<int>& queries) {
        dfs(root);
        sort(res.begin(), res.end());
        
        for(int i = 0; i < queries.size(); i ++){
            vector<int> zhon;
            auto x = upper_bound(res.begin(), res.end(), queries[i]);
            auto y = lower_bound(res.begin(), res.end(), queries[i]);
 
            if(x != res.begin())  zhon.push_back(*prev(x));
            else  zhon.push_back(-1);
           
            if(y != res.end())  zhon.push_back(*y);
            else  zhon.push_back(-1);
            
            ans.push_back(zhon);
        }
        
        return ans;
    }
    
    void dfs(TreeNode* root){
        if(!root)  return ;
        res.push_back(root -> val);
        
        dfs(root -> left);
        dfs(root -> right);
    }
};

第三题https://leetcode.cn/problems/minimum-fuel-cost-to-report-to-the-capital/description/?languageTags=cpp关键在于 seats 的限制，假设车的数量是无限的，每公里消耗一辆车，考虑每条边几辆车

一条边 u→v（设 u 是 v 的父节点）的贡献就是以 v 为根的子树中有几辆车经过了这条边，答案就是所有边的贡献之和。设以 v 为根的子树中共有 sv 个节点，显然至少需要 sv / seats 辆车

class Solution {
public:
    int seats;
    unordered_map<int, vector<int>> adjvex;
    long long res;
 
    long long dfs(int x, int fx){
        long long cur = 0LL;
        for (int y: adjvex[x]){
            if (y == fx){
                continue;
            }
            cur += dfs(y, x);
        }
        if (x != 0){
            cur ++;
            res += (cur + seats - 1) / seats;
        }
        return cur;
    }
 
    long long minimumFuelCost(vectorint>>& roads, int seats) {
        this->seats = seats;
        res = 0LL;
        for (vector<int> & e: roads){
            int x = e[0];
            int y = e[1];
            adjvex[x].push_back(y);
            adjvex[y].push_back(x);
        }
 
        dfs(0, -1);
        return res;
    }
};

acwing : 

第一题https://www.acwing.com/problem/content/4722/用 set 存储自动去重

#include 
using namespace std;
 
int main(){
    int n;
    cin >> n;
    
    set> q;
    
    while(n --){
        string a, b;
        cin >> a >> b;
        
        q.insert({a, b});
    }
    
    cout << q.size() << endl;
    return 0;
}

第二题https://www.acwing.com/problem/content/4723/

将 string 放入栈中去重 

#include 
using namespace std;
 
int main(){
    string res;
    cin >> res;
    
    stack<char> q;
    for(int i = res.size() - 1; i >= 0; i --){
        if(q.empty() || (!q.empty() && q.top() != res[i]))  q.push(res[i]);
        else  q.pop();
    }
    
    while(!q.empty()){
        cout << q.top();
        q.pop();
    }
    
    return 0;
}