数据结构与算法python版 MOOC 第十一周

十一、图及算法-上

本系列博客基于“ (北京大学)数据结构与算法python版”慕课,课程在中国大学慕课bilibili上均可找到。

1. 内容

  1. 图数据类型的实现
  2. 图的应用:词梯问题
  3. 广度优先搜索BFS算法及其应用(骑士周游问题)

2. 课程代码

GitHub中下载

3. OJ作业

所有代码均可在github中下载

3.1 找到小镇的法官

题目内容:
   在一个小镇里,按从 1 到 N 标记了 N 个人。传言称,这些人中有一个是小镇上的秘密法官。如果小镇的法官真的存在,那么:
   小镇的法官不相信任何人。
   每个人(除了小镇法官外)都信任小镇的法官。
   只有一个人同时满足属性 1 和属性 2 。
   给定列表 trust,该列表由信任对 trust[i] = [a, b] 组成,表示标记为 a 的人信任标记为 b 的人。如果小镇存在秘密法官并且可以确定他的身份,请返回该法官的标记。否则,返回 -1。

输入格式: 输入包含两行,第一行为一个正整数N,第二行为信任对列表trust,以合法的Python表达式给出
输出格式: 一个整数,表示法官的编号

输入样例:
4
[[1,3],[1,4],[2,3],[2,4],[4,3]]
输出样例:
3

方法:不用建图,直接遍历 首先建立小镇人列表[1,2,3,4],然后去掉trust列表里面第一列出现的编号。对剩下的编号进行遍历,如果剩下人的编号的边有3条,则是法官 如果没有人的边是三条,则说明无法官。注意特殊情况:N=1并且信任列表为空,法官就是1号

def findJudge(N, trust):
    people_list = list(range(1, N+1))  # 建立小镇人表
    judge_index = -1  # 法官编号
    for i in range(len(trust)):  # 按行遍历
        if trust[i][0] in people_list:
            people_list.remove(trust[i][0])  # 去除信任别人的人

    trusted_list = [b[1] for b in trust]  # 被信任人列表
    for j in range(len(people_list)):
        if people_list[j] in trusted_list:  # 如果此人有人信任
            trust_num = trusted_list.count(people_list[j])  # 数有多少人信任
            if trust_num == N-1:  # 其他所有人都信任,说明是法官
                judge_index = people_list[j]

    if N == 1 and len(trust) == 0:
        judge_index = 1

    return judge_index


N = int(input())
trust = eval(input())
print(findJudge(N, trust))

3.2 远离大陆

题目内容:
   你现在手里有一份大小为 M x N 的『地图』(网格) grid,上面的每个『区域』(单元格)都用 0 和 1 标记好了。其中 0 代表海洋,1 代表陆地。对于每个海洋方格,其存在一个距离它最近的陆地方格,相应有一个到陆地的最小距离。请输出上述所有最小距离中的最大值。
   我们这里说的距离是『曼哈顿距离』( Manhattan Distance):(x0, y0) 和 (x1, y1) 这两个区域之间的距离是 |x0 - x1| + |y0 - y1| 。
   如果地图上只有陆地或者海洋,请返回 -1。

输入格式:
输入共1行,为一个仅包含0与1的嵌套列表,用合法的Python表达式给出
输出格式:
一个整数,表示最短距离

输入样例:
[[1,0,1],[0,0,0],[1,0,1]]
输出样例:
2

方法:广度优先搜索。把每个点的距离都算好,先把陆地设为距离0,然后搜索附近的点。因为是队列存储要搜索的点,先入先出,所以是逐渐从陆地最近的地方向远的地方搜索,所以每一步找到的海洋 都是得到的最小距离。最后从这些最短距离中找到最大的

代码

def maxDistance(grid):
    # 分离陆地和海洋
    ocean_list = []
    land_list = []
    M = len(grid)  # 列
    N = len(grid[0])  # 行
    for i in range(len(grid)):  # 行遍历
        for j in range(len(grid[0])):  # 列遍历
            if grid[i][j] == 0:  # 海洋
                ocean_list.append([i, j])
            else:  # 陆地
                land_list.append([i, j])

    if len(ocean_list) == 0 or len(land_list) == 0:
        return -1

    max_dist = 0
    for ocean in ocean_list:
        each_min_dist = M+N  # 最大距离
        for land in land_list:
            dist = abs(ocean[0]-land[0])+abs(ocean[1]-land[1])
            if dist < each_min_dist:
                each_min_dist = dist  # 更新dist 找到对每片海洋最小的
        if each_min_dist > max_dist:
            max_dist = each_min_dist  # 更显max_dist 找到所有海洋最大的

    return max_dist


grid = eval(input())
print(maxDistance(grid))

3.3 钥匙和房间

题目内容:
   有 N 个房间,开始时你位于 0 号房间。每个房间有不同的号码:0,1,2,…,N-1,并且房间里可能有一些钥匙能使你进入下一个房间。
   在形式上,对于每个房间 i 都有一个钥匙列表 rooms[i],每个钥匙 rooms[i][j] 由 [0,1,…,N-1] 中的一个整数表示,其中 N = rooms.length。 钥匙 rooms[i][j] = v 可以打开编号为 v 的房间。
   最初,除 0 号房间外的其余所有房间都被锁住。你可以*地在房间之间来回走动。请判断是否可以最终打开所有房间。

输入格式:一行嵌套列表,列表长度为N,以合法的Python表达式格式给出
输出格式:True或False,代表是否可以进入每个房间

输入样例:
[[1],[2],[3],[]]
输出样例:
True

方法:一个搜索队列,储存可以搜索的房间。一个列表存储每个房间的状态 1是已经到达,0是未到达。使用广度优先搜索

代码:

def canVisitAll(rooms):
    N = len(rooms)  # 房间数量
    search_q = []  # 存储可以搜索的房间
    room_state = [0]*N  # 存储房间状态 不能搜索
    room_state[0] = 1  # 准备搜索
    search_q.append(0)
    while search_q:  # 当还有可以搜索的房间
        current_room = search_q.pop(0)  # 当前搜索房间
        key_list = rooms[current_room]  # 拿到当前房间的钥匙列表
        for key in key_list:
            if room_state[key] == 0:  # 如果钥匙的房间没有搜索过
                room_state[key] = -1  # 准备搜索
                search_q.append(key)  # 加入可以搜索队列
        room_state[current_room] = 1  # 搜索完毕

    # 搜索完毕的点 状态为1
    num_searched = room_state.count(1)
    if N == num_searched:
        return True
    else:
        return False


rooms = eval(input())
print(canVisitAll(rooms))

上一篇:Adaptive AUTOSAR 学习笔记 10 - 执行管理


下一篇:记一次MacOS 证书信任配置不生效的解决方法(*X)