头像

wzc1995

ByteDance Ltd. & AcWing




离线:2天前



wzc1995
2天前

题目描述

给你两个整数 mk,以及数据流形式的若干整数。你需要实现一个数据结构,计算这个数据流的 MK 平均值

MK 平均值 按照如下步骤计算:

  1. 如果数据流中的整数少于 m 个,MK 平均值-1,否则将数据流中最后 m 个元素拷贝到一个独立的容器中。
  2. 从这个容器中删除最小的 k 个数和最大的 k 个数。
  3. 计算剩余元素的平均值,并 向下取整到最近的整数

请你实现 MKAverage 类:

  • MKAverage(int m, int k) 用一个空的数据流和两个整数 mk 初始化 MKAverage 对象。
  • void addElement(int num) 往数据流中插入一个新的元素 num
  • int calculateMKAverage() 对当前的数据流计算并返回 MK 平均数,结果需 向下取整到最近的整数

样例

输入:
[
    "MKAverage",
    "addElement", "addElement",
    "calculateMKAverage",
    "addElement",
    "calculateMKAverage",
    "addElement", "addElement", "addElement",
    "calculateMKAverage"
]
[
    [3, 1],
    [3], [1],
    [],
    [10],
    [],
    [5], [5], [5],
    []
]
输出:
[null, null, null, -1, null, 3, null, null, null, 5]

解释:
MKAverage obj = new MKAverage(3, 1); 
obj.addElement(3);        // 当前元素为 [3]
obj.addElement(1);        // 当前元素为 [3,1]
obj.calculateMKAverage(); // 返回 -1,因为 m = 3,但数据流中只有 2 个元素
obj.addElement(10);       // 当前元素为 [3,1,10]
obj.calculateMKAverage(); // 最后 3 个元素为 [3,1,10]
                          // 删除最小以及最大的 1 个元素后,容器为 [3]
                          // [3] 的平均值等于 3/1 = 3,故返回 3
obj.addElement(5);        // 当前元素为 [3,1,10,5]
obj.addElement(5);        // 当前元素为 [3,1,10,5,5]
obj.addElement(5);        // 当前元素为 [3,1,10,5,5,5]
obj.calculateMKAverage(); // 最后 3 个元素为 [5,5,5]
                          // 删除最小以及最大的 1 个元素后,容器为 [5]
                          // [5] 的平均值等于 5/1 = 5,故返回 5

限制

  • 3 <= m <= 10^5
  • 1 <= k*2 < m
  • 1 <= num <= 10^5
  • addElementcalculateMKAverage 总操作次数不超过 10^5 次。

算法1

(二分,树状数组) 插入 $O(\log S)$;查询 $O(\log^2 S)$
  1. 维护两个树状数组 $f$ 和 $g$。其中 $f(i)$ 维护数字 $i$ 出现次数的前缀和,$g(i)$ 维护数字 $i$ 累加的前缀和。维护总和 $sum$。
  2. 插入一个数字 $x$ 时,更新树状数组 $f(x) + 1$,$g(x) + x$。
  3. 查询时,通过树状数组,二分查询第 $k$ 个与第 $m - k$ 个所在的数字,并根据 $g$ 求出最小的 $k$ 个数字与最大的 $k$ 个数字之和。

时间复杂度

  • 插入时,更新树状数组,时间复杂度为 $O(\log S)$。其中 $S$ 为最大的数字。
  • 查询时,二分第 $k$ 个与第 $m - k$ 个数字,二分过程每次查询需要 $O(\log S)$ 的时间,故单次查询的总时间为 $O(\log^2 S)$。

空间复杂度

  • 需要 $O(m + S)$ 的空间存储数据流队列,以及两个树状数组。

C++ 代码

#define LL long long
#define NUM 100000

class MKAverage {
private:
    queue<int> q;
    LL f[NUM + 1], g[NUM + 1], sum;
    int m, k;

    void add(LL *f, int x, int y) {
        for (; x <= NUM; x += x & -x)
            f[x] += y;
    }

    LL query(LL *f, int x) {
        LL tot = 0;
        for (; x; x -= x & -x)
            tot += f[x];
        return tot;
    }

public:
    MKAverage(int m, int k) {
        memset(f, 0, sizeof(f));
        memset(g, 0, sizeof(g));
        sum = 0;
        this->m = m;
        this->k = k;
    }

