网站建设分工说明,如何在百度上投放广告,红酒公司网站建设模板6841,长沙医院网站建设文章目录 1. 题目来源2. 题目解析 1. 题目来源
链接#xff1a;2182. 构造限制重复的字符串 力扣题解#xff1a;[C] 贪心模拟#xff0c;分类讨论#xff0c;注释清晰
2. 题目解析
很明显贪心#xff0c;有最大尽可能多的填最大#xff0c;发现达到限制数后#xff… 文章目录 1. 题目来源2. 题目解析 1. 题目来源
链接2182. 构造限制重复的字符串 力扣题解[C] 贪心模拟分类讨论注释清晰
2. 题目解析
很明显贪心有最大尽可能多的填最大发现达到限制数后就换个次大值进来接着尽可能多的填最大。 这里就有两个想法: 1- 直接哈希计数后根据规则构造结果字符串 2- sort 排序后原字符串进行判断、交换等操作获取结果仔细想想异常情况太多没考虑了
这里需要体会下与官解双指针写法的不通感觉那个更优雅点…这种写法把算法题写成了纯业务题… 时间复杂度 O ( n ) O(n) O(n) 感觉是会比 O(n) 大因为可能存在一些无效的遍历空间复杂度 O ( 1 ) O(1) O(1) class Solution {
public:string repeatLimitedString(string s, int repeatLimit) {int um[26] {0};for (char c : s) um[c - a] ; // 哈希计数string res ;int last -1, cnt -1; // last:当前构造字符串的末尾元素cnt:当前构造字符串的末尾连续元素个数while (1) {bool out true; // 是否构造完毕标志for (int i 25; i 0; i -- ) { // 逆序构造结果if (um[i] 0) continue ;if (cnt repeatLimit) { // 如果连续元素已经满了需要找下一个合适的字符if (i ! last um[i] 0) { // 筛选规则下一个与当前不同且字符尽可能大配合上逆序添加的性质只要遇到第一个不和末尾字符相同的可用字符即可这里只需要一个字符res string(1, i a);um[i] -- ;last i, cnt 1;out false;break;}} else { // 末尾元素没满看看当前元素可以放几个进去if (um[i] repeatLimit) { // 如果当前元素较多大于了限制数if (last ! i) { // 如果末尾和当前待放入的元素不同则直接放满限制数个字符res string(repeatLimit, i a);um[i] - repeatLimit;last i, cnt repeatLimit; // 更新末尾元素更新连续元素个数out false;} else { // 如果末尾和当前待放入的元素相同那么只能放入一部分该部分和末尾字符加在一起补充满限制数int t repeatLimit - cnt;res string(t, i a);um[i] - t;last i, cnt repeatLimit; // 更新末尾元素更新连续元素个数out false;}} else { // 如果末尾元素不是很多少于限制数// if (last ! i) { // 如果末尾和当前待放入的元素不同则直接放满限制数即可res string(um[i], i a);um[i] 0;last i, cnt um[i];out false;// } else { // 如果末尾和当前待放入的元素相同那么也要考虑剩余部分放进入会不会导致超出限制只能放入一部分补充满限制数字符// int t um[i] cnt repeatLimit ? repeatLimit - cnt : um[i];// res string(t, i a);// um[i] - t;// last i, cnt t;// out false;// }// 这里将上面代码注释的原因该场景存在但不用分类讨论因为不会超过限制直接添加所有字符即可// 因为走到 else 逻辑, um[i] 肯定小于限制且当前的 i 即便和 last 同一个字符但此时的last只有一个字符// 填充了多个字符--》选择次大值--》刚好次大值选中了当前的这个字符填充一个--》该字符元素没超过限制数--》该字符走到当前逻辑// 所以只有一个字符的情况下且剩余字符数本身就小于限制数所以直接将剩余的所有字符全部添加进去即可}}}if (out) return res;}return ;}
};
