头像

wzc1995

北京大学




离线:1天前


最近来访(4943)
用户头像
封禁用户
用户头像
howerguss
用户头像
qinxiaohaier
用户头像
咕哒.
用户头像
一万小时定律
用户头像
洗衣机里的纸巾
用户头像
内田有纪
用户头像
JcWing
用户头像
抓住努力的尾巴
用户头像
南街戏子
用户头像
Troiy
用户头像
laidui
用户头像
Dream_zsh
用户头像
2022fjq
用户头像
sailor
用户头像
zhouyishan
用户头像
Spare
用户头像
wyy20188
用户头像
肖肖_123
用户头像
ᐛ妙蛙


wzc1995
2天前

题目描述

给你一个有向图,图中有 n 个节点,节点编号从 0n - 1,其中每个节点都 恰有一条 出边。

图由一个下标从 0 开始、长度为 n 的整数数组 edges 表示,其中 edges[i] 表示存在一条从节点 i 到节点 edges[i]有向 边。

节点 i边积分 定义为:所有存在一条指向节点 i 的边的节点的 编号 总和。

返回 边积分 最高的节点。如果多个节点的 边积分 相同,返回编号 最小 的那个。

样例

image-20220620195403-1.png

输入:edges = [1,0,0,0,0,7,7,5]
输出:7
解释:
- 节点 1、2、3 和 4 都有指向节点 0 的边,节点 0 的边积分等于 1 + 2 + 3 + 4 = 10。
- 节点 0 有一条指向节点 1 的边,节点 1 的边积分等于 0。
- 节点 7 有一条指向节点 5 的边,节点 5 的边积分等于 7。
- 节点 5 和 6 都有指向节点 7 的边,节点 7 的边积分等于 5 + 6 = 11。
节点 7 的边积分最高,所以返回 7。

image-20220620200212-3.png

输入:edges = [2,0,0,2]
输出:0
解释:
- 节点 1 和 2 都有指向节点 0 的边,节点 0 的边积分等于 1 + 2 = 3。
- 节点 0 和 3 都有指向节点 2 的边,节点 2 的边积分等于 0 + 3 = 3。
节点 0 和 2 的边积分都是 3。由于节点 0 的编号更小,返回 0。

限制

  • n == edges.length
  • 2 <= n <= 10^5
  • 0 <= edges[i] < n
  • edges[i] != i

算法

(模拟) $O(n)$
  1. 通过 edges 数组计算出每个点的积分,然后找到积分最大且编号尽量小的点。

时间复杂度

  • 遍历 edges 数组一次,然后找到目标点,时间复杂度为 $O(n)$。

空间复杂度

  • 需要 $O(n)$ 的额外空间存储点的积分。

C++ 代码

#define LL long long

class Solution {
public:
    int edgeScore(vector<int>& edges) {
        const int n = edges.size();

        vector<LL> s(n, 0);

        for (int i = 0; i < n; i++)
            s[edges[i]] += i;

        int ans = 0;

        for (int i = 1; i < n; i++)
            if (s[i] > s[ans])
                ans = i;

        return ans;
    }
};



wzc1995
2天前

题目描述

给你一个大小为 n x n 的整数矩阵 grid

生成一个大小为 (n - 2) x (n - 2) 的整数矩阵 maxLocal,并满足:

  • maxLocal[i][j] 等于 grid 中以 i + 1 行和 j + 1 列为中心的 3 x 3 矩阵中的 最大值

换句话说,我们希望找出 grid 中每个 3 x 3 矩阵中的最大值。

返回生成的矩阵。

样例

ex1.png

输入:grid = [[9,9,8,1],[5,6,2,6],[8,2,6,4],[6,2,2,2]]
输出:[[9,9],[8,6]]
解释:原矩阵和生成的矩阵如上图所示。
注意,生成的矩阵中,每个值都对应 grid 中一个相接的 3 x 3 矩阵的最大值。

ex2new2.png

输入:grid = [[1,1,1,1,1],[1,1,1,1,1],[1,1,2,1,1],[1,1,1,1,1],[1,1,1,1,1]]
输出:[[2,2,2],[2,2,2],[2,2,2]]
解释:注意,2 包含在 grid 中每个 3 x 3 的矩阵中。