    void addElement(int num) {
        q.push(num);
        sum += num;
        add(f, num, 1);
        add(g, num, num);

        if (q.size() > m) {
            sum -= q.front();
            add(f, q.front(), -1);
            add(g, q.front(), -q.front());
            q.pop();
        }
    }

    LL left() {
        int l = 1, r = NUM;

        while (l < r) {
            int mid = (l + r) >> 1;
            if (query(f, mid) < k) l = mid + 1;
            else r = mid;
        }

        return query(g, l) - (query(f, l) - k) * l;
    }

    LL right() {
        int l = 1, r = NUM;

        while (l < r) {
            int mid = (l + r) >> 1;
            if (query(f, mid) < m - k) l = mid + 1;
            else r = mid;
        }

        return sum - (query(g, l) - (query(f, l) - (m - k)) * l);
    }

    int calculateMKAverage() {
        if (q.size() < m) return -1;
        return (sum - left() - right()) / (m - k - k);
    }
};

/**
 * Your MKAverage object will be instantiated and called as such:
 * MKAverage* obj = new MKAverage(m, k);
 * obj->addElement(num);
 * int param_2 = obj->calculateMKAverage();
 */

算法2

(多重集/平衡树) 插入 $O(\log m)$;查询 $O(1)$
  1. 维护三个多重集:L 记录最小的 k 个数字,M 记录中间的 m - k - k 个数字,R 记录最大的 k 个数字。维护 M 中数字的和 sum
  2. 插入一个数字时,首先插入 L。如果 L 的大小超过了 k,则转移 L 中最大的数字到 M。如果 M 的大小超过了 m - k - k,则转移 M 中最大的数字到 R
  3. 这样 R 的大小为 k 或者 k + 1,所以删除时,如果删除了 L 中的数字,则需要从 R 中取出一个最小的数字放到 M 中,然后再从 M 中取出一个最小的数字放到 L 中。删除了 M 或者 R 中的元素同理。

时间复杂度

  • 每次插入需要调整若干个多重集,故插入的时间复杂度为 $O(\log n)$。
  • 查询时直接使用 sum 计算答案,故查询的时间复杂度为常数。

空间复杂度

  • 需要 $O(m)$ 的额外空间存储数据流队列和三个多重集。

C++ 代码

#define LL long long

class MKAverage {
private:
    queue<int> q;
    int m, k;
    LL sum;

    multiset<int> L, M, R;

public:
    MKAverage(int m, int k) {
        sum = 0;
        this->m = m;
        this->k = k;
    }

    void transL2M() {
        int x = *L.rbegin();
        L.erase(L.find(x));
        M.insert(x);
        sum += x;
    }

    void transM2R() {
        int x = *M.rbegin();
        M.erase(M.find(x));
        R.insert(x);
        sum -= x;
    }

    void transR2M() {
        int x = *R.begin();
        R.erase(R.find(x));
        M.insert(x);
        sum += x;
    }

    void transM2L() {
        int x = *M.begin();
        M.erase(M.find(x));
        L.insert(x);
        sum -= x;
    }

    void insert(int num) {
        L.insert(num);
        if (L.size() > k) transL2M();
        if (M.size() > m - k - k) transM2R();
    }

    void erase(int num) {
        if (L.find(num) != L.end()) {
            L.erase(L.find(num));
            transR2M();
            transM2L();
        } else if (M.find(num) != M.end()) {
            M.erase(M.find(num));
            sum -= num;
            transR2M();
        } else {
            R.erase(R.find(num));
        }
    }

    void addElement(int num) {
        q.push(num);
        insert(num);

        if (q.size() > m) {
            erase(q.front());
            q.pop();
        }
    }

    int calculateMKAverage() {
        if (q.size() < m) return -1;
        return sum / (m - k - k);
    }
};

/**
 * Your MKAverage object will be instantiated and called as such:
 * MKAverage* obj = new MKAverage(m, k);
 * obj->addElement(num);
 * int param_2 = obj->calculateMKAverage();
 */



wzc1995
2天前

题目描述

给你一个长度为 n3 跑道道路,它总共包含 n + 1,编号为 0n。一只青蛙从 0 号点第二条跑道 出发,它想要跳到点 n 处。然而道路上可能有一些障碍。

