论坛 › Python交流 › Python：每日一题 380

zltzlt 发表于 2020-4-19 20:13:49

Python：每日一题 380

本帖最后由 zltzlt 于 2020-4-19 20:37 编辑

今天的题目：

给定一个经过编码的字符串，返回它解码后的字符串。

编码规则为：k，表示其中方括号内部的 encoded_string 正好重复 k 次。其中 k 为正整数。

说明：输入字符串中没有额外的空格。

注意：原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2 的输入。

示例 1：

输入：s = "32"
输出："aaabcbc"
示例 2：

输入：s = "3]"
输出："accaccacc"
示例 3：

输入：s = "23ef"
输出："abcabccdcdcdef"

{:10_298:}欢迎大家一起答题！{:10_298:}

March2615 发表于 2020-4-19 20:36:10

本帖最后由 March2615 于 2020-4-19 21:02 编辑

def daily380(s: str) -> str:
    # 解题思路：
    # 从左到右遍历找第一个]，找到一个就和前一个[对应，并将其展开，返回新字符串
    # 展开时需要注意数字的完整取值
    while ']' in s:
      n_index = 0
      r_index = s.index(']')
      l_index = s[:r_index].rfind('[')
      for i in range(l_index-1, -1, -1):
            if not s.isdigit():
                n_index = i + 1
                break
      s = s[:n_index] + s * int(s) + s
    return s

没有验证输入有误的情况
可以改进的地方
1. 验证输入（因为没说输入有误怎么办就没去考虑）
2. 数字提取，可以想想有没有其他方法


至于输入的合理性，在leetcode做过合法的括号，可以用栈

_2_ 发表于 2020-4-19 20:44:09

占楼

永恒的蓝色梦想 发表于 2020-4-19 20:46:49

占楼

永恒的蓝色梦想 发表于 2020-4-19 20:47:38

盲猜这道题用栈{:10_279:}

kinkon 发表于 2020-4-19 20:52:22

本帖最后由 kinkon 于 2020-4-20 11:16 编辑

模拟法
def f380(s):
    res = ''
    for i in range(len(s)):
      if s.isdigit():
            res += '+' + s + '*'
      elif s == '[':
            res += '('
      elif s == ']':
            res += ')'
      else:
            res += '+1*%s' %repr(s)
    return eval(res)

塔利班 发表于 2020-4-19 21:22:20

本帖最后由 塔利班 于 2020-4-20 15:40 编辑

def f380(s):
    res,l,count='',[],0
    for e in s:
      if e.isdigit():
            count=10*count+int(e)
      elif e=="[":
            l.append((res,count))
            res,count='',0
      elif e!="]":
            res+=e
      elif e==']':
            inner,innercount=l.pop()
            res =inner +innercount*res
    return res

永恒的蓝色梦想 发表于 2020-4-19 22:07:33

塔利班 发表于 2020-4-19 21:22


第二种方法也太秀了吧……

fan1993423 发表于 2020-4-19 22:12:14

本帖最后由 fan1993423 于 2020-4-19 22:21 编辑

import re
def fun380(s):
    try:
      d=re.search('\d+',s).group()
      while len(d):
            a,b=re.search('(\d+)\[(+)\]',s).groups()
            s=s.replace(a+'['+b+']',int(a)*b)
    except:
      return s

TJBEST 发表于 2020-4-19 22:33:55

本帖最后由 TJBEST 于 2020-4-20 21:54 编辑

递归函数做的我想应该不超时
def fun380(s):
    result = ''
    state = 0#[的个数
    repeat = ''#存储个数
    inner = ''#存储内部内容
    for each in s:
      if each.isdigit():
            if state == 0:
                repeat += each
            else:
                inner += each
      elif each == '[':
            if state == 0:
                state = 1
            else:
                inner += '['
                state += 1
      elif each == ']':
            if state == 1:
                state = 0
                result += fun380(inner) * (int(repeat))
                inner= ''
                repeat = ''
            else:
                inner += ']'
                state -= 1
      else:
            if state == 0:
                result += each
            else:
                inner += each
    return result

Python3005 发表于 2020-4-20 01:26:27

本帖最后由 Python3005 于 2020-4-20 01:33 编辑

import re

def fun(s):
        result = re.search('(\D*)(\d*)\[(.*)\]', s)
        w, n, m = result.groups()
        while '[' in m:
                m = fun(m)
        return w + m*int(n)

sjtuszy 发表于 2020-4-20 01:45:40

本帖最后由 sjtuszy 于 2020-4-20 16:14 编辑

def fun380(s):
    a = ''
    for i in range(len(s)):
      if s == '[':
            a += '*('
      elif s == ']':
            a += ')'
      elif s.isalpha():
            a += '+ 1 * %s' %repr(s)
      elif s.isdigit():
            if s.isdigit():
                a += '%s' %s
            else:
                a += '+%s' %s
    if a == '':
      return a
    return eval(a)

道晓镖 发表于 2020-4-20 02:33:32

虽然现在看不懂，但是以后肯定能看懂

kkk999de 发表于 2020-4-20 09:55:19

本帖最后由 kkk999de 于 2020-4-20 10:11 编辑

def f380(s):
    a,b = s.find('['),s.find(']')
    s = s[:a-1]+s*int(s)+s
    if s.find('[') != -1:
      s = f380(s)
    return s

风魔孤行者 发表于 2020-4-20 11:04:48

import re
def f(s):
    def f1(s):
      num = re.search(r'\d+',s)
      string = re.search(r'+',s)
      return int(num.group())*string.group()
    while s.find('[') != -1:
            code = re.search(r'\d+?\[+\]',s)
            s = s.replace(code.group(),f1(code.group()))
    return s

旅途Z 发表于 2020-4-20 11:45:48

# 找到所有的方括号，依次进行解码
def decode(encoding_str):
    def repeat(string, num):
      str1 = ""
      for i in range(num):
            str1 += string
      return str1
    left_index = encoding_str.find('[')
    while left_index != -1:
      right_index = encoding_str.find(']')
      reused_str = repeat(encoding_str, int(encoding_str))
      encoding_str = encoding_str.replace(encoding_str, reused_str)
      left_index = encoding_str.find('[')
    return encoding_str

ouyunfu 发表于 2020-4-20 13:08:12

import re
def f380(s):
    while re.search('(\d+)\[(+)\]',s):
      x,y=re.search('(\d+)\[(+)\]',s).groups()
      s=s.replace(x+'['+y+']',int(x)*y)
    return s

zltzlt 发表于 2020-4-20 13:32:26

March2615 发表于 2020-4-19 20:36
没有验证输入有误的情况
可以改进的地方
1. 验证输入（因为没说输入有误怎么办就没去考虑）


750 ms

zltzlt 发表于 2020-4-20 13:33:24

kinkon 发表于 2020-4-19 20:52
模拟法

输入空字符串出错

zltzlt 发表于 2020-4-20 13:34:17

塔利班 发表于 2020-4-19 21:22


第一种方法输入示例 2 中的数据结果有误

查看完整版本: Python：每日一题 380