Amazon OA：整体反转与左转一格，最少操作不能只数旋转

题意与假设

这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。

• 每次reverse和左rotate一格都成本1，不能一次旋转任意格算1。
• n≥1为原任务；训练额外允许空数组0，非法排列拒绝，不可达返回None便于验证。

解题路线

1. 两个操作只改变环方向和起点，故可达排列恰为升序环的旋转或降序环旋转。验证相邻值模n差+1或-1，不能假设任意排列都可排序。
2. 设升序方向排列中1下标d，直接左转d次完成；也可F R^(n-d) F实现右转n-d步，成本n-d+2，最优min(d,n-d+2)。
3. 降序方向先看反转后1下标s=n-1-position(1)。一次F再左转s，或先左转n-s再F分别成本1+s和1+n-s，最优1+min(s,n-s)。
4. 最短证明：没有F只能单向转，偶数F且非零至少2；圈上反向到目标至少n-d个转步。奇数F至少1，旋转步至少圆周最短距离，两种把F放前/后均能达到。更多F不减这个旋转下界，反增加成本。
5. n=1/2时两方向表示可能重叠，取所有合法候选最小即可。作者“升序旋转/降序旋转/反转后升序旋转”的分类不足以推出最少，因为两次F能替代逆向旋转。

手动走一遍

训练[2,3,4,5,1]：直接左转4次，但F、左转1、F只要3次；[5,4,3,2,1]只F一次；[1,3,2,4]不在可达环中。

Python 参考实现

下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。

代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。

def minimum_operations(permutation):
    """Unit-cost full reversal and one-position left rotation; None if unreachable."""
    n=len(permutation)
    if len(set(permutation))!=n or any(not 1<=v<=n for v in permutation):
        raise ValueError("not a permutation of 1..n")
    if not n:return 0
    position=permutation.index(1)
    answers=[]
    if all((permutation[(i+1)%n]-permutation[i])%n==1%n for i in range(n)):
        answers.append(min(position,n-position+2))
    if all((permutation[(i+1)%n]-permutation[i])%n==(n-1)%n for i in range(n)):
        after_reverse=n-1-position
        answers.append(1+min(after_reverse,n-after_reverse))
    return min(answers) if answers else None

复杂度

验证与找1 O(n)期望时间/空间（set校验），已保证合法时循环检查可O(n)时间、O(1)辅助空间。不实际模拟指数种排列。

易错点与追问

容易失分的边界

• 把任意移动格数算一次操作。
• 只数1的位置忽略两次F捷径。
• 任意排列都视可达。

继续深挖

• reverse成本不同怎样改最短公式？
• 允许右转一格时怎样简化？
• 要输出具体操作序列？