给你一个长度为 n + 1 的数组 obstacles,其中 obstacles[i]取值范围从 0 到 3)表示在点 i 处的 obstacles[i] 跑道上有一个障碍。如果 obstacles[i] == 0,那么点 i 处没有障碍。任何一个点的三条跑道中 最多有一个 障碍。

  • 比方说,如果 obstacles[2] == 1,那么说明在点 2 处跑道 1 有障碍。

这只青蛙从点 i 跳到点 i + 1 且跑道不变的前提是点 i + 1 的同一跑道上没有障碍。为了躲避障碍,这只青蛙也可以在 同一个 点处 侧跳另外一条 跑道(这两条跑道可以不相邻),但前提是跳过去的跑道该点处没有障碍。

  • 比方说,这只青蛙可以从点 3 处的跑道 3 跳到点 3 处的跑道 1

这只青蛙从点 0 处跑道 2 出发,并想到达点 n 处的 任一跑道,请你返回 最少侧跳次数

注意:点 0 处和点 n 处的任一跑道都不会有障碍。

样例

ic234-q3-ex1.png

输入:obstacles = [0,1,2,3,0]
输出:2 
解释:最优方案如上图箭头所示。总共有 2 次侧跳(红色箭头)。
注意,这只青蛙只有当侧跳时才可以跳过障碍(如上图点 2 处所示)。

ic234-q3-ex2.png

输入:obstacles = [0,1,1,3,3,0]
输出:0
解释:跑道 2 没有任何障碍,所以不需要任何侧跳。

ic234-q3-ex3.png

输入:obstacles = [0,2,1,0,3,0]
输出:2
解释:最优方案如上图所示。总共有 2 次侧跳。

限制

  • obstacles.length == n + 1
  • 1 <= n <= 5 * 10^5
  • 0 <= obstacles[i] <= 3
  • obstacles[0] == obstacles[n] == 0

算法

(动态规划) $O(n)$
  1. 设状态 $f(i, j)$ 表示在点 $i$ 的跑道 $j$ 时的最少侧跳次数,其中 $i$ 的取值范围为 $[0, n]$,$j$ 的取值范围为 $[0, 2]$。
  2. 初始时,$f(0, 1) = 0$,$f(0, 0) = f(0, 2) = 2$,其余待定。
  3. 转移时,对于每个点 $i$,
    • 如果点 $i$ 没有障碍,则 $f(i, j) = f(i - 1, j)$。考虑侧跳,$f(i, j) = \min(f(i, j), m + 1)$,其中 $m$ 为 $f(i, j)$ 中的最小值。
    • 如果点 $i$ 有障碍,假设障碍为 $j_0$。则 $f(i, j_0) = +\infty$,其余 $j \neq j_0$,有 $f(i, j) = f(i - 1, j)$。考虑侧跳,当 $j \neq j_0$ 时,$f(i, j) = \min(f(i, j), m + 1)$,其中 $m$ 为 $f(i, j)$ 中的最小值。
  4. 最终答案为 $\min(f(n, 0), f(n, 1), f(n, 2))$。

时间复杂度

  • 状态数为 $O(n)$,转移时间为常数,故总时间复杂度为 $O(n)$。

空间复杂度

  • 可以将第一维优化掉,故总空间复杂度为常数。

C++ 代码

class Solution {
public:
    int minSideJumps(vector<int>& obstacles) {
        const int n = obstacles.size() - 1;
        const int INF = 1000000000;
        vector<int> f(3, INF);

        f[1] = 0;
        f[0] = f[2] = 1;

        for (int i = 1; i <= n; i++) {
            int mi = INF;
            for (int j = 0; j < 3; j++)
                if (j != obstacles[i] - 1)
                    mi = min(mi, f[j]);

            for (int j = 0; j < 3; j++)
                if (j != obstacles[i] - 1)
                    f[j] = min(f[j], mi + 1);
                else
                    f[j] = INF;
        }

        return min(f[0], min(f[1], f[2]));
    }
};



wzc1995
2天前

题目描述

共有 n 名小伙伴一起做游戏。小伙伴们围成一圈,按 顺时针顺序1n 编号。确切地说,从第 i 名小伙伴顺时针移动一位会到达第 (i+1) 名小伙伴的位置,其中 1 <= i < n,从第 n 名小伙伴顺时针移动一位会回到第 1 名小伙伴的位置。

