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

相关文章

Java中字符串转时间与时间转字符串的操作详解

《Java中字符串转时间与时间转字符串的操作详解》Java的java.time包提供了强大的日期和时间处理功能,通过DateTimeFormatter可以轻松地在日期时间对象和字符串之间进行转换,下面... 目录一、字符串转时间(一)使用预定义格式(二)自定义格式二、时间转字符串(一)使用预定义格式(二)自

Java字符串操作技巧之语法、示例与应用场景分析

《Java字符串操作技巧之语法、示例与应用场景分析》在Java算法题和日常开发中,字符串处理是必备的核心技能,本文全面梳理Java中字符串的常用操作语法,结合代码示例、应用场景和避坑指南,可快速掌握字... 目录引言1. 基础操作1.1 创建字符串1.2 获取长度1.3 访问字符2. 字符串处理2.1 子字

一文详解如何在Python中从字符串中提取部分内容

《一文详解如何在Python中从字符串中提取部分内容》:本文主要介绍如何在Python中从字符串中提取部分内容的相关资料,包括使用正则表达式、Pyparsing库、AST(抽象语法树)、字符串操作... 目录前言解决方案方法一:使用正则表达式方法二:使用 Pyparsing方法三:使用 AST方法四:使用字

Java字符串处理全解析(String、StringBuilder与StringBuffer)

《Java字符串处理全解析(String、StringBuilder与StringBuffer)》:本文主要介绍Java字符串处理全解析(String、StringBuilder与StringBu... 目录Java字符串处理全解析:String、StringBuilder与StringBuffer一、St

MySQL中动态生成SQL语句去掉所有字段的空格的操作方法

《MySQL中动态生成SQL语句去掉所有字段的空格的操作方法》在数据库管理过程中,我们常常会遇到需要对表中字段进行清洗和整理的情况,本文将详细介绍如何在MySQL中动态生成SQL语句来去掉所有字段的空... 目录在mysql中动态生成SQL语句去掉所有字段的空格准备工作原理分析动态生成SQL语句在MySQL

MySQL更新某个字段拼接固定字符串的实现

《MySQL更新某个字段拼接固定字符串的实现》在MySQL中,我们经常需要对数据库中的某个字段进行更新操作,本文就来介绍一下MySQL更新某个字段拼接固定字符串的实现,感兴趣的可以了解一下... 目录1. 查看字段当前值2. 更新字段拼接固定字符串3. 验证更新结果mysql更新某个字段拼接固定字符串 -

Java String字符串的常用使用方法

《JavaString字符串的常用使用方法》String是JDK提供的一个类,是引用类型,并不是基本的数据类型,String用于字符串操作,在之前学习c语言的时候,对于一些字符串,会初始化字符数组表... 目录一、什么是String二、如何定义一个String1. 用双引号定义2. 通过构造函数定义三、St

golang获取当前时间、时间戳和时间字符串及它们之间的相互转换方法

《golang获取当前时间、时间戳和时间字符串及它们之间的相互转换方法》:本文主要介绍golang获取当前时间、时间戳和时间字符串及它们之间的相互转换,本文通过实例代码给大家介绍的非常详细,感兴趣... 目录1、获取当前时间2、获取当前时间戳3、获取当前时间的字符串格式4、它们之间的相互转化上篇文章给大家介

Python使用自带的base64库进行base64编码和解码

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

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

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