2024.9.27华为笔试题解

第一题

题目： 给成员分成两组，认识的人不能在同一组。

思路： 涂色问题，广搜、深搜都行。

第二题

题目： 小明需要从家出发，通过公交换乘，先到早餐店，再到公司。题目给出多条公交路线，每条包含该公交可到达的站点。求最少换乘方案的公交路线数。

思路： 个人认为这是三道题里最难的，本人的解法为分两段（家-早餐店、早餐店-公司）分别用广搜找最少换乘方案，每段求解的具体思路可参考力扣815。和力扣815只需统计换乘次数不同的是，本题两段路线可能存在共同的公交，因此在求解每段方案时需要记录下最少换乘方案中到达某站的上一站及乘坐的公交，最后从目标站根据这些记录反向找出到起始站所换乘的所有公交，类似于动态规划最后的反向搜索过程。

解法一（广搜）代码：

# 样例
# s：起始站（家）、m：中间站（早餐店）、t：目标站（公司）
# bus_routes: 公交路线

s0, m0, t0 = 1, 5, 7
bus_routes0 = [
    [1, 2, 3], 
    [2, 7], 
    [3, 5]
]
ans0 = 3


s1, m1, t1 = 1, 3, 4
bus_routes1 = [
    [1, 2, 4],
    [3, 5, 6]
]
ans1 = -1


s2, m2, t2 = 1, 3, 5
bus_routes2 =  [
    [1, 2, 6], 
    [2, 3, 7], 
    [5, 6, 8], 
    [5, 7]
]
ans2 = 3

s3, m3, t3 = 4, 19, 28
bus_routes3 = [
    [3, 4, 7, 8, 10],
    [10, 12, 16, 19, 27, 28],
    [5, 7, 11, 17],
    [17, 19, 22, 23],
    [23, 27, 28]
]
ans3 = 2

# ---------------------
# 核心代码
def solution(s, m, t, bus_routes):
    from collections import deque, defaultdict
    
    stop_to_bus = defaultdict(set)  # stop: [bus1, bus2, ...]

    for bus_idx in range(len(bus_routes)):
        for stop_idx in bus_routes[bus_idx]:
            stop_to_bus[stop_idx].add(bus_idx)

    bus_routes = [set(route) for route in bus_routes]

    def get_shortest_path(start_stop, target_stop):
        buses = set()
        queue = deque([])

        for bus_idx in stop_to_bus[start_stop]:
            queue.append((bus_idx, start_stop))

        dp = dict()  # stop: (bus, pre_stop)
        dp[start_stop] = (-1, -1)

        while queue:
            # 出队列
            (bus_idx, pre_stop) = queue.popleft()
            buses.add(bus_idx)
            # 找可达的站点和其他公交
            for stop in bus_routes[bus_idx]:
                if stop in dp:
                    continue
                dp[stop] = (bus_idx, pre_stop)
                if target_stop == stop:
                    return True, dp
                # 入队列
                for next_bus in stop_to_bus[stop] - buses:
                    queue.append((next_bus, stop))
        return False, dp  # 不存在方案
        
    found1, dp1= get_shortest_path(s, m)
    found2, dp2 = get_shortest_path(m, t)

    if not found1 or not found2:
        return -1
    
    def get_selected_bus_set(dp, start_stop, target_stop):
        selected_bus_set = set()
        cur_stop = target_stop
        # 从终点站开始找最优方案里的上一站和公交
        while cur_stop != start_stop:
            bus, pre_stop = dp[cur_stop]
            selected_bus_set.add(bus)
            cur_stop = pre_stop
        return selected_bus_set
    
    selected_bus_set1 = get_selected_bus_set(dp1, s, m)
    selected_bus_set2 = get_selected_bus_set(dp2, m, t)
    selected_bus_set = set.union(selected_bus_set1, selected_bus_set2)
    print(selected_bus_set)
    return len(selected_bus_set)


# 测试
if __name__ == '__main__':
    s, m, t, bus_routes, ans = s3, m3, t3, bus_routes3, ans3
    ret = solution(s, m, t, bus_routes)

    if ret == ans:
        print('Answer Right')
    else:
        print('Wrong')
    print('your answer:', ret)

解法二（其他大佬提到的Floyd最短路解法）之后更新

第三题

题目： 给了一个矩阵，里面某些位置有人和墙。人分为感染者和未感染者：感染者有危险值，随距离递减；未感染者有被感染阈值，所处位置的危险值超过阈值就会被感染。人戴口罩和不带口罩会影响危险值和感染阈值，墙可以阻止往该方向的危险值传播。求感染状态稳定后的矩阵。

思路： 不算太难，根据题目描述的过程模拟一下就能过大部分样例，就是计算每天的矩阵各位置的危险值，和未感染者的阈值比较，更新感染情况直到无新的感染者出现。信息更新过程用广搜优化一下应该就能A了。