游戏遵循如下规则:

  1. 从第 1 名小伙伴所在位置 开始
  2. 沿着顺时针方向数 k 名小伙伴,计数时需要 包含 起始时的那位小伙伴。逐个绕圈进行计数,一些小伙伴可能会被数过不止一次。
  3. 你数到的最后一名小伙伴需要离开圈子,并视作输掉游戏。
  4. 如果圈子中仍然有不止一名小伙伴,从刚刚输掉的小伙伴的 顺时针下一位 小伙伴 开始,回到步骤 2 继续执行。
  5. 否则,圈子中最后一名小伙伴赢得游戏。

给你参与游戏的小伙伴总数 n,和一个整数 k,返回游戏的获胜者。

样例

ic234-q2-ex11.png

输入:n = 5, k = 2
输出:3
解释:游戏运行步骤如下:
1) 从小伙伴 1 开始。
2) 顺时针数 2 名小伙伴,也就是小伙伴 1 和 2。
3) 小伙伴 2 离开圈子。下一次从小伙伴 3 开始。
4) 顺时针数 2 名小伙伴,也就是小伙伴 3 和 4。
5) 小伙伴 4 离开圈子。下一次从小伙伴 5 开始。
6) 顺时针数 2 名小伙伴,也就是小伙伴 5 和 1。
7) 小伙伴 1 离开圈子。下一次从小伙伴 3 开始。
8) 顺时针数 2 名小伙伴,也就是小伙伴 3 和 5。
9) 小伙伴 5 离开圈子。只剩下小伙伴 3 。所以小伙伴 3 是游戏的获胜者。
输入:n = 6, k = 5
输出:1
解释:小伙伴离开圈子的顺序:5、4、6、2、3 。小伙伴 1 是游戏的获胜者。

限制

  • 1 <= k <= n <= 500

算法

(数学,约瑟夫环问题) $O(n)$
  1. n 个人的编号看做 0n - 1
  2. 假设 k < n,则第一轮会淘汰掉编号为 k - 1 的人。剩下的人编号为 0, 1, ..., k - 2, k, k + 1, ... n - 1,下一轮游戏则会从 k 开始。我们进行重编号,即 k 变成 0k + 1 变为 1,以此类推。之前编号小于 k 的,假设为 x,则编号变为 n - k + x。如果 k >= n 也同理,当游戏人数为 n 时,游戏后,编号会变为 (x - k + n) % n
  3. 已知最后一轮游戏,只有一位玩家会被淘汰(获胜),编号为 0。那根据上述的递推公式,倒数第二轮开始前,在最后一轮被淘汰的游戏者的编号会变为 (0 + k) % 2。继续往回退,每次编号都会变为上一次的编号,加上 k,然后模游戏的人数。
  4. 一直到第一轮游戏前,得到最后一位玩家的初始编号。

时间复杂度

  • 1n 递推,总时间复杂度为 $O(n)$。

空间复杂度

  • 仅需要常数的额外空间。

C++ 代码

class Solution {
public:
    int findTheWinner(int n, int k) {
        int ans = 0;

        for (int i = 2; i <= n; i++)
            ans = (ans + k) % i;

        return ans + 1;
    }
};



wzc1995
2天前

题目描述

已知函数 signFunc(x) 将会根据 x 的正负返回特定值:

  • 如果 x 是正数,返回 1
  • 如果 x 是负数,返回 -1
  • 如果 x 是等于 0,返回 0

给你一个整数数组 nums。令 product 为数组 nums 中所有元素值的乘积。

返回 signFunc(product)

样例

输入:nums = [-1,-2,-3,-4,3,2,1]
输出:1
解释:数组中所有值的乘积是 144,且 signFunc(144) = 1
输入:nums = [1,5,0,2,-3]
输出:0
解释:数组中所有值的乘积是 0,且 signFunc(0) = 0
输入:nums = [-1,1,-1,1,-1]
输出:-1
解释:数组中所有值的乘积是 -1,且 signFunc(-1) = -1

限制

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

算法

(数学) $O(n)$
  1. signFunc 满足 signFunc(x * y) = signFunc(signFunc(x) * signFunc(y)),所以仅需单独计算每个的值,最后输出答案。

时间复杂度

  • 遍历数组一次,故总时间复杂度为 $O(n)$。

空间复杂度

  • 仅需要常数的额外空间。

C++ 代码

class Solution {
public:
    int arraySign(vector<int>& nums) {
        int ans = 1;
        for (int x : nums) {
            if (x == 0) return 0;
            if (x < 0) ans = -ans;
        }

        return ans;
    }
};



