Holy Shit这样的一系列算法题:我完全不知道怎么做,即便想采用BF的方法,也不知道怎么做,无奈只能看答案,结果答案还看不懂,分类都不知道如何分类的这样一系列的题。不过聪明的你肯定知道怎么做。所以吾之shit,彼之甘露。
Leetcode 60 Permutation Sequence
- 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:"123"
"132"
"213"
"231"
"312"
"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”
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;
}
};