資料結構
網路
關係資料庫管理系統 (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 次檢視