限制

  • n == grid.length == grid[i].length
  • 3 <= n <= 100
  • 1 <= grid[i][j] <= 100

算法

(模拟) $O(n^2)$
  1. 暴力枚举每个 3 x 3 矩阵的最大值。

时间复杂度

  • 每个位置最多被遍历 9 次,故时间复杂度为 $O(n^2)$。

空间复杂度

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

C++ 代码

class Solution {
public:
    vector<vector<int>> largestLocal(vector<vector<int>>& grid) {
        const int n = grid.size();

        vector<vector<int>> ans(n - 2, vector<int>(n - 2, 0));

        for (int i = 0; i < n - 2; i++)
            for (int j = 0; j < n - 2; j++)
                for (int k = 0; k < 3; k++)
                    for (int l = 0; l < 3; l++)
                        ans[i][j] = max(ans[i][j], grid[i + k][j + l]);

        return ans;
    }
};



wzc1995
2天前

题目描述

如果一个正整数每一个数位都是 互不相同 的,我们称它是 特殊整数

给你一个 整数 n,请你返回区间 [1, n] 之间特殊整数的数目。

样例

输入:n = 20
输出:19
解释:1 到 20 之间所有整数除了 11 以外都是特殊整数。所以总共有 19 个特殊整数。
输入:n = 5
输出:5
解释:1 到 5 所有整数都是特殊整数。
输入:n = 135
输出:110
解释:从 1 到 135 总共有 110 个整数是特殊整数。
不特殊的部分数字为:22,114 和 131。

限制

  • 1 <= n <= 2 * 10^9

算法1

(暴力递归回溯) $O((\log_{10} n)!)$
  1. 由于出现的数字互不相同,答案个数不会很多,所以可以按数位暴力枚举填充的数字。
  2. 通过二进制掩码判断递归的重复数字,以提高速度。
  3. 如果当前拼成的数字小于等于 $n$,则累加答案。

时间复杂度

  • 共有 $O(\log_{10} n)$ 个数位,故需要 $O((\log_{10} n)!)$ 的时间枚举。

空间复杂度

  • 需要 $O(\log_{10} n)$ 的额外空间存储递归调用的系统栈。

C++ 代码

#define LL long long

class Solution {
private:
    int ans;

    void solve(LL s, int used, int n) {
        if (s > n)
            return;

        ans++;

        for (int i = 0; i <= 9; i++)
            if (!(used & (1 << i)))
                solve(s * 10 + i, used | (1 << i), n);
    }

public:
    int countSpecialNumbers(int n) {
        ans = 0;

        for (int i = 1; i <= 9; i++)
            solve(i, 1 << i, n);

        return ans;
    }
};

算法2

(数位统计) $O(10 \cdot \log_{10} n)$

整个计算过程分为两步:

  1. 计算位数 $m$ 小于 $n$ 的非零开头符合条件的数字。对于位数 $i$,其方案数为 $9 \cdot P_9^{i-1}$。其中 $P$ 表示排列数。
  2. 计算位数 $m$ 等于 $n$ 的符合条件的数字,这里需要用到数位统计的思想。
    • 对于首位(第一位),假设为 $j’ > 0$,则首位小于 $j’$ 的数字个数就是 $(j’ - 1) * P_9^{m - 1}$。
      • 然后计算首位为 $j’$ 时的数字个数,同时需要记录数字 $j’$ 已经使用过。
    • 接着对于第 $k$ 位,假设为 $j$,则枚举从 $0$ 到 $j - 1$,统计之前没使用过的数字的个数 $c$,则当前位小于 $j$ 的个数为 $c \cdot P_{10 - k}^{m - k}$。
      • 然后计算第 $k$ 位为 $j$ 时的数字个数,同时记录数字 $j$ 已经被使用过。如果发现 $j$ 已经被使用过,则直接返回答案(过程结束)。
    • 如果遍历到最低位退出了循环,则返回答案加 $1$($n$ 本身可以看做合法答案)。

时间复杂度

  • 初始化需要 $O(10)$ 的时间。
  • 共有 $O(\log_{10} n)$ 个数位,每个数位最多需要 $O(10)$ 的时间,故总时间复杂度为 $O(10 \cdot \log_{10} n)$。

