首页 > 试题广场 >

牛牛的字符串

[编程题]牛牛的字符串

热度指数：488 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

有一个长度为N的由小写字母组成的字符串S，还有一个整数K。在每一步中，可以选择一个位置 i 并在 i 和 i + K 处交换字符（i + K < N）并且 $S_i < S_{i+k}$ ,即交换之后，新形成的字符串应字典序大于旧字符串。为了尽可能交换尽量多的步数。最多可以交换多少步呢。

示例1

输入

"cbexa",2

输出

说明

cbexa -> cxeba -> excba 步数为2

备注:

算法知识视频讲解

C++

胡澳治

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 cnt = 0, n = s.size();
        for (int i = 0; i < k; i++) {
            for (int j = i; j < n-k; j += k) {
                for (int l = i; l < n-k-j; l += k) {
                    if (s[l] < s[l+k]) {
                        cnt++;
                    }
                }
            }
        }
        return cnt;
    }
};

以上是我模拟冒泡排序，是不成功的，因为冒泡不会让交换步数最多，而是较优化的。应该每个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 cnt = 0, n = s.size();
        for (int i = 0; i < k; i++) {
            int num[26] = {0};
            for (int j = i; j < n; j += k) {
                int index = s[j]-'a';
                num[index]++;
                for (int l = 0; l < index; l++) {
                    if (num[l] > 0)
                        cnt += num[l];
                }
            }
        }
        return cnt;
    }
};

发表于 2021-12-08 10:43:59 回复(0)

牛客970572410号

运行超时

int num1 = strlen(s);

char s1[num1];
strcpy(s1,s);
int bj = 1;
int num = 0;
while(bj)
{
bj = 0;
for(int i = 0 ;i + k < num1;i++)
{
if(s1[i + k] > s1[i])
{
char t = s1[i + k];
s1[i + k] = s1[i];
s1[i] = t;
num++;
bj = 1;
}
}
}
return num;

}

发表于 2021-09-02 20:20:47 回复(0)