leetcode刷题记录15（2023-08-19）【字符串解码(括号问题、栈的运用) | 等式方程的可满足性(并查集) | 除法求值(加权) | 根据身高重建队列(自定义排序)】

ゞ浴缸里的玫瑰 2024-03-24 18:46 73阅读 0赞

## 394. 字符串解码 ##

给定一个经过编码的字符串，返回它解码后的字符串。

编码规则为: k\[encoded\_string\]，表示其中方括号内部的 encoded\_string 正好重复 k 次。注意 k 保证为正整数。

你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。

此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2\[4\] 的输入。

示例 1：  
输入：s = “3\[a\]2\[bc\]”  
输出：“aaabcbc”

示例 2：  
输入：s = “3\[a2\[c\]\]”  
输出：“accaccacc”

示例 3：  
输入：s = “2\[abc\]3\[cd\]ef”  
输出：“abcabccdcdcdef”

示例 4：  
输入：s = “abc3\[cd\]xyz”  
输出：“abccdcdcdxyz”

提示：  
 1 < = s . l e n g t h < = 30 1 <= s.length <= 30 1<=s.length<=30  
s 由小写英文字母、数字和方括号 ‘\[\]’ 组成  
s 保证是一个 有效 的输入。  
s 中所有整数的取值范围为 \[1, 300\]

主要思路是不仅要保存**当前的字符串**入栈，还要保存**字符串对应的倍数**入栈。

#include<string>
    #include<iostream>
    #include<stack>
    using namespace std;
    
    class Solution {
        
    public:
        string decodeString(string s) {
        
            stack<string>nums;
            stack<string>strs;
            string num = "";
            string str = "";
            for (int i = 0; i < s.size(); i++) {
        
                if (s[i] >= '0' && s[i] <= '9') {
        
                    num += s[i];
                }
                else if (s[i] == '[') {
         // 入栈
                    nums.push(num);
                    num = "";
                    strs.push(str);
                    str = "";
                }
                else if (s[i] == ']') {
         // 出栈
                    string curRes = strs.top();
                    for (int j = 0; j < atoi(nums.top().c_str()); j++) {
        
                        curRes += str;
                    }
                    str = curRes;
                    nums.pop();
                    strs.pop();
                }
                else {
        
                    str += s[i];
                }
            }
            return str;
        }
    };
    
    int main() {
        
        Solution sol;
        string s = "3[a2[c]]";
        string res = sol.decodeString(s);
        cout << res << endl;
        return 0;
    }

## 990. 等式方程的可满足性 ##

给定一个由表示变量之间关系的字符串方程组成的数组，每个字符串方程 equations\[i\] 的长度为 4，并采用两种不同的形式之一：“a==b” 或 “a!=b”。在这里，a 和 b 是小写字母（不一定不同），表示单字母变量名。

只有当可以将整数分配给变量名，以便满足所有给定的方程时才返回 true，否则返回 false。

示例 1：  
输入：\[“a = = == ==b”,“b ! = != !=a”\]  
输出：false  
解释：如果我们指定，a = 1 且 b = 1，那么可以满足第一个方程，但无法满足第二个方程。没有办法分配变量同时满足这两个方程。

示例 2：  
输入：\[“b = = == ==a”,“a = = == ==b”\]  
输出：true  
解释：我们可以指定 a = 1 且 b = 1 以满足满足这两个方程。

示例 3：  
输入：\[“a = = == ==b”,“b = = == ==c”,“a = = == ==c”\]  
输出：true

示例 4：  
输入：\[“a = = == ==b”,“b ! = != !=c”,“c = = == ==a”\]  
输出：false

示例 5：  
输入：\[“c = = == ==c”,“b = = == ==d”,“x ! = != !=z”\]  
输出：true

提示：

1.  1 <= equations.length <= 500
2.  equations\[i\].length == 4
3.  equations\[i\]\[0\] 和 equations\[i\]\[3\] 是小写字母
4.  equations\[i\]\[1\] 要么是 ‘=’，要么是 ‘!’
5.  equations\[i\]\[2\] 是 ‘=’

主要利用了并查集进行求解，将并查集的大小预设为26，代码比较简单，如下：

class UFSets {
        
    public:
        vector<int> vec;
    
        UFSets(int sz) {
        
            vec = vector<int>(sz, -1);
        }
        int Find(int x) {
        
            while (vec[x] >= 0)x = vec[x];
            return x;
        }
        bool Union(int root1, int root2) {
        
            int r1 = Find(root1);
            int r2 = Find(root2);
            if (r1 == r2) {
        
                return false;
            }
            if (vec[r2] < vec[r1]) {
        
                vec[r2] = vec[r1] + vec[r2];
                vec[r1] = r2;
            }
            else {
        
                vec[r1] = vec[r1] + vec[r2];
                vec[r2] = r1;
            }
            return true;
        }
    };
    
    
    class Solution {
        
    public:
        bool equationsPossible(vector<string>& equations) {
        
            UFSets ufst(26); // 最多26个字母
    
            for (auto str : equations) {
        
                if (str[1] == '=') {
        
                    // 进行合并
                    ufst.Union(str[0] - 'a', str[3] - 'a');
                }
            }
    
            for (auto str : equations) {
        
                if (str[1] == '!') {
        
                    if (ufst.Find(str[0] - 'a') == ufst.Find(str[3] - 'a')) {
        
                        return false;
                    }
                }
            }
    
            return true;
        }
    };

