Leetcode每日一题 —— 3863. 将一个字符串排序的最小操作次数

开发调优
,
1

思路

也就是要在不选择整个字串的前提下选择其中的失序子序列进行排序，且因为操作数尽量少，选择的失序子序列要尽量长。

因为不能选择整个字串，若要选择尽量长的子序列，那就可以考虑最长的真前缀和真后缀了（即不等于字串本身的前后缀）。下面分类讨论：

  1. 操作 1 次的情况：字串中的最小字母在开头或者末尾，这个时候选择最长真后缀或者最长真前缀排序一次即可；
  2. 操作 2 次的情况：字串中的最小字母或者最大字母在非开头、非末尾的地方出现了（注意同一个字母可能重复出现），这个时候选择一次真前缀再选择一次真后缀即可；
  3. 操作 3 次：字串中的最小字母在末尾且最大字母在开头，这种时候得先选择一次真后缀，然后选择一次真前缀，再选择一次真后缀这样来操作；
  4. 无法操作的情况：在上面要操作三次的情况下，整个字串的长度却不足 3。

这样理清后解题的思路就很明显了。

代码

class Solution {
public:
    int minOperations(string s) {
        // 简单来说就是找失序子序列
        // 因为操作要尽量少，找的子序列也要尽量长，而且不能选择整个字串
        // 1. 如果字串中最小字母已经在开头，那么可以直接选择一次从第二个字符开始的后缀排序
        // 2. 同理最大字母已经在末尾，那么也可以直接选择一次前缀
        // 3. 如果最小字母在末尾的同时最大字母在开头，这个时候就需要三次，比如先选择后缀，再选择前缀，再选择后缀 (前提: s 长度 >=3，而且这两种字母没有重复出现)
        // 4. 其他情况前缀、后缀 2 次选择就能解决
        int n=s.size();
        char maxA=s[0],minA=s[0];
        int maxCnt=1,minCnt=1;
        bool ordered=true; // 是否已经有序
        for(int i=1;i<n;i++){
            if(s[i-1]>s[i]){
                ordered=false;
            }
            if(s[i]>maxA){
                maxA=s[i];
                maxCnt=1;
            }else if(s[i]==maxA){
                maxCnt++;
            }
            if(s[i]<minA){
                minA=s[i];
                minCnt=1;
            }else if(s[i]==minA){
                minCnt++;
            }
        }
        if(ordered){
            // 已经有序
            return 0;
        }
        if(minA==s[n-1]&&maxA==s[0]&&maxCnt==1&&minCnt==1){
            // 最大字母在开头，最小字母在末尾
            // 注意这两种字母如果重复出现，其实 2 次操作就够了
            return n>=3 ? 3 : -1;
        }
        if(minA==s[0]||maxA==s[n-1]){
            // 最小字母已经在最开头 or 最大字母已经在末尾
            return 1;
        }
        // 其他情况两次
        return 2;
    }
};
4 个赞
2

分类讨论。比较暴力

class Solution {
public:
    int minOperations(string s) {
        auto t = s;
        sort(t.begin(),t.end());
        if(s == t) {
            return 0;
        }
        int n = s.size();
        auto minv = t[0];
        auto maxv = t[n - 1];
        if(minv == s[0] || maxv == s[n - 1]) {
            return 1;
        } else if(minv == s[n - 1] && maxv == s[0]) {
            if(n == 2) {
                return -1;
            }
            int minvidx = n - 1, maxvidx = 0;
            for(int i = 1; i < n - 1; i++) {
                if(s[i] == minv) {
                    minvidx = min(minvidx,i);
                }
                if(s[i] == maxv) {
                    maxvidx = max(maxvidx,i);
                }
            }
            if(minvidx != n - 1 || maxvidx != 0) {
                return 2;
            }
            return 3;
        } else {
            return 2;
        }
        return 0;
    }
};
// min .... max  -> 0 / 1;
// .. min .. max / min .. max ..  -> 1
// n == 2 . spec.
// .. min .. max .. / .. max .. min ..  -> 2
// max .... min -> 3
// spec. -> max  max. ...  min min  -> 2.
2 个赞
3

Kotlin每日打卡（贪心与分类讨论 - 两次遍历）：

class Solution {
    fun minOperations(s: String): Int {
        val n = s.length
        if (n == 2) {
            return if (s[0] <= s[1]) 0 else -1
        }

        var minChar = s[0]
        var maxChar = s[0]
        var isReversed = false
        for (i in 1..<n) {
            if (!isReversed && s[i] < s[i - 1]) {
                isReversed = true
            }
            minChar = minOf(minChar, s[i])
            maxChar = maxOf(maxChar, s[i])
        }

        if (!isReversed) {
            return 0
        }

        if (s[0] == minChar || s[n - 1] == maxChar) {
            return 1
        }

        for (i in 1..(n - 2)) {
            if (s[i] == minChar || s[i] == maxChar) {
                return 2
            }
        }
        return 3
    }
}
2 个赞
4

最多操作三次（右左右）

class Solution {
public:
    int dfs(int d,string s,int l,int r){
        if(d>=3)return 3;
        if(l||r)sort(s.begin()+l,s.end()-r);
        if(is_sorted(s.begin(),s.end()))return d;
        if(s.size()==2)return -1;
        return min(dfs(d+1,s,1,0),dfs(d+1,s,0,1));
    }
    int minOperations(string s) {
        return dfs(0,s,0,0);
    }
};
1 个赞