脚本宝典收集整理的这篇文章主要介绍了LeetCode第68场双周赛，脚本宝典觉得挺不错的，现在分享给大家，也给大家做个参考。
题目描述：给你(n)个句子，求出含有最多单词的句子所含有的单词数
思路：根据题意模拟即可
@R_44_1304@：(O(sum|S|))
参考代码：
class Solution {
public:
int mostWordsFound(vector<string>& sentences) {
int res = 0;
string t;
for(auto s : sentences){
stringstream text(s);
int cnt = 0;
while(text >> t) ++cnt;
res = max(res , cnt);
}
return res;
}
};
题目描述：你有(n)道不同菜的信息。给你一个字符串数组(reciPEs) 和一个二维字符串数组(ingredients)。第(i)道菜的名字为 (recipes[i])，如果你有它所有的原材料(ingredients[i])，那么你可以做出这道菜。一道菜的原材料可能是 另一道 菜也就是说 (ingredients[i])可能包含(recipes) 中另一个字符串。同时给你一个字符串数组 (supplies)，它包含你初始时拥有的所有原材料，每一种原材料你都有无限多。请你返回你可以做出的所有菜。你可以以 任意顺序 返回它们。
思路：比较明显的拓扑关系，考虑用map将菜品名称映射成点然后建图跑拓扑即可
时间复杂度：(O(n))
参考代码：
class Solution {
public:
vector<string> findAllRecipes(vector<string>& recipes, vector<vector<string>>& ingredients, vector<string>& supplies) {
vector<string> res;
vector<int>income(1000, 0);
map<string, int> mp1;
map<int, string> mp2;
int cnt = 0;
vector<vector<int>>graph(1000);
int n = recipes.size();
for (auto s : recipes) {
if (mp1[s]) continue;
mp1[s] = ++cnt;
mp2[cnt] = s;
}
for (int i = 0; i < n; ++i) {
for (int j = 0; j < ingredients[i].size(); ++j) {
string s = ingredients[i][j];
if (mp1[s] == 0) {
mp1[s] = ++cnt;
mp2[cnt] = s;
}
int dx = mp1[s];
graph[dx].push_back(mp1[recipes[i]]);
income[mp1[recipes[i]]] ++;
}
}
vector<int>vis(cnt + 1, 0);
queue<int> q;
for (auto s : supplies) {
if (mp1[s] == 0) continue;
int dx = mp1[s];
vis[dx] = true;
q.push(dx);
}
while (!q.empty()) {
int ver = q.front(); q.pop();
for (auto g : graph[ver]) {
if (vis[g]) continue;
if (--income[g] == 0) {
vis[g] = true;
q.push(g);
}
}
}
for (auto s : recipes) {
if (vis[mp1[s]]) res.push_back(s);
}
return res;
}
};
题目描述：给你两个串(s)与(t)，(s)串只包含('(')与(')')，(t)串只包含(0 , 1)，其含义是：如果是(0)表示(s)串对应位上的字符可以更改，否则不可更改，判断(s)串是否是合法的括号序列。
思路：考虑将(t_i = 0)的位置作为通配符，定义(minCntleft)表示当前最少的左括号，(maxCntleft)表示当前最多的左括号，每次遇到(t_i = 1)的位置就将二者都(+1)或(-1)，遇到可以更改的地方，就将(maxCntleft + 1) ，并将(minCntleft - 1)，注意最少的左括号数应当不小于(0)，同时(maxCntleft)在任意时刻都必须非负。最终判断(minCntleft)是否等于(0)即可。
时间复杂度：(O(n))
参考代码：
class Solution {
PRivate:
public:
bool canBeValid(string s, string t) {
int n = s.size();
if(n % 2 == 1) return false;
int minCntleft = 0 , maxCntleft = 0;
for(int i = 0 ; i < n ; ++i){
if(s[i] == '(' && t[i] == '1') ++minCntleft, ++maxCntleft;
else if(s[i] == ')' && t[i] == '1') --minCntleft , --maxCntleft;
else --minCntleft, ++maxCntleft;
minCntleft = max(0 , minCntleft);
if(maxCntleft < 0) return false;
}
return minCntleft == 0;
}
};
题目描述：给你两个正整数 (left) 和 (right) ，满足 (left leq right) 。请你计算 闭区间$ [left, right]$ 中所有整数的 乘积 。由于乘积可能非常大，你需要将它按照以下步骤 缩写 ：统计乘积中 后缀 (0) 的数目，将这个数目记为$ C$ 。 比方说，(1000)中有(3)个后缀 (0) ，(546) 中没有后缀 (0) 。将乘积中剩余数字记为(d) 。如果 (d > 10) ，那么将乘积表示为 (<pre>...<suf>)的形式，其中 (<pre>) 表示乘积最 开始 的 (5)个数位，(<suf>)表示删除后缀 (0) 之后 结尾的(5) 个数位。如果 (d leq 10) ，我们不对它做修改。比方说，我们将 (1234567654321) 表示为 (12345...54321) ，但是 (1234567) 仍然表示为(1234567) 。最后，将乘积表示为 字符串 (''<pre>...<suf>eC'') 。比方说，(12345678987600000)被表示为 (''12345...89876e5'') 。请你返回一个字符串，表示 闭区间 ([left, right]) 中所有整数 乘积 的 缩写 。
思路：首先考虑尾数(C)，考虑求出([left , right])内每个数含有因子(2)和因子(5)的个数，二者中的较小者即为(C);对于尾数考虑将([left , right])之间的数字全剔除掉因子(2)和(5)，然后构成一个新的数组，这些数字的乘积再乘以多剔除的(2)或(5)就是乘积中不含尾数(0)的部分，我们只需要在计算过程中对该乘积模(1e5)即可；对于前缀部分，考虑在计算乘积过程中保留高(12)位(理论上不正确)，然后再最后再保留高(5)位；判断乘积是否超过(10)位可以在计算前缀部分的时候判断一下即可。
可以参考大佬写的题解 ：拆一个区间内所有数乘积的缩写
时间复杂度：(O(nLOGn))
参考代码：
class Solution {
private:
string cal(vector<int>& nums, int cnt2, int cnt5) {
long long res = 1, ans = 1;//前缀 后缀
const int mod = 1e5;//模
bool flag = false;//标记成绩长度是否超过10位
int cnt = 5;//前缀保留过程中需要进行的除法次数至少为5
//计算数组内的元素的成绩
for (auto num : nums) {
res *= num;
ans *= num;
ans %= mod;
if (res >= 1e10)flag = true;//乘积超过了10位
while (res >= 1e12)res /= 10, --cnt;//保留高12位 并对除法计数次数-1
}
//乘上多剔除的2
for (int i = 1; i <= cnt2; ++i) {
res *= 2;
ans *= 2;
ans %= mod;
if (res >= 1e10)flag = true;
while (res >= 1e12)res /= 10, --cnt;
}
//乘上多剔除的5
for (int i = 1; i <= cnt5; ++i) {
res *= 5;
ans *= 5;
ans %= mod;
if (res >= 1e10)flag = true;
while (res >= 1e12)res /= 10, --cnt;
}
//前缀只保留5位
while (res >= 100000) res /= 10, --cnt;
//如果还没除到5次 还需要继续除
while (cnt > 0) res /= 10, --cnt;
string t1 = to_string(res), t2 = to_string(ans);
if (flag) {//如果长度超过10
while (t2.size() < 5) t2 = '0' + t2;//需要对后缀补前导0
return t1 + "..." + t2;
}
//长度小于10
else if (res == 0) return to_string(ans);//前缀等于0
//前缀不等于0 就需要对后缀补前导0
while (t2.size() < 5) t2 = '0' + t2;
return t1 + t2;
}
public:
string abbreviateProduct(int left, int right) {
//将区间转化成数组，并剔除因子2 和 5
vector<int> nums;
int cnt2 = 0, cnt5 = 0;
for (int i = left; i <= right; ++i) {
int j = i;
while (j % 2 == 0) ++cnt2, j /= 2;
while (j % 5 == 0) ++cnt5, j /= 5;
nums.push_back(j);
}
//0的个数等于 2 和 5中的较小者
int C = min(cnt2, cnt5);
//计算前面的部分
string res = cal(nums, cnt2 - C, cnt5 - C);
return res + "e" + to_string(C);
}
};
以上是脚本宝典为你收集整理的LeetCode第68场双周赛全部内容，希望文章能够帮你解决LeetCode第68场双周赛所遇到的问题。
本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。