## 399. 除法求值 ##

给你一个变量对数组 equations 和一个实数值数组 values 作为已知条件，其中 equations\[i\] = \[Ai, Bi\] 和 values\[i\] 共同表示等式 Ai / Bi = values\[i\] 。每个 Ai 或 Bi 是一个表示单个变量的字符串。

另有一些以数组 queries 表示的问题，其中 queries\[j\] = \[Cj, Dj\] 表示第 j 个问题，请你根据已知条件找出 Cj / Dj = ? 的结果作为答案。

返回 所有问题的答案 。如果存在某个无法确定的答案，则用 -1.0 替代这个答案。如果问题中出现了给定的已知条件中没有出现的字符串，也需要用 -1.0 替代这个答案。

注意：输入总是有效的。你可以假设除法运算中不会出现除数为 0 的情况，且不存在任何矛盾的结果。

注意：未在等式列表中出现的变量是未定义的，因此无法确定它们的答案。

示例 1：

输入：equations = \[\[“a”,“b”\],\[“b”,“c”\]\], values = \[2.0,3.0\], queries = \[\[“a”,“c”\],\[“b”,“a”\],\[“a”,“e”\],\[“a”,“a”\],\[“x”,“x”\]\]  
输出：\[6.00000,0.50000,-1.00000,1.00000,-1.00000\]  
解释：  
条件：a / b = 2.0, b / c = 3.0  
问题：a / c = ?, b / a = ?, a / e = ?, a / a = ?, x / x = ?  
结果：\[6.0, 0.5, -1.0, 1.0, -1.0 \]  
注意：x 是未定义的 => -1.0

示例 2：

输入：equations = \[\[“a”,“b”\],\[“b”,“c”\],\[“bc”,“cd”\]\], values = \[1.5,2.5,5.0\], queries = \[\[“a”,“c”\],\[“c”,“b”\],\[“bc”,“cd”\],\[“cd”,“bc”\]\]  
输出：\[3.75000,0.40000,5.00000,0.20000\]

示例 3：

输入：equations = \[\[“a”,“b”\]\], values = \[0.5\], queries = \[\[“a”,“b”\],\[“b”,“a”\],\[“a”,“c”\],\[“x”,“y”\]\]  
输出：\[0.50000,2.00000,-1.00000,-1.00000\]

提示：

*  1 <= equations.length <= 20
 *  equations\[i\].length == 2
 *  1 <= Ai.length, Bi.length <= 5
 *  values.length == equations.length
 *  0.0 < values\[i\] <= 20.0
 *  1 <= queries.length <= 20
 *  queries\[i\].length == 2
 *  1 <= Cj.length, Dj.length <= 5
 *  Ai, Bi, Cj, Dj 由小写英文字母与数字组成

