解题思路 有一个长度为 n 的字符串（仅包含小写字母），把这个字符串每隔 k 个就分出来一个子串，比如 [1,k] 为第一个子串，[k+1,2k] 为第二个、[2k+1,3k] 为第三个.....（保证n%k=0）求：把这些子串都变成一样的最少操作次数。 对所有子串的第 1 个字符，求出哪个字符最多
展开全文
#include <bits/stdc++.h>
using namespace std;
int n,k;
int cnt[27];
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin>&g
展开全文
我们发现牛牛实际上只关心每组对应位置上的字母是否相同，那么就会很自然且贪心地想到，把出现最多的那个字母不动，修改其他字母。首先统计每组的第i个位置各个字母的数量，存储方式可以用数组或者哈希表来存储。然后枚举0~k-1个位置，每次ans都累加所有字母数(实际上就是n/k，有n个字母，每k个字母一组，一
展开全文
#include <bits/stdc++.h>
#include <unordered_map>
using namespace std;
int main() {
int n,k;cin>>n>>k;
string s;cin&g
展开全文
这道题其实超简单的说~ (*≧▽≦)我们只需要把字符串s分成n/k个子串，每个子串的成员是那些间隔相等的位置上的字母喵~然后对每个子串的相同位置，我们数一数哪种小字母出现得最多，就让其他所有小字母都变成这个最多的小字母。这样需要改动的次数就最少啦！最后把每个子串要改的次数加起来，就是总的改动次数了喵
展开全文
解题思路：这道题目目的是让字串相同，且要求操作次数最少，也就是对每个子串相同位置进行修改，而想要修改次数最少，我们肯定选择出现次数最大的字符作为目标字符，代码实现如下，先分割统计每个子串同一位置的字母数量，由于子串有n/k个，所以ans直接相加不同的个数即可
#include <bits/st
展开全文
这是一道经典的贪心题首先先用列表去存储按长度分割的每一个子串随后进行k次遍历，每次遍历各个子串的0,1……k - 1索引对应的字符，用字典进行出现次数的累加。因为要修改的总次数最小，依据贪心我们让每次遍历时修改的次数都最小，所以我们找到一次遍历中出现最多的那个字符让它保持不动，修改其余字符，每一次答
展开全文
核心算法：贪心
竖向切片
我们可以将这 个长度为 的子串想象成一个 的字符矩阵：
第 1 行：
第 2 行：
...
第 行：
目标转化：
要是所有行（子串）完全相同，意味着在这个矩阵中，每一列的所有字符必须相同。
由于不同列之间的字符选择是相互独立的，我们可以将大问题分解为 个独立的
展开全文
思路：贪心，我们需要最少的操作次数，那就可以cnt出每个字符串对应位置的元素个数，并且要所有对应位置的字符都变成最大数量的那个字符，具体是什么字符我们不关心。那么剩下需要修改的字符数量就是n // k - mx，我们遍历一遍，然后累加即可得到ans
注意：具体实现的时候不需要把具体的n // k个字
展开全文
-
扫描二维码，关注牛客
- 意见反馈
-
下载牛客APP，随时随地刷题
- 牛客竞赛，专业的竞技算法训练平台
-
扫描二维码，进入QQ群
扫码关注“比赛自动姬”
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备 11010502036488号
