字符串解压缩问题——贪心算法
算法 字符串 贪心 解压缩 问题
2023-09-14 09:11:51 时间
import sys def load_data(): return sys.stdin.read() def get_position_map(s): result = {} stack = [] for i,c in enumerate(s): if c == "[": result[i] = -1 stack.append(i) elif c == "]": if stack: pos = stack.pop() result[pos] = i return result def decode_str(s, start, end, pos_map): def in_range(i, start, end): return start<=i<end def is_str(c): return ord('a')<=ord(c)<=ord('z') or ord('A')<=ord(c)<=ord('Z') def is_num(c): return ord('0') <= ord(c) <= ord('9') result = "" i = start while in_range(i, start, end): string = "" while in_range(i, start, end) and is_str(s[i]): string += s[i] i += 1 if not in_range(i, start, end): return string digit = "" while in_range(i, start, end) and is_num(s[i]): digit += s[i] i += 1 if not in_range(i, start, end): return string if pos_map[i] == -1: return string d_str = decode_str(s, i+1, pos_map[i], pos_map) result += string + d_str*int(digit) i = pos_map[i]+1 return result def main(): encoded_str = load_data() # "abc3[xyz4[mn]" # "abc3[xyz" # "abc2[xyz3[mn]]" #"aaabcbc" #"3[a]2[bc]" pos_map = get_position_map(encoded_str) decoded_str = decode_str(encoded_str, 0, len(encoded_str), pos_map) print(decoded_str) if __name__ == "__main__": main()
相关文章
- JS自己实现字符串加密和解密算法
- 字符串匹配算法BF、KCP
- Java实现 蓝桥杯 算法训练 字符串合并
- Java实现 蓝桥杯VIP 算法训练 删除多余括号
- Java实现 蓝桥杯VIP 算法训练 比较字符串
- Java实现 蓝桥杯VIP 算法训练 黑白无常
- Java实现 蓝桥杯VIP 算法训练 星际交流
- Java实现 蓝桥杯VIP 算法训练 FBI树
- Java实现 蓝桥杯VIP 算法训练 字符串逆序
- Java蓝桥杯 算法提高 九宫格
- 关于KMP算法理解(快速字符串匹配)
- 一步步教你轻松学支持向量机SVM算法之案例篇2
- Python排序算法之选择排序定义与用法示例
- Algorithm:C++语言实现之动态规划算法相关(矩阵连乘状态转移方程、字符串的交替连接、分析格网棋盘的特点、最短路线问题、生产计划问题、动态规划解下列非线性规划)
- DL之CNN:基于CRNN_OCR算法(keras,CNN+RNN)利用数据集(torch,mdb格式)训练来实现新图片上不定长度字符串进行识别—预测过程
- DL之R-CNN:R-CNN算法的简介(论文介绍)、架构详解、案例应用等配图集合之详细攻略
- 基于最小均数四分法 (LMF) 和最小均方 (LMS) 算法进行系统识别(Matlab代码实现)
- 智能优化算法:旗鱼优化算法-附代码
- BFGS算法
- 2405. 子字符串的最优划分-贪心算法
- 1763. 最长的美好子字符串-贪心算法
- 字符串匹配算法之 KMP 极简动画教程
- 一步一步写算法(之排序二叉树)
- 数据结构 算法 框架 面试题
- 字符串匹配的sunday算法
- 基于sklearn决策树算法对鸢尾花数据进行分类