leetcode conttest 306

本周的题目确实不是特别难，后来看答案才知道，第三题和第四题都是之前的原题。前两题确实太水了，质量下滑厉害。

6148. 矩阵中的局部最大值

题目

给你一个大小为 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 矩阵中的最大值。

返回生成的矩阵。

示例 1：

输入：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 矩阵的最大值。

示例 2：

1
2
3

输入：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

地址

https://leetcode.cn/problems/largest-local-values-in-a-matrix

题意

直接遍历

思路

直接遍历即可，设矩阵的行数与列数分别为 $m,n$，则可以知道目标矩阵的行数与列数为 $m- 2, n - 2$，我们直接遍历即可。
复杂度分析：

时间复杂度：$O(m \times n)$，矩阵的行数与列数分别为 $m,n$。
空间复杂度：$O(1)$。
代码

直接遍历

class Solution {
public:
    vector<vector<int>> largestLocal(vector<vector<int>>& grid) {
        int m = grid.size();
        int n = grid[0].size();
        vector<vector<int>> ans(m - 2, vector<int>(n - 2));
        for (int i = 0; i < m - 2; i++) {
            for (int j = 0; j < n - 2; j++) {
                for (int r = i; r <= i + 2; r++) {
                    for (int c = j; c <= j + 2; c++) {
                        ans[i][j] = max(ans[i][j], grid[r][c]);
                    }
                }
            }
        }
        return ans;
    }
};

6149. 边积分最高的节点

题目

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

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

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

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

示例 1：

输入：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 。

示例 2：

输入：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 <= 105
0 <= edges[i] < n
edges[i] != i

地址

https://leetcode.cn/problems/node-with-highest-edge-score

题意

直接遍历

思路

这个题感觉就是个简单题目，直接统计每个节点的得分即可，毫无难度可言。
复杂度分析：

时间复杂度：时间复杂度为 $O(n)$，$n$ 表示节点的数目。

空间复杂度：$O(n)$，$n$ 表示节点的数目。

代码

class Solution {
public:
    int edgeScore(vector<int>& edges) {
        int n = edges.size();
        vector<long long> score(n);
        for (int i = 0; i < n; i++) {
            score[edges[i]] += i;
        }
        int ans = 0;
        for (int i = 0; i < n; i++) {
            if(score[i] > score[ans]) {
                ans = i;
            }
        }
        return ans;
    }
};

6150. 根据模式串构造最小数字

题目

给你下标从 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。

示例 1：

输入：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 次。

示例 2：

输入：pattern = "DDD"
输出："4321"
解释：
一些可能的 num 的值为 "9876" ，"7321" 和 "8742" 。
"4321" 是满足条件最小的数字。

提示：

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

地址

https://leetcode.cn/problems/construct-smallest-number-from-di-string

题意

动态规划或者贪心

思路

动态规划：
感觉就是暴力解法。这 $dp[i][j]$ 表示前 $i$ 个字母且以数字 $j$ 为结尾且符合字符串前 $i-1$ 个规则的最小字符串。我们每次贪心的选择字典序最小的字符串即可，感觉解法实际上有点繁琐了。
复杂度分析：

时间复杂度：时间复杂度为 $O(n^2 \times |\Sigma| ^ 2)$，其中 $n$ 表示字符串的长度，$|\Sigma|$ 表示字符集的大小。
空间复杂度：空间复杂度为 $O(n^2 \times |\Sigma|)$，其中 $n$ 表示字符串的长度，$|\Sigma|$ 表示字符集的大小。

贪心算法：
为什么需要贪心算法，我们可以看到每次 $\text{“IIIDDD”}$ 将其分为 $\text{“III”}$ 与 $\text{“DDDD”}$，每次遇到第一个 D 时我们将剩余元素的最小值倒序顺序压入到栈中，这样出栈顺序即按照倒序出栈，满足递减。遇到 I 时，如果前方没有 D 时，此时我们直接压入 num 。
复杂度分析：

时间复杂度：时间复杂度为 $O(n)$，其中 $n$ 表示字符串的长度。

空间复杂度：空间复杂度为 $O(n)$，其中 $n$ 表示字符串的长度。

代码

const string inf = "999999999";

