Holy Shit

Holy Shit这样的一系列算法题：我完全不知道怎么做，即便想采用BF的方法，也不知道怎么做，无奈只能看答案，结果答案还看不懂，分类都不知道如何分类的这样一系列的题。不过聪明的你肯定知道怎么做。所以吾之shit，彼之甘露。

Leetcode 60 Permutation Sequence

1. Permutation Sequence The set [1,2,3,...,_n_] contains a total of n! unique permutations. By listing and labeling all of the permutations in order, we get the following sequence for n = 3:
2. "123"
3. "132"
4. "213"
5. "231"
6. "312"
7. "321"

Given n and k, return the k permutation sequence.

Note:

• Given n will be between 1 and 9 inclusive.
• Given k will be between 1 and n! inclusive.

Example 1:

Input: n = 3, k = 3

Output: “213”

Example 2:

Input: n = 4, k = 9

Output: “2314”

评论区的一个C++的答案)

class Solution {
public:
    string getPermutation(int n, int k) {
          int i, j, f=1;
        string s(n,'0');
        for(i = 1; i <= n; i++)
        {
            f *= i;
            s[i - 1] += i;
        }
        for(i=0,k--; i < n; i++)
        {
            f /= n - i;
            j = i + k/f;
            char c=s[j];
            for(;j>i;j--)
                s[j]=s[j-1];
            k%=f;
            s[i]=c;
        }
        return s;
    }
};

Leetcode 1519 子树中标签相同的节点数

给你一棵树（即，一个连通的无环无向图），这棵树由编号从 0 到 n - 1 的 n 个节点组成，且恰好有 n - 1 条 edges 。树的根节点为节点 0 ，树上的每一个节点都有一个标签，也就是字符串 labels 中的一个小写字符（编号为 i 的 节点的标签就是 labels[i] ）

边数组 edges 以 edges[i] = [ai, bi] 的形式给出，该格式表示节点 ai 和 bi 之间存在一条边。

返回一个大小为 n 的数组，其中 ans[i] 表示第 i 个节点的子树中与节点 i 标签相同的节点数。

树 T 中的子树是由 T 中的某个节点及其所有后代节点组成的树。

示例 1：

输入：n = 7, edges = [[0,1],[0,2],[1,4],[1,5],[2,3],[2,6]], labels = “abaedcd”

输出：[2,1,1,1,1,1,1]

解释：节点 0 的标签为 ‘a’ ，以 ‘a’ 为根节点的子树中，节点 2 的标签也是 ‘a’ ，因此答案为 2 。注意树中的每个节点都是这棵子树的一部分。

节点 1 的标签为 ‘b’ ，节点 1 的子树包含节点 1、4 和 5，但是节点 4、5 的标签与节点 1 不同，故而答案为 1（即，该节点本身）。

示例 2：

输入：n = 4, edges = [[0,1],[1,2],[0,3]], labels = “bbbb”

输出：[4,2,1,1]

解释：节点 2 的子树中只有节点 2 ，所以答案为 1 。

节点 3 的子树中只有节点 3 ，所以答案为 1 。

节点 1 的子树中包含节点 1 和 2 ，标签都是 ‘b’ ，因此答案为 2 。

节点 0 的子树中包含节点 0、1、2 和 3，标签都是 ‘b’，因此答案为 4 。

示例 3：

输入：n = 5, edges = [[0,1],[0,2],[1,3],[0,4]], labels = “aabab”

输出：[3,2,1,1,1]

示例 4：

输入：n = 6, edges = [[0,1],[0,2],[1,3],[3,4],[4,5]], labels = “cbabaa”

输出：[1,2,1,1,2,1]

示例 5：

输入：n = 7, edges = [[0,1],[1,2],[2,3],[3,4],[4,5],[5,6]], labels = “aaabaaa”

输出：[6,5,4,1,3,2,1]

提示：

1 <= n <= 10^5

edges.length == n - 1

edges[i].length == 2

0 <= ai, bi < n

ai != bi

labels.length == n

labels 仅由小写英文字母组成

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/number-of-nodes-in-the-sub-tree-with-the-same-label

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

超出时间限制
代码分成两部分，第一部分是构建出这棵树，第二部分是遍历每个节点，找到和该节点具备相同label的子树

class Solution {
public:
    vector<int> countSubTrees(int n, vector<vector<int>>& edges, string labels) {
        map<int, vector<int>>constructTree;
        map<int, vector<int>>treeRela;
        for(auto &vec: edges)
        {
            constructTree[vec[0]].push_back(vec[1]);
            constructTree[vec[1]].push_back(vec[0]);
        }
        vector<bool>treeflag(n, false);
        stack<int>treestack;
        treestack.push(0);
        while(!treestack.empty())
        {
            int tmp = treestack.top();
            treestack.pop();
            treeflag[tmp] = true;
            vector<int>tmpvec = constructTree[tmp];
            for(auto& val : tmpvec)
            {
                if(treeflag[val])
                    continue;
                treestack.push(val);
                treeRela[tmp].push_back(val);
            }
        }
        vector<int>ret(n , 1);
        for(auto index = treeRela.begin(); index != treeRela.end(); index++)
        {
            char label = labels[index->first];
            vector<int>labelvec = index->second;
            for(auto &vec : labelvec)
            {
                stack<int>stacklabel;
                stacklabel.push(vec);
                while(!stacklabel.empty())
                {
                    int top = stacklabel.top();
                    stacklabel.pop();
                    for(auto &tmp : treeRela[top])
                    {
                        stacklabel.push(tmp);
                    }
                    if(label == labels[top])
                        ret[index->first]++;
                }
            }
        }
        return ret;
    }
};