wzc1995
7天前

题目描述

给你一个由正整数组成的数组 nums

数字序列的 最大公约数 定义为序列中所有整数的共有约数中的最大整数。

例如,序列 [4,6,16] 的最大公约数是 2
数组的一个 子序列 本质是一个序列,可以通过删除数组中的某些元素(或者不删除)得到。

例如,[2,5,10][1,2,1,2,4,1,5,10] 的一个子序列。
计算并返回 nums 的所有 非空 子序列中 不同 最大公约数的 数目

样例

image-1.png

输入:nums = [6,10,3]
输出:5
解释:上图显示了所有的非空子序列与各自的最大公约数。
不同的最大公约数为 6 、10 、3 、2 和 1。
输入:nums = [5,15,40,5,6]
输出:7

限制

  • 1 <= nums.length <= 10^5
  • 1 <= nums[i] <= 2 * 10^5

算法

(暴力枚举) $O(n + m \log^2 m)$
  1. 使用一个布尔数组记录数字是否出现过。假设 $m$ 为出现过的最大的数字。
  2. 从 1 开始枚举约数直到 $m$。对于每个约数 $i$,如果所有是 $i$ 的倍数的数字的最大公约数为 $i$,则 $i$ 必定是这些数字构成的子序列的最大公约数。

时间复杂度

  • 初始化数字是否出现过需要 $O(n + m)$ 的时间。
  • 枚举的时间最多为 $m + m / 2 + m / 3 + … + 1 = O(m \log m)$,求最大公约数的时间复杂度为 $O(\log m)$。
  • 故总时间复杂度为 $O(n + m \log^2 m)$。

空间复杂度

  • 需要 $O(m)$ 的额外空间存储数字是否被使用。

C++ 代码

class Solution {
public:
    int countDifferentSubsequenceGCDs(vector<int>& nums) {
        const int M = 200000;
        vector<bool> seen(M + 1, false);
        int m = 0;
        for (int x : nums) {
            seen[x] = true;
            if (m < x) m = x;
        }

        int ans = 0;
        for (int i = 1; i <= m; i++) {
            int g = 0;
            for (int j = i; j <= m && g != i; j += i)
                if (seen[j])
                    g = __gcd(g, j);

            if (g == i)
                ans++;
        }

        return ans;
    }
};



wzc1995
8天前

题目描述

给你两个正整数数组 nums1nums2,数组的长度都是 n

数组 nums1nums2绝对差值和 定义为所有 |nums1[i] - nums2[i]|0 <= i < n)的 总和下标从 0 开始)。

你可以选用 nums1 中的 任意一个 元素来替换 nums1 中的 至多 一个元素,以 最小化 绝对差值和。

在替换数组 nums1 中最多一个元素 之后,返回最小绝对差值和。因为答案可能很大,所以需要对 10^9 + 7 取余 后返回。

|x| 定义为:

  • 如果 x >= 0,值为 x,或者
  • 如果 x <= 0,值为 -x

样例

输入:nums1 = [1,7,5], nums2 = [2,3,5]
输出:3
解释:有两种可能的最优方案:
- 将第二个元素替换为第一个元素:[1,7,5] => [1,1,5],或者
- 将第二个元素替换为第三个元素:[1,7,5] => [1,5,5]。
两种方案的绝对差值和都是 |1-2| + (|1-3| 或者 |5-3|) + |5-5| = 3。
输入:nums1 = [2,4,6,8,10], nums2 = [2,4,6,8,10]
输出:0
解释:nums1 和 nums2 相等,所以不用替换元素。绝对差值和为 0。
输入:nums1 = [1,10,4,4,2,7], nums2 = [9,3,5,1,7,4]
输出:20
解释:将第一个元素替换为第二个元素:[1,10,4,4,2,7] => [10,10,4,4,2,7]
绝对差值和为 |10-9| + |10-3| + |4-5| + |4-1| + |2-7| + |7-4| = 20。

限制

  • n == nums1.length
  • n == nums2.length
  • 1 <= n <= 10^5
  • 1 <= nums1[i], nums2[i] <= 10^5

算法

(二分) $O(n \log n)$
  1. 遍历数组一次计算出不改变数组的情况下的答案。
  2. nums1 拷贝一份,从小到大排序。
  3. 再次遍历数组,遍历时,尝试替换 $i$ 位置的元素为 $nums1$ 中最接近 $nums2(i)$ 的元素。这里可以通过二分进行检索。然后更新答案。

