第 198 场周赛

换酒问题

class Solution {
public:
    int numWaterBottles(int a, int b) {
        int res = a;
        while (a >= b)
        {
            res += a/b;
            a = a/b+a%b;
        }
        return res;
    }
};

子树中标签相同的节点数

class Solution {
public:
    vector<int> countSubTrees(int n, vector<vector<int>>& edges, string labels) {
        vector<vector<int>> v(n);
        for (auto &e : edges)
        {
            int x = e[0], y = e[1];
            v[x].push_back(y);
            v[y].push_back(x);
        }
        vector<vector<int>> s(n, vector<int>(26));
        
        vector<int> res(n);
        function<void(int,int)> dfs = [&](int x, int pre)
        {
            s[x][labels[x]-'a'] ++;
            for (auto y : v[x])
            {
                if (y == pre) continue;
                dfs(y, x);
                for (int i = 0; i < 26; ++i) s[x][i] += s[y][i];
            }
            res[x] = s[x][labels[x]-'a'];
        };
        
        dfs(0, -1);
        return res;
    }
};

最多的不重叠子字符串

class Solution {
public:
    using pii = pair<int, int>;
    vector<string> maxNumOfSubstrings(string s) {
        int n = s.size();
        const int INF = 1000000000;
        
        vector<vector<int>> pos(26);
        
        vector<int> L(26, INF), R(26, -INF);
        vector<int> cnt(26);
        for (int i = 0; i < n; ++i)
        {
            pos[s[i]-'a'].push_back(i);
            L[s[i]-'a'] = min(L[s[i]-'a'], i);
            R[s[i]-'a'] = max(R[s[i]-'a'], i);
            cnt[s[i]-'a'] ++;
        }
        
        vector<pii> H;
        for (int i = 0; i < 26; ++i)
        {
            if (cnt[i] == 0) continue;
            int x = L[i], y = R[i], tot = cnt[i];
            vector<int> u(26);
            u[i] = 1;
            while (y-x+1 != tot)
            {
                for (int j = 0; j < 26; ++j)
                {
                    if (!u[j] && cnt[j] != 0)
                    {
                        auto it = lower_bound(pos[j].begin(), pos[j].end(), x);
                        if (it != pos[j].end() && *it <= y)
                        {
                            u[j] = 1;
                            tot += cnt[j];
                            x = min(x, L[j]);
                            y = max(y, R[j]);
                        }
                    }
                }
            }
            H.push_back({x, y});
        }
        
        sort(H.begin(), H.end(), [](const pii &a, const pii &b)
             {
                 return abs(a.first-a.second) < abs(b.first-b.second);
             });
        
        vector<string> res;
        vector<int> ok(H.size());
        for (int i = 0; i < H.size(); ++i)
        {
            if (ok[i]) continue;
            auto [x, y] = H[i];
            for (int j = 0; j < H.size(); ++j)
            {
                auto [L, R] = H[j];
                if (L <= x && y <= R) ok[j] = 1;
            }
            res.push_back(s.substr(x, y-x+1));
        }
        return res;
    }
};

找到最接近目标值的函数值

class Solution {
public:
    int closestToTarget(vector<int>& arr, int target) {
        int ans = abs(arr[0] - target);
        vector<int> valid = {arr[0]};
        for (int num: arr) {
            vector<int> validNew = {num};
            ans = min(ans, abs(num - target));
            for (int prev: valid) {
                validNew.push_back(prev & num);
                ans = min(ans, abs((prev & num) - target));
            }
            validNew.erase(unique(validNew.begin(), validNew.end()), validNew.end());
            valid = validNew;
        }
        return ans;
    }
};