华为计试——刷题

判断两个IP是否属于同一子网

题目：给定一个子网掩码和两个 IP 地址，判断这两个 IP 地址是否在同一个子网中。

思路：首先，判断这个 IP 地址和子网掩码格式是否正确，不正确输出 ‘1’，进而结束；接着，判断两个 IP 地址是否是同一个子网络：若属于同一子网络输出 ‘0’；若不属于同一子网络输出 ‘2’。

子网掩码可以简单看成一串连续的 1 和一串连续的 0 拼接而成的 32 位二进制数，左边部分都是 1，右边部分都是 0。
IP地址是由 4 个 0-255 之间的整数构成的，用“.”符号相连。

def checkIP(ipLst):
    if len(ipLst) != 4:
        return False
    for i in ipLst:
        if not 0 <= i <= 255:
            return False
    return True 

def checkMask(maskLst):
    # "255.255.255.0" 
    # 若二进制全为 0 或全为 1，结果是错误的。
    if len(maskLst) != 4:  
        return False 
    mm = ''.join(f'{part:08b}' for part in maskLst)  # 转为二进制的子网掩码
    return '01' not in mm and '1' in mm and '0' in mm
    

while True:
    try:
        mask = list(map(int, input().split('.')))
        ip1 = list(map(int, input().split('.')))
        ip2 = list(map(int, input().split('.')))

        # 判断格式是否正确，竟然存在负号 -255.0.0.0
        if not (checkMask(mask) and checkIP(ip1) and checkIP(ip2)) or max(mask+ip1+ip2)>255 or min(mask+ip1+ip2)<0:
            print(1)
        else:
            m, n = [], []
            for i in range(len(mask)):
                m.append(int(mask[i]) & int(ip1[i]))
                n.append(int(mask[i]) & int(ip2[i]))
            if m == n:
                print(0)
            else:
                print(2)
    except:
        break

称砝码

题目：给定 $n$ 种不同的砝码，重量和个数不等。求这些砝码能组成多少种不同的总重量（包括 $0$）。
例如，现在，有 $2$ 个重量为 $1$ 的砝码和有 $1$ 个重量为 $2$ 的砝码，它们可以称出 $5$ 种不同的重量（0、1、2、3 和 4）。具体为，选择 $1$ 个重量为 $1$ 的砝码、选择 $2$ 个重量为 $1$ 的砝码、选择 $1$ 个重量为 $1$ 的砝码和选择 $1$ 个重量为 $2$ 的砝码，以及选择全部的砝码。

解题步骤：遍历所有的砝码，记录当前砝码在不同数量下的重量，并与之前的所得到的重量相加并去重；遍历完成后就可得到不同重量的数目：
（1）初始化结果集合 l = { 0 } l=\{0\} l={0}；
（2）遍历砝码，记当前砝码的重量为 $m_i$，数量为 $x_i$。首先，从数量为 1 开始，逐渐叠加到 $x_i$，计算不同数量下不同的重量并存储到列表中，即 s = { k ∗ m i   ∣   0 ≤ k ≤ x i } \{k * m_i \ | \ 0 \le k \le x_i \} {k∗mi​ ∣ 0≤k≤xi​}；接着，将 s 与现有的 res 集合逐元素相加并去重，得到新的 res 集合，即 l = { x + y   ∣   x ∈ s , y ∈ l } l = \{x+ y \ | \ x \in s, y \in l\} l={x+y ∣ x∈s,y∈l}；
（3）重复步骤（2），直到遍历完所有的砝码。最终，$l$ 集合中元素的个数即为答案。

n = int(input())
weight = list(map(int, input().split(' ')))
number = list(map(int, input().split(' ')))

res = [0]  # 不加 0 就不能遍历 res 列表
for i in range(n):
    s = [weight[i] * j for j in range(number[i] + 1)]
    res = list(set(x + y for x in s for y in res)) 
print(len(res))

迷宫问题

def dfs(i, j, pos=[(0, 0)]):
    if i + 1 == h and j + 1 == w:
        for p in pos:
            print("(" + str(p[0]) + "," + str(p[1]) + ")")
            
    if j + 1 < w and grid[i][j + 1] == 0 and (i, j + 1) not in pos:  # 向右
        dfs(i, j + 1, pos + [(i, j + 1)])
    if j - 1 >= 0 and grid[i][j - 1] == 0 and (i, j - 1) not in pos:  # 向左
        dfs(i, j - 1, pos + [(i, j - 1)])
    if i + 1 < h and grid[i + 1][j] == 0 and (i + 1, j) not in pos:  # 向上
        dfs(i + 1, j, pos + [(i + 1, j)])
    if i - 1 >= 0 and grid[i - 1][j] == 0 and (i - 1, j) not in pos:  # 向下
        dfs(i - 1, j, pos + [(i - 1, j)])


h, w = list(map(int, input().split(" ")))  # map 返回的结果是迭代器
grid = []
for i in range(h):
    grid.append(list(map(int, input().split(" "))))

dfs(0, 0)