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;
    }
};