PHP解决并优化算法题皇位继承顺序(皇位继承顺序 数组 算法 优化 递归 图解)

皇位继承顺序

题目大概的意思就是, 要写一个类.要求如下: 1)创建国家(对象)的时候输入一个人名, 那个人就是国王 2)国家里面的每个人都可以生娃, (开局一光棍,造娃靠自己), 生出来的娃也归属于这个国家 3)时不时还会死人 4)时不时还要捋一下继承的顺序,活着才能继承 (不然怎么知道该干掉谁才能上位)国王排序第一,然后到大王子, 到大王子的大儿子, 到大儿子的大儿子…到大儿子的二儿子… 大王子一脉死光了才到二王子

如图绿色的是继承顺序

原题如下, 可以忽略

一个王国里住着国王、他的孩子们、他的孙子们等等。每一个时间点，这个家庭里有人出生也有人死亡。

这个王国有一个明确规定的皇位继承顺序，第一继承人总是国王自己。我们定义递归函数 Successor(x, curOrder) ，给定一个人 x 和当前的继承顺序，该函数返回 x 的下一继承人。

Successor(x, curOrder): 如果 x 没有孩子或者所有 x 的孩子都在 curOrder 中： 如果 x 是国王，那么返回 null 否则，返回 Successor(x 的父亲, curOrder) 否则，返回 x 不在 curOrder 中最年长的孩子 比方说，假设王国由国王，他的孩子 Alice 和 Bob （Alice 比 Bob 年长）和 Alice 的孩子 Jack 组成。

一开始， curOrder 为 [“king”]. 调用 Successor(king, curOrder) ，返回 Alice ，所以我们将 Alice 放入 curOrder 中，得到 [“king”, “Alice”] 。 调用 Successor(Alice, curOrder) ，返回 Jack ，所以我们将 Jack 放入 curOrder 中，得到 [“king”, “Alice”, “Jack”] 。 调用 Successor(Jack, curOrder) ，返回 Bob ，所以我们将 Bob 放入 curOrder 中，得到 [“king”, “Alice”, “Jack”, “Bob”] 。 调用 Successor(Bob, curOrder) ，返回 null 。最终得到继承顺序为 [“king”, “Alice”, “Jack”, “Bob”] 。 通过以上的函数，我们总是能得到一个唯一的继承顺序。

请你实现 ThroneInheritance 类：

ThroneInheritance(string kingName) 初始化一个 ThroneInheritance 类的对象。国王的名字作为构造函数的参数传入。 void birth(string parentName, string childName) 表示 parentName 新拥有了一个名为 childName 的孩子。 void death(string name) 表示名为 name 的人死亡。一个人的死亡不会影响 Successor 函数，也不会影响当前的继承顺序。你可以只将这个人标记为死亡状态。 string[] getInheritanceOrder() 返回 除去 死亡人员的当前继承顺序列表。

示例：

输入： [“ThroneInheritance”, “birth”, “birth”, “birth”, “birth”, “birth”, “birth”, “getInheritanceOrder”, “death”, “getInheritanceOrder”] [[“king”], [“king”, “andy”], [“king”, “bob”], [“king”, “catherine”], [“andy”, “matthew”], [“bob”, “alex”], [“bob”, “asha”], [null], [“bob”], [null]] 输出： [null, null, null, null, null, null, null, [“king”, “andy”, “matthew”, “bob”, “alex”, “asha”, “catherine”], null, [“king”, “andy”, “matthew”, “alex”, “asha”, “catherine”]]

解释： ThroneInheritance t= new ThroneInheritance(“king”); // 继承顺序：king t.birth(“king”, “andy”); // 继承顺序：king > andy t.birth(“king”, “bob”); // 继承顺序：king > andy > bob t.birth(“king”, “catherine”); // 继承顺序：king > andy > bob > catherine t.birth(“andy”, “matthew”); // 继承顺序：king > andy

