面试题库 › 算法 / 大模型 › 字符串变换的最小交换次数

字符串变换的最小交换次数

难度 ★★☆在 1 场真实面经中被问到 方向:算法 / 大模型考点:贪心与回溯

哪些公司问过

地平线机器人1

常见岗位:计算机视觉

答案要点

  1. 先确认是任意位置交换还是相邻交换,两种问题解法不同
  2. 字符不重复时,用哈希表把目标位置映射成一个排列
  3. 任意交换:最小次数 = n − 环的个数,O(n) 求解
  4. 相邻交换:最小次数 = 排列的逆序对数,归并排序或树状数组 O(n log n)
  5. 先校验长度和字符集一致,不一致直接判无解

易错点

面试官常见追问

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

相关面试题