TikTok真题第3天 | 856.括号的分数、2115. 从给定原材料中找到所有可以做出的菜、394.字符串解码

本文主要是介绍TikTok真题第3天 | 856.括号的分数、2115. 从给定原材料中找到所有可以做出的菜、394.字符串解码,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

856.括号的分数

题目链接:856.score-of-parentheses

解法:

leetcode官方的题解基本是每个字都认得,连起来就看不懂。

使用栈来解决,后进先出,后面加入的左括号,先弹出和右括号去匹配。定义一个记录分数的栈,假设string前面是空字符串(我不知道为啥这么假设),所以开始就要先压入一个0。

接下来遍历字符,如果是左括号,则压入0,如果是右括号,则弹出栈顶元素score:(1)如果栈顶元素是0,说明前一个是左括号,那么构成 (),则分数为1;(2)如果栈顶元素为1,说明前一个还是右括号,那么构成的是 )),说明是(A)这种类型,那么分数为 2*score。

最后返回栈顶元素。

解法参考:栈

边界条件:无

时间复杂度:O(n)

空间复杂度:O(n)

class Solution {
public:int scoreOfParentheses(string s) {stack<int> scores;scores.push(0);for (char c: s) {if (c=='(') {scores.push(0);} else {int score = scores.top();scores.pop();if (score==0) {scores.top() += 1;} else {scores.top() += 2 * score;}}}return scores.top();}
};

2115. 从给定原材料中找到所有可以做出的菜

题目链接:find-all-possible-recipes-from-given-supplies

解法:

ingredient 指向 recipe,构建有向图,同时记录各recipe的入度。那么ingredient是入度为0的,而recipe的入度不为0。

以supplies(入度为0)初始化队列,遍历整个图,减少recipe的入度。如果recipe的入度已经为0,那么可以做该道菜,加入队列中。这也就是拓扑排序。

迭代结束后,取出入度为0的所有recipe,作为结果。也就是说,图中 indegree=0 的 recipes 即为可以做出的菜。

解法参考:拓扑排序+BFS

拓扑排序的思想:

拓扑排序(Topological Sorting)是图论中的一个概念,用于对有向无环图(Directed Acyclic Graph,简称 DAG)的所有顶点进行排序。这种排序方式满足一个条件:对于图中的每一条有向边 UV(从顶点 U 指向顶点 V),在排序结果中顶点 U 都出现在顶点 V 之前。

拓扑排序的一个典型应用是在任务调度或课程规划中确定任务或课程的执行顺序。在这些应用中,边表示一个任务必须在另一个任务之前完成的关系。

拓扑排序的特点和步骤如下:

  1. 特点

    • 拓扑排序只适用于有向无环图(DAG)。如果图中存在环,那么没有有效的拓扑排序。
    • 对于给定的图,拓扑排序可能不是唯一的。可能存在多个有效的排序顺序。
  2. 步骤

    • 计算入度:首先计算图中每个顶点的入度(指向该顶点的边的数量)。
    • 初始化队列:将所有入度为 0 的顶点放入队列中。
    • 处理队列:当队列非空时,执行以下步骤:
      • 从队列中移除一个顶点。
      • 将该顶点添加到拓扑排序的结果中。
      • 减少所有由该顶点指向的顶点的入度。如果某个顶点的入度变为 0,则将其加入队列。
  3. 结果

    • 最终,队列处理完毕后,如果排序结果中的顶点数量与图中的顶点总数相同,则图是有向无环的,并且得到了一个有效的拓扑排序。
    • 如果排序结果中的顶点数量少于图中的顶点总数,则图中存在环,无法进行有效的拓扑排序。

边界条件:无

class Solution {
public:vector<string> findAllRecipes(vector<string>& recipes, vector<vector<string>>& ingredients, vector<string>& supplies) {unordered_map<string, vector<string>> graph;unordered_map<string, int> indgree;// 构建图,为 原料->菜,同时记录菜的入度for (size_t i=0; i<recipes.size(); i++) {for (const auto& ingred: ingredients[i]) {graph[ingred].push_back(recipes[i]);indgree[recipes[i]] ++;}}// 使用supplies构建队列,用于迭代做菜queue<string> deque;for (string sup: supplies) {deque.push(sup);}// 对supplies进行迭代,并更新入度while (!deque.empty()) {string cur = deque.front();deque.pop();for (const auto& next: graph[cur]) {indgree[next]--;if (indgree[next]==0) deque.push(next);}}// 入度为0的即为可以做的菜vector<string> result;for (string recp: recipes) {if (indgree[recp]==0) result.push_back(recp); }return result;}
};

394.字符串解码

题目链接:394.decode-string

解法:

第一种解法:栈,参考资料:栈题解

需要从内向外生成与拼接字符串,这与栈的先入后出特性对应,所以使用栈。栈里面放的是当前单词(可能有多个letter)前面的单词和数字,以便于在遇到 ] 时弹出来拼接为新单词。其他的看题解吧。

