难度: Medium
Submission
运行时间: 248 ms
内存: 16.9 MB
mod = 1000000007
class Solution:
def buildWall(self, height: int, width: int, bricks: List[int]) -> int:
bricks.sort()
mask_in_w = [[0]] + [[] for _ in range(width)]
for w in range(1, width + 1):
for bw in bricks:
if bw > w: break
mask_in_w[w].extend([mk + (1 << (w - 1)) for mk in mask_in_w[w - bw]])
mask = mask_in_w[-1]
n, target = len(mask), 1 << (width - 1)
d = collections.defaultdict(list)
for i in range(n):
for j in range(i + 1, n):
if (mask[i] & mask[j]) == target:
d[i].append(j); d[j].append(i)
if width in bricks:d[n - 1].append(n - 1)
return sum(reduce(lambda dp, _: [sum(dp[i] for i in d[j]) % mod for j in range(n)], range(height - 1), [1] * n)) % mod
Explain
此题解采用动态编程和位运算来解决问题。首先，对砖块按长度进行排序以简化后续处理。然后，计算所有可能的墙的一层的布局（使用位掩码表示），其中每种布局都由一系列砖块组成，确保布局的总宽度等于墙的宽度。接着，检查两种布局之间是否可以无缝连接，即它们之间没有连续的竖直缝隙。这是通过比较两个布局的位掩码来完成的。最后，使用动态编程计算所有可能的布局组合，以建立指定高度的墙。具体来说，定义一个数组 dp，其中 dp[j] 表示以第 j 种布局结尾的墙的构造方式数量。最终答案为所有 dp 值的总和，即所有可能的建墙方式。
时间复杂度: O(height * n^2)
空间复杂度: O(n)
mod = 1000000007
class Solution:
def buildWall(self, height: int, width: int, bricks: List[int]) -> int:
bricks.sort() # 对砖块进行排序
mask_in_w = [[0]] + [[] for _ in range(width)] # 初始化每个宽度的可能布局列表
for w in range(1, width + 1):
for bw in bricks:
if bw > w: break # 如果砖块宽度超过当前宽度，停止处理
mask_in_w[w].extend([mk + (1 << (w - 1)) for mk in mask_in_w[w - bw]]) # 生成新的布局
mask = mask_in_w[-1] # 最终宽度的所有可能布局
n, target = len(mask), 1 << (width - 1) # 布局数量和位掩码的目标值
d = collections.defaultdict(list) # 存储可以无缝连接的布局对
for i in range(n):
for j in range(i + 1, n):
if (mask[i] & mask[j]) == target:
d[i].append(j); d[j].append(i) # 建立连接关系
if width in bricks: d[n - 1].append(n - 1) # 特殊情况处理
# 使用 reduce 进行动态编程，计算所有可能的建墙方式
return sum(reduce(lambda dp, _: [sum(dp[i] for i in d[j]) % mod for j in range(n)], range(height - 1), [1] * n)) % mod
Explore
对砖块进行排序主要是为了简化布局生成的过程。排序后，当我们逐步构建布局时，可以更快地判断哪些砖块可以用在当前宽度上，因为一旦遇到一个砖块宽度超过当前考虑的宽度，就可以停止进一步的考虑。这样可以避免对每个宽度都遍历所有砖块，提高算法的效率。
位掩码是一种有效的方式来表示和存储墙的布局信息。每一位代表墙的一个单元格，位的值（0或1）可以表示该位置是否为某一层的结束。通过位掩码，可以快速地进行布局之间的比较和组合。例如，位运算（如AND运算）可以用来检测两个布局是否在同一位置结束，这对于确定哪些布局可以无缝连接是非常有用的。
确保两个布局之间可以无缝连接主要是通过比较它们的位掩码。具体条件是，两个布局的位掩码进行AND运算之后，结果应该等于最后一个位置的位（即表示墙的最右端）为1的掩码，这表示两个布局在墙的右端结束，中间没有任何竖直缝隙全通过。这种方式确保了在任何两层之间都不会有连续的竖缝，从而可以逐层堆叠构建整面墙。
动态编程中的dp数组用来存储每种布局作为最后一层时，可以构成的墙的总数。初始化时，每种布局的数量设为1，表示每种布局都可以单独作为一层墙的起始。更新过程是通过迭代，对于每一层墙，根据之前的层（dp数组的当前值）和可以无缝连接的布局（通过上述位掩码检查确定），更新dp数组的值。具体地，对于每种布局j，更新的值是所有可以与其无缝连接的布局i的dp值的总和。这样，经过height层的迭代后，dp数组的所有值的总和即为答案。