首页 > 牛牛的字符串
开通博客写题解
头像 xqxls
发表于 2021-09-10 17:29:44
题意整理 给定一个长度为n的字符串和一个整数k。 每一步可以交换下标i与i+k对应的元素，保证交换之后字典序变大。 求最多交换多少步。 方法一（分组+临时计数统计） 1.解题思路 将字符串分为k组，每组的起点分别是0到。 然后分别遍历每一组，并用计数数组记录当前元素访问次数。 如果之前有下标小 展开全文
去ta的博客 赞 (1) 回复(1) 收起
头像 Victor丶
发表于 2021-05-18 10:21:02
实际就是求位于i+nK的字符组成的数组按从大到小排序所需要的步骤（可以当成S为新数组，K=1的解，从左往右遍历，求出新数组中当前位置前面比当前数小的字符数量的和)，再求和分成的数组数量为K和N-K的最小值 # # # @param s string字符串 s.size() <= 1e5 # 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 不会做题的小菜鸡
发表于 2021-10-20 01:30:55
思路 题目分析 题目给出我们一个字符串和一个数字k 题目允许我们对字符串中的字符进行交换操作，规则是只能互相索引差为k的字符之间可以进行交换 题目要求的结果是根据规则，请用最多的交换次数，使这个字符串顺序变成最大字典序的字符串 最终返回交换的次数 方法一：暴力（超时） 思路 由于我们交换 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 东溪看水
发表于 2020-07-31 15:19:21
题目 有一个长度为 的由小写字母组成的字符串 ，还有一个整数 。在每一步中，可以选择一个位置 并在 和 处交换字符（）并且 ，即交换之后，新形成的字符串应字典序大于旧字符串。求最多可以交换多少步。 解题思路 将字符串分成 组子串，每组子串由字符串 中下标 模 后相等的字符组成。对于每 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 牛客313925129号
发表于 2021-10-11 11:15:53
题意理解 当第i个字母小于第i+k个字母时，可以交换两个字母顺序，记作一次交换。我们要求给定的字符串中，最多可以进行几次交换，直到不存在符合交换条件的两个对应字母。 方法一 可以看到，第i、i+k、i+2k、i+3k等等这些字母之间进行交换，和其它字母无关，所以可以把这样的字母序列提取出来，依次计算 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 我的昵称是个响亮的名字吧
发表于 2021-09-17 15:50:28
题目描述 题意 首先我觉得题目示例中给的例子的说明不太好，很容易让人误解，按照我们的正常思路一般是从左到右去交换 所以把说明改为 cbexa -> ebcxa -> excba 这样会更好理解一点 先来理解一下字典序是个什么概念，这里也是题目没有交代清楚的一点，其实这个跟逆序数有点类 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 leehom
发表于 2021-08-10 20:00:43
观察规律: 1、可以首先将字符串分为k个独立的子串分别处理，每个子串的步长是k。2、如果相同字符串中，一个字符串的前面有x个字符比这个字符小，那么乱序数为x，所有字符的乱序数的和为该字符串的乱序数n3、如果一个字符串的字符乱序数为n，那么需要n步来对数组进行从大到小排序处理独立子串：在遍历过程中，将 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 牛客487943642号
发表于 2021-08-19 10:43:34
题目描述 有一个长度为N的由小写字母组成的字符串S，还有一个整数K。在每一步中，可以选择一个位置 i 并在 i 和 i + K 处交换字符（i + K < N）并且Si < S(i + k),即交换之后，新形成的字符串应字典序大于旧字符串。为了尽可能交换尽量多的步数。最多可以交换多少步呢 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 佛系的华夫饼
发表于 2023-04-28 20:31:57
# # # @param s string字符串 s.size() <= 1e5 # @param k int整型 k <= s.size() # @return int整型 # class Solution: def turn(self , s , k ): 展开全文
去ta的博客 赞 (0) 回复(0) 收起
查看本题
查看本题讨论

相关比赛

等你来战

查看全部
牛客竞赛，专业的竞技算法训练平台

扫描二维码，进入QQ群

扫码关注“比赛自动姬”