初学python记录:力扣1600. 王位继承顺序

题目:

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

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

Successor(x, curOrder):
    如果 x 没有孩子或者所有 x 的孩子都在 curOrder 中:
        如果 x 是国王,那么返回 null
        否则,返回 Successor(x 的父亲, curOrder)
    否则,返回 x 不在 curOrder 中最年长的孩子

比方说,假设王国由国王,他的孩子 Alice 和 Bob (Alice 比 Bob 年长)和 Alice 的孩子 Jack 组成。

  1. 一开始, curOrder 为 ["king"].
  2. 调用 Successor(king, curOrder) ,返回 Alice ,所以我们将 Alice 放入 curOrder 中,得到 ["king", "Alice"] 。
  3. 调用 Successor(Alice, curOrder) ,返回 Jack ,所以我们将 Jack 放入 curOrder 中,得到 ["king", "Alice", "Jack"] 。
  4. 调用 Successor(Jack, curOrder) ,返回 Bob ,所以我们将 Bob 放入 curOrder 中,得到 ["king", "Alice", "Jack", "Bob"] 。
  5. 调用 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() 返回 除去 死亡人员的当前继承顺序列表。

提示:

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

思考:

分析题目中的递归函数Successor:

Successor(x, curOrder):
    如果 x 没有孩子或者所有 x 的孩子都在 curOrder 中:
        如果 x 是国王,那么返回 null
        否则,返回 Successor(x 的父亲, curOrder)
    否则,返回 x 不在 curOrder 中最年长的孩子

也就是说,继承列表最初为[国王],然后将国王的长子加入继承列表,然后将长子的长子加入继承列表......直到当前继承人没有孩子或者已经把所有孩子加入到继承列表了为止,然后将当前继承人的相邻的下一个兄弟加入继承列表,再重复以上加入长子的操作。

可以看出,以上操作类似于树的深度优先搜索中的前序遍历,因此我们定义一个函数,对整个家族的父子关系树进行前序遍历,用继承列表存储遍历到的人名。

因此,需要记录每个人的儿子和每个人是否存活,这里使用字典存储这两个关系,可以减少时间。

代码如下: 


class ThroneInheritance(object):

    def __init__(self, kingName):
        """
        :type kingName: str
        """
        self.kingName = kingName
        self.child_dict = {kingName:[]}    # 孩子字典存储每个人的孩子
        self.alive_dict = {kingName:1}    # 存活字典存储每个人的生死状态,1表示活着,0表示死亡


    def birth(self, parentName, childName):
        """
        :type parentName: str
        :type childName: str
        :rtype: None
        """
        if parentName not in self.child_dict:
            self.child_dict[parentName] = []
        self.child_dict[parentName].append(childName)    # 向孩子字典中加入父子关系
        self.alive_dict[childName] = 1    # 向生死字典中加入新生儿的存活状态


    def death(self, name):
        """
        :type name: str
        :rtype: None
        """
        self.alive_dict[name] = 0    # 在生死字典中将死人的状态设为死亡(0)


    def getInheritanceOrder(self):
        """
        :rtype: List[str]
        """
        kingName = self.kingName
        child_dict = self.child_dict
        alive_dict = self.alive_dict
        
        curOrder = []     # 初始化继承顺序列表

        def dfs(person):
            if alive_dict[person] == 1:   # 若此人活着,加入继承列表
                curOrder.append(person)
            for child in self.child_dict.get(person, []):    
            # 遍历这个人的所有孩子,使用get()方法避免访问字典中不存在的键导致错误
                dfs(child)
        

        dfs(kingName)    # 从国王开始进行深度优先搜索
        return curOrder



# Your ThroneInheritance object will be instantiated and called as such:
# obj = ThroneInheritance(kingName)
# obj.birth(parentName,childName)
# obj.death(name)
# param_3 = obj.getInheritanceOrder()

提交通过:

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/528224.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

基于SpringBoot+Vue+Mysql的图书管理系统