时间复杂度

  • 排序的时间复杂度为 $O(n \log n)$。
  • 每个位置二分,时间复杂度为 $O(\log n)$。
  • 故总时间复杂度为 $O(n \log n)$。

空间复杂度

  • 需要 $O(n)$ 的额外空间存储临时数组。

C++ 代码

#define LL long long

class Solution {
public:
    int minAbsoluteSumDiff(vector<int>& nums1, vector<int>& nums2) {
        const int mod = 1000000007;
        const int n = nums1.size();

        LL res = 0;
        vector<int> s(n);
        for (int i = 0; i < n; i++) {
            res += abs(nums1[i] - nums2[i]);
            s[i] = nums1[i];
        }

        sort(s.begin(), s.end());

        LL ans = res;
        for (int i = 0; i < n; i++) {
            int l = 0, r = n - 1; 
            while (l < r) {
                int mid = (l + r) >> 1;
                if (nums2[i] <= s[mid]) r = mid;
                else l = mid + 1;
            }
            ans = min(ans, 
                res - abs(nums1[i] - nums2[i]) + abs(s[l] - nums2[i]));
            if (l > 0)
                ans = min(ans,
                    res - abs(nums1[i] - nums2[i]) + abs(s[l - 1] - nums2[i]));
        }

        return ans % mod;
    }
};



wzc1995
8天前

题目描述

给你用户在 LeetCode 的操作日志,和一个整数 k。日志用一个二维整数数组 logs 表示,其中每个 logs[i] = [ID_i, time_i] 表示 ID 为 ID_i 的用户在 time_i 分钟时执行了某个操作。

多个用户 可以同时执行操作,单个用户可以在同一分钟内执行 多个操作

指定用户的 用户活跃分钟数(user active minutes,UAM) 定义为用户对 LeetCode 执行操作的 唯一分钟数。即使一分钟内执行多个操作,也只能按一分钟计数。

请你统计用户活跃分钟数的分布情况,统计结果是一个长度为 k下标从 1 开始计数 的数组 answer,对于每个 j1 <= j <= k),answer[j] 表示 用户活跃分钟数 等于 j 的用户数。

返回上面描述的答案数组 answer

样例

输入:logs = [[0,5],[1,2],[0,2],[0,5],[1,3]], k = 5
输出:[0,2,0,0,0]
解释:
ID=0 的用户执行操作的分钟分别是:5 、2 和 5。因此,该用户的用户活跃分钟数为 2(分钟 5 只计数一次)。
ID=1 的用户执行操作的分钟分别是:2 和 3。因此,该用户的用户活跃分钟数为 2。
2 个用户的用户活跃分钟数都是 2,answer[2] 为 2,其余 answer[j] 的值都是 0。
输入:logs = [[1,1],[2,2],[2,3]], k = 4
输出:[1,1,0,0]
解释:
ID=1 的用户仅在分钟 1 执行单个操作。因此,该用户的用户活跃分钟数为 1。
ID=2 的用户执行操作的分钟分别是:2 和 3。因此,该用户的用户活跃分钟数为 2。
1 个用户的用户活跃分钟数是 1 ,1 个用户的用户活跃分钟数是 2。
因此,answer[1] = 1,answer[2] = 1,其余的值都是 0。

限制

  • 1 <= logs.length <= 10^4
  • 0 <= ID_i <= 10^9
  • 1 <= time_i <= 10^5
  • k 的取值范围是 [用户的最大用户活跃分钟数, 10^5]

算法

(哈希表) $O(n)$
  1. 将每条日志存储哈希表,哈希表的 key 为用户 ID,值为一个无重复的集合。
  2. 最后遍历哈希表,累计每个用户的访问集合的 size

时间复杂度

  • 每条日志存储哈希表的时间为常数,最后遍历一次哈希表。
  • 故总时间复杂度为 $O(n)$。

空间复杂度

  • 需要 $O(n)$ 的额外空间存储哈希表。

C++ 代码

class Solution {
public:
    vector<int> findingUsersActiveMinutes(vector<vector<int>>& logs, int k) {
        vector<int> ans(k, 0);
        unordered_map<int, unordered_set<int>> seen;

        for (const auto &v : logs)
            seen[v[0]].insert(v[1]);

        for (const auto &[_, v] : seen)
            ans[v.size() - 1]++;

        return ans;
    }
};



