443. String Compression
2021/7/2 6:21:13
本文主要是介绍443. String Compression,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
Given an array of characters chars
, compress it using the following algorithm:
Begin with an empty string s
. For each group of consecutive repeating characters in chars
:
- If the group's length is 1, append the character to
s
. - Otherwise, append the character followed by the group's length.
The compressed string s
should not be returned separately, but instead be stored in the input character array chars
. Note that group lengths that are 10 or longer will be split into multiple characters in chars
.
After you are done modifying the input array, return the new length of the array.
You must write an algorithm that uses only constant extra space.
Example 1:
Input: chars = ["a","a","b","b","c","c","c"] Output: Return 6, and the first 6 characters of the input array should be: ["a","2","b","2","c","3"] Explanation: The groups are "aa", "bb", and "ccc". This compresses to "a2b2c3".
Example 2:
Input: chars = ["a"] Output: Return 1, and the first character of the input array should be: ["a"] Explanation: The only group is "a", which remains uncompressed since it's a single character.
Example 3:
Input: chars = ["a","b","b","b","b","b","b","b","b","b","b","b","b"] Output: Return 4, and the first 4 characters of the input array should be: ["a","b","1","2"]. Explanation: The groups are "a" and "bbbbbbbbbbbb". This compresses to "ab12".
Example 4:
Input: chars = ["a","a","a","b","b","a","a"] Output: Return 6, and the first 6 characters of the input array should be: ["a","3","b","2","a","2"]. Explanation: The groups are "aaa", "bb", and "aa". This compresses to "a3b2a2". Note that each group is independent even if two groups have the same character.
Constraints:
1 <= chars.length <= 2000
chars[i]
is a lower-case English letter, upper-case English letter, digit, or symbol.
class Solution { public int compress(char[] chars) { int slow = 0, fast = 0; while(fast < chars.length) { int cnt = 0; char c = chars[fast]; while(fast < chars.length && c == chars[fast]) { fast++; cnt++; } chars[slow++] = c; if(cnt != 1) { for(char ch : (""+cnt).toCharArray()) chars[slow++] = ch; } } return slow; } }
String相关,用快慢指针,快指针遍历string,慢指针负责填空。
每次循环都是cnt重置,然后获得当前的char,如果后面有相等的就一直往后面fast++直到不相等。然后慢指针填空当前的char,然后填cnt。
这篇关于443. String Compression的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-15PingCAP 黄东旭参与 CCF 秀湖会议,共探开源教育未来
- 2024-05-13PingCAP 戴涛:构建面向未来的金融核心系统
- 2024-05-09flutter3.x_macos桌面os实战
- 2024-05-09Rust中的并发性:Sync 和 Send Traits
- 2024-05-08使用Ollama和OpenWebUI在CPU上玩转Meta Llama3-8B
- 2024-05-08完工标准(DoD)与验收条件(AC)究竟有什么不同?
- 2024-05-084万 star 的 NocoDB 在 sealos 上一键起,轻松把数据库编程智能表格
- 2024-05-08Mac 版Stable Diffusion WebUI的安装
- 2024-05-08解锁CodeGeeX智能问答中3项独有的隐藏技能
- 2024-05-08RAG算法优化+新增代码仓库支持,CodeGeeX的@repo功能效果提升