空间复杂度

  • 需要 $O(10 + \log_{10} n)$ 的额外空间存储阶乘和 $n$ 字符串形式的数组。

C++ 代码

class Solution {
private:
    int power[10];

    int p(int x, int y) {
        return power[x] / power[x - y];
    }

public:
    int countSpecialNumbers(int n) {
        power[0] = 1;

        for (int i = 1; i < 10; i++)
            power[i] = power[i - 1] * i;

        vector<int> s;
        while (n > 0) {
            s.push_back(n % 10);
            n /= 10;
        }

        int ans = 0;
        for (int i = 1; i < s.size(); i++)
            ans += 9 * p(9, i - 1);

        int used = 0;
        for (int i = s.size() - 1; i >= 0; i--) {
            int c = 0;
            for (int j = (i == s.size() - 1) ? 1 : 0; j < s[i]; j++)
                if (!(used & (1 << j)))
                    c++;

            ans += c * p(10 - s.size() + i, i);

            if (used & (1 << s[i]))
                return ans;

            used |= 1 << s[i];
        }

        return ans + 1;
    }
};



wzc1995
2天前

题目描述

给你下标从 0 开始、长度为 n 的字符串 pattern,它包含两种字符,'I' 表示 上升'D' 表示 下降

你需要构造一个下标从 0 开始长度为 n + 1 的字符串,且它要满足以下条件:

  • num 包含数字 '1''9',其中每个数字 至多 使用一次。
  • 如果 pattern[i] == 'I',那么 num[i] < num[i + 1]
  • 如果 pattern[i] == 'D',那么 num[i] > num[i + 1]

请你返回满足上述条件字典序 最小 的字符串 num

样例

输入:pattern = "IIIDIDDD"
输出:"123549876"
解释:
下标 0,1,2 和 4 处,我们需要使 num[i] < num[i+1]。
下标 3,5,6 和 7 处,我们需要使 num[i] > num[i+1]。
一些可能的 num 的值为 "245639871","135749862" 和 "123849765"。
"123549876" 是满足条件最小的数字。
注意,"123414321" 不是可行解因为数字 '1' 使用次数超过 1 次。
输入:pattern = "DDD"
输出:"4321"
解释:
一些可能的 num 的值为 "9876","7321" 和 "8742"。
"4321" 是满足条件最小的数字。

限制

  • 1 <= pattern.length <= 8
  • pattern 只包含字符 'I''D'

算法1

(暴力枚举) $O(n \cdot (n + 1)!)$
  1. 注意到,长度为 $n$ 的 pattern 只需要用到 $1$ 到 $n + 1$ 的数字。
  2. 可以直接枚举 $1$ 到 $n + 1$ 的全排列,然后判断是否符合条件。

时间复杂度

  • 共有 $(n + 1)!$ 个全排列,每个都需要 $O(n)$ 的时间判断,故时间复杂度为 $O(n \cdot (n + 1)!)$。

空间复杂度

  • 需要 $O(n)$ 的额外空间存储全排列数组和答案。

C++ 代码

class Solution {
private:
    bool check(const string &pattern, const string &p) {
        for (int i = 0; i < pattern.size(); i++) {
            if (pattern[i] == 'I' && p[i] > p[i + 1])
                return false;

            if (pattern[i] == 'D' && p[i] < p[i + 1])
                return false;
        }

        return true;
    }

public:
    string smallestNumber(string pattern) {
        const int n = pattern.size();

        string p;
        for (int i = 0; i <= n; i++)
            p += i + 1 + '0';

        string ans;

        do {
            if (!check(pattern, p))
                continue;

            if (ans.empty() || ans > p)
                ans = p;

        } while (next_permutation(p.begin(), p.end()));

        return ans;
    }
};

算法2

(拓扑排序) $O(n \log n)$
  1. 将问题抽象出图论的问题,假设共有 $0$ 到 $n$ 共 $n + 1$ 个点,如果 $pattern(i) = I$,则 $i$ 到 $i + 1$ 连一条有向边,代表位置 $i$ 确定之后才可以确定位置 $i + 1$。反之,连接 $i + 1$ 到 $i$。
  2. 建图完成后,对当前的图进行拓扑排序。需要找到字典序最小拓扑序列,然后按照该拓扑序列从 $1$ 到 $n + 1$ 安排数字。
  3. 求字典序最小的拓扑序可以使用优先队列宽度优先遍历。