第二种写法是递归,感觉很容易出错,就不管了。

边界条件:无

时间复杂度:O(n)

空间复杂度:O(n)

class Solution {
public:string decodeString(string s) {// string 表示数字前面的字母,int表示[前的数字std::stack<pair<string, int>> stack;string res;int multi = 0;for (char c: s) {// 遇到[,那下一步就是字母了,那么先把前面的字母和数字加入栈中备用if (c == '[') {stack.push({res, multi});res.clear();multi = 0;} else if (c == ']') {auto [last_res, cur_multi] = stack.top();stack.pop();string cur_res;// c++中的实现有点麻烦for (int i=0; i<cur_multi; i++) {cur_res += res;}res = last_res + cur_res;} else if ('0' <= c && c <= '9') {// 数字可能是多位数multi = multi * 10 + (c - '0');} else {// 可能有多个字母res += c;}}return res;}
};

这篇关于TikTok真题第3天 | 856.括号的分数、2115. 从给定原材料中找到所有可以做出的菜、394.字符串解码的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/533850

相关文章

Python中反转字符串的常见方法小结

《Python中反转字符串的常见方法小结》在Python中,字符串对象没有内置的反转方法,然而,在实际开发中,我们经常会遇到需要反转字符串的场景,比如处理回文字符串、文本加密等,因此,掌握如何在Pyt... 目录python中反转字符串的方法技术背景实现步骤1. 使用切片2. 使用 reversed() 函

MySQL查询JSON数组字段包含特定字符串的方法

《MySQL查询JSON数组字段包含特定字符串的方法》在MySQL数据库中,当某个字段存储的是JSON数组,需要查询数组中包含特定字符串的记录时传统的LIKE语句无法直接使用,下面小编就为大家介绍两种... 目录问题背景解决方案对比1. 精确匹配方案(推荐)2. 模糊匹配方案参数化查询示例使用场景建议性能优

MySQL 获取字符串长度及注意事项

《MySQL获取字符串长度及注意事项》本文通过实例代码给大家介绍MySQL获取字符串长度及注意事项,本文通过实例代码给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录mysql 获取字符串长度详解 核心长度函数对比⚠️ 六大关键注意事项1. 字符编码决定字节长度2

python3如何找到字典的下标index、获取list中指定元素的位置索引

《python3如何找到字典的下标index、获取list中指定元素的位置索引》:本文主要介绍python3如何找到字典的下标index、获取list中指定元素的位置索引问题,具有很好的参考价值,... 目录enumerate()找到字典的下标 index获取list中指定元素的位置索引总结enumerat

Python打印对象所有属性和值的方法小结

《Python打印对象所有属性和值的方法小结》在Python开发过程中,调试代码时经常需要查看对象的当前状态,也就是对象的所有属性和对应的值,然而,Python并没有像PHP的print_r那样直接提... 目录python中打印对象所有属性和值的方法实现步骤1. 使用vars()和pprint()2. 使

Python pip下载包及所有依赖到指定文件夹的步骤说明

《Pythonpip下载包及所有依赖到指定文件夹的步骤说明》为了方便开发和部署,我们常常需要将Python项目所依赖的第三方包导出到本地文件夹中,:本文主要介绍Pythonpip下载包及所有依... 目录步骤说明命令格式示例参数说明离线安装方法注意事项总结要使用pip下载包及其所有依赖到指定文件夹,请按照以

Springboot3+将ID转为JSON字符串的详细配置方案

《Springboot3+将ID转为JSON字符串的详细配置方案》:本文主要介绍纯后端实现Long/BigIntegerID转为JSON字符串的详细配置方案,s基于SpringBoot3+和Spr... 目录1. 添加依赖2. 全局 Jackson 配置3. 精准控制(可选)4. OpenAPI (Spri

使用Python实现base64字符串与图片互转的详细步骤

《使用Python实现base64字符串与图片互转的详细步骤》要将一个Base64编码的字符串转换为图片文件并保存下来,可以使用Python的base64模块来实现,这一过程包括解码Base64字符串... 目录1. 图片编码为 Base64 字符串2. Base64 字符串解码为图片文件3. 示例使用注意

golang float和科学计数法转字符串的实现方式

《golangfloat和科学计数法转字符串的实现方式》:本文主要介绍golangfloat和科学计数法转字符串的实现方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望... 目录golang float和科学计数法转字符串需要对float转字符串做处理总结golang float

Python如何判断字符串中是否包含特殊字符并替换

《Python如何判断字符串中是否包含特殊字符并替换》这篇文章主要为大家详细介绍了如何使用Python实现判断字符串中是否包含特殊字符并使用空字符串替换掉,文中的示例代码讲解详细,感兴趣的小伙伴可以了... 目录python判断字符串中是否包含特殊字符方法一:使用正则表达式方法二:手动检查特定字符Pytho