题目要求：
实现一个字符串摘要算法，输出给定字符串的摘要值。
步骤：
1. 去除字符串中非字母的符号。
2. 如果出现连续字符（不区分大小写），则输出：该字符（小写）+ 连续出现的次数。
3. 如果是非连续的字符（不区分大小写），则输出：该字符（小写）+ 该字母之后字符串中出现的该字符的次数。
4. 对按照以上方式表示后的字符串进行排序：字母和紧随的数字作为一组进行排序，数字大的在前，数字相同的则按字母进行排序，字母小的在前。
输入描述：
一行字符串，长度为 [1, 200]。
输出描述：摘要字符串。
• 示例1：
◦ 输入：aabbcc
◦ 输出：a2b2c2
• 示例2：
◦ 输入：bAaAcBb
◦ 输出：a3b2b2c0
说明：第一个b非连续，输出b2（因为后面有2个b）；a连续出现3次，输出a3；c非连续，后面没有c，输出c0；Bb连续2次，输出b2。然后排序：a3, b2, b2, c0 → 输出a3b2b2c0。
"""
1.
输入：aabbcc
输出：a2b2c2
2.
输入：bAaAcBb
输出：a3b2b2c0
"""
def get_digest(s):
s = ''.join(c for c in s if c.isalpha())
if not s:
return
result = []
length = 0
i = 0
while i<len(s):
current = s[i].lower()
if i == 0 or s[i-1]!=s[i]: # 判断是否是起始字符
j = i
"""
如果是连续字符，则计算连续字符的长度
"""
while j< len(s) and s[j].lower()==current:
j += 1
length = j-i
if length > 1:
result.append(current + str(length))
i = j
continue
else:
"""
若非连续字符
"""
counts = s[i+1:].lower().count(current)
result.append(current + str(counts))
i+=1
result.sort(key=lambda x :(-int(x[1:]),x[0]))
return ''.join(result)
if __name__ == '__main__':
print(get_digest('bAaAcBb'))算法逻辑总结
核心思想
混合统计策略：根据字符的连续性采用不同的统计方法，兼顾效率和准确性。
算法流程图
输入字符串
↓
过滤非字母字符
↓
遍历每个字符位置
↓
判断是否为新字符开始
↓
是 → 检查连续性 → 连续 → 统计连续长度 → 添加到结果 → 跳过连续块
↓ ↘
否 不连续 → 统计后续出现次数 → 添加到结果
↓
继续下一个位置
↓
按规则排序输出
字符串知识点和考点扩展
一、基础操作考点
1. 字符串创建与基本操作
# 创建方式
s1 = "hello"
s2 = str(123)
s3 = """多行
字符串"""
s4 = ''.join(['a', 'b', 'c']) # 高效拼接
# 基本操作
len(s) # 长度
s[i] # 索引
s[i:j] # 切片
s1 + s2 # 拼接
s * 3 # 重复2. 常用方法考点
# 查找类
s.find(sub) # 返回索引，找不到返回-1
s.index(sub) # 返回索引，找不到报错
s.count(sub) # 统计出现次数
# 判断类
s.startswith(prefix)
s.endswith(suffix)
s.isalpha() # 是否全字母
s.isdigit() # 是否全数字
s.isalnum() # 是否字母或数字
# 变换类
s.lower() # 小写
s.upper() # 大写
s.strip() # 去除两端空白
s.replace(old, new)
s.split(sep) # 分割二、核心算法考点
1. 字符串反转
# 多种反转方法
def reverse_string(s):
return s[::-1] # 切片法
def reverse_string2(s):
return ''.join(reversed(s)) # 内置函数
def reverse_string3(s):
result = []
for i in range(len(s)-1, -1, -1):
result.append(s[i])
return ''.join(result) # 循环法2. 字符统计与频率分析
from collections import Counter, defaultdict
# 方法1：使用Counter
def char_frequency(s):
return Counter(s)
# 方法2：使用字典
def char_frequency2(s):
freq = {}
for char in s:
freq[char] = freq.get(char, 0) + 1
return freq
# 方法3：使用数组（针对小写字母）
def char_frequency3(s):
freq = [0] * 26
for char in s:
if 'a' <= char <= 'z':
freq[ord(char) - ord('a')] += 1
return freq3. 字符串匹配算法
# 1. 朴素匹配算法 O(m*n)
def naive_search(text, pattern):
n, m = len(text), len(pattern)
for i in range(n - m + 1):
if text[i:i+m] == pattern:
return i
return -1
# 2. KMP算法 O(m+n)
def kmp_search(text, pattern):
# 构建部分匹配表
def build_lps(pattern):
lps = [0] * len(pattern)
length = 0
i = 1
while i < len(pattern):
if pattern[i] == pattern[length]:
length += 1
lps[i] = length
i += 1
else:
if length != 0:
length = lps[length-1]
else:
lps[i] = 0
i += 1
return lps
lps = build_lps(pattern)
i = j = 0
while i < len(text):
if pattern[j] == text[i]:
i += 1
j += 1
if j == len(pattern):
return i - j
elif i < len(text) and pattern[j] != text[i]:
if j != 0:
j = lps[j-1]
else:
i += 1
return -1三、高级字符串处理
1. 字符串编码与解码
# Base64编码解码
import base64
encoded = base64.b64encode(b"hello")
decoded = base64.b64decode(encoded)
# URL编码解码
from urllib.parse import quote, unquote
url_encoded = quote("hello world")
url_decoded = unquote(url_encoded)2. 正则表达式应用
import re
# 常用模式
pattern = r'\d+' # 匹配数字
pattern = r'[a-zA-Z]+' # 匹配单词
pattern = r'^[a-z0-9]+@[a-z0-9]+\.[a-z]+$' # 邮箱验证
# 常用方法
re.findall(pattern, text) # 查找所有匹配
re.search(pattern, text) # 搜索第一个匹配
re.sub(pattern, repl, text) # 替换
re.split(pattern, text) # 分割3. 字符串压缩算法
# 游程编码 (Run-Length Encoding)
def rle_encode(s):
if not s:
return ""
result = []
count = 1
for i in range(1, len(s)):
if s[i] == s[i-1]:
count += 1
else:
result.append(s[i-1] + str(count))
count = 1
result.append(s[-1] + str(count))
return ''.join(result)
def rle_decode(encoded):
result = []
i = 0
while i < len(encoded):
char = encoded[i]
i += 1
count_str = ""
while i < len(encoded) and encoded[i].isdigit():
count_str += encoded[i]
i += 1
count = int(count_str)
result.append(char * count)
return ''.join(result)四、常见面试题型
1. 验证类问题
验证回文字符串
验证括号有效性
验证IP地址格式
验证字符串是否为数字
2. 转换类问题
字符串到整数转换 (atoi)
数字到字符串转换
罗马数字与整数互转
ZigZag转换
3. 查找类问题
最长不含重复字符子串
最长回文子串
最小覆盖子串
字符串的排列组合
4. 操作类问题
字符串相乘
字符串相加
字符串分割
字符串替换
五、实战例题
例题1：最长不含重复字符子串
def length_of_longest_substring(s):
char_map = {}
left = max_length = 0
for right in range(len(s)):
if s[right] in char_map and char_map[s[right]] >= left:
left = char_map[s[right]] + 1
char_map[s[right]] = right
max_length = max(max_length, right - left + 1)
return max_length例题2：字符串相乘
def multiply_strings(num1, num2):
if num1 == "0" or num2 == "0":
return "0"
m, n = len(num1), len(num2)
result = [0] * (m + n)
for i in range(m-1, -1, -1):
for j in range(n-1, -1, -1):
mul = (ord(num1[i]) - ord('0')) * (ord(num2[j]) - ord('0'))
p1, p2 = i + j, i + j + 1
total = mul + result[p2]
result[p2] = total % 10
result[p1] += total // 10
# 转换为字符串
start = 0
while start < len(result) and result[start] == 0:
start += 1
return ''.join(str(x) for x in result[start:]) if start < len(result) else "0"六、性能优化要点
字符串拼接：使用
''.join()而非+字符查找：使用字典或集合进行O(1)查找
空间优化：对于固定字符集使用数组而非字典
算法选择：根据数据规模选择合适的匹配算法
这些知识点涵盖了字符串处理的核心内容，是算法面试中的高频考点。
·