时间复杂度

  • 共有 $O(n)$ 个点和 $O(n)$ 条边,故优先队列的拓扑排序为 $O(n \log n)$。

空间复杂度

  • 需要 $O(n)$ 的额外空间存储图的边、度数、优先队列和答案。

C++ 代码

class Solution {
public:
    string smallestNumber(string pattern) {
        const int n = pattern.size();

        vector<vector<int>> graph(n + 1);
        vector<int> deg(n + 1, 0);

        for (int i = 0; i < n; i++)
            if (pattern[i] == 'I') {
                graph[i].push_back(i + 1);
                deg[i + 1]++;
            } else {
                graph[i + 1].push_back(i);
                deg[i]++;
            }

        priority_queue<int, vector<int>, greater<int>> q;
        for (int i = 0; i <= n; i++)
            if (deg[i] == 0)
                q.push(i);

        string ans(n + 1, ' ');
        int c = 1;

        while (!q.empty()) {
            int u = q.top();
            q.pop();

            ans[u] = c + '0';
            c++;

            for (int v : graph[u]) {
                deg[v]--;
                if (deg[v] == 0)
                    q.push(v);
            }
        }

        return ans;
    }
};

算法3

(贪心) $O(n)$
  1. 先将答案初始化为 $1$ 到 $n + 1$。
  2. 对于连续出现的 D,可以作为一块整体进行翻转,这样得到的数字一定是字典序最小的。
  3. 例如对于样例 IIIDIDDD,共有两块连续的 D。初始时答案为 123456789,第一次翻转后为 123546789,第二次翻转后为 123549876

时间复杂度

  • 最多翻转 $n$ 个数字,故时间复杂度为 $O(n)$。

空间复杂度

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

C++ 代码

class Solution {
public:
    string smallestNumber(string pattern) {
        const int n = pattern.size();

        string ans;
        for (int i = 1; i <= n + 1; i++)
            ans += i + '0';

        int d = -1;
        for (int i = 0; i < n; i++) {
            if (pattern[i] == 'I' && d != -1) {
                reverse(ans.begin() + d, ans.begin() + i + 1);
                d = -1;
            } else if (pattern[i] == 'D' && d == -1) {
                d = i;
            }
        }

        if (d != -1)
            reverse(ans.begin() + d, ans.end());

        return ans;
    }
};



wzc1995
9天前

题目描述

给你一个由小写字母组成的字符串 s,和一个整数 k。如果满足下述条件,则可以将字符串 t 视作是 理想字符串

  • t 是字符串 s 的一个子序列。
  • t 中每两个 相邻 字母在字母表中位次的绝对差值小于或等于 k

返回 最长 理想字符串的长度。

字符串的子序列同样是一个字符串,并且子序列还满足:可以经由其他字符串删除某些字符(也可以不删除)但不改变剩余字符的顺序得到。

注意:字母表顺序不会循环。例如,'a''z' 在字母表中位次的绝对差值是 25,而不是 1

样例

输入:s = "acfgbd", k = 2
输出:4
解释:最长理想字符串是 "acbd"。该字符串长度为 4,所以返回 4。
注意 "acfgbd" 不是理想字符串,因为 'c' 和 'f' 的字母表位次差值为 3。
输入:s = "abcd", k = 3
输出:4
解释:最长理想字符串是 "abcd",该字符串长度为 4,所以返回 4。

限制

  • 1 <= s.length <= 10^5
  • 0 <= k <= 25
  • s 由小写英文字母组成。

算法

(动态规划) $O(nk)$
  1. 设 $f(c)$ 表示从头开始遍历过程中,以字符 $c$ 结尾的最长理想字符串的长度。
  2. 初始时,$f(c) = 0$。
  3. 转移时,对于当前位置 $c := s(i)$,找到下标 $[c - k, c + k]$ 内的 $f$ 的最大值 $m$,转移 $f(c) = m + 1$。
  4. 最终答案为 $\max(f(c))$。

