2025年涂色算法面试题及答案

2025年涂色算法面试题及答案无向图k色着色判定问题给定邻接表表示的无向图`graph`（其中`graph[i]`为节点`i`的所有相邻节点列表），节点编号为`0`到`n-1`。要求判断是否存在一种使用`k`种颜色的着色方式，使得任意相邻节点颜色不同。解题思路：采用回溯法逐节点尝试颜色。从第0个节点开始，为每个节点选择一种颜色（1到k），确保该颜色与所有已着色的相邻节点颜色不同。若当前节点无法找到合法颜色，则回溯到前一节点更换颜色；若所有节点均成功着色，则返回`True`。关键优化点是剪枝：在为当前节点选择颜色时，仅保留与所有已着色邻居颜色不同的选项，减少无效递归。代码实现（Python）：```pythondefis_k_colorable(graph,n,k):color=[-1]n记录各节点颜色，-1表示未着色defbacktrack(node):ifnode==n:所有节点已着色returnTrueforcinrange(k):检查当前颜色是否与所有邻居冲突conflict=Falseforneighboringraph[node]:ifcolor[neighbor]==c:conflict=Truebreakifnotconflict:color[node]=cifbacktrack(node+1):returnTruecolor[node]=-1回溯returnFalsereturnbacktrack(0)```复杂度分析：最坏情况下，每个节点有`k`种选择，总时间复杂度为`O(k^n)`，其中`n`为节点数。但通过剪枝（提前排除冲突颜色），实际运行时间会显著降低。空间复杂度为`O(n)`（存储颜色数组和递归栈）。m×n网格涂色方案数计算给定`m`行`n`列的网格（`m≥1`，`n≥2`），每个格子可涂红（0）、蓝（1）、绿（2）三种颜色，要求相邻（上下左右）格子颜色不同。求所有合法的涂色方案总数。解题思路：动态规划（DP）。定义`dp[i][s]`为第`i`行状态为`s`时的方案数，其中`s`是长度为`n`的元组，表示该行每个格子的颜色（如`s=(0,1,0)`表示第一列红、第二列蓝、第三列红）。状态转移时，第`i`行的状态`s`需满足两个条件：1.`s`自身相邻格子颜色不同（行内约束）；2.`s`与第`i-1`行的状态`t`在每一列的颜色不同（行间约束）。步骤：1.预处理所有可能的行状态：提供所有长度为`n`、相邻元素不同的元组（如`n=2`时有`3×2=6`种状态）。2.初始化`dp[0][s]=1`（第一行所有合法状态各有一种方案）。3.对于第`i`行（`i≥1`），遍历所有可能的当前状态`s`和上一行状态`t`，若`s`与`t`每列颜色不同，则`dp[i][s]+=dp[i-1][t]`。4.最终结果为所有第`m-1`行状态的`dp[m-1][s]`之和。代码实现（Python）：```pythondefcount_grid_colorings(m,n):提供所有合法行状态（相邻颜色不同）colors=[0,1,2]valid_states=[]defgenerate_states(current):iflen(current)==n:valid_states.append(tuple(current))returnforcincolors:ifnotcurrentorc!=current[-1]:generate_states(current+[c])generate_states([])S=len(valid_states)合法行状态总数初始化DP表dp_prev={s:1forsinvalid_states}foriinrange(1,m):dp_curr=defaultdict(int)forsinvalid_states:当前行状态fortindp_prev:上一行状态检查每一列颜色是否不同conflict=Falseforcolinrange(n):ifs[col]==t[col]:conflict=Truebreakifnotconflict:dp_curr[s]+=dp_prev[t]dp_prev=dp_currreturnsum(dp_prev.values())```复杂度分析：预处理行状态的时间为`O(3×2^(n-1))`（每行第一个格子3种选择，后续每个格子2种选择）。动态规划阶段，每行有`S`种状态，状态转移需遍历`S×S`次比较，总时间复杂度为`O(m×S²)`。当`n=5`时，`S=3×2⁴=48`，`m=10`时总计算量约为`10×48²=23040`，可高效处理。二叉树节点涂色方案数计算给定二叉树的根节点`root`，每个节点可选5种颜色（编号1-5），要求父节点与子节点颜色不同。求所有可能的涂色方案总数。解题思路：后序遍历递归。对于每个节点，计算其涂每种颜色时的方案数。假设当前节点涂颜色`c`，则其左子节点只能涂非`c`的颜色，右子节点同理。左子树的方案数为左子节点所有非`c`颜色的方案数之和，右子树同理，当前节点涂`c`的方案数为左方案数×右方案数。最终总方案数为根节点所有颜色方案数之和。代码实现（Python，假设树节点定义为`classTreeNode:def__init__(self,val=0,left=None,right=None):`）：```pythondefcount_tree_colorings(root):返回字典：{颜色:该颜色下子树的方案数}defdfs(node):ifnotnode:return{}空树无颜色约束，方案数为1（但需特殊处理）left=dfs(node.left)right=dfs(node.right)当前节点可选颜色1-5color_count={}forcinrange(1,6):左子树方案数：若左子树存在，取所有非c颜色的方案数之和；否则为1（空树）left_sum=1ifnotnode.leftelsesum(vforclr,vinleft.items()ifclr!=c)右子树同理right_sum=1ifnotnode.rightelsesum(vforclr,vinright.items()ifclr!=c)color_count[c]=left_sumright_sumreturncolor_counttotal=dfs(root)returnsum(total.values())iftotalelse0空树返回0（无节点）```复杂度分析：每个节点遍历5种颜色，总时间复杂度为`O(n×5)`，其中`n`为树的节点数。空间复杂度为`O(n)`（递归栈深度）。DAG节点颜色大小约束方案数计算给定有向无环图（DAG）的邻接表`dag`（`dag[u]`为`u`的所有直接后继节点），节点编号0到`n-1`。颜色可选1-4，约束：若存在边`u→v`，则`color[u]<color[v]`。求所有合法的涂色方案总数。解题思路：拓扑排序结合动态规划。按拓扑序处理节点（确保处理节点时其所有前驱已处理），定义`dp[u][c]`为节点`u`涂颜色`c`时的方案数。对于每个节点`u`，其颜色`c`需满足所有前驱节点`p`的颜色`k<c`。`dp[u][c]`等于所有前驱节点`p`的`sum(dp[p][k]fork<c)`的乘积（若`u`无先驱，则`sum`为1）。步骤：1.计算每个节点的入度，初始化拓扑队列（入度为0的节点）。2.初始化`dp[u][c]`：入度为0的节点`u`，若没有前驱，`dp[u][c]=1`（颜色`c`本身合法）。3.按拓扑序处理每个节点`u`，遍历其所有后继`v`，更新`v`的入度；当`v`的入度减为0时，计算`dp[v][c]`（遍历`c=1-4`，累加所有前驱`p`的`sum(dp[p][k]fork<c)`的乘积）。4.最终结果为所有节点的`dp[u][c]`之和（若图中有多个终止节点，需累加所有节点的所有颜色方案数）。代码实现（Python）：```pythonfromcollectionsimportdequedefcount_dag_colorings(dag,n):in_degree=[0]n构建逆邻接表（记录每个节点的前驱）reverse_dag=[[]for_inrange(n)]foruinrange(n):forvindag[u]:reverse_dag[v].append(u)in_degree[v]+=1dp=[[0]5for_inrange(n)]dp[u][c]，c=1-4q=deque()初始化入度为0的节点foruinrange(n):ifin_degree[u]==0:forcinrange(1,5):dp[u][c]=1无先驱，颜色c合法q.append(u)whileq:u=q.popleft()forvindag[u]:处理v的前驱u，更新v的dp值forcinrange(1,5):前驱u对v颜色c的贡献：u的颜色必须小于csum_u=sum(dp[u][k]forkinrange(1,c))若v已有其他前驱，需将当前贡献与之前的相乘ifdp[v][c]==0:dp[v][c]=sum_uelse:dp[v][c]=sum_uin_degree[v]-=1ifin_degree[v]==0:q.append(v)所有节点的所有颜色方案数之和total=0foruinrange(n):total+=sum(dp[u][1:5])returntotal```复杂度分析：拓扑排序时间为`O(n+m)`（`m`为边数）。动态规划阶段，每个节点处理4种颜色，每条边参与4次计算（每个颜色`c`需累加前驱颜色`<c`的方案数），总时间复杂度为`O(n×4+m×4)`，即`O(n+m)`，可高效处理大规模DAG。平面地图最少颜色数判定给定平面地图（转化为无向图`graph`，节点代表区域，边代表相邻），求最少需要几种颜色，使得相邻区域颜色不同。解题思路：根据四色定理，平面地图最多需要4种颜色。实际最少颜色数（色数）的判定步骤如下：1.判断是否为二分图（2色可染）：通过BFS或DFS尝试用两种颜色染色，若出现冲突则不是二分图。2.若不是二分图，尝试3色染色（回溯法）：逐个节点尝试颜色1-3，确保与相邻节点颜色不同。若存在可行方案则返回3。3.若3色不可行，返回4（根据四色定理，必然可行）。代码实现（Python）：```pythondefmin_map_colors(graph,n):判断是否为二分图（2色）defis_bipartite():color=[-1]nforiinrange(n):ifcolor[i]==-1:q=deque([i])color[i]=0whileq:u=q.popleft()forvingraph[u]:ifcolor[v]==-1:color[v]=color[u]^1q.append(v)elifcolor[v]==color[u]:returnFalsereturnTruei