leetcode解题思路分析（一百六十一）1394 - 1400 题
- 找出数组中的幸运数
在整数数组中，如果一个整数的出现频次和它的数值大小相等，我们就称这个整数为「幸运数」。给你一个整数数组 arr，请你从中找出并返回一个幸运数。如果数组中存在多个幸运数，只需返回 最大 的那个。如果数组中不含幸运数，则返回 -1 。
一个哈希表搞定
class Solution {
public:
int findLucky(vector<int>& arr) {
unordered_map<int, int> cnt_map;
for (auto n : arr) {
cnt_map[n]++;
}
int ret = -1;
for (auto it : cnt_map) {
if (it.first == it.second) {
ret = max(ret, it.first);
}
}
return ret;
}
};
- 统计作战单位数
n 名士兵站成一排。每个士兵都有一个 独一无二 的评分 rating 。
从中选出 3 个士兵组成一个作战单位，规则如下：
从队伍中选出下标分别为 i、j、k 的 3 名士兵，他们的评分分别为 rating[i]、rating[j]、rating[k]
作战单位需满足： rating[i] < rating[j] < rating[k] 或者 rating[i] > rating[j] > rating[k] ，其中 0 <= i < j < k < n
请你返回按上述条件组建的作战单位的方案数。
最简单的是三层暴力查找，但是其实可以遍历中间值，然后左右各查一次再相乘即可。当然，还有更好的做法：提前遍历一遍，记录当前位置i前面有多少个比i大，多少个比i小，利用前缀和的特性实现。
class Solution {
public:
int numTeams(vector<int>& rating) {
int n = rating.size();
int ret = 0;
for (int i = 1; i < n - 1; ++i) {
auto inc_less = 0, inc_more = 0;
auto dec_less = 0, dec_more = 0;
for (int j = 0; j < i; ++j) {
if (rating[j] < rating[i])
inc_less++;
if (rating[j] > rating[i])
dec_more++;
}
for (int k = i + 1; k < n; ++k) {
if (rating[k] > rating[i])
inc_more++;
if (rating[k] < rating[i])
dec_less++;
}
ret += inc_less * inc_more + dec_less * dec_more;
}
return ret;
}
};
- 设计地铁系统
地铁系统跟踪不同车站之间的乘客出行时间，并使用这一数据来计算从一站到另一站的平均时间。实现 UndergroundSystem 类。
很简单的设计题
class UndergroundSystem {
public:
using Start = pair <string, int>;
using StartEnd = pair <string, string>;
using SumAndAmount = pair <int, int>;
struct StartEndHash {
int operator() (const StartEnd& x) const{
return hash <string> () (x.first + x.second);
}
};
unordered_map <int, Start> startInfo;
unordered_map <StartEnd, SumAndAmount, StartEndHash> table;
UndergroundSystem() {}
void checkIn(int id, string stationName, int t) {
startInfo[id] = {stationName, t};
}
void checkOut(int id, string stationName, int t) {
auto startTime = startInfo[id].second;
table[{startInfo[id].first, stationName}].first += t - startTime;
table[{startInfo[id].first, stationName}].second++;
}
double getAverageTime(string startStation, string endStation) {
auto sum = table[{startStation, endStation}].first;
auto amount = table[{startStation, endStation}].second;
return double(sum) / amount;
}
};
- 找到所有好字符串
给你两个长度为 n 的字符串 s1 和 s2 ，以及一个字符串 evil 。请你返回 好字符串 的数目。好字符串 的定义为：它的长度为 n ，字典序大于等于 s1 ，字典序小于等于 s2 ，且不包含 evil 为子字符串。由于答案可能很大，请你返回答案对 10^9 + 7 取余的结果。
数位DP的经典使用场景：给定下界 l 和上界 r，求 [l,r] 之间满足某一要求的元素个数。结合KMP，可以解题。
class Solution {
private:
// 这是用来帮助计算关于 stats 的转移函数的 fail 数组
vector<int> fail;
// 这是存储动态规划结果的数组
// 维度从左到右分别为 pos, stats, bound
int f[500][50][4];
// 这是存储转移函数结果的数组
// 两个维度分别为 stats 和 d
int trans[50][26];
static constexpr int mod = 1000000007;
string s1, s2, evil;
public:
// 这是计算关于 stats 的转移函数
// 输入为 stats 和 d
// 输出为转移的结果 g_s(stats, d)
int getTrans(int stats, char ch) {
// 如果之前计算过该转移函数就直接返回结果
if (trans[stats][ch - 97] != -1) {
return trans[stats][ch - 97];
}
// 这是 KMP 算法的一部分
// 把 evil 看作「模式串」，stats 看作「主串」匹配到的位置
while (stats && evil[stats] != ch) {
stats = fail[stats - 1];
}
// 存储结果并返回
return trans[stats][ch - 97] = (evil[stats] == ch ? stats + 1 : 0);
}
// 这是用来进行记忆化搜索的函数
// 输入为 pos, stats 和 bound
// 输出为 f[pos][stats][bound]
int dfs(int pos, int stats, int bound) {
// 如果匹配到了 evil 的末尾
// 说明字符串不满足要求了
// 返回 0
if (stats == evil.size()) {
return 0;
}
// 如果匹配到了上下界的末尾
// 说明找到了一个满足要求的字符串
// 返回 1
if (pos == s1.size()) {
return 1;
}
// 记忆化搜索的关键
// 如果之前计算过该状态就直接返回结果
if (f[pos][stats][bound] != -1) {
return f[pos][stats][bound];
}
// 将当前状态初始化
// 因为未初始化的状态值为 -1
f[pos][stats][bound] = 0;
// 计算第 pos 位可枚举的字符下界
char l = (bound & 1 ? s1[pos] : 'a');
// 计算第 pos 位可枚举的字符上界
char r = (bound & 2 ? s2[pos] : 'z');
for (char ch = l; ch <= r; ++ch) {
int nxt_stats = getTrans(stats, ch);
// 这里写得较为复杂
// 本质上就是关于 bound 的转移函数
// 可以根据自己的理解编写
int nxt_bound = (bound & 1 ? ch == s1[pos] : 0) ^ (bound & 2 ? (ch == s2[pos]) << 1 : 0);
f[pos][stats][bound] += dfs(pos + 1, nxt_stats, nxt_bound);
f[pos][stats][bound] %= mod;
}
return f[pos][stats][bound];
}
int findGoodStrings(int n, string _s1, string _s2, string _evil) {
s1 = _s1;
s2 = _s2;
evil = _evil;
int m = evil.size();
fail.resize(m);
// 这是 KMP 算法的一部分
// 把「evil」看作模式串，得到它的 fail[] 数组
for (int i = 1; i < m; ++i) {
int j = fail[i - 1];
while (j && evil[j] != evil[i]) {
j = fail[j - 1];
}
if (evil[j] == evil[i]) {
fail[i] = j + 1;
}
}
// 将未搜索过的动态规划状态置为 -1
memset(f, -1, sizeof(f));
// 将未计算过的转移函数置为 -1
memset(trans, -1, sizeof(trans));
// 答案即为 f[0][0][3]
return dfs(0, 0, 3);
}
};
- 统计最大组的数目
给你一个整数 n 。请你先求出从 1 到 n 的每个整数 10 进制表示下的数位和（每一位上的数字相加），然后把数位和相等的数字放到同一个组中。请你统计每个组中的数字数目，并返回数字数目并列最多的组有多少个。
哈希表存一下然后遍历一遍读取即可。
class Solution {
public:
int countLargestGroup(int n) {
std::unordered_map<int, int> bit_sum_map;
int max_val = 0;
for (int num = 1; num <= n; ++num) {
int sum = 0, n = num;
while (n) {
sum += n % 10;
n = n / 10;
}
if (bit_sum_map.find(sum) != bit_sum_map.end())
bit_sum_map[sum]++;
else
bit_sum_map[sum] = 1;
max_val = max(max_val, bit_sum_map[sum]);
}
if (bit_sum_map.size() == 0) return 0;
int ret = 0;
for (auto iter : bit_sum_map) {
if (max_val == iter.second)
ret++;
}
return ret;
}
};
- 构造 K 个回文字符串
给你一个字符串 s 和一个整数 k 。请你用 s 字符串中 所有字符 构造 k 个非空 回文串 。如果你可以用 s 中所有字符构造 k 个回文字符串，那么请你返回 True ，否则返回 False 。
如果 s 中有 p 个字符出现了奇数次，q 个字符出现了偶数次，那么 s 最少可以构造的回文串个数就为 p，这是因为每一种出现了奇数次的字符都必须放在不同的回文串中。特别地，如果 p=0，那么最少构造的回文串个数为 1。而最大回文串个数则为字符种类
class Solution {
public:
bool canConstruct(string s, int k) {
// 右边界为字符串的长度
int right = s.size();
// 统计每个字符出现的次数
int occ[26] = {0};
for (char ch: s) {
++occ[ch - 'a'];
}
// 左边界为出现奇数次字符的个数
int left = 0;
for (int i = 0; i < 26; ++i) {
if (occ[i] % 2 == 1) {
++left;
}
}
// 注意没有出现奇数次的字符的特殊情况
left = max(left, 1);
return left <= k && k <= right;
}
};