回文树题目回顾

题目

输入数据

2
3
1 2 1
1 2
2 3
2
2 2
1 2

输出数据

4
3

输入输出数据分析

这里,我们输入了两组数据,每组数据互相独立,互不影响。输出数据分别为各组输入数据经过核心算法后计算出的符合回文串定义的数量。核心算法就是回文串统计算法。执行回文串统计算法前需准备这些数据:

  1. 点的数目n
  2. 每个点身上的值a[1],a[2],a[3].......a[n]
  3. n-1个无向边

以第一组为例。点的数目是3。这三个点身上的值分别为a[1]=1、a[2]=2、a[3]=1。两条边分别为1-2,2-3。由于用例简单,可以直接判断共有4个回文串,分别是a[1],a[2],a[3],a[1]-a[2]-a[3]

测试算法请这样做

  1. 给出组数后回车
  2. 给出第一组的点数n后回车
  3. 随后给出这n个点各自带的值,用空格分开,输入完毕后回车
  4. 给出n-1组边,每组边一行,给出边的两个点即可,用空格分开两个点,用回车分开各组边。
  5. 给完边后,就会输出回文串的数目。
  6. 如果组数大于1,重复步骤2、3、4、5。
  7. 组数给够后,控制台应用就会结束。

Java 代码以及算法分析

主执行函数

输入组数
用于处理轮次,程序一开始就是输入组数。每一组独立执行 huiwenTree(in); 回文树算法。

huiwenTree()函数

state

  • point_Value:各点身上的值使用Map <Integer,Integer>数据结构来存储。key 为点标号,value
    为该点身上的值。
  • point_Connection:边关系使用Map<Integer,ArrayList<Integer>>数据结构来存储。key 为点标号,value 为 ArrayList<Integer> 数据结构类型。value 存储着所有与该点直接相连的点标号。

prepare

  • 函数一开始对数据进行初始化,并从控制台获得点的数目(pointLen)。
    comparator
  • 同时使用Comparator<Integer>类,重写compare()函数,用于将 ArrayList 上与某点相连的所有点标号数组元素按照其值的大小进行升序排序。数组标号越小的,其点值一定小于或等于后面的。后面会进一步解释这么做的原因,此处仅说明Comparator<Integer>的使用目的。
    set and reset
  • 从控制台获得pointLen个点的值,将点标号与其值存入point_Value中。在遍历的同时,对point_Connection中的多个ArrayList进行初始化,将初始化结果存入point_Connection中。
    set edge
  • 从控制台获得pointLen-1对点的标号point1point2,从而获得边关系,并存入point_Connection中。对于point1来说,point2是它的邻接点;对于point2来说,point1是它的邻接点。所以,每增加一条边要对这两个点所属的的ArrayList增加新元素(两个ArrayList各新增一个元素)。
    arraylist.sort
  • 每个点所带领的ArrayList数组都存着若干个点序号。为了在同一个数组里方便的提取同value的所有点序号,我选择按照各点身上的值由小至大对这些杂乱的点序号进行排序。这样,对于同数组中同value的点序号,它们的数组下标号就一定是由小至大且依次加一的关系,使用for循环从最小的下标开始到最大的下标结束,就可以遍历所有同value的点序号以及点。
    开始挖掘
  • 遍历每一个点从而统计回文串的数目。dig_huiwenTree(i,NOTEXIST,NOTEXIST,i);是遍历回文串为奇数个点的开端,从一个点开始,紧接着3个点,5个点,7个点.....dig_huiwenTree(i,relate,i,relate);是遍历回文串为偶数个点的开端,从点标号i和与i同value的所有邻接点标号relate开始,2个点,4个点,6个点......这两个函数已经将所有符合要求的长度为1或者为2的回文串找出并代入dig_huiwenTree函数进行计数并预备尝试进一步延长该回文串。下面将即将解释函数四个传入变量的含义。

dig_huiwenTree(int edgeLeft,int nearedgeLeft,int nearedgeRight,int edgeRight) 函数