matthew > bob > catherine t.birth(“bob”, “alex”); // 继承顺序：king > andy > matthew > bob > alex > catherine t.birth(“bob”, “asha”); // 继承顺序：king > andy > matthew > bob > alex > asha > catherine t.getInheritanceOrder(); // 返回 [“king”, “andy”, “matthew”, “bob”, “alex”, “asha”, “catherine”] t.death(“bob”); // 继承顺序：king > andy > matthew > bob（已经去世）> alex > asha > catherine t.getInheritanceOrder(); // 返回 [“king”, “andy”, “matthew”, “alex”, “asha”, “catherine”]

提示：

1 <= kingName.length, parentName.length, childName.length, name.length <= 15 kingName，parentName， childName 和 name 仅包含小写英文字母。 所有的参数 childName 和 kingName 互不相同。 所有 death 函数中的死亡名字 name 要么是国王，要么是已经出生了的人员名字。 每次调用 birth(parentName, childName) 时，测试用例都保证 parentName 对应的人员是活着的。 最多调用 105 次birth 和 death 。 最多调用 10 次 getInheritanceOrder 。

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/throne-inheritance 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

默认代码模板

class ThroneInheritance { /** * @param String $kingName */ function __construct($kingName) { } /** * @param String $parentName * @param String $childName * @return NULL */ function birth($parentName, $childName) { } /** * @param String $name * @return NULL */ function death($name) { } /** * @return String[] */ function getInheritanceOrder() { } } /** * Your ThroneInheritance object will be instantiated and called as such: * $obj = ThroneInheritance($kingName); * $obj->birth($parentName, $childName); * $obj->death($name); * $ret_3 = $obj->getInheritanceOrder(); */

编写测试用例

//执行的方法 $methods = ["ThroneInheritance","birth","death","birth","getInheritanceOrder","birth","death","getInheritanceOrder"]; //方法对应的参数 $params = [["king"],["king","clyde"],["king"],["clyde","shannon"],[null],["shannon","scott"],["clyde"],[null]]; //第一个肯定是实例化王国 array_shift($methods); array_shift($params); $obj = new ThroneInheritance('king'); //遍历参数 $res = []; while ($method = array_shift($methods)){ $param = array_shift($params); if ($method == 'birth'){ $res []= $obj->birth($param[0], $param[1]); }elseif ($method == 'death'){ $res []= $obj->death($param[0]); }else{ $res []= $obj->getInheritanceOrder(); } } echo json_encode($res);exit();

解题步骤

每个生一个娃就实例化一个ThroneInheritance 对象, 每个人都有自己的小娃娃, 挂了就标记一下. 要继承顺序的时候就跳过他 每个人都有以下属性

/** * @var string 名字 */ private $name = ''; /** * @var int 是否已挂 */ private $isDeath = 0; /** * 该对象下的娃娃 * @var self[] $children */ private $children = [];

有以下方法

/** * 创建一个对象只需要他的名字 * @param String $kingName */ function __construct($kingName) { $this->name = $kingName; return; }

时间复杂度O(n)

/** * 递归去找到老爸自个生自个的娃娃 * @param String $parentName * @param String $childName * @return NULL */ function birth($parentName, $childName) { if ($this->name == $parentName){ $this->children []= new self($childName); return null; }else{ foreach ($this->children as $child) { if ($child->birth($parentName, $childName) === null){ return null; } } } return false; }

时间复杂度O(n)

/** * 递归找到自己, 自个让自个挂(不用你动手, 我自己来) * @param String $name * @return NULL */ function death($name) { if ($this->name == $name){ $this->isDeath = 1; return null; }else{ foreach ($this->children as $child) { if ($child->death($name) === null){ return null; } } } return false; }

时间复杂度O(n)

/** * 递归自己后代的皇位继承顺序, 把自己排在他们前面 * @return String[] */ function getInheritanceOrder() { if ($this->isDeath){ $res = []; }else{ $res = [$this->name]; } foreach ($this->children as $child) { $res = array_merge($res,$child->getInheritanceOrder()); } return $res; }

