clhiker
竹杖芒鞋轻胜马,谁怕?一蓑烟雨任平生!
Home
Categories
Archives
Tags
About
Home
美团春招一面面经
美团春招一面面经
取消
美团春招一面面经
由
clhiker
发布于 2023-03-28
·
最后更新:2023-03-28
## 算法题:删除并保留一位最长连续重复子串 - input - "aabbcc" - "aabbccaaa" - "aabbccaa" - output - "abc" - "bca" - abca" 要求:时间复杂度:O(N),空间复杂度:O(1)。 ```cpp string solve(string& str){ map<char, int> total; // 先统计每个字符的最长连续长度 for (int i = 1; i < str.size(); ++i) { int count = 1; while (i < str.size() && str[i] == str[i-1]){ count ++; i++; } if (total.find(str[i-1]) == total.end()){ total[str[i-1]] = count; } else{ total[str[i-1]] = count > total[str[i-1]] ? count : total[str[i-1]]; } } for (int i = 1; i < str.size(); ++i) { int count=1; int j=i-1; while (i<str.size() && str[i] == str[i-1]){ count ++ ; i++; } if (count == total[str[i-1]]){ // 留一个 str.erase(j, i-j-1); i = j+1; } else{ // 删完 str.erase(j, i-j); i = j; } } return str; } ```
该博客文章由作者通过
CC BY 4.0
进行授权。
分享
最近更新
wsl 使用经验
十个命令开始玩转docker
node 使用教程
米哈游面试
Verilog语法-1
热门标签
red
文章目录
金山WPS
京东面经