字节后端二面手撕题
字节二面前面就简单聊聊天,问一些八股,手撕题竟然直接两题,限时三十分钟,不过最好还是搞定了,简单分享下手撕题
Q1:给定一组可用数字和一个上限整数 n,用可用数字构造不超过 n 的max整数。
思路:采用DFS,从高位到低位尝试拼接数字。若当前数值超过 n 则剪枝,否则更新max。通过递归枚举所有可能组合,找到满足条件的max。
Q2:给定一个 n 行 m 列的矩阵和一个整数 k,求所有大小为 k×k 的子矩阵中元素和的max。
思路:使用二维前缀和数组预处理矩阵,其中 `sum[i][j]` 表示从 (1,1) 到 (i,j) 的子矩阵和。枚举所有可能的 k×k 子矩阵的右下角坐标 (i,j),通过前缀和数组快速计算子矩阵和,并更新max。时间复杂度为 O(n×m)。