面试题库 › 嵌入式 › 俄罗斯套娃信封:回溯输出所有嵌套路径

俄罗斯套娃信封:回溯输出所有嵌套路径

难度 ★★★在 1 场真实面经中被问到 方向:嵌入式考点:贪心与回溯

哪些公司问过

腾讯1

常见岗位:C/C++ 软件开发

答案要点

  1. 宽高都必须严格大于才能嵌套,信封不能旋转
  2. 求最大层数:宽升序、同宽高降序后,对高度求最长严格递增子序列
  3. 贪心加二分求长度为O(n log n)
  4. 输出所有路径用排序后DFS回溯,加入、递归、撤销
  5. 用DP预处理最长链长度做剪枝,路径数可能是指数级

易错点

面试官常见追问

完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。

相关面试题