题解 | #牛牛的字符串#

牛牛的字符串

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

思路

题目分析

题目给出我们一个字符串和一个数字k

题目允许我们对字符串中的字符进行交换操作，规则是只能互相索引差为k的字符之间可以进行交换

题目要求的结果是根据规则，请用最多的交换次数，使这个字符串顺序变成最大字典序的字符串

最终返回交换的次数

方法一：暴力（超时）

思路
- 由于我们交换的位置有数字k来限制，所以我们可以将每k个字符提取出来一个视作一个子字符串，这样相当于我们需要交换这个子字符串钟相邻的字符。
- 我们根据这个思路可以提取出来k个子字符串
- 我们以某一个子字符串为例思考
  - 首先遍历这个字符串
  - 对于当前遍历到的某个字符，如果其前面有出现比当前字符字典序小的字符，则统计需要交换的次数+1
- 因此遍历k个字符串统计所有的交换次数结果即可

class Solution {
public:
    /**
     * 
     * @param s string字符串 s.size() <= 1e5
     * @param k int整型 k <= s.size()
     * @return int整型
     */
    int turn(string s, int k) {
        // write code here
        int n = s.size();
        int count = 0;
        for(int i = 0; i < k; i++) {                                // 找遍所有的起点
            for(int cur = i; cur < n; cur += k) {                   // 对一个子组部分进行遍历
                for(int pre = cur - k; pre >= 0; pre -= k) {        // 对当前遍历到的子组的cur字符进行向前寻找pre字符
                    if(s[cur] > s[pre]) count++;                    // 如果有交换的必要则计数+1
                }
            }
        }
        return count;
    }
};

复杂度分析

时间复杂度： $O (n^{2} / k)$ ，外轮循环k次，内轮循环 $(1 + n / k) * (n * k) / 2$ 次，最后时间代价就是 $O (n^{2} / k)$
空间复杂度： $O (1)$ ，没有引入额外的空间

方法二：

思路
- 我们用一个字母表的数组来统计所有字母出现的次数
- 还是照例分成k组来考虑单个子字符串
- 这次通过先将前面先出现的字符进行计数统计
- 然后后出现的字符直接看着前面字典序小于自己的字符有出现多少个，就加在count里面多少数量
- 对k个子字符串全部进行统计，得到最后的count结果

alt

class Solution {
public:
    /**
     * 
     * @param s string字符串 s.size() <= 1e5
     * @param k int整型 k <= s.size()
     * @return int整型
     */
    int turn(string s, int k) {
        // write code here
        int count = 0;
        int n = s.size();
        for(int i = 0; i < k; i++) {                                    // 对k组进行访问
            int cha[128] = {0};                                         // 每一组都要初始化各个字母的计数器为0
            for(int j = i; j < n; j += k) {                             // 对子组进行遍历
                for(int ch = 'a'; ch < s[j]; ch++) count += cha[ch];    // 如果在s[j]字符出现之前出现过比s[j]字典序小的字符，则需要考虑进行一次交换，记录总共需要交换的次数
                cha[s[j]]++;                                            // 统计每个字符出现的次数
            }
        }
        return count;
    }
};