时间复杂度

  • 遍历字符串,对于每个字符,都需要 $O(k)$ 的时间更新状态,故时间复杂度为 $O(nk)$。

空间复杂度

  • 需要 $O(\Sigma)$ 的额外空间存储状态。

C++ 代码

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

        vector<int> f(26, 0);

        for (int i = 0; i < n; i++) {
            int c = s[i] - 'a';

            int m = 0;
            for (int j = max(0, c - k); j <= min(25, c + k); j++)
                m = max(m, f[j]);

            f[c] = m + 1;
        }

        int ans = 0;
        for (int i = 0; i < 26; i++)
            ans = max(ans, f[i]);

        return ans;
    }
};



wzc1995
9天前

题目描述

给你一个下标从 0 开始的整数数组 nums,你必须将数组划分为一个或多个 连续 子数组。

如果获得的这些子数组中每个都能满足下述条件 之一,则可以称其为数组的一种 有效 划分:

  • 子数组 2 个相等元素组成,例如,子数组 [2,2]
  • 子数组 3 个相等元素组成,例如,子数组 [4,4,4]
  • 子数组 3 个连续递增元素组成,并且相邻元素之间的差值为 1。例如,子数组 [3,4,5],但是子数组 [1,3,5] 不符合要求。

如果数组 至少 存在一种有效划分,返回 true,否则,返回 false

样例

输入:nums = [4,4,4,5,6]
输出:true
解释:数组可以划分成子数组 [4,4] 和 [4,5,6]。
这是一种有效划分,所以返回 true。
输入:nums = [1,1,1,2]
输出:false
解释:该数组不存在有效划分。

限制

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

算法

(动态规划) $O(n)$
  1. 设 $f(i)$ 表示以 $i$ 结尾的数组是否存在有效划分。$i$ 的有效下标从 $1$ 开始。
  2. 初始时,$f(0) := true$,其余待定。
  3. 转移时,如果 $nums(i) = nums(i - 1)$,则可以转移 $f(i) = f(i) \text{ OR } f(i - 2)$;如果前三个数字都相同或连续递增,则转移 $f(i) = f(i) \text{ OR } f(i - 3)$;
  4. 最终答案为 $f(n)$。

时间复杂度

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

空间复杂度

  • 需要 $O(n)$ 的额外空间存储状态。
  • 注意到,每个状态只依赖前序的两个状态,故可以优化到常数。

C++ 代码

class Solution {
public:
    bool validPartition(vector<int>& nums) {
        const int n = nums.size();

        vector<bool> f(n + 1, false);
        f[0] = true;

        for (int i = 2; i <= n; i++) {
            if (nums[i - 1] == nums[i - 2])
                f[i] = f[i] || f[i - 2];

            if (i >= 3 && nums[i - 1] == nums[i - 2] && nums[i - 1] == nums[i - 3])
                f[i] = f[i] || f[i - 3];

            if (i >= 3 && nums[i - 1] == nums[i - 2] + 1 && nums[i - 2] == nums[i - 3] + 1)
                f[i] = f[i] || f[i - 3];
        }

        return f[n];
    }
};



wzc1995
9天前

题目描述

现有一棵由 n 个节点组成的无向树,节点编号从 0n - 1,共有 n - 1 条边。

给你一个二维整数数组 edges,长度为 n - 1,其中 edges[i] = [a_i, b_i] 表示树中节点 a_ib_i 之间存在一条边。另给你一个整数数组 restricted 表示 受限 节点。

在不访问受限节点的前提下,返回你可以从节点 0 到达的 最多 节点数目。

注意,节点 0 会标记为受限节点。

样例

ex1drawio.png

输入:n = 7, edges = [[0,1],[1,2],[3,1],[4,0],[0,5],[5,6]], restricted = [4,5]
输出:4
解释:上图所示正是这棵树。
在不访问受限节点的前提下,只有节点 [0,1,2,3] 可以从节点 0 到达。

ex2drawio.png

输入:n = 7, edges = [[0,1],[0,2],[0,5],[0,4],[3,2],[6,5]], restricted = [4,2,1]
输出:3
解释:上图所示正是这棵树。
在不访问受限节点的前提下,只有节点 [0,5,6] 可以从节点 0 到达。