然后结果就

超时了啊啊啊啊啊

时间复杂度优化一下

把当前对象的所有后代都记录一下, 让死人变得更快, O(1) 加一个属性

/** * 该对象的所有后代 * @var array */ private $descendant = [];

改一下方法

/** * 递归去找到老爸自个生自个的娃娃, 都在自个的族谱记一下自个后代 * @param String $parentName * @param String $childName * @return ThroneInheritance */ function birth($parentName, $childName) { if ($this->name == $parentName){ $child = new self($childName); //对象, 传递的都是引用 $this->children [$childName]= $child; $this->descendant [$childName]= $child; return $child; }else{ foreach ($this->children as $child) { if (($child = $child->birth($parentName, $childName)) instanceof self){ //对象, 传递的都是引用 $this->descendant [$childName]= $child; if ($this->name != 'king'){ return $child; } } } } return null; } /** * 不用递归了, 国王直接翻族谱告诉后代, 你死了 * @param String $name * @return NULL */ function death($name) { if ($this->name == $name){ $this->isDeath = 1; }else{ $this->descendant[$name]->isDeath = 1; } return null; }

那么生娃的时候是不是也可以通过族谱找到父母呢? 再优化一下生娃回到O(1)

/** * 国王直接管后代生娃的事了, 就算死了仍然灵魂接着管 * @param String $parentName * @param String $childName * @return ThroneInheritance */ function birth($parentName, $childName) { $child = new self($childName); if ($parentName == $this->name){ $this->children [$childName]= $child; }else{ $this->descendant[$parentName]->children[$childName] = $child; } $this->descendant[$childName] = $child; return null; }

国王都死了, 还操心这事, 貌似不妥当. 搞个上帝出来吧 他生了国王, 不参与皇位继承,不会死. 族谱也只需要掌握在上帝手里. 造娃上帝通过族谱直接硬塞给父母, 死亡上帝直接干掉他, 要继承顺序上帝遍历族谱… 一切都是上帝说了算… 那么其他人直接给个键值对数组记录一下就好了

有以下属性

/** * @var array 上帝说是国王的那一伙 */ private $king = []; /** * @var array 族谱 */ private $descendant = []; /** * @var array 继承顺序 */ private $inheritanceOrder = [];

有以下方法

/** * 上帝造娃, 搞了个国王出来 * @param String $kingName */ function __construct($kingName) { $king = ['isDeath'=>0, 'name'=>$kingName, 'children'=>[]]; $this->king [$kingName]= &$king; $this->descendant [$kingName]= &$king; return; } /** * 上帝造娃, 找到父母硬塞给他. 总感觉画风不对 * @param String $parentName * @param String $childName * @return ThroneInheritance */ function birth($parentName, $childName) { $child = ['isDeath'=>0, 'name'=>$childName, 'children'=>[]]; $parent = &$this->descendant[$parentName]; $parent['children'] [$childName]= &$child; $this->descendant [$childName]= &$child; return null; } /** * 上帝杀人, 毫不讲理 * @param String $name * @return NULL */ function death($name) { $this->descendant[$name]['isDeath'] = 1; return null; } /** * 递归自己后代的皇位继承顺序, 把自己排在他们前面 * @return String[] */ function getInheritanceOrder() { $this->inheritanceOrder = []; $this->getOrder($this->king); return $this->inheritanceOrder; } /** * 获取每个人的后代继承顺序 * @param $members * @return null */ private function getOrder($members){ foreach ($members as $member) { if (!$member['isDeath']){ $this->inheritanceOrder []= $member['name']; } $this->getOrder($member['children']); } return null; }

有些数据是不必要存的, 精简一下. 最终完整代码如下

class ThroneInheritance { /** * @var array 上帝说是国王的那一伙 */ private $king = []; /** * @var array 族谱 */ private $descendant = []; /** * @var array 继承顺序 */ private $inheritanceOrder = []; /** * 上帝造娃, 搞了个国王出来 * @param String $kingName */ function __construct($kingName) { $king = ['isDeath'=>0]; $this->king [$kingName]= &$king; $this->descendant [$kingName]= &$king; return; } /** * 上帝造娃, 找到父母硬塞给他. 总感觉画风不对 * @param String $parentName * @param String $childName * @return ThroneInheritance */ function birth($parentName, $childName) { $child = ['isDeath'=>0]; $parent = &$this->descendant[$parentName]; $parent['children'] [$childName]= &$child; $this->descendant [$childName]= &$child; return null; } /** * 上帝杀人, 毫不讲理 * @param String $name * @return NULL */ function death($name) { $this->descendant[$name]['isDeath'] = 1; return null; } /** * 递归自己后代的皇位继承顺序, 把自己排在他们前面 * @return String[] */ function getInheritanceOrder() { $this->inheritanceOrder = []; $this->getOrder($this->king); return $this->inheritanceOrder; } /** * 获取每个人的后代继承顺序 * @param $members * @return null */ private function getOrder($members){ foreach ($members as $name=>$member) { if (!$member['isDeath']){ $this->inheritanceOrder []= $name; } if (isset($member['children'])){ $this->getOrder($member['children']); } } return null; } }

再给一下测试方法

$methods = ["ThroneInheritance","birth","death","birth","getInheritanceOrder","birth","death","getInheritanceOrder"]; $params = [["king"],["king","clyde"],["king"],["clyde","shannon"],[null],["shannon","scott"],["clyde"],[null]]; array_shift($methods); array_shift($params); $obj = new ThroneInheritance('king'); $res = []; while ($method = array_shift($methods)){ $param = array_shift($params); if ($method == 'birth'){ $res []= $obj->birth($param[0], $param[1]); }elseif ($method == 'death'){ $res []= $obj->death($param[0]); }else{ $res []= $obj->getInheritanceOrder(); } } echo json_encode($res);exit();

提交结果

再优化一下, 减少的数据

反正都是上帝干活, 只需要上帝知道谁是谁的娃, 还有谁活着就好了 存数据也可以不用存那么深的引用 只存一下这个样子的, 每个人都娃娃都从族谱开始的位置找

class ThroneInheritance { /** * @var array 上帝说是国王那小伙的名字 */ private $kingName = ''; /** * @var array 族谱 */ private $descendant = []; /** * @var array 继承顺序 */ private $inheritanceOrder = []; /** * 上帝说有一个国王 * @param String $kingName */ function __construct($kingName) { $this->kingName = $kingName; $this->descendant [$kingName]= ['isDeath'=>0]; return; } /** * 上帝在族谱记下了, 隔壁家的阿花自个生了个娃 * @param String $parentName * @param String $childName * @return ThroneInheritance */ function birth($parentName, $childName) { $parent = &$this->descendant[$parentName]; $parent['children'] []= $childName; $this->descendant [$childName]= ['isDeath'=>0]; return null; } /** * 上帝在族谱中记录了阿花的死亡 * @param String $name * @return NULL */ function death($name) { $this->descendant[$name]['isDeath'] = 1; return null; } /** * 从国王开始, 往继承列表塞人名 * @return String[] */ function getInheritanceOrder() { $this->inheritanceOrder = []; $this->getOrder($this->kingName); return $this->inheritanceOrder; } /** * 找一下每个人是不是没死, 没死的放进继承列表. * 不管死没死都从他的大儿子开始往下继续找 * @param $name * @return null */ private function getOrder($name){ if (!$this->descendant[$name]['isDeath']){ $this->inheritanceOrder []= $name; } if (isset($this->descendant[$name]['children'])){ foreach ($this->descendant[$name]['children'] as $childName) { $this->getOrder($childName); } } return null; } }

应该还有地方可以优化

如果觉得我把话说清楚了, 请给我点个赞