wzc1995
8天前

题目描述

句子 是一个单词列表,列表中的单词之间用单个空格隔开,且不存在前导或尾随空格。每个单词仅由大小写英文字母组成(不含标点符号)。

  • 例如,"Hello World""HELLO""hello world hello world" 都是句子。

给你一个句子 s 和一个整数 k,请你将 s 截断,使截断后的句子仅含 k 个单词。返回 截断 s 后得到的句子。

样例

输入:s = "Hello how are you Contestant", k = 4
输出:"Hello how are you"
解释:
s 中的单词为 ["Hello", "how" "are", "you", "Contestant"]。
前 4 个单词为 ["Hello", "how", "are", "you"]。
因此,应当返回 "Hello how are you"。
输入:s = "What is the solution to this problem", k = 4
输出:"What is the solution"
解释:
s 中的单词为 ["What", "is" "the", "solution", "to", "this", "problem"]。
前 4 个单词为 ["What", "is", "the", "solution"]。
因此,应当返回 "What is the solution"。
输入:s = "chopper is not a tanuki", k = 5
输出:"chopper is not a tanuki"

限制

  • 1 <= s.length <= 500
  • k 的取值范围是 [1, s 中单词的数目]。
  • s 仅由大小写英文字母和空格组成。
  • s 中的单词之间由单个空格隔开。
  • 不存在前导或尾随空格。

算法

(模拟) $O(n)$
  1. 按照题目描述模拟。
  2. 每遇到一个空格,就将 $k$ 减一。如果 $k$ 被减为了 0,则直接返回字符串的当前前缀。

时间复杂度

  • 最多遍历一次字符串,故时间复杂度为 $O(n)$。

空间复杂度

  • 需要 $O(n)$ 的额外空间存储答案。

C++ 代码

class Solution {
public:
    string truncateSentence(string s, int k) {
        const int n = s.size();

        for (int i = 0; i < n; i++) {
            if (s[i] != ' ') continue;
            k--;
            if (k == 0)
                return s.substr(0, i);
        }

        return s;
    }
};



wzc1995
8天前

题目描述

有一个甜甜圈商店,每批次都烤 batchSize 个甜甜圈。这个店铺有个规则,就是在烤一批新的甜甜圈时,之前 所有 甜甜圈都必须已经全部销售完毕。给你一个整数 batchSize 和一个整数数组 groups,数组中的每个整数都代表一批前来购买甜甜圈的顾客,其中 groups[i] 表示这一批顾客的人数。每一位顾客都恰好只要一个甜甜圈。

当有一批顾客来到商店时,他们所有人都必须在下一批顾客来之前购买完甜甜圈。如果一批顾客中第一位顾客得到的甜甜圈不是上一组剩下的,那么这一组人都会很开心。

你可以随意安排每批顾客到来的顺序。请你返回在此前提下,最多 有多少组人会感到开心。

样例

输入:batchSize = 3, groups = [1,2,3,4,5,6]
输出:4
解释:你可以将这些批次的顾客顺序安排为 [6,2,4,5,1,3]。
那么第 1,2,4,6 组都会感到开心。
输入:batchSize = 4, groups = [1,3,2,5,2,2,1,6]
输出:4

限制

  • 1 <= batchSize <= 9
  • 1 <= groups.length <= 30
  • 1 <= groups[i] <= 10^9

算法

(状态压缩动态规划) $O((n / m)^m \cdot m)$
  1. 每个组中的人数在模去 $batchSize$ 后才有意义。统计出 $0$ 到 $batchSize$ 中,每一种余数出现的次数 $fre(i)$。显然 $fre(0)$ 可以直接加入到最终的答案中,接下来只考虑 $fre(1)$ 到 $fre(batchSize - 1)$。
  2. 定义动态规划的状态为 $f(mask)$ 表示,当前使用的 $fre$ 的状态为 $mask$ 时,最多有多少次转移时的余数为 0。
  3. 使用记忆化搜索,对于当前状态 $mask$,如果对应的 $fre(i) > 0$,则可以从 $fre(i) - 1$ 对应的 $mask_0$ 中转移。如果 $mask_0$ 的余数为 0,则转移 $f(mask) = \max(f(mask), f(mask_0) + 1)$。否则转移,$f(mask) = \max(f(mask), f(mask_0))$。
  4. 最终答案为 $solve(mask) + fre(0)$。
  5. 接下来需要分析如何从 $fre$ 数组映射到一个整数值状态 $mask$。(这里忽略 $fre(0)$)
  6. 抽象来看,我们要将一个数组映射到一个整数。我们可以规定每一位的权重 $w$。即,$w(1) = 1$,$w(i) = w(i - 1) * (1 + fre(i - 1))$。
  7. 正映射:$mask = fre(1) * w(1) + fre(2) * w(2) + \dots + fre(m - 1) * w(m - 1)$。
  8. 逆映射:$fre(i) = mask \text{ mod } w(i + 1) / w(i)$。

