LeetCode周赛306，用原题，你对得起我们吗，日内瓦，退钱！
LeetCode周赛306，用原题，你对得起我们吗，日内瓦，退钱！
作者 | 梁唐
大家好，我是梁唐。
今天是周一，我们照惯例来聊聊昨天的LeetCode周赛。
昨天的这场由蔚来汽车赞助，前1000名能获得简历内推的机会。据我所知，蔚来最近正在大规模招人。有想要找工作的同学可以考虑一下。
这一场比赛当中有两题与之前的问题非常相似，赛后引起了不小的争议。评论区里吐槽和批评很多，摘录几条，因为评论区是公开的，就不打码了。
怎么说呢，虽然LeetCode不像是codeforces、topcoder那样面向竞赛的平台，但直接搬运原题也确实不太好。也难怪这么多同学会对此失望。
吐槽就到这里，下面来看题吧。
矩阵中的局部最大值
给你一个大小为 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 矩阵中的最大值。
返回生成的矩阵。
题解
做深度学习的同学不难看出来这就是求maxpooling，数据范围也很小，直接暴力即可。
class Solution {
public:
vector<vector<int>> largestLocal(vector<vector<int>>& grid) {
int n = grid.size();
vector<vector<int>> ret(n-2, vector<int>(n-2, 0));
for (int i = 1; i < n-1; i++) {
for (int j = 1; j < n-1; j++) {
int cur = grid[i][j];
for (int _i = i-1; _i <= i+1; _i++) {
for (int _j = j-1; _j <= j+1; _j++) {
cur = max(cur, grid[_i][_j]);
}
}
ret[i-1][j-1] = cur;
}
}
return ret;
}
};
边积分最高的节点
给你一个有向图，图中有 n 个节点，节点编号从 0 到 n - 1 ，其中每个节点都 恰有一条 出边。
图由一个下标从 0 开始、长度为 n 的整数数组 edges 表示，其中 edges[i] 表示存在一条从节点 i 到节点 edges[i] 的 有向 边。
节点 i 的 边积分 定义为：所有存在一条指向节点 i 的边的节点的 编号 总和。
返回 边积分 最高的节点。如果多个节点的 边积分 相同，返回编号 最小 的那个。
题解
图遍历问题，遍历一下图上的边，把对应的积分加到对应的点上。最后找出积分最大且序号最小的节点。
题目里有一个坑，节点累加之后的积分和可能超过int的范围。所以我们在统计的时候需要使用long long类型。
class Solution {
public:
int edgeScore(vector<int>& edges) {
int n = edges.size();
vector<long long> sc(n, 0);
long long maxi = 0, ret = 0;
for (int i = 0; i < n; i++) {
int v = edges[i];
sc[v] += i;
if (sc[v] > maxi || sc[v] == maxi && v < ret) {
maxi = sc[v];
ret = v;
}
}
return ret;
}
};
根据模式串构造最小数字
给你下标从 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。
题解
观察一下数据范围可以发现，本题最多只有9个数字。9个数字的全排列最多只有362880种，我们直接遍历即可，完全不用担心时限的问题。
我们从最小的排列开始枚举，可以使用next_permutation库函数直接得到下一个排列。我们枚举所有的排列，直到找到满足题意的排列为止。
class Solution {
public:
string smallestNumber(string pat) {
int n = pat.length();
string base = "";
for (int i = 0; i <= n; i++) base.push_back('0' + i+1);
do {
bool match = true;
for (int i = 0; i < n; i++) {
// 遍历所有位置，如果存在某个位置的大小关系不成立，退出循环
if (pat[i] == 'I' && base[i] > base[i+1] || pat[i] == 'D' && base[i] < base[i+1]) {
match = false;
break;
}
if (!match) break;
}
if (match) return base;
}while (next_permutation(base.begin(), base.end()));
return "";
}
};
统计特殊整数
如果一个正整数每一个数位都是 互不相同 的，我们称它是 特殊整数 。
给你一个 正 整数 n ，请你返回区间 [1, n] 之间特殊整数的数目。
题解
这道题被诟病得最多，原因也简单，除了因为是模板题之外，它和题库中的一题高度相似。相似到不仅解题思路，而且题意都几乎一模一样。
我们分析一下题意会发现由于限制了每一位的数字都要各不相同，所以使用的数字的组合数量是非常有限的。由于最多只有0-9十个数字，所有的组合总数一共有
种可能。
我们也可以用二进制的角度来思考，一共有10个数字，我们用10位二进制来表示。如果选择对应的二进制位设为1，否则设为0。那么最多只需要使用10位二进制位就可以表示这10个数字的所有组合。10个二进制最大能表示的整数就是1023。
进而我们可以想到能不能维护每一个组合对应的数量，最后再把所有的数量相加是不是就是答案了？
但进一步思考会发现，有了数字组合还不够，我们还需要知道具体的排列，因为只有知道了具体的排列才能知道是否会大于n。但显然我们不可能意义枚举所有的排列，因为排列的数量会比组合大得多，一定会超时。
其实这个问题要解决很简单，因为我们只要顺着n的高位开始设置数字就可以避免出现越界的问题。如果从当前位开始，之前的高位都和n相等。那么当前位最大也不能超过n的对应数字。如果之前出现过了小于n的数字，那么当前位可以随意设置。
举个例子，比如说n是100，如果我们在最高位设置了1，那么之后就只能和n的位数齐平，只能设置两个0，否则就超过n了。如果我们百位设置的是0，那么后面的两位就可以随意设置。我们用一个flag标记之前的高位是否和n完全相等，如果完全相等，那么之后能用的数字都不能超过n，如果不完全相等，那么可以随意设置。
前文当中说了，我们使用一个不超过1024的整数就可以表示这10个数字的使用状况。最后，我们还需要一个维度表示当前设置数字的位置，它的范围是0到9。
最后，我们把这些都串起来，我们创建一个数组dp[10][2][1024]。10表示最高位，2表示从最高位开始之前的数字是否和n严格相等，1024表示当前使用的数字状态。从这三个维度描述状态，我们就可以进行状态转移了。
整体的思路用记忆化搜索的想法也可以推导出来，算是殊途同归了。
class Solution {
public:
int countSpecialNumbers(int n) {
int dp[10][2][1024];
memset(dp, 0xff, sizeof dp);
int nums[10]{0};
for (int i = 0, x = n; i < 10; i++, x/=10) nums[i] = x % 10;
function<int(int, bool, int)> dfs = [&](int p, bool flag, int status) -> int {
if (p < 0) return status != 0;
int &cur = dp[p][flag][status];
if (cur >= 0) return cur;
cur = 0;
for (int i = 0; i <= (flag ? nums[p]: 9); i++) {
if (i == 0 && status == 0) cur += dfs(p-1, flag && (i == nums[p]), 0);
else if (!(status & (1 << i))) cur += dfs(p-1, flag && (i == nums[p]), status | (1 << i));
}
return cur;
};
return dfs(9, 1, 0);
}
};
腾讯云开发者
