数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学统计树中加权字符串是给定字符串的字母异位词的节点数
要检查加权字符串是给定字符串的变位词的树的节点，请对树执行深度优先搜索 (DFS)。从根节点开始，遍历每个节点并通过为节点值中的每个字符分配权重来计算加权字符串。将此加权字符串与给定字符串进行比较以检查变位词匹配。如果它们是变位词，则增加计数。递归地遍历每个节点的子节点。最后，返回满足条件的节点总数。这种方法确保遍历树中的每个节点，只检查那些加权字符串是给定字符串的变位词的节点。
使用的方法
深度优先搜索 (DFS)
先序遍历
深度优先搜索 (DFS)
深度优先搜索 (DFS) 是一种算法方法，用于对加权字符串是给定字符串的变位词的树的节点进行编号。从根节点开始，我们以深度优先的方式访问每个节点。在每个节点处，我们通过为节点值中的每个字符分配权重来计算加权字符串。然后，我们将此加权字符串与给定字符串进行比较。如果它们是变位词，则我们增加计数。我们递归地遍历每个节点的子节点，重复此过程，直到遍历所有节点。最后，我们返回满足变位词条件的节点总数。
算法
将变量“count”初始化为 0。
定义一个递归函数“DFS(node, targetString, characterCount)”来执行 DFS 遍历。
通过根据“characterCount”为每个字符分配权重来计算“节点”的加权字符串。
检查加权字符串是否为“targetString”的变位词。如果是，则增加“count”。
通过将“节点”的字符添加到其中来更新“characterCount”。
递归地为“节点”的每个子节点调用“DFS”。
使用树的根节点、给定字符串作为“targetString”和一个空的“characterCount”字典调用“DFS”函数。
返回“count”的值，它表示加权字符串是给定字符串的变位词的节点总数。
示例
#include <iostream>
#include <unordered_map>
#include <algorithm>
using namespace std;
int totalCount = 0;
string calculateWeightedString(const string& word, unordered_map<char, int>& characterCount) {
string weightedString = "";
for (char c : word) {
weightedString += to_string(characterCount[c]);
}
return weightedString;
}
struct Node {
string data;
Node* next;
Node(const string& value) : data(value), next(nullptr) {}
};
void DFS(Node* node, const string& targetString, unordered_map<char, int> characterCount) {
string hub = calculateWeightedString(node->data, characterCount);
sort(hub.begin(), hub.end()); // Sort the weighted string for comparison
if (hub == targetString) {
totalCount++;
}
for (char c : node->data) {
characterCount[c]++;
}
if (node->next) {
DFS(node->next, targetString, characterCount);
}
}
int main() {
Node* root = new Node("root"); // Sample code - Initialize the root node
root->next = new Node("child1");
root->next->next = new Node("child2");
root->next->next->next = new Node("grandchild1");
root->next->next->next->next = new Node("grandchild2");
string targetString = "toor"; // Sample code - Set the target string
unordered_map<char, int> characterCount; // Store character counts for each node
for (char c : root->data) {
characterCount[c] = 0;
}
DFS(root, targetString, characterCount);
cout << "Total Count: " << totalCount << endl;
// Clean up memory
Node* current = root;
while (current) {
Node* nextNode = current->next;
delete current;
current = nextNode;
}
return 0;
}
输出
Total Count: 0
先序遍历
要使用先序遍历方法检查加权字符串是给定字符串的变位词的树的节点，请从根节点开始。计算当前节点的加权字符串并将其与给定字符串进行比较。如果它们是变位词，则增加计数。然后，递归地遍历左子树并重复此过程。之后，递归地遍历右子树并应用相同的步骤。累加来自两个子树的计数。最后，返回总数，包括树中所有加权字符串是给定字符串的变位词的节点。
算法
将计数变量初始化为 0。
定义一个函数 preorderCount(node, givenString, count)
如果当前节点无效，则返回。
计算当前节点的加权字符串。
如果加权字符串是给定字符串的变位词，则增加计数。
递归地对左子树调用 preorderCount。
递归地对右子树调用 preorderCount。
调用 preorderCount(root, givenString, count)，其中 root 是树的根节点。
返回计数变量的值。
来自两个子树的计数之和，加上增加的计数。
示例
#include <iostream>
#include <algorithm>
#include <string>
struct Node {
std::string data;
Node* left;
Node* right;
Node(const std::string& value) : data(value), left(nullptr), right(nullptr) {}
};
// Function to calculate the weighted string
std::string calculateWeightedString(const std::string& input) {
std::string weightedString = input;
std::sort(weightedString.begin(), weightedString.end());
return weightedString;
}
// Function to perform preorder count
int preorderCount(Node* node, const std::string& given, int count) {
if (node == nullptr) {
return count;
}
std::string weightedString = calculateWeightedString(node->data);
if (weightedString == given) {
count++;
}
count = preorderCount(node->left, given, count);
count = preorderCount(node->right, given, count);
return count;
}
int main() {
// Binary Search Tree creation
Node* root = new Node("abc");
root->left = new Node("cba");
root->right = new Node("bac");
std::string givenString = "abc";
int tally = 0;
int result = preorderCount(root, givenString, tally);
std::cout << "Preorder count: " << result << std::endl;
// TODO: Free memory by deleting the nodes
return 0;
}
输出
Preorder count: 3
结论
本文提供了一种算法方法，用于检查加权字符串是给定字符串的变位词的树的节点。它解释了两种方法：深度优先搜索 (DFS) 和先序遍历。DFS 方法包括递归地遍历树，计算每个节点的加权字符串，并将其与给定字符串进行比较。先序遍历方法按照特定顺序访问节点，计算加权字符串，并累加满足变位词条件的节点计数。给定的代码示例说明了这两种方法的用法。
73 次查看