class Solution {
public:
    string smallestNumber(string pattern) {
        int n = pattern.size();   
        vector<vector<string>> dp(n + 1, vector<string>(10, inf));
        for (int i = 1; i <= 9; i++) {
            dp[0][i] = to_string(i);
        }
        for (int i = 0; i < n; i++) {
            for (int j = 1; j <= 9; j++) {
                if (pattern[i] == 'I') {
                    for (int k = 1; k < j; k++) {
                        if (dp[i][k] < dp[i + 1][j]) {
                            bool valid = true;
                            for (int l = 0; l < dp[i][k].size(); l++) {
                                if (dp[i][k][l] == '0' + j) {
                                    valid = false;
                                    break;
                                }
                            }
                            if (valid) {
                                dp[i + 1][j] = dp[i][k];
                            }
                        }
                    }
                } else {
                    for (int k = j + 1; k <= 9; k++) {
                        if (dp[i][k] < dp[i + 1][j]) {
                            bool valid = true;
                            for (int l = 0; l < dp[i][k].size(); l++) {
                                if (dp[i][k][l] == '0' + j) {
                                    valid = false;
                                    break;
                                }
                            }
                            if (valid) {
                                dp[i + 1][j] = dp[i][k];
                            }
                        }
                    }
                }
                dp[i+1][j].push_back(j + '0');
            }
        }
        return *min_element(dp[n].begin(), dp[n].end());
    }
};

贪心算法:

class Solution {
public:
    string smallestNumber(string pattern) {
        string ans;
        stack<char> st;
        char num = '1';
        for (auto c : pattern) {
            if (c == 'D') {
                st.emplace(num++);
            } else {
                if (st.empty()) {
                    ans.push_back(num++);
                } else {
                    st.emplace(num++);
                    while (!st.empty()) {
                        ans.push_back(st.top());
                        st.pop();
                    }
                }
            }
        }
        st.emplace(num);
        while(!st.empty()) {
            ans.push_back(st.top());
            st.pop();
        }
        return ans;
    }
};

6151. 统计特殊整数

题目

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

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

示例 1：

1
2
3

输入：n = 20
输出：19
解释：1 到 20 之间所有整数除了 11 以外都是特殊整数。所以总共有 19 个特殊整数。

示例 2：

1
2
3

输入：n = 5
输出：5
解释：1 到 5 所有整数都是特殊整数。

示例 3：

输入：n = 135
输出：110
解释：从 1 到 135 总共有 110 个整数是特殊整数。
不特殊的部分数字为：22 ，114 和 131 。

提示：

1 <= n <= 2 * 109

地址

https://leetcode.cn/problems/count-special-integers

题意

数位dp 或者分类讨论

思路

分类讨论：
分类讨论的解法非常简单，感觉就是一个小学奥数题目。设数字 $n$ 的十进制共有 $m$ 位，分为两种情况讨论：

组成的数字位数 $ k < m$ 的情况：这个比较简单简单的排列组合 $count = \sum_{i=1}^{m-1}(A_9^{k} + 9 \times A_9^{k-1})$，相当于从 $10$ 个不同的数字中选出 $i$ 个不同的数，但需要考虑第一个数字不为 $0$ 的问题。
组成的数字位数 $k = m$ 的情况: 这种就稍微复杂一些，左边 $k$ 保持与 $n$ 一致，右边的 $m-k$ 位小于 $n$ 的右边 $m-k$ 位，在满足前 $i$ 位数字均不相同的前提下，排列组合公式如下： $count = \sum_{i = 0}^{m-1}\sum_{j=0}^{d[i]-1}(A_{10-i-1}^{m-i-1}) \\ tot = \sum_{i=1}^{m-1}(A_9^{k} + 9 \times A_9^{k-1}) + \sum_{i = 0}^{m-1}\sum_{j=0}^{d[i]-1}(A_{10-i-1}^{m-i-1})$ 前 $i-1$ 个数字沿用 $n$ 的前 $i-1$ 个数字，第 $i$ 个数字的选择为 $[0,d[i])$，剩余的 $m - i$ 个数字则按照排列组合的形式，从 $10$ 个不同的数字中选择 $m-i$ 个的组合数，当然以上还需要特殊考虑第 $1$ 个数字为 $0$ 情形，同时还需要单独讨论数字 $n$ 是否符合特殊整数的情形。
复杂度分析：
时间复杂度：$O(m \times |\Sigma|)$，其中 $|\Sigma|$ 表示字符集，在这里字符集的数目为 $10$。
空间复杂度：$O(m + |\Sigma|)$。

典型的数位 $dp$ 解法，不过这个题目因为限制条件多，用数位 dp 的解法实际还麻烦一些。实际还稍微麻烦一些，写出来的代码逻辑非常丑陋，感觉不如分类讨论来的直接一些。对于位数小于 $m$ 的特殊整数的数量，我们还是按照排列组合来讨论，只需要单独讨论位数等于 $m$ 的情形。设 $dp[i][limit][mask]$ 表时左边前 $i$ 位，$limit$ 为 $1$ 表示严重数字的上限，$limit$ 为 $0$ 表示未沿着数字的上线，$mask$ 表示当前的数字集合。则我们可以知道以下递推公式: $dp[i][1][mask | (1 << d[i])] = dp[i-1][1][mask] \\ dp[i][0][mask | (1 << k)] = \sum_{k = 0}^{d[i]-1}dp[i-1][1][mask] + \sum_{k = 0}^{9}dp[i-1][0][mask]$ 也是分两种情况讨论，要么严着上限，要么低于上限。数位 dp 在力扣平台上有非常多的类似的题目。
复杂度分析：