全局视角

  • edgeLeft:是指当前回文串上左对称中心最左边界点的点序号,如回文串 a[1]-a[2]-a[3] 的例子,点序号就是最左边的序号1。
  • edgeRight:是指当前回文串上右对称中心最右边界点的点序号,同样是上面的例子,点序号就是最右边的序号3。
  • nearedgeLeft:是指与edgeLeft紧紧邻着的点的点序号,上面的例子里,与点1紧紧邻着的就是点2。(点序号)
  • nearedgeRight:是指与edgeRight紧紧邻着的点的点序号,上面的例子里,与点3紧紧邻着的就是点2。(点序号)
  • 特别地,当回文串上只有一个点,那么edgeLeft=edgeRightnearedgeLeftnearedgeRight不存在,标记为NOTEXIST
  • 特别地,当回文串上只有两个点,那么edgeLeftedgeRight代表了这两个点,且nearedgeLeft=edgeRight && nearedgeRight=edgeLeft
    first
  • 回文串上的参数能够传入dig_huiwenTree函数,就说明传入的这些点以及中间可能已省略的点已经构成回文串。这时需要对回文串计数器进行+1操作。为防止重复计数,就需要规定左方边界点序号要不大于右方的(定义为不小于也是可以的),比如点序号edgeLeft作为左方,点序号edgeRight作为右方完成一次计数后,将点序号edgeLeft作为右方,点序号edgeRight作为左方再执行计数,就会导致重复。
  • 算法后续要围绕左边界点和右边界点上各自所有相邻点对上面的回文串进行进一步扩展与延伸,从而找到更长的回文串。显然,每成功完成一次回文串扩展,原回文串会在左右两端会各自增加一个点,共增加两个点。增加的这两个点,成为新回文串上的最左边界点edgeLeft’最右边界点edgeRight’,原旧回文串上的edgeLeftedgeRight更新为新回文串上的nearedgeLeft’nearedgeRight’。参数转化完成后,继续对新回文串调用dig_huiwenTree函数做下一步递归重复上面的算法。后面会解释为什么需要nearedgeLeft和nearedgeRight。
    explore
  • 要遍历与左边界点有邻接关系的所有邻接点,只需要访问point_Connection中根据该点序号即key找到value即多个邻接点构成的ArrayList。按下标递增的方向依次固定ArrayList中的每一个点作为可能的左延伸点expend。需要注意的是,点 nearedgeLeft 也一定会出现在此ArrayList中(NOTEXIST除外),expend 不能等于 nearedgeLeft,即不能扩展已经包含在回文串里的点。
  • 同理,我们需要遍历右边界上的所有邻接点,也是遍历另外一个ArrayList实现。在按照数组下标递增的顺序遍历过程中,要寻找与点expend同value的所有点,我们只需要确定该数组的下标取值范围即可。理由上面已经说过,ArrayList经过排序后要获得同value的点序号,它们的数组下标号就一定是由小至大且依次加一的关系。符合条件的若干个点都可能是右延伸点。遍历数组,使用while循环跳过所有小于该value的点,一旦遇到同value或数组边界,就退出循环,从而获得下标边界下限值round_min。类似的,利用while循环跳过所有不大于该value的点,一旦遇到大于该value或数组边界,就退出循环,从而获得下标边界上限值round_max。下标取值范围确定为[round_min,round_max)。
  • 用变量j在给定的下标取值范围内执行遍历,确定可能的右延伸点expend2 (其点标号=point_Connection.get(edgeRight).get(j))。需要注意的是点 expend2 不能是点expend,虽然它们的值必须相等,否则将回文串将闭环,造成死循环。同时,点expend2 不能是 点nearedgeRight,即不能扩展已经包含在回文串里的点。
  • 每找到符合条件的左延伸点和右延伸点后,就可以进行参数转化(边界点、紧邻点已发生变化),作为新回文串,继续调用该函数进行计数和可能的探索与延伸。
  • 点 expend 每发生一次更新,round_min和round_max并不需要重置。这是因为,由于ArrayList已经按value升序排序,点 expend 每发生一次更新,其点 value 不可能减小。右边界点的另外一个ArrayList也已经按value升序排序,凡是下标小于round_min的点其值一定不符合条件,一定会被跳过;对于round_max来说,同理。当然,如果仍然要将round_min和round_max重置为0,这也不会有什么错误。基于算法优化的角度,我们选择不重置。
最后修改:2020 年 06 月 03 日 09 : 52 PM
如果觉得我的文章对你有用,请随意赞赏,感谢您支持6zgm.com !