题解 | #牛牛的字符串#

牛牛的字符串

http://www.nowcoder.com/practice/0cc3b103e43f4ec093be586df292822e

题目描述

图片说明

题意

首先我觉得题目示例中给的例子的说明不太好，很容易让人误解，按照我们的正常思路一般是从左到右去交换所以把说明改为

cbexa -> ebcxa -> excba 这样会更好理解一点先来理解一下字典序是个什么概念，这里也是题目没有交代清楚的一点，其实这个跟逆序数有点类似，只是不是数字比较，而是字符交换后的结果比较：假设四个字母abc，其形成的所有序列按字典序应该是 abc<acb<bac<bca<cab<cba

详细说明下步骤吧：首先对于字符串S="cbexa",i从0开始,k=2,S[0]=c S[2]=e ,S[0]<S[2]，符合交换条件，交换后结果为 ebcxa;而后面S[4]=a 不符合交换条件，S[6]超出数组长度，本轮结束。

第二轮,i从1开始,k=2,S[1]=b,S[3]=x,S[1]<S[3]，符合交换条件，交换后为excba，S[5]超出数组长度，本轮结束。

问题降维

从上面分析我们可以发现，其实字符串S按照K的比较步长被分成了K个子串，例如示例中的cbexa，就因为K=2分成了2个串，分别是cea 和 bx。问题就降为到分别求cea和bx的交换步数的总和（此时可以看做K=1）的一个过程。

cea -> eca 只能交换1步 bx -> xb 只能交换1步所以总交换次数为2

所以我们可将这个题目降维聚焦计算一个：在k=1的字符串能够交换次数

在这个基础上(即字符串已经分成多个k=1的子串)我们继续剖析问题，这个问题有两个问题很容易让我们把问题想复杂了：

交换的顺序是否影响结果？举个例子看看，假设S="abc", 从左到右交换(a先交换，然后b然后c)，依次是 bac cba acb 从右到左交换，依次是acb,cba,bac 从结果的值和数量上都是一致的。可以再多用一些例子去证明这一点所以结果跟交换顺序是没有关系的
是否需要根据每次交换后的结果再进行分析，从原始状态是否可以推导出结果？依然拿S="abc"这个例子来说，从我们交换的顺序来看，依次是bac cba acb，有3个结果那有没有办法不经过这种动态的交换，从原字符串"abc"的初始状态就能计算出结果呢？其实回到这个问题的本质，其交换过程与冒泡算法是非常相似的，本质上是一个基于冒泡的思路去将原始字符数组进行从大到小排序的一个过程。在学习冒泡排序的时候，有一个知识点是冒泡排序的交换次数等于这个数组的逆序数。

在结合1、2两点之后，问题再次被降维：求字符串按照字符大小比较的逆序数

代码实现一：常规解法（暴力法）

import java.util.*;

public class Solution {
    /**
     *
     * @param s string字符串 s.size() <= 1e5
     * @param k int整型 k <= s.size()
     * @return int整型
     */
    public int turn (String s, int k) {
        
        List<List<Character>> sl = new ArrayList<>();
        //初始化k个字符列表，为了方便遍历将子串以List<Character>的形式存储
        for(int i=0;i<k;i++){
            sl.add(new ArrayList<>());
        }
        // 将S拆成k个子串
        for(int i=0;i<s.length();i++){
            sl.get(i%k).add(s.charAt(i));
        }
        int sum = 0;
        for(List<Character> l : sl){
            // K个逆序数相加
            sum+=count(l);
        }
        return sum;
    }
    // 计算一个字符数组的逆序数
    public int count(List<Character> s){
        int count = 0;
        for(int i= 1; i<s.size();i++){
            for(int j=0;j<i;j++){
                // 比较并计算逆序数
                if(s.get(i)>s.get(j)){
                    count++;
                }
            }
        }
        return count;
    }
}

图片说明

咳咳，基本操作，看到题干中N的范围就应该猜到常规做法有可能会超时。

代码实现二：算法优化

上面代码耗时的地方主要在count函数中，2个for循环，复杂度为 $O (n^{2})$ ,但实际我们需要得逻辑是为了计算S[i]之前有多少个小于S[i]的字母。那我们换个思路，我们不再一个个比较，而是存储下当前字符前每个字符出现的次数，这样我们只需要遍历这个存储的数组，累加小于这个字符的出现次数值就可以了。举个例子，abcfe，当计算e 前面有几个小于e的字符时，之前的思路是遍历比较前面每一个值，但是我们知道字母就26个，我们可以一个int[26]数组去存储在某个坐标之前所有字母出现的次数，通过index = char - 'a' 计算出坐标，我们只需要累加所有坐标小于'e'-'a'的数组值就可以了。于是代码可以优化为：

public int count(List<Character> s){
        int[] charCount = new int[26];
        int count = 0;
        charCount[s.get(0)-'a']++;
        for(int i= 1; i<s.size();i++){
            charCount[s.get(i)-'a']++;
            for(int j=0;j<s.get(i)-'a';j++){
                count+=charCount[j];
            }
        }
        return count;
    }

图片说明

咳咳，数据上有点丑陋，那再优化下。

代码实现三：代码结构优化

其实没有必要先分组再计算的，可以把代码合在一起。如下所示

public int turn (String s, int k) {
        int result = 0;
        int n = s.length();
        for(int i=0; i<k; i++){
            int[] num = new int[26];
            num[s.charAt(i) - 'a']++;
            for(int j=i+k; j<n; j = j+k){
                int current = s.charAt(j) - 'a';
                for(int pront = 0; pront < current; pront++){
                    result += num[pront];
                }
                num[current]++;
            }
        }
        return result;
    }

虽然还是2个for循环，但是本质上只是按分组去遍历字符串，所以时间复杂度是 $O (n)$ ; 空间复杂度为 $O (1)$ ;