时间复杂度：$O(m \times |\Sigma| \times 2 ^ {|\Sigma|})$，其中 $|\Sigma|$ 表示字符集，在这里字符集的数目为 $10$。
空间复杂度：$O(m \times |\Sigma| \times 2 ^ {|\Sigma|})$。

代码

class Solution {
public:
    int countSpecialNumbers(int n) {
        int ans = 0;
        string s = to_string(n);
        int m = s.size();
        vector<int> Fac(10, 1);
        vector<int> bitsmask(m + 1, -1);
        for (int i = 1; i <= 9; i++) {
            Fac[i] = Fac[i-1] * i;
        }
        bitsmask[0] = 0;
        for (int i = 1; i <= m; i++) {
            if (bitsmask[i - 1] != -1) {
                if (bitsmask[i - 1] & (1 << (s[i-1] - '0'))) {
                    continue;
                }
                bitsmask[i] = bitsmask[i - 1] | (1 << (s[i-1] - '0'));
            }
        }
        /* less than m */
        for (int i = 1; i < m; i++) {
            ans += Fac[9] / Fac[9 - i] + (i - 1) == 0 ? 0 : (9 * Fac[9] / Fac[10 - i]);
        }
        /* m bits */
        for (int i = m - 1; i >= 0; i--) {
            int mask = bitsmask[i];
            int y = 10 - i - 1;
            int bits = m - i - 1;
            if (mask != -1) {
                int x = s[i] - '0';
                /* m bits */
                if (i == m - 1 && !(mask & (1 << x))) {
                    ans++;
                } 
                for (int k = (i == 0 ? 1 : 0); k < x; k++) {
                    if (mask & (1 << k)) {
                        continue;
                    }
                    ans += Fac[y] / Fac[y - bits];
                }
            }
        }
        return ans;
    }
};

class Solution {
public:
    int countSpecialNumbers(int n) {
        auto s = to_string(n);
        int m = s.length();
        int dp[m + 1][2][1024];
        memset(dp, 0, sizeof(dp));
        vector<long long> Fac(10, 1);
        /* less than m bits */
        int tot = 0;
        for (int i = 1; i <= 9; i++) {
            Fac[i] = Fac[i-1] * i;
        }
        for (int i = 1; i < m; i++) {
            tot += Fac[9] / Fac[9 - i] + (i - 1) == 0 ? 0 : (9 * Fac[9] / Fac[10 - i]);
        }
        dp[0][1][0] = 1;
        for (int i = 1; i <= m; i++) {
            int x = s[i - 1] - '0';
            for (int j = 0; j < 1024; j++) {
                if (__builtin_popcount(j) != i - 1) continue;
                /* upper bound */
                if (dp[i-1][1][j] != 0) {
                    if (!(j & (1 << x))) {
                        dp[i][1][j | (1 << x)] = dp[i-1][1][j];
                    }
                    for (int k = 0; k < x; k++) {
                        if (j & (1 << k)) continue;
                        if (k == 0 && i == 1) continue;
                        dp[i][0][j | (1 << k)] += dp[i-1][1][j];
                    }
                }
                /* lower bound */
                if (dp[i-1][0][j] != 0) {
                    for (int k = 0; k <= 9; k++) {
                        if (j & (1 << k)) continue;
                        dp[i][0][j | (1 << k)] += dp[i-1][0][j];
                    }
                }
            }
        }
        for (int i = 1; i < 1024; i++) {
            if (dp[m][0][i] > 0 || dp[m][1][i] > 0) {
                tot += dp[m][0][i] + dp[m][1][i];
            }
        }
        return tot;
    }
};

#

欢迎关注和打赏，感谢支持！

关注我的博客: http://mikemeng.org/
关注我的知乎：https://www.zhihu.com/people/da-hua-niu
关注我的微信公众号: 公务程序猿

力扣周赛

#力扣周赛

leetcode conttest 306

http://example.com/2022/11/01/力扣周赛题解/24/

Author

Mike Meng

Posted on

November 1, 2022

Updated on

September 8, 2026

Licensed under

leetcode conttest 305 Previous

leetcode biweekly contest 85 Next