时间复杂度

  • 动态规划最多有 $O((n / m)^m)$ 个状态,每个状态需要 $O(m)$ 的时间转移,故总时间复杂度为 $O((n / m)^m \cdot m)$。其中 $m$ 为 $batchSize$。

空间复杂度

  • 需要 $O((n / m)^m)$ 的额外空间存储状态。

C++ 代码

class Solution {
private:
    vector<int> w, f;

    int solve(int mask, int r, int m) {
        if (f[mask] != -1)
            return f[mask];

        int res = 0;
        for (int i = 1; i < m; i++) {
            if (mask % w[i + 1] / w[i] == 0) continue;

            int t = solve(mask - w[i], (r - i + m) % m, m);
            if (r == i) res = max(res, t + 1);
            else res = max(res, t);
        }

        return f[mask] = res;
    }

public:
    int maxHappyGroups(int batchSize, vector<int>& groups) {
        vector<int> fre(batchSize, 0);

        int r = 0;
        for (int g : groups) {
            fre[g % batchSize]++;
            r = (r + g) % batchSize;
        }

        w.resize(batchSize + 1);
        w[1] = 1;
        int mask = 0;
        for (int i = 2; i < batchSize + 1; i++) {
            w[i] = w[i - 1] * (fre[i - 1] + 1);
            mask += fre[i - 1] * w[i - 1];
        }

        f.resize(w[batchSize], -1);
        return solve(mask, r, batchSize) + fre[0];
    }
};



wzc1995
8天前

题目描述

给你一个数组 nums,数组中只包含非负整数。定义 rev(x) 的值为将整数 x 各个数字位反转得到的结果。比方说 rev(123) = 321rev(120) = 21。我们称满足下面条件的下标对 (i, j)好的

  • 0 <= i < j < nums.length
  • nums[i] + rev(nums[j]) == nums[j] + rev(nums[i])

请你返回好下标对的数目。由于结果可能会很大,请将结果对 10^9 + 7 取余 后返回。

样例

输入:nums = [42,11,1,97]
输出:2
解释:两个坐标对为:
 - (0,3):42 + rev(97) = 42 + 79 = 121, 97 + rev(42) = 97 + 24 = 121 。
 - (1,2):11 + rev(1) = 11 + 1 = 12, 1 + rev(11) = 1 + 11 = 12 。
输入:nums = [13,10,35,24,76]
输出:4

限制

  • 1 <= nums.length <= 10^5
  • 0 <= nums[i] <= 10^9

算法

(哈希表) $O(n \log S)$
  1. 将条件进行等价转换,即 nums[i] - rev(nums[i]) == nums[j] - rev(nums[j])
  2. 通过哈希表计算出每个数字对应的 x - rev(x) 的值。
  3. 枚举哈希表,每个 key 贡献的答案为 value * (value - 1) / 2

时间复杂度

  • 构建哈希表的时间复杂度为 $O(n \log S)$。其中 $S$ 为最大的数字。
  • 求答案仅需要 $O(n)$ 的时间,故总时间复杂度为 $O(n \log S)$。

空间复杂度

  • 需要 $O(n)$ 的额外空间存储哈希表。

C++ 代码

#define LL long long

class Solution {
private:
    int rev(int x) {
        queue<int> q;
        int res = 0;
        while (x) {
            q.push(x % 10);
            x /= 10;
        }

        while (!q.empty()) {
            res = res * 10 + q.front();
            q.pop();
        }

        return res;
    }

public:
    int countNicePairs(vector<int>& nums) {
        unordered_map<int, int> seen;
        for (int x : nums)
            seen[x - rev(x)]++;

        const int mod = 1000000007;
        int ans = 0;
        for (const auto &[_, v] : seen)
            ans = (ans + (LL)(v) * (v - 1) / 2) % mod;

        return ans;
    }
};