限制

  • 2 <= n <= 10^5
  • edges.length == n - 1
  • edges[i].length == 2
  • 0 <= a_i, b_i < n
  • a_i != b_i
  • edges 表示一棵有效的树。
  • 1 <= restricted.length < n
  • 1 <= restricted[i] < n
  • restricted 中的所有值 互不相同

算法

(递归遍历) $O(n)$
  1. 从 $0$ 开始递归遍历树。如果遇到受限节点则停止遍历。

时间复杂度

  • 每个节点最多遍历一次,故时间复杂度为 $O(n)$。

空间复杂度

  • 需要 $O(n)$ 的额外空间存储递归的系统栈。

C++ 代码

class Solution {
private:
    vector<vector<int>> graph;
    unordered_set<int> re;
    int ans;

    void calc(int u, int fa) {
        ans++;

        for (int v : graph[u])
            if (v != fa && re.find(v) == re.end())
                calc(v, u);
    }

public:
    int reachableNodes(int n, vector<vector<int>>& edges, vector<int>& restricted) {
        for (int x : restricted)
            re.insert(x);

        graph.resize(n);

        for (const auto &e : edges) {
            graph[e[0]].push_back(e[1]);
            graph[e[1]].push_back(e[0]);
        }

        ans = 0;

        calc(0, -1);

        return ans;
    }
};



wzc1995
9天前

题目描述

给你一个下标从 0 开始、严格递增 的整数数组 nums 和一个正整数 diff。如果满足下述全部条件,则三元组 (i, j, k) 就是一个 算术三元组

  • i < j < k
  • nums[j] - nums[i] == diffnums[k] - nums[j] == diff

返回不同 算术三元组 的数目。

样例

输入:nums = [0,1,4,6,7,10], diff = 3
输出:2
解释:
(1, 2, 4) 是算术三元组:7 - 4 == 3 且 4 - 1 == 3。
(2, 4, 5) 是算术三元组:10 - 7 == 3 且 7 - 4 == 3。
输入:nums = [4,5,6,7,8,9], diff = 2
输出:2
解释:
(0, 2, 4) 是算术三元组:8 - 6 == 2 且 6 - 4 == 2。
(1, 3, 5) 是算术三元组:9 - 7 == 2 且 7 - 5 == 2。

限制

  • 3 <= nums.length <= 200
  • 0 <= nums[i] <= 200
  • 1 <= diff <= 50
  • nums 严格 递增。

算法

(哈希表) $O(n^2)$
  1. 由于 nums 单调递增,故可以枚举 nums[i]nums[k],然后通过哈希表累加符合条件的 nums[j]

时间复杂度

  • 枚举两个位置,并通过哈希表判断,故时间复杂度为 $O(n^2)$。

空间复杂度

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

C++ 代码

class Solution {
public:
    int arithmeticTriplets(vector<int>& nums, int diff) {
        const int n = nums.size();

        int ans = 0;
        for (int i = 0; i < n; i++) {
            unordered_map<int, int> s;

            for (int j = i + 1; j < n; j++) {
                if (nums[j] - nums[i] == 2 * diff && s.find(nums[i] + diff) != s.end())
                    ans += s[nums[i] + diff];

                s[nums[j]]++;
            }
        }

        return ans;
    }
};



wzc1995
9天前

题目描述

给你一个下标从 0 开始的整数数组 nums。每次操作中,你可以将数组中任何一个元素替换为 任意两个 和为该元素的数字。

  • 比方说,nums = [5,6,7]。一次操作中,我们可以将 nums[1] 替换成 24,将 nums 转变成 [5,2,4,7]

请你执行上述操作,将数组变成元素按 非递减 顺序排列的数组,并返回所需的最少操作次数。

样例

输入:nums = [3,9,3]
输出:2
解释:以下是将数组变成非递减顺序的步骤:
- [3,9,3],将 9 变成 3 和 6,得到数组 [3,3,6,3]。
- [3,3,6,3],将 6 变成 3 和 3,得到数组 [3,3,3,3,3]。 
总共需要 2 步将数组变成非递减有序,所以我们返回 2。
输入:nums = [1,2,3,4,5]
输出:0
解释:数组已经是非递减顺序,所以我们返回 0。

