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使用自带的base64库进行base64编码和解码

《Python使用自带的base64库进行base64编码和解码》在Python中,处理数据的编码和解码是数据传输和存储中非常普遍的需求,其中,Base64是一种常用的编码方案,本文我将详细介绍如何使... 目录引言使用python的base64库进行编码和解码编码函数解码函数Base64编码的应用场景注意

C#数据结构之字符串(string)详解

《C#数据结构之字符串(string)详解》:本文主要介绍C#数据结构之字符串(string),具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录转义字符序列字符串的创建字符串的声明null字符串与空字符串重复单字符字符串的构造字符串的属性和常用方法属性常用方法总结摘

Java实现时间与字符串互相转换详解

《Java实现时间与字符串互相转换详解》这篇文章主要为大家详细介绍了Java中实现时间与字符串互相转换的相关方法,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录一、日期格式化为字符串(一)使用预定义格式(二)自定义格式二、字符串解析为日期(一)解析ISO格式字符串(二)解析自定义

Python实现将MySQL中所有表的数据都导出为CSV文件并压缩

《Python实现将MySQL中所有表的数据都导出为CSV文件并压缩》这篇文章主要为大家详细介绍了如何使用Python将MySQL数据库中所有表的数据都导出为CSV文件到一个目录,并压缩为zip文件到... python将mysql数据库中所有表的数据都导出为CSV文件到一个目录,并压缩为zip文件到另一个

利用Go语言开发文件操作工具轻松处理所有文件

《利用Go语言开发文件操作工具轻松处理所有文件》在后端开发中,文件操作是一个非常常见但又容易出错的场景,本文小编要向大家介绍一个强大的Go语言文件操作工具库,它能帮你轻松处理各种文件操作场景... 目录为什么需要这个工具?核心功能详解1. 文件/目录存javascript在性检查2. 批量创建目录3. 文件

python中字符串拼接的几种方法及优缺点对比详解

《python中字符串拼接的几种方法及优缺点对比详解》在Python中,字符串拼接是常见的操作,Python提供了多种方法来拼接字符串,每种方法有其优缺点和适用场景,以下是几种常见的字符串拼接方法,需... 目录1. 使用 + 运算符示例:优缺点:2. 使用&nbsjsp;join() 方法示例:优缺点:3

java字符串数字补齐位数详解

《java字符串数字补齐位数详解》:本文主要介绍java字符串数字补齐位数,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录Java字符串数字补齐位数一、使用String.format()方法二、Apache Commons Lang库方法三、Java 11+的St

C++字符串提取和分割的多种方法

《C++字符串提取和分割的多种方法》在C++编程中,字符串处理是一个常见的任务,尤其是在需要从字符串中提取特定数据时,本文将详细探讨如何使用C++标准库中的工具来提取和分割字符串,并分析不同方法的适用... 目录1. 字符串提取的基本方法1.1 使用 std::istringstream 和 >> 操作符示

C语言字符函数和字符串函数示例详解

《C语言字符函数和字符串函数示例详解》本文详细介绍了C语言中字符分类函数、字符转换函数及字符串操作函数的使用方法,并通过示例代码展示了如何实现这些功能,通过这些内容,读者可以深入理解并掌握C语言中的字... 目录一、字符分类函数二、字符转换函数三、strlen的使用和模拟实现3.1strlen函数3.2st

Java反转字符串的五种方法总结

《Java反转字符串的五种方法总结》:本文主要介绍五种在Java中反转字符串的方法,包括使用StringBuilder的reverse()方法、字符数组、自定义StringBuilder方法、直接... 目录前言方法一:使用StringBuilder的reverse()方法方法二:使用字符数组方法三:使用自