2023.1.15LeetCode第328场周赛

2535. 数组元素和与数字和的绝对差

思路

分别计算元素和、各位数字和即可

代码

class Solution {
public:
    int differenceOfSum(vector<int>& nums) {
        int a = 0, b = 0;
        for (int x : nums) {
            int t = x;
            a += t;
            while (t) {
                b += t % 10;
                t /= 10;
            }
        }
        return abs(a - b);
    }
};

2536. 子矩阵元素加 1

思路

二维差分模版
定义插入函数

代码

class Solution {
public:
    vector<vector<int>> b;
    
    void ins(int x1, int y1, int x2, int y2, int c) {
        b[x1][y1] += c;
        b[x2 + 1][y1] -= c;
        b[x1][y2 + 1] -= c;
        b[x2 + 1][y2 + 1] += c;
    }
    
    vector<vector<int>> rangeAddQueries(int n, vector<vector<int>>& q) {
        b.resize(n + 2, vector<int>(n + 2));
        for (int i = 0; i < q.size(); i ++ ) {
                ins(q[i][0] + 1, q[i][1] + 1, q[i][2] + 1, q[i][3] + 1, 1);
            }
        vector<vector<int>> a(n, vector<int>(n)); 
        for (int i = 1; i <= n; i ++ )
            for (int j = 1; j <= n; j ++ ) {
                b[i][j] += b[i - 1][j] + b[i][j - 1] - b[i - 1][j - 1];
                a[i - 1][j - 1] = b[i][j];
            }
        return a;
    }
};

2537. 统计好子数组的数目

思路

滑动窗口
用一个数记录当前窗口内的好子数组的数目，窗口越长，越有可能满足条件
对于每一个右端点，求一个最远的左端点，[0, l]间的数都满足结果

代码

class Solution {
public:
    typedef long long ll;

    long long countGood(vector<int>& nums, int k) {
        ll ans = 0;
        int n = nums.size();
        unordered_map<int, ll> cnt;
        ll c = 0;
        for (int l = 0, r = 0; r < n; r ++ ) {
            c += cnt[nums[r]];
            cnt[nums[r]] ++ ;
            while (l < r && c >= k) {
                cnt[nums[l]] -- ;
                c -= cnt[nums[l]];
                l ++ ;
            }
            ans += l;
        }
        return ans;
    }
};

2538. 最大价值和与最小价值和的差值

思路

求树的直径
一个节点作为根节点时，最小价值的路径就是本身，故只用求最大价值的路径
如果分别以每个点作为根节点去搜索会超时
以任意一点作为根节点进行搜索，树种任意一点的最大价值路径只能来源于两个方向，一是向下（选定根节点的反方向），二是向上（根节点的方向）
进行两次搜索求得答案

代码

const int N = 100010;

class Solution {
public:
    typedef long long ll;

    vector<vector<int>> g;
    vector<int> p;
    ll d1[N], d2[N], up[N], pa[N]; //分别表示向下最远，向下第二远，向上最远，向下最远的路径对应的子节点
    int n;
    
    void dfs_d(int u, int fa) { //向下搜索（根节点的反方向）
        for (int i : g[u]) {
            if (i != fa) {
                dfs_d(i, u);
                ll d = d1[i] + p[u];
                if (d > d1[u]) {
                    d2[u] = d1[u];
                    d1[u] = d;
                    pa[u] = i;
                }
                else if (d > d2[u]) d2[u] = d;
            }
        }
    }
    
    void dfs_u(int u, int fa) { //向上搜索（根节点的方向）
        for (int i : g[u]) {
            if (i != fa) {
                if (pa[u] == i) up[i] = max(up[u], d2[u]) + p[i];
                else up[i] = max(up[u], d1[u]) + p[i];
                dfs_u(i, u);
            }
        }
    }
    
    long long maxOutput(int _n, vector<vector<int>>& edges, vector<int>& price) {
        n = _n;
        g.resize(n);
        p = price;
        for (auto e : edges) {
            g[e[0]].push_back(e[1]);
            g[e[1]].push_back(e[0]);
        }
        for (int i = 0; i < n; i ++ ) {
            d1[i] = up[i] = p[i];
        }
        dfs_d(0, -1);
        dfs_u(0, -1);
        ll ans = 0;
        for (int i = 0; i < n; i ++ ) {
            ll x = max(d1[i], up[i]);
            ans = max(ans, x - p[i]);
        }
        return ans;
    }
};