目录
- 题目描述
- 整理题意
- 解题思路分析
- 具体实现
- 复杂度分析
- 代码实现
- 总结
题目描述
题目链接：1417. 重新格式化字符串
给你一个混合了数字和字母的字符串 s，其中的字母均为小写英文字母。
请你将该字符串重新格式化，使得任意两个相邻字符的类型都不同。也就是说，字母后面应该跟着数字，而数字后面应该跟着字母。
请你返回 重新格式化后 的字符串；如果无法按要求重新格式化，则返回一个 空字符串 。
提示:
- 1⩽s.length⩽5001
s仅由小写英文字母和/或数字组成。
示例 1：
输入：s = "a0b1c2"
输出："0a1b2c"
解释："0a1b2c" 中任意两个相邻字符的类型都不同。 "a0b1c2", "0a1b2c", "0c2a1b" 也是满足题目要求的答案。
示例 2：
输入： s = "leetcode"
输出： ""
解释： "leetcode" 中只有字母，所以无法满足重新格式化的条件。
示例 3：
输入： s = "1229857369"
输出： ""
解释： "1229857369" 中只有数字，所以无法满足重新格式化的条件。
示例 4：
输入： s = "covid2019"
输出： "c2o0v1i9d"
示例 5：
输入： s = "ab123"
输出： "1a2b3"
整理题意
题目给定一个字符串，仅包含小写字母和数字，让我们利用字符串中所给的这些字符构造一个字符串，使得构造出来的字符串中字母字符和数字字符不相邻。答案返回任意一个满足条件的字符串即可，如果无法构造这样的字符串返回空字符串。
解题思路分析
根据题目描述可知，为了使得字符串中不含有相邻的字母和数字，我们尽可能的使得字母和数字交叉排列，那么当字符串中数字个数和字母个数的差值大于 1 时，无论我们怎么排列总会有两个相同的字母字符或数字字符相邻。
那么考虑当字符串中数字个数和字母个数的差值小于等于 1 时，我们将个数较多的种类字符放在偶数位置上，较少的字符种类放在奇数位置上（位置从 0 开始）。
具体实现
首先统计字符串中数字字符个数和字母字符个数，并判断两者差值是否大于 1，大于 1 的情况直接返回空字符串。
双指针 实现字符串排列：
- 指针
i指向偶数位置，j指向奇数位置； - 初始化
i = 0，j = 1； - 当
i位置上的字符不为较多的字符种类时，利用j指针从左到右找到第一个较多的字符种类，与位置i进行交换字符； - 重复步骤
3直至遍历完整个字符串。
细节操作：代码实现过程中仅用 if(isdigit(s[i]) != f) 这样的判断语句涵括了两种情况的判断。
复杂度分析
- 时间复杂度：O(n)，其中
n为字符串s的长度，需要遍历两遍字符串。 - 空间复杂度：O(1)，仅使用常量空间。
代码实现
class Solution {
public:
string reformat(string s) {
// 统计数字和字母的个数
int sum_digit = 0, sum_alpha = 0;
for(auto &c : s){
if(isdigit(c)) sum_digit++;
else sum_alpha++;
}
// 当个数差大于 1 时无法构造
if(abs(sum_digit - sum_alpha) > 1) return "";
bool f = sum_digit > sum_alpha;
int n = s.size();
for(int i = 0, j = 1; i < n; i += 2){
// 注意判断语句的难点，和 f 有关
if(isdigit(s[i]) != f){
while(isdigit(s[j]) != f) j += 2;
swap(s[i], s[j]);
}
}
return s;
}
};
总结
- 该题为简单的字符串题目，需要注意的是代码实现过程中的判断语句部分，
isdigit(s[i]) != f这样一句判断语句即可涵括两种情况的判断，且判断语句需要根据f的定义来写。 - 另外就是双指针的思想，巧妙利用双指针实现字符串的原地构造。
- 测试结果：
以上就是C C++ 题解LeetCode1417重新格式化字符串的详细内容，更多关于C C++ 重新格式化字符串的资料请关注自由互联其它相关文章！