C++深度优先搜索(DFS)算法的应用:树中可以形成回文的路径数

简介: C++深度优先搜索(DFS)算法的应用:树中可以形成回文的路径数

本文涉及知识点

深度优先搜索(DFS) 状态压缩

题目

给你一棵 树(即,一个连通、无向且无环的图),根 节点为 0 ,由编号从 0 到 n - 1 的 n 个节点组成。这棵树用一个长度为 n 、下标从 0 开始的数组 parent 表示,其中 parent[i] 为节点 i 的父节点,由于节点 0 为根节点,所以 parent[0] == -1 。

另给你一个长度为 n 的字符串 s ,其中 s[i] 是分配给 i 和 parent[i] 之间的边的字符。s[0] 可以忽略。

找出满足 u < v ,且从 u 到 v 的路径上分配的字符可以 重新排列 形成 回文 的所有节点对 (u, v) ,并返回节点对的数目。

如果一个字符串正着读和反着读都相同,那么这个字符串就是一个 回文 。

示例 1:

输入:parent = [-1,0,0,1,1,2], s = “acaabc”

输出:8

解释:符合题目要求的节点对分别是:

  • (0,1)、(0,2)、(1,3)、(1,4) 和 (2,5) ,路径上只有一个字符,满足回文定义。
  • (2,3),路径上字符形成的字符串是 “aca” ,满足回文定义。
  • (1,5),路径上字符形成的字符串是 “cac” ,满足回文定义。
  • (3,5),路径上字符形成的字符串是 “acac” ,可以重排形成回文 “acca” 。
    示例 2:
    输入:parent = [-1,0,0,0,0], s = “aaaaa”
    输出:10
    解释:任何满足 u < v 的节点对 (u,v) 都符合题目要求。
    参数提示
    n == parent.length == s.length
    1 <= n <= 105
    对于所有 i >= 1 ,0 <= parent[i] <= n - 1 均成立
    parent[0] == -1
    parent 表示一棵有效的树
    s 仅由小写英文字母组成

解法一稍稍超时,通过不了

分析

状态压缩

排序后能构成回文,那只有两种可能,一:所有字符数量都为偶数。二,有一个字符数量为奇数,其余全部是偶数。可以用二进制状态压缩,每个二进制位表示某个字符是否为偶数。1表示z是奇数数量,2表示y是奇数数量,3表示yz都是奇数数量。

异或(^)

增加一个字符可以用异或操作,由于异或的逆操作就是自己,所以删除字符也用异或。

难理解的地方

mNums记录以下路径:

起点和终点都是cur的路径
起点是cur,终点是已处理子树的任意节点

childNums:记录以child为起点,以child为根节点的子树的任意节点为终点的路径。

下面以{-1,0,0}来说明,由于起点是固定的,所以下表只记录终点。路径指的是:以child子树中的节点为起点,以mNums中的节点为终点的路径

mNums childNums 路径
处理根节点 {0} {}
处理节点1 {0} {1} {0,1}
处理节点2 {0,1} {2} {0,2},{1,2}
{0,1,2}

总结:第四列的路径,就是mNums 和childNums 各取一个节点的两两组合。

注意

一个节点没有字符,所以不是合法路径。

ChangeNum

不要枚举mNums 和childNums ,枚举其中的一个和27种合法可能。

核心代码

