Leetcode每日一题 —— 3942. 排序排列的最少操作数

把0换到开头，判有没有排序；注意反转2次可以右旋

class Solution {

public:

	int minOperations(vector<int>& v) {

		#define L v.begin()

		#define R v.end()

		

		int p0=find(L,R,0)-L,n=v.size();

		

		rotate(L,L+p0,R);

		if(is_sorted(L,R))return min(p0,n-p0+2);

		

		rotate(L,L+1,R);

		reverse(L,R);

		if(is_sorted(L,R))return min(p0+2,n-p0);

		

		return -1;

	}

};

忙，忙点好啊.jpg

分类讨论题。先判断循环数组的单调性，如果不单调直接 pass。

class Solution {

public:

    int minOperations(vector<int>& nums) {

        // 要让数组变成递增的，整个数组必须至少是循环递增或者循环递减的

        // 如果都不是直接返回 -1

        int n=nums.size();

        if(n==1){

            return 0;

        }

        // 先找到 0 位置

        int zeroPos=0;

        while(nums[zeroPos]!=0){

            zeroPos++;

        }

        // 检查单调性

        bool incre=true,decre=true;

        int i=(zeroPos+1)%n;

        while(i!=zeroPos){

            if(nums[i]-nums[(i+n-1)%n]!=1){

                // 非单增

                incre=false;

                // 如果发现非单增时距离起始位置已经有 i-zeroPos > 1，那这个序列就肯定也不是递减

                if((i+n-zeroPos)%n>1){

                    return -1;

                }

                break;

            }

            i=(i+1)%n;

        }

        i=(zeroPos+n-1)%n;

        while(i!=zeroPos){

            if(nums[i]-nums[(i+1)%n]!=1){

                // 非单减

                decre=false;

                break;

            }

            i=(i+n-1)%n;

        }

        if(!incre&&!decre){

            return -1;

        }

        if(incre&&zeroPos==0){

            // 整个序列已经递增

            return 0;

        }

        if(decre){

            // 循环递减的情况

            // 肯定要有一次反转，问题是在旋转前还是后反转

            // 1. 先旋转再反转，旋转要把 0 向左移动到最右边 (n-1 位置)

            // 2. 先反转再旋转，相当于把 0 向右移动到最右边

            return min((zeroPos+n-(n-1))%n+1,n-1-zeroPos+1);

        }else if(incre){

            // 循环递增的情况

            // 1. 把 0 向左移动到 0 位置

            // 2. 反转后，把 0 向左移动最右边位置，再反转 (相当于把 0 向右滚动到 0 位置)

            return min(zeroPos-0,(0+n-zeroPos)%n+2);

        }

        return -1;

    }

};

通过相邻元素差值判断数组的方向，再利用断点 pos 计算操作次数。

无序排列返回 -1

对升序排列，有两种选择

1. 直接左旋


2. 翻转一次，把左旋方向转换成右旋方向，再翻转回来（两次翻转可以模拟向右旋转，而且成本只增加 2）

对降序排列

1. 断点之前左旋，反转


2. 先反转，之前断点右边的部分左旋

class Solution {

public:

    int minOperations(vector<int>& nums) {

        int n = nums.size();

        if (n == 1) return 0;



        int order = 0, pos = 0;



        for (int i = 1; i < n; i++) {

            int d = nums[i] - nums[i - 1];



            if (abs(d) == 1) {

                int dir = d > 0 ? 1 : -1;

                if (order == 0) order = dir;

                else if (order != dir) return -1;

            } else if (abs(d) == n - 1) {

                pos = i;

            } else {

                return -1;

            }

        }



        int left = pos, right = n - pos;



        if (order == 1)

            return min(left, right + 2);



        return min(left + 1, right + 1);

    }

};

顺便一提，这道题还可以牵涉到循环群与二面体群的关系

Kotlin每日打卡（分类讨论）：

class Solution {

    fun minOperations(nums: IntArray): Int {

        val size = nums.size

        if (size == 1) {

            return 0

        }



        var commonDifference = nums[1] - nums[0]

        if (Math.abs(commonDifference) != 1) {

            if (size <= 2) return -1

            commonDifference = nums[2] - nums[1]

            if (Math.abs(commonDifference) != 1) {

                return -1

            }

        }



        var mutationIndex = 0

        for (i in 1..size - 1) {

            if (nums[i] - nums[i - 1] != commonDifference) {

                if (mutationIndex > 0) {

                    return -1

                }

                mutationIndex = i

            }

        }



        return if (commonDifference == 1) {

            minOf(mutationIndex, size - mutationIndex + 2)

        } else {

            minOf(mutationIndex, size - mutationIndex) + 1

        }

    }

}