文章目录
题目描述与示例
题目描述
给定一个字符串的摘要算法，请输出给定字符串的摘要值
- 去除字符串中非字母的符号
- 对于去除非字母符号后的字符串：
- 如果出现连续字符（不区分大小写），则输出: 该字母（小写) + 连续出现的次数
- 如果是非连续的字符（不区分大小写），则输出: 该字母（小写）之后字符串中出现的该字符的次数
- 对按照以上方式表示后的字符串进行排序：字母和紧随的数字作为一组进行排序，数字大的在前，数字相同的则按字母进行排序，字母小的在前。
输入描述
一行字符串，长度为[1,200]
输出描述
转换后的摘要字符串
示例一
输入
aabbcc
输出
a2b2c2
说明
示例二
输入
bAaAcBb
输出
a3b2b2c0
说明
第一个b非连续字母，该字母之后字符串中还出现了2次 (最后的两个Bb) ，所以输出b2；
a连续出现3次，输出a3；
c非连续，该字母之后字符串再没有出现过c，输出c0；
Bb连续2次，输出b2。
对b2a3c0b2进行排序，最终输出a3b2b2c0。
解题思路
去除非字母字符的操作非常简单，使用以下代码即可完成。
s = "".join(ch for ch in s if ch.isalpha())
每一个字符都会被摘要为字母+数字的形式。对于每一个字符ch，分为两种情况，若
ch属于连续字母，那么后面的数字应该是本段连续字母的个数ch属于非连续字母，那么后面的数字应该是该ch右边的相同字母的个数
对于第一点，统计某一段连续字母的个数，可以用滑动窗口来解决这个问题。
对于第二点，储存每一个字符ch右边的相同字母的个数，很容想到用哈希表来储存元素个数，但需要从右往左遍历字符串s。
正因为上述问题的存在，所以滑动窗口的过程不再是常规的right右移再动left右移，而是先令left左移再令right左移，即构建一个从右往左进行的滑动窗口。
滑窗三问
**Q1：**对于每一个左指针left所指的元素ch，做什么操作？
**Q2：**右指针right移动到什么位置？
**Q3：**如何进行答案的更新？
滑窗三答
**A1：**将其与右指针right所指的元素s[right]进行比较
**A2：**右指针right移动到当前左指针left的位置，用于后续的继续判断
**A3：**右指针right所指字母和左指针letf所指字母不相同时，更新答案
代码
Python
# 题目：2023B-字符串摘要
# 分值：200
# 作者：许老师-闭着眼睛学数理化
# 算法：滑动窗口
# 代码看不懂的地方，请直接在群上提问
# 用于更新答案的函数
def update(ans, dic, left, right, ch_right):
# 当前窗口本段连续的ch的个数为right-left
numContinue = right - left
# 如果数量为1，说明本段窗口其实是非连续字母
if numContinue == 1:
# 储存该字符，以及该字符右边的相同字符的个数，储存在dic[ch_right]中
ans.append((ch_right, dic[ch_right]))
# 如果数量不为1，说明本段窗口是连续字母
else:
# 储存该字符，以及该字符连续出现的次数即numContinue
ans.append((ch_right, numContinue))
# 将ch_right出现的次数更新在dic中，用于后续的继续判断
dic[ch_right] += numContinue
from collections import defaultdict
# 输入字符串
s = input()
# 去除非字母字符
s = "".join(ch for ch in s if ch.isalpha())
n = len(s)
# 初始化答案列表
ans = list()
# 初始化哈希表，用于记录一个字符ch右边，出现的相同字符的个数
dic = defaultdict(int)
# 初始化右指针
right = n-1
# 不同于传统的滑窗，要考虑一个从右往左滑动的滑动窗口
for left in range(n-1, -1, -1):
# Q1：对于每一个左指针left所指的元素ch，做什么操作？
# A1：将其与右指针right所指的元素s[right]进行比较
ch = s[left].lower()
ch_right = s[right].lower()
# 如果两者是同一个字母（不区分大小写），
# 说明当前窗口是一段连续的相同字符，则继续循环
# 否则，需要进行right的左移和ans的修改
if ch != ch_right:
# Q3：如何进行答案的更新
# A3：右指针right所指字母和左指针letf所指字母不相同时
update(ans, dic, left, right, ch_right)
# Q2：右指针移动到什么位置？
# A2：右指针right移动到当前左指针left的位置，用于后续的继续判断
right = left
# A3：退出循环后，还需要最后再做一次答案的更新
# 因为最左边的相同连续字符串实际上并没有在上述循环中被考虑到
# 需要取left = -1，right-left才能得到符合要求的连续字母长度
update(ans, dic, -1, right, s[right].lower())
# 退出循环，需要对ans中的元组进行排序
# 先按照数字降序排序，再按照字典序排序
ans.sort(key = lambda x: (-x[1], x[0]))
# 将ans中的二元组转为字符串，合并后输出
print("".join(item[0]+str(item[1]) for item in ans))
Java
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
String input = scanner.nextLine();
String s = input.replaceAll("[^a-zA-Z]", "");
int n = s.length();
List<Map.Entry<Character, Integer>> ans = new ArrayList<>();
Map<Character, Integer> dic = new HashMap<>();
int right = n - 1;
for (int left = n - 1; left >= 0; left--) {
char ch = Character.toLowerCase(s.charAt(left));
char chRight = Character.toLowerCase(s.charAt(right));
if (ch != chRight) {
update(ans, dic, left, right, chRight);
right = left;
}
}
update(ans, dic, -1, right, Character.toLowerCase(s.charAt(right)));
ans.sort((a, b) -> {
if (!a.getValue().equals(b.getValue())) {
return b.getValue() - a.getValue();
} else {
return a.getKey() - b.getKey();
}
});
StringBuilder result = new StringBuilder();
for (Map.Entry<Character, Integer> item : ans) {
result.append(item.getKey()).append(item.getValue());
}
System.out.println(result.toString());
}
public static void update(List<Map.Entry<Character, Integer>> ans, Map<Character, Integer> dic, int left, int right, char chRight) {
int numContinue = right - left;
if (numContinue == 1) {
ans.add(new AbstractMap.SimpleEntry<>(chRight, dic.getOrDefault(chRight, 0)));
} else {
ans.add(new AbstractMap.SimpleEntry<>(chRight, numContinue));
}
dic.put(chRight, dic.getOrDefault(chRight, 0) + numContinue);
}
}
C++
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;
void update(vector<pair<char, int>>& ans, map<char, int>& dic, int left, int right, char chRight) {
int numContinue = right - left;
if (numContinue == 1) {
ans.push_back(make_pair(chRight, dic[chRight]));
} else {
ans.push_back(make_pair(chRight, numContinue));
}
dic[chRight] += numContinue;
}
int main() {
string input;
getline(cin, input);
string s;
for (char ch : input) {
if (isalpha(ch)) {
s += tolower(ch);
}
}
int n = s.length();
vector<pair<char, int>> ans;
map<char, int> dic;
int right = n - 1;
for (int left = n - 1; left >= 0; left--) {
char ch = tolower(s[left]);
char chRight = tolower(s[right]);
if (ch != chRight) {
update(ans, dic, left, right, chRight);
right = left;
}
}
update(ans, dic, -1, right, tolower(s[right]));
sort(ans.begin(), ans.end(), [](pair<char, int>& a, pair<char, int>& b) {
if (a.second != b.second) {
return b.second < a.second;
} else {
return a.first < b.first;
}
});
string result;
for (pair<char, int>& item : ans) {
result += item.first + to_string(item.second);
}
cout << result << endl;
return 0;
}
时空复杂度
时间复杂度：O(N)。仅需逆序遍历一次字符串s
空间复杂度：O(N)。
