东莞寮步网站建设网络公司,成都响应网站建设,阿里云建设网站的流程,平价网站建设文章目录 题目描述与示例题目描述输入描述输出描述示例一输入输出说明 示例二输入输出说明 解题思路滑窗三问滑窗三答 代码PythonJavaC时空复杂度 华为OD算法/大厂面试高频题算法练习冲刺训练 题目描述与示例
题目描述
给定一个字符串的摘要算法#xff0c;请输出给定字符串… 文章目录 题目描述与示例题目描述输入描述输出描述示例一输入输出说明 示例二输入输出说明 解题思路滑窗三问滑窗三答 代码PythonJavaC时空复杂度 华为OD算法/大厂面试高频题算法练习冲刺训练 题目描述与示例
题目描述
给定一个字符串的摘要算法请输出给定字符串的摘要值
去除字符串中非字母的符号对于去除非字母符号后的字符串 如果出现连续字符不区分大小写则输出: 该字母小写) 连续出现的次数如果是非连续的字符不区分大小写则输出: 该字母小写之后字符串中出现的该字符的次数 对按照以上方式表示后的字符串进行排序字母和紧随的数字作为一组进行排序数字大的在前数字相同的则按字母进行排序字母小的在前。
输入描述
一行字符串长度为[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-leftnumContinue right - left# 如果数量为1说明本段窗口其实是非连续字母if numContinue 1:# 储存该字符以及该字符右边的相同字符的个数储存在dic[ch_right]中ans.append((ch_right, dic[ch_right]))# 如果数量不为1说明本段窗口是连续字母else:# 储存该字符以及该字符连续出现的次数即numContinueans.append((ch_right, numContinue))# 将ch_right出现的次数更新在dic中用于后续的继续判断dic[ch_right] numContinuefrom 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 -1right-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();ListMap.EntryCharacter, Integer ans new ArrayList();MapCharacter, 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.EntryCharacter, Integer item : ans) {result.append(item.getKey()).append(item.getValue());}System.out.println(result.toString());}public static void update(ListMap.EntryCharacter, Integer ans, MapCharacter, 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(vectorpairchar, int ans, mapchar, 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();vectorpairchar, int ans;mapchar, 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(), [](pairchar, int a, pairchar, int b) {if (a.second ! b.second) {return b.second a.second;} else {return a.first b.first;}});string result;for (pairchar, int item : ans) {result item.first to_string(item.second);}cout result endl;return 0;
}时空复杂度
时间复杂度O(N)。仅需逆序遍历一次字符串s
空间复杂度O(N)。 华为OD算法/大厂面试高频题算法练习冲刺训练 华为OD算法/大厂面试高频题算法冲刺训练目前开始常态化报名目前已服务100同学成功上岸 课程讲师为全网50w粉丝编程博主吴师兄学算法 以及小红书头部编程博主闭着眼睛学数理化 每期人数维持在20人内保证能够最大限度地满足到每一个同学的需求达到和1v1同样的学习效果 60天陪伴式学习40直播课时300动画图解视频300LeetCode经典题200华为OD真题/大厂真题还有简历修改、模拟面试、专属HR对接将为你解锁 可上全网独家的欧弟OJ系统练习华子OD、大厂真题 可查看链接 大厂真题汇总 OD真题汇总(持续更新) 绿色聊天软件戳 od1336了解更多