博主介绍&#xff1a; 大家好&#xff0c;本人精通Java、Python、C#、C、C编程语言&#xff0c;同时也熟练掌握微信小程序、Php和Android等技术&#xff0c;能够为大家提供全方位的技术支持和交流。 我有丰富的成品Java、Python、C#毕设项目经验&#xff0c;能够为学生提供各类…

[leetcode]只出现一次的数字Ⅲ

题目&#xff1a; 给你一个整数数组 nums&#xff0c;其中恰好有两个元素只出现一次&#xff0c;其余所有元素均出现两次。 找出只出现一次的那两个元素。你可以按 任意顺序 返回答案。 你必须设计并实现线性时间复杂度的算法且仅使用常量额外空间来解决此问题。 示例 1&…

Tiktok矩阵系统是什么?——Tiktok矩阵系统的优势、功能、及应用场景的介绍

摘要 Tiktok作为全球现象级的短视频平台,其发展前景日益明朗。 Tiktok全世界有多少用户? TikTok作为全球性的社交媒体平台,其用户数量一直在持续增长。根据最新的数据,预计到2024年,TikTok的用户数量将达到数十亿,覆盖全球范围内的各个年龄段和地区。具体来说,根据Ti…

总结SQL相对常用的几个字符函数

目录 字符的截取 substr() trim()、ltrim()、rtrim() 字符串的拼接 ||、 字符的大小写转换 upper(column_name):大写 lower(column_name):小写 字符替换 replace() 搜索字符 instr(column_name, substring_to_find,start,n_appearence) charindex(substring_to_fi…

HarmonyOS4.0 ArkUI构建布局

一、线性布局 属性说明&#xff1a; justifyContent&#xff1a;设置子元素在主轴方向的对齐方式 参数&#xff1a;FlexAlign枚举 alignItems&#xff1a;设置子元素在交叉轴方向的对齐方式 参数&#xff1a; Row容器使用VerticalAlign枚举Column容器使用HorizontalAlign枚举 …

k8s的ca以及相关证书签发流程

k8s的ca以及相关证书签发流程 1. kube-apiserver相关证书说明2. 生成CA凭证1.1. 生成CA私钥1.2. 生成CA证书 2. 生成kube-apiserver凭证2.1. 生成kube-apiserver私钥2.2. 生成kube-apiserver证书请求2.3. 生成kube-apiserver证书 3. 疑问和思考4. 参考文档 对于网站类的应用&am…

springboot 整合 mybatis(配置版)

代码及配置整合 创建实体类,与数据库对应 创建 mapper、service 和 controller @AutowiredUserService userService;@ResponseBody@GetMapping("/user")public com.vazquez.bootstudy.model.User getById(@RequestParam("id") Long id) {return userServ…

计算机网络:数据链路层 - CSMA/CD协议

计算机网络&#xff1a;数据链路层 - CSMA/CD协议 媒体接入控制CSMA/CD协议截断二进制指数退避算法帧长与帧间间隔信道利用率 媒体接入控制 如图所示&#xff0c;这是一根同轴电缆&#xff0c;有多台主机连接到这根同轴电缆上&#xff0c;他们共享这根传输媒体&#xff0c;形成…

LeetCode-347. 前 K 个高频元素【数组 哈希表 分治 桶排序 计数 快速选择 排序 堆(优先队列)】

LeetCode-347. 前 K 个高频元素【数组 哈希表 分治 桶排序 计数 快速选择 排序 堆&#xff08;优先队列&#xff09;】 题目描述&#xff1a;解题思路一&#xff1a;哈希表记录出现次数&#xff0c;然后用最小堆取&#xff0c;因为每次都是弹出最小的&#xff0c;剩下的一定是K…

CentOS7安装MySQL8.0教程

环境介绍 操作系统&#xff1a;Centos7.6 MySQL版本&#xff1a; 8.0.27 只要是8.0.*版本&#xff0c;那就可以按照本文说明安装 一、安装前准备 1、卸载MariaDB 安装MySQL的话会和MariaDB的文件冲突&#xff0c;所以需要先卸载掉MariaDB。 1.1、查看是否安装mariadb rpm -…

SQL注入利用学习-Union联合注入

联合注入的原理 在SQL语句中查询数据时&#xff0c;使用select 相关语句与where 条件子句筛选符合条件的记录。 select * from person where id 1; #在person表中&#xff0c;筛选出id1的记录如果该id1 中的1 是用户可以控制输入的部分时&#xff0c;就有可能存在SQL注入漏洞…

自媒体内容创作助手:7款必备ai写作工具一览! #学习方法#科技#其他

这些工具不仅可以快速生成高质量的文本内容&#xff0c;还可以根据用户的需求进行个性化定制。它们可以帮助我们节省大量的时间和精力&#xff0c;让我们更加专注于创意和细节的打磨。本文将为大家详细介绍几个AI写作工具&#xff0c;让你在写作领域更上一层楼。 1.七燕写作 这…

【随笔】Git 高级篇 -- 撤销变更 reset | revert(十四)

&#x1f48c; 所属专栏&#xff1a;【Git】 &#x1f600; 作  者&#xff1a;我是夜阑的狗&#x1f436; &#x1f680; 个人简介&#xff1a;一个正在努力学技术的CV工程师&#xff0c;专注基础和实战分享 &#xff0c;欢迎咨询&#xff01; &#x1f496; 欢迎大…

uniapp项目问题及解决(前后端互联)

1.路由跳转的问题 uni.navigateTo&#xff08;&#xff09; 保留当前页面&#xff0c;跳转到应用内的某个页面&#xff0c;使用uni.navigateBack可以返回到原页面 uni.redirectTo&#xff08;&#xff09; 关闭当前页面&#xff0c;跳转到应用内的某个页面。 uni.reLaunch&…

探索未来产业:新技术、新商业、新趋势

引言 随着科技的迅速发展和全球经济的不断变化&#xff0c;未来产业已经成为全球关注的焦点之一。未来产业的兴起不仅代表着新的商业机遇&#xff0c;更是对传统产业模式的颠覆和重构。在这个充满挑战和机遇的时代&#xff0c;我们不得不认真思考未来产业的重要性和前景。 未…

STM32之HAL开发——FatFs文件系统移植

FatFs文件系统移植 FatFs 程序结构图 移植 FatFs 之前我们先通过 FatFs 的程序结构图了解 FatFs 在程序中的关系网络 用户应用程序需要由用户编写&#xff0c;想实现什么功能就编写什么的程序&#xff0c;一般我们只用到 f_mount()、f_open()、 f_write()、f_read() 就可以…

在【Cencos7】中安装【Nacos】并适配【PostgreSQL】数据库

在【Cencos7】中安装【Nacos-2.3.0】并适配【PostgreSQL】数据库 安装JDK wget命令下载&#xff1a; wget https://repo.huaweicloud.com/java/jdk/8u151-b12/jdk-8u151-linux-x64.tar.gz解压 tar -xzvf jdk-7u80-linux-x64.tar.gz将解压后的目录移动到/opt下 sudo mv jdk…

unity_Button:单击的三种实现方式

1.针对特定单个按钮 此代码直接绑定到button上面无需其他操作 using UnityEngine; using UnityEngine.UI;public class PrintHelloOnButtonClick : MonoBehaviour {private Button button;void Start(){// 获取当前GameObject上的Button组件button GetComponent<Button&g…

【Redis系列】Spring Boot 集成 Redis 实现缓存功能

&#x1f49d;&#x1f49d;&#x1f49d;欢迎来到我的博客&#xff0c;很高兴能够在这里和您见面&#xff01;希望您在这里可以感受到一份轻松愉快的氛围&#xff0c;不仅可以获得有趣的内容和知识&#xff0c;也可以畅所欲言、分享您的想法和见解。 推荐:kwan 的首页,持续学…

[C语言]——动态内存管理

目录 一.为什么要有动态内存分配 二.malloc和free 1.malloc 2.free 三.calloc和realloc 1.calloc 2.realloc 3.空间的释放​编辑 四.常见的动态内存的错误 1.对NULL指针的解引用操作 2.对动态开辟空间的越界访问 3.对非动态开辟内存使用free释放 4.使用free释放⼀块…