class Solution {
public:
long long countPalindromePaths(vector& parent, string s) {
m_c = parent.size();
m_str = s;
m_vNeiBo.assign(m_c, vector());
for (int i = 0; i < 26; i++)
{
m_iVilidMask[i] = 1 << i;
}
m_llRet = 0;
int iRoot = -1;
for (int i = 0; i < m_c; i++)
{
if (-1 == parent[i])
{
iRoot = i;
}
else
{
m_vNeiBo[parent[i]].emplace_back(i);
}
}
std::unordered_map<int, int> mNums;
dfs(iRoot, mNums);
return m_llRet ;
}
void dfs(int cur, std::unordered_map<int, int>& mNums)
{
const int curMask = 1 << (m_str[cur] - ‘a’);
mNums[curMask]++;
for (const auto& child : m_vNeiBo[cur])
{
std::unordered_map<int, int> childNums;
dfs(child, childNums);
ChangeNum(mNums, childNums,curMask);
for (const auto& it : childNums)
{
mNums[it.first ^ curMask] += it.second;
}
}
}
void ChangeNum(const std::unordered_map<int, int>& mNums, const std::unordered_map<int, int>& childNums, const int curMask )
{
for (const auto& it : childNums)
{
for (int i = 0; i < 27; i++)
{
const int iNeedMask = it.first ^ m_iVilidMask[i] ^ curMask;
if (mNums.count(iNeedMask))
{
m_llRet += (long long)it.second * mNums.find(iNeedMask)->second;
}
}
}
}
//状态压缩 1表示z是奇数数量,2表示y是奇数数量,3表示yz都是奇数数量
int m_iVilidMask[27] = { 0 };//记录所有字符都是偶数和只有一个字符是奇数
vector<vector> m_vNeiBo;
//vector m_vNums;
int m_c;
long long m_llRet = 0;//不包括单节点的合法路径数
string m_str;
};

测试用例

template
void Assert(const vector& v1, const vector& v2)
{
if (v1.size() != v2.size())
{
assert(false);
return;
}
for (int i = 0; i < v1.size(); i++)
{
Assert(v1[i], v2[i]);
}
}
int main()
{
Solution slu;
vector parent;
long long res;
string s;
parent = { -1 };
s = “a”;
res = slu.countPalindromePaths(parent, s);
Assert(res, 0LL);
parent = { -1,0 };
s = “aa”;
res = slu.countPalindromePaths(parent, s);
Assert(res, 1LL);
parent = { -1,0,1 };
s = “aaa”;
res = slu.countPalindromePaths(parent, s);
Assert(res, 3LL);
parent = { -1,0,0 };
s = “aaa”;
res = slu.countPalindromePaths(parent, s);
Assert(res, 3LL);
parent = { -1,0,0 };
s = “aba”;
res = slu.countPalindromePaths(parent, s);
Assert(res,2LL);
parent = { -1,0,0 };
s = “baa”;
res = slu.countPalindromePaths(parent, s);
Assert(res, 3LL);
parent = { -1,0,0,1,1,2 };
s = “acaabc”;
res = slu.countPalindromePaths(parent, s);
Assert(res, 8LL);
parent = { -1, 0, 0, 0, 0 };
s = “aaaaa”;
res = slu.countPalindromePaths(parent, s);
Assert(res, 10LL);
//CConsole::Out(res);

}

解法二

分析

假定节点A,B的公共最近祖先是C,那么A到B的路径为:A->C->B和路径A->0->B的 字符数量的奇偶性相同。A->0可以拆分成A->C->0 ,0->B可以拆分成0->C->B。0到C和C到0抵消了。

### 时间复杂度

o(27n)。n是节点数量,27是合法掩码的数量。

代码

class Solution{
public:
  long long countPalindromePaths(vector<int>&parent, string s) {
    m_c = parent.size();
    m_str = s;
    m_vNeiBo.assign(m_c, vector<int>());
    for (int i = 0; i < 26; i++)
    {
      m_iVilidMask[i] = 1 << i;
    }
    m_llRet = 0;
    m_mMaskNums.clear();
    int iRoot = -1;
    for (int i = 0; i < m_c; i++)
    {
      if (-1 == parent[i])
      {
        iRoot = i;
      }
      else
      {
        m_vNeiBo[parent[i]].emplace_back(i);
      }
    }
    dfs(iRoot,0);
    return m_llRet;
  }
  void dfs(int cur,int iMask)
  {
    const int curMask = iMask ^ ( 1 << (m_str[cur] - 'a'));
    for (int i = 0; i < 27; i++)
    {
      const int iNeedMask = m_iVilidMask[i] ^ curMask;
      if (m_mMaskNums.count(iNeedMask))
      {
        m_llRet += m_mMaskNums[iNeedMask];
      }
    }
    m_mMaskNums[curMask]++;
    for (const auto& child : m_vNeiBo[cur])
    {
      dfs(child, curMask);
    }
  }
  int m_iVilidMask[27] = { 0 };//记录所有字符都是偶数和只有一个字符是奇数
  vector<vector<int>> m_vNeiBo;
  std::unordered_map<int,int> m_mMaskNums;
  int m_c;
  long long m_llRet = 0;//不包括单节点的合法路径数
  string m_str;
};