主要参考了官方题解，写的很棒！ [https://leetcode.cn/problems/evaluate-division/solutions/548634/399-chu-fa-qiu-zhi-nan-du-zhong-deng-286-w45d/][https_leetcode.cn_problems_evaluate-division_solutions_548634_399-chu-fa-qiu-zhi-nan-du-zhong-deng-286-w45d].

利用了并查集来实现，但这个并查集是加权并查集，同时采用了路径压缩，很巧妙，代码如下：

#include<iostream>
    #include<unordered_map>
    #include<vector>
    #include<string>
    using namespace std;
    
    // 加权并查集
    class UFSets {
        
    public:
        vector<int> parent;
    
        vector<double> weight;
    
        UFSets(int n) {
        
            parent = vector<int>(n);
            weight = vector<double>(n);
            for (int i = 0; i < n; i++) {
        
                parent[i] = i;
                weight[i] = 1.0;
            }
        }
    
        int Find(int x) {
        
            if (x != parent[x]) {
        
                int origin = parent[x];
                parent[x] = Find(parent[x]);
                weight[x] *= weight[origin];
            }
            return parent[x];
        }
    
        void Union(int x, int y, double value) {
        
            int rootX = Find(x);
            int rootY = Find(y);
            if (rootX == rootY) {
        
                return;
            }
            parent[rootX] = rootY;
            weight[rootX] = weight[y] * value / weight[x];
        }
    
        double isConnected(int x, int y) {
        
            int rootX = Find(x);
            int rootY = Find(y);
            if (rootX == rootY) {
        
                return weight[x] / weight[y];
            }
            else {
        
                return -1.0;
            }
        }
    };
    
    class Solution {
        
    public:
        vector<double> calcEquation(vector<vector<string>>& equations, vector<double>& values, vector<vector<string>>& queries) {
        
            // 1. 建立并查集
            // 考虑最大的情况，所有变量都不相同
            UFSets ufs = UFSets(2 * equations.size());
    
            // 建立一个变量到id的映射
            unordered_map<string, int> mp;
            int id = 0; // 给变量编号
            for (int i = 0; i < equations.size(); i++) {
        
                if (mp.find(equations[i][0]) == mp.end()) {
        
                    mp[equations[i][0]] = id;
                    id++;
                }
    
                if (mp.find(equations[i][1]) == mp.end()) {
        
                    mp[equations[i][1]] = id;
                    id++;
                }
                ufs.Union(mp[equations[i][0]], mp[equations[i][1]], values[i]);
            }
    
            // 2. 查询
            vector<double> res(queries.size());
            for (int i = 0; i < queries.size(); i++) {
        
                if (mp.find(queries[i][0]) == mp.end() ||
                    mp.find(queries[i][1]) == mp.end()) {
        
                    res[i] = -1.0;
                }
                else {
        
                    res[i] = ufs.isConnected(mp[queries[i][0]], mp[queries[i][1]]);
                }
            }
            return res;
        }
    };

## 406. 根据身高重建队列 ##

假设有打乱顺序的一群人站成一个队列，数组 people 表示队列中一些人的属性（不一定按顺序）。每个 people\[i\] = \[hi, ki\] 表示第 i 个人的身高为 hi ，前面 正好 有 ki 个身高大于或等于 hi 的人。

请你重新构造并返回输入数组 people 所表示的队列。返回的队列应该格式化为数组 queue ，其中 queue\[j\] = \[hj, kj\] 是队列中第 j 个人的属性（queue\[0\] 是排在队列前面的人）。

示例 1：

输入：people = \[\[7,0\],\[4,4\],\[7,1\],\[5,0\],\[6,1\],\[5,2\]\]  
输出：\[\[5,0\],\[7,0\],\[5,2\],\[6,1\],\[4,4\],\[7,1\]\]  
解释：  
编号为 0 的人身高为 5 ，没有身高更高或者相同的人排在他前面。  
编号为 1 的人身高为 7 ，没有身高更高或者相同的人排在他前面。  
编号为 2 的人身高为 5 ，有 2 个身高更高或者相同的人排在他前面，即编号为 0 和 1 的人。  
编号为 3 的人身高为 6 ，有 1 个身高更高或者相同的人排在他前面，即编号为 1 的人。  
编号为 4 的人身高为 4 ，有 4 个身高更高或者相同的人排在他前面，即编号为 0、1、2、3 的人。  
编号为 5 的人身高为 7 ，有 1 个身高更高或者相同的人排在他前面，即编号为 1 的人。  
因此 \[\[5,0\],\[7,0\],\[5,2\],\[6,1\],\[4,4\],\[7,1\]\] 是重新构造后的队列。

示例 2：

输入：people = \[\[6,0\],\[5,0\],\[4,0\],\[3,2\],\[2,2\],\[1,4\]\]  
输出：\[\[4,0\],\[5,0\],\[2,2\],\[3,2\],\[1,4\],\[6,0\]\]

提示：

*   1 < = p e o p l e . l e n g t h < = 2000 1 <= people.length <= 2000 1<=people.length<=2000
 *   0 < = h i < = 1 0 6 0 <= hi <= 10^6 0<=hi<=106
 *   0 < = k i < p e o p l e . l e n g t h 0 <= ki < people.length 0<=ki<people.length
 *  题目数据确保队列可以被重建

主要思路为排序，按照自定义的顺序进行，先排个子矮的、k值大的，留够k个空位后安置它。

#include<iostream>
    #include<vector>
    #include<algorithm>
    using namespace std;
    
    class Solution {
        
    public:
        vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
        
            // 通过构造一个匿名函数，对vector中元素进行排序
            sort(people.begin(), people.end(), [](const vector<int>& u, const vector<int>& v) {
        
                return u[0] < v[0] || u[0] == v[0] && u[1] > v[1];
                });
    
            vector<vector<int>> res(people.size(), vector<int>());
    
            for (const auto & person : people) {
        
                // 前边需要的空位个数（比他大，比他相等但k更小
                int space = person[1] + 1;
                for (int i = 0; i < res.size();i++) {
        
                    if (res[i].empty()) {
        
                        space--;
                        if (space == 0) {
        
                            res[i] = person;
                            break; // 开始下一个数组
                        }
                    }
                }
    
            }
            return res;
        }
    };

[https_leetcode.cn_problems_evaluate-division_solutions_548634_399-chu-fa-qiu-zhi-nan-du-zhong-deng-286-w45d]: https://leetcode.cn/problems/evaluate-division/solutions/548634/399-chu-fa-qiu-zhi-nan-du-zhong-deng-286-w45d/