2182.构造限制重复的字符串(模拟 贪心 优先队列 C++ Go)

简介: 【2月更文挑战第19天】2182.构造限制重复的字符串(模拟 贪心 优先队列 C++ Go)

题目链接

题意

给你一个字符串 s 和一个整数 repeatLimit ,用 s 中的字符构造一个新字符串 repeatLimitedString ,使任何字母 连续 出现的次数都不超过 repeatLimit 次。你不必使用 s 中的全部字符。

返回 字典序最大的 repeatLimitedString 。

如果在字符串 a 和 b 不同的第一个位置,字符串 a 中的字母在字母表中出现时间比字符串 b 对应的字母晚,则认为字符串 a 比字符串 b 字典序更大 。如果字符串中前 min(a.length, b.length) 个字符都相同,那么较长的字符串字典序更大。
提示:

$1 <= repeatLimit <= s.length <= 10^5$
s 由小写英文字母组成

思路

贪心的构造

  • 每次将当前剩余的字典序最大的字符添加到答案里,如果该字符已经连续出现了repeatLimit次,则先将当前剩余的字典序次大的字符添加到答案里,再继续将当前剩余的字典序最大的字符添加到答案里,直到该最大的字符用完或是没有次大的字符可以插入

有两种写法

  1. 多层for循环,不断尝试填入新字符
    • 结合上述的思路可以得知,每个字符i最多被添加min(repeatLimit,mp[i])次,其中mp[i]为字符i的出现次数
    • 可以先统计字符串s里每个字符的出现次数
    • 倒序进行遍历,这时候i里维护的就是当前剩余的字典序最大的字符
    • 尝试将字符i添加到答案字符串里
    • 如果i已经填完了的话,跳出循环,找下一个当前剩余的字典序最大的字符
    • 否则的话找第一个存在且字典序次大的字符,插入到答案字符串里,这样后面就可以继续填字母i
  2. 使用优先队列维护字典序最大字符和次大字符
    • 思路1的本质是通过for循环找当前剩余的字典序最大/次大的字符,可以通过优先队列来维护

代码

func repeatLimitedString(s string, repeatLimit int) string {
   
    mp := make(map[rune]int, 26)
    for _, ch := range s {
   
        mp[ch]++
    }
    ans := make([]rune,0,len(s))
    for i := 'z'; i >= 'a'; i-- {
   //倒序填入字母
        las := i - 1//记录次小的字母值
        for {
   
            for j := 0; j < repeatLimit && mp[i] > 0; j++ {
   //最多填入min(repeatLimit,mp[i])个字母i
                mp[i]--
                ans = append(ans, i)
            }
            if mp[i] == 0 {
   //i填完了 找下一个字典序最大的字母
                break
            }
            for las >= 0 && mp[las] == 0 {
   //找到第一个存在的字典序次大的字母
                las--
            }
            if las < 0 {
   //找不到 跳出
                break
            }
            //先填入次大字母 后面可以继续填最大字母i
            mp[las]--
            ans = append(ans, las)
        }
    }
    return string(ans)
}
class Solution {
   
    public:
        string repeatLimitedString(string s, int repeatLimit) {
   
            int mp[26];
            for(int i=0; i<26; i++) {
   
                mp[i]=0;
            }
            for(char ch:s) {
   
                mp[ch-'a']++;
            }
            string ans;
            for(int i=25; i>=0; i--) {
   
                int las = i-1;
                while(1) {
   
                    for(int j=0; j<repeatLimit&&mp[i]>0; j++) {
   
                        mp[i]--;
                        ans.push_back(i+'a');
                        //ans = ans + char(i+'a');
                    }
                    if(mp[i]==0) {
   
                        break;
                    }
                    while(las>=0&&mp[las]==0) {
   
                        las--;
                    }
                    if(las < 0) {
   
                        break;
                    }
                    mp[las]--;
                    ans.push_back(las+'a');
                //    ans = ans + char(las+'a');
                }
            }
            return ans;
        }
};
目录
相关文章
|
2月前
|
人工智能 自然语言处理 算法
Go语言统计字符串中每个字符出现的次数 — 简易频率分析器
本案例实现一个字符统计程序,支持中文、英文及数字,可统计用户输入文本中各字符的出现次数,并以整洁格式输出。内容涵盖应用场景、知识点讲解、代码实现与拓展练习,适合学习文本分析及Go语言基础编程。
|
2月前
|
C语言 C++
【实战指南】 C/C++ 枚举转字符串实现
本文介绍了在C/C++中实现枚举转字符串的实用技巧,通过宏定义与统一管理枚举名,提升代码调试效率并减少维护错误。
181 33
|
10月前
|
存储 Go 索引
go语言中遍历字符串
go语言中遍历字符串
140 5
|
5月前
|
Go 索引
【LeetCode 热题100】394:字符串解码(详细解析)(Go语言版)
本文详细解析了 LeetCode 热题 394:字符串解码。题目要求对编码字符串如 `k[encoded_string]` 进行解码,其中 `encoded_string` 需重复 `k` 次。文章提供了两种解法:使用栈模拟和递归 DFS,并附有 Go 语言实现代码。栈解法通过数字栈与字符串栈记录状态,适合迭代;递归解法则利用函数调用处理嵌套结构,代码更简洁。两者时间复杂度均为 O(n),但递归需注意栈深度问题。文章还总结了解题注意事项及适用场景,帮助读者更好地掌握字符串嵌套解析技巧。
123 6
|
6月前
|
存储 机器学习/深度学习 缓存
🚀 力扣热题 394:字符串解码(详细解析)(Go语言版)
文章提供了两种解法:栈结构和递归解法。栈解法通过维护数字栈与字符串栈,依次处理 `[` 和 `]`,构造解码结果;递归解法则利用函数调用逐层解析嵌套结构。两者时间复杂度均为 $O(n)$,空间复杂度也为 $O(n)$。栈解法直观易懂,适合初学者;递归解法优雅简洁,适合处理深度嵌套规则。掌握这两种方法,可灵活应对类似问题,提升解题能力。
167 11
|
7月前
|
消息中间件 Linux C++
c++ linux通过实现独立进程之间的通信和传递字符串 demo
的进程间通信机制,适用于父子进程之间的数据传输。希望本文能帮助您更好地理解和应用Linux管道,提升开发效率。 在实际开发中,除了管道,还可以根据具体需求选择消息队列、共享内存、套接字等其他进程间通信方
143 16
|
9月前
|
Go
go语言for 遍历字符串
go语言for 遍历字符串
115 8
|
10月前
|
Go 索引
go语言遍历字符串
go语言遍历字符串
163 3
|
11月前
|
缓存 网络协议 API
C/C++ StringToAddress(字符串转 boost::asio::ip::address)
通过上述步骤和示例代码,你可以轻松地在C++项目中实现从字符串到 `boost::asio::ip::address`的转换,从而充分利用Boost.Asio库进行网络编程。
305 0
|
7月前
|
编译器 C++ 开发者
【C++篇】深度解析类与对象(下)
在上一篇博客中,我们学习了C++的基础类与对象概念,包括类的定义、对象的使用和构造函数的作用。在这一篇,我们将深入探讨C++类的一些重要特性,如构造函数的高级用法、类型转换、static成员、友元、内部类、匿名对象,以及对象拷贝优化等。这些内容可以帮助你更好地理解和应用面向对象编程的核心理念,提升代码的健壮性、灵活性和可维护性。