扩展阅读

视频课程

有效学习:明确的目标 及时的反馈 拉伸区(难度合适),可以先学简单的课程,请移步CSDN学院,听白银讲师(也就是鄙人)的讲解。

https://edu.csdn.net/course/detail/38771

如何你想快速形成战斗了,为老板分忧,请学习C#入职培训、C++入职培训等课程

https://edu.csdn.net/lecturer/6176

相关下载

想高屋建瓴的学习算法,请下载《闻缺陷则喜算法册》doc版

https://download.csdn.net/download/he_zhidan/88348653

鄙人想对大家说的话
闻缺陷则喜是一个美好的愿望,早发现问题,早修改问题,给老板节约钱。
墨家名称的来源:有所得以墨记之。
如果程序是一条龙,那算法就是他的是睛

测试环境

操作系统:win7 开发环境: VS2019 C++17

或者 操作系统:win10 开发环境: VS2022 C++17


相关文章
|
19天前
|
存储 监控 算法
员工上网行为监控中的Go语言算法:布隆过滤器的应用
在信息化高速发展的时代,企业上网行为监管至关重要。布隆过滤器作为一种高效、节省空间的概率性数据结构,适用于大规模URL查询与匹配,是实现精准上网行为管理的理想选择。本文探讨了布隆过滤器的原理及其优缺点,并展示了如何使用Go语言实现该算法,以提升企业网络管理效率和安全性。尽管存在误报等局限性,但合理配置下,布隆过滤器为企业提供了经济有效的解决方案。
63 8
员工上网行为监控中的Go语言算法:布隆过滤器的应用
|
4天前
|
存储 C++
【C++数据结构——树】哈夫曼树(头歌实践教学平台习题) 【合集】
【数据结构——树】哈夫曼树(头歌实践教学平台习题)【合集】目录 任务描述 相关知识 测试说明 我的通关代码: 测试结果:任务描述 本关任务:编写一个程序构建哈夫曼树和生成哈夫曼编码。 相关知识 为了完成本关任务,你需要掌握: 1.如何构建哈夫曼树, 2.如何生成哈夫曼编码。 测试说明 平台会对你编写的代码进行测试: 测试输入: 1192677541518462450242195190181174157138124123 (用户分别输入所列单词的频度) 预
35 14
【C++数据结构——树】哈夫曼树(头歌实践教学平台习题) 【合集】
|
4天前
|
Java C++
【C++数据结构——树】二叉树的基本运算(头歌实践教学平台习题)【合集】
本关任务:编写一个程序实现二叉树的基本运算。​ 相关知识 创建二叉树 销毁二叉树 查找结点 求二叉树的高度 输出二叉树 //二叉树节点结构体定义 structTreeNode{ intval; TreeNode*left; TreeNode*right; TreeNode(intx):val(x),left(NULL),right(NULL){} }; 创建二叉树 //创建二叉树函数(简单示例,手动构建) TreeNode*create
31 12
|
4天前
|
C++
【C++数据结构——树】二叉树的性质(头歌实践教学平台习题)【合集】
本文档介绍了如何根据二叉树的括号表示串创建二叉树,并计算其结点个数、叶子结点个数、某结点的层次和二叉树的宽度。主要内容包括: 1. **定义二叉树节点结构体**:定义了包含节点值、左子节点指针和右子节点指针的结构体。 2. **实现构建二叉树的函数**:通过解析括号表示串,递归地构建二叉树的各个节点及其子树。 3. **使用示例**:展示了如何调用 `buildTree` 函数构建二叉树并进行简单验证。 4. **计算二叉树属性**: - 计算二叉树节点个数。 - 计算二叉树叶子节点个数。 - 计算某节点的层次。 - 计算二叉树的宽度。 最后,提供了测试说明及通关代
31 10
|
4天前
|
存储 算法 测试技术
【C++数据结构——树】二叉树的遍历算法(头歌教学实验平台习题) 【合集】
本任务旨在实现二叉树的遍历,包括先序、中序、后序和层次遍历。首先介绍了二叉树的基本概念与结构定义,并通过C++代码示例展示了如何定义二叉树节点及构建二叉树。接着详细讲解了四种遍历方法的递归实现逻辑,以及层次遍历中队列的应用。最后提供了测试用例和预期输出,确保代码正确性。通过这些内容,帮助读者理解并掌握二叉树遍历的核心思想与实现技巧。
21 2
|
13天前
|
存储 算法 安全
基于红黑树的局域网上网行为控制C++ 算法解析
在当今网络环境中,局域网上网行为控制对企业和学校至关重要。本文探讨了一种基于红黑树数据结构的高效算法,用于管理用户的上网行为,如IP地址、上网时长、访问网站类别和流量使用情况。通过红黑树的自平衡特性,确保了高效的查找、插入和删除操作。文中提供了C++代码示例,展示了如何实现该算法,并强调其在网络管理中的应用价值。
|
11天前
|
存储 算法 安全
基于哈希表的文件共享平台 C++ 算法实现与分析
在数字化时代,文件共享平台不可或缺。本文探讨哈希表在文件共享中的应用,包括原理、优势及C++实现。哈希表通过键值对快速访问文件元数据(如文件名、大小、位置等),查找时间复杂度为O(1),显著提升查找速度和用户体验。代码示例展示了文件上传和搜索功能,实际应用中需解决哈希冲突、动态扩容和线程安全等问题,以优化性能。
|
18天前
|
算法 安全 C++
用 C++ 算法控制员工上网的软件,关键逻辑是啥?来深度解读下
在企业信息化管理中,控制员工上网的软件成为保障网络秩序与提升办公效率的关键工具。该软件基于C++语言,融合红黑树、令牌桶和滑动窗口等算法,实现网址精准过滤、流量均衡分配及异常连接监测。通过高效的数据结构与算法设计,确保企业网络资源优化配置与安全防护升级,同时尊重员工权益,助力企业数字化发展。
38 4
|
19天前
|
存储 缓存 算法
探索企业文件管理软件:Python中的哈希表算法应用
企业文件管理软件依赖哈希表实现高效的数据管理和安全保障。哈希表通过键值映射,提供平均O(1)时间复杂度的快速访问,适用于海量文件处理。在Python中,字典类型基于哈希表实现,可用于管理文件元数据、缓存机制、版本控制及快速搜索等功能,极大提升工作效率和数据安全性。
52 0
|
2月前
|
机器学习/深度学习 算法 数据挖掘
C语言在机器学习中的应用及其重要性。C语言以其高效性、灵活性和可移植性,适合开发高性能的机器学习算法,尤其在底层算法实现、嵌入式系统和高性能计算中表现突出
本文探讨了C语言在机器学习中的应用及其重要性。C语言以其高效性、灵活性和可移植性,适合开发高性能的机器学习算法,尤其在底层算法实现、嵌入式系统和高性能计算中表现突出。文章还介绍了C语言在知名机器学习库中的作用,以及与Python等语言结合使用的案例,展望了其未来发展的挑战与机遇。
57 1