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]] |
示例 2：
输入：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]] |
提示：
n == grid.length == grid[i].length3 <= n <= 1001 <= 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] |
示例 2：
输入：edges = [2,0,0,2] |
提示：
n == edges.length2 <= n <= 1050 <= edges[i] < nedges[i] != i
地址
https://leetcode.cn/problems/node-with-highest-edge-score
题意
直接遍历
思路
- 这个题感觉就是个简单题目，直接统计每个节点的得分即可，毫无难度可言。
- 复杂度分析：
- 时间复杂度：时间复杂度为 $O(n)$，$n$ 表示节点的数目。
- 空间复杂度：$O(n)$，$n$ 表示节点的数目。
代码
class Solution { |
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" |
示例 2：
输入：pattern = "DDD" |
提示：
1 <= pattern.length <= 8pattern只包含字符'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) {
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：
输入：n = 20 |
示例 2：
输入：n = 5 |
示例 3：
输入：n = 135 |
提示：
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 { |
class Solution { |
欢迎关注和打赏，感谢支持！
- 关注我的博客: http://mikemeng.org/
- 关注我的知乎：https://www.zhihu.com/people/da-hua-niu
- 关注我的微信公众号: 公务程序猿
扫描二维码，分享此文章