限制

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

算法

(贪心) $O(n)$
  1. 注意到,数字只会越拆分越小,所以需要对较大的数字下手。
  2. 从数组末尾开始往前寻找,找到第一个非递减顺序的位置 $p$,满足 $p > 0$ 且 $nums(p) < nums(p - 1)$。
  3. 如果 $p$ 不存在,则说明数组已经是非递减顺序,直接返回。
  4. 定义最大可保留的数字为 $target$,初始化 $target := nums(p)$。从 $p - 1$ 开始倒序拆分。
  5. 如果 $nums(i) \text{ mod } target = 0$,则说明 $nums(i)$ 可以完全拆分为若干个 $target$,则答案增加 $nums(i) / target - 1$,并且 $target$ 保持不变。
  6. 否则,拆分的最少次数就是 $c := nums(i) / target$ 次,但拆分为 $c + 1$ 个数字后需要尽可能的让最小的数字最大(作为下一次拆分的 $target$),此时最小数字的最大可能值为 $target := nums(i) / (c + 1)$。
  7. 注意到,两种情况可以合到一起处理,即直接从数组末尾开始计算。

时间复杂度

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

空间复杂度

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

C++ 代码

#define LL long long

class Solution {
public:
    LL minimumReplacement(vector<int>& nums) {
        const int n = nums.size();

        LL ans = 0;
        int target = nums[n - 1];

        for (int i = n - 2; i >= 0; i--) {
            int c = nums[i] / target;

            if (nums[i] % target == 0) {
                ans += c - 1;
            } else {
                ans += c;
                target = nums[i] / (c + 1);
            }
        }

        return ans;
    }
};



wzc1995
9天前

题目描述

给你一个下标从 0 开始的正整数数组 tasks,表示需要 按顺序 完成的任务,其中 tasks[i] 表示第 i 件任务的 类型

同时给你一个正整数 space,表示一个任务完成 ,另一个 相同 类型任务完成前需要间隔的 最少 天数。

在所有任务完成前的每一天,你都必须进行以下两种操作中的一种:

  • 完成 tasks 中的下一个任务
  • 休息一天

请你返回完成所有任务所需的 最少 天数。

样例

输入:tasks = [1,2,1,2,3,1], space = 3
输出:9
解释:
9 天完成所有任务的一种方法是:
第 1 天:完成任务 0。
第 2 天:完成任务 1。
第 3 天:休息。
第 4 天:休息。
第 5 天:完成任务 2。
第 6 天:完成任务 3。
第 7 天:休息。
第 8 天:完成任务 4。
第 9 天:完成任务 5。
可以证明无法少于 9 天完成所有任务。
输入:tasks = [5,8,8,5], space = 2
输出:6
解释:
6 天完成所有任务的一种方法是:
第 1 天:完成任务 0。
第 2 天:完成任务 1。
第 3 天:休息。
第 4 天:休息。
第 5 天:完成任务 2。
第 6 天:完成任务 3。
可以证明无法少于 6 天完成所有任务。

限制

  • 1 <= tasks.length <= 10^5
  • 1 <= tasks[i] <= 10^9
  • 1 <= space <= tasks.length

算法

(哈希表) $O(n)$
  1. 按顺序遍历任务数组,使用变量 $day$ 记录天数,即完成当前任务后的下一天。天数从 $0$ 开始。
  2. 使用哈希表记录上一次完成同种任务的 $day$。
  3. 遍历时,如果发现上一次完成同种任务时的间隔天数不足 $space$,则重置 $day := last(t) + space + 1$。
  4. 完成当前任务后 $day := day + 1$。

时间复杂度

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

空间复杂度

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

C++ 代码

#define LL long long

class Solution {
public:
    LL taskSchedulerII(vector<int>& tasks, int space) {
        unordered_map<int, LL> last;
        LL day = 0;

        for (int t : tasks) {
            if (last.find(t) != last.end() && day - last[t] <= space)
                day = last[t] + space + 1;

            last[t] = day;
            day++;
        }

        return day;
    }
};