16

我正在尝试编写一个简单的python算法来解决这个问题。你能帮我弄清楚为什么我的代码不起作用：

问题：

如果任何字符重复超过 4 次，则应将整个重复字符集替换为斜杠“/”，后跟一个 2 位数字，该数字是该重复字符的长度，以及该字符。例如，“aaaaa”将被编码为“/05a”。不应替换 4 个或更少字符的运行，因为执行编码不会减少字符串的长度。

我的代码：

def runLengthEncode (plainText):
    res=''
    a=''
    for i in plainText:
        if a.count(i)>0:
            a+=i
        else:
            if len(a)>4:
                res+="/" + str(len(a)) + a[0][:1]
            else:
                res+=a
                a=i
    return(res)
4

10 回答 10

7

我在这里看到了很多很棒的解决方案，但没有一个让我觉得很蟒蛇。所以我正在为我今天为这个问题编写的一个实现做出贡献。

def run_length_encode(data: str) -> Iterator[Tuple[str, int]]:
    """Returns run length encoded Tuples for string"""
    # A memory efficient (lazy) and pythonic solution using generators
    return ((x, sum(1 for _ in y)) for x, y in groupby(data))

这将返回具有字符和实例数量的元组生成器，但也可以轻松修改为返回字符串。这样做的一个好处是它都是惰性评估的，如果您不需要耗尽整个搜索空间，它不会消耗比需要更多的内存或 CPU。

如果您仍然想要字符串编码，则可以很容易地针对该用例修改代码，如下所示：

def run_length_encode(data: str) -> str:
    """Returns run length encoded string for data"""
    # A memory efficient (lazy) and pythonic solution using generators
    return "".join(f"{x}{sum(1 for _ in y)}" for x, y in groupby(data))

这是一种更通用的运行长度编码，适用于所有长度，而不仅仅是超过 4 个字符的编码。但是，如果需要，这也可以很容易地与字符串的条件相适应。

于 2019-12-04T19:02:13.283 回答
6

Rosetta Code 有很多实现，应该很容易适应您的用例。

这是带有正则表达式的 Python 代码：

from re import sub

def encode(text):
    '''
    Doctest:
        >>> encode('WWWWWWWWWWWWBWWWWWWWWWWWWBBBWWWWWWWWWWWWWWWWWWWWWWWWBWWWWWWWWWWWWWW')
        '12W1B12W3B24W1B14W'    
    '''
    return sub(r'(.)\1*', lambda m: str(len(m.group(0))) + m.group(1),
               text)

def decode(text):
    '''
    Doctest:
        >>> decode('12W1B12W3B24W1B14W')
        'WWWWWWWWWWWWBWWWWWWWWWWWWBBBWWWWWWWWWWWWWWWWWWWWWWWWBWWWWWWWWWWWWWW'
    '''
    return sub(r'(\d+)(\D)', lambda m: m.group(2) * int(m.group(1)),
               text)

textin = "WWWWWWWWWWWWBWWWWWWWWWWWWBBBWWWWWWWWWWWWWWWWWWWWWWWWBWWWWWWWWWWWWWW"
assert decode(encode(textin)) == textin
于 2014-02-04T21:19:30.180 回答
5

除了a=i在对序列进行编码后设置并在打印到字符串时为 int 设置宽度。您还可以利用 pythons 执行以下操作groupby。format在构造字符串时使用它也是一个好主意。

from itertools import groupby

def runLengthEncode (plainText):
    res = []

    for k,i in groupby(plainText):
        run = list(i)
        if(len(run) > 4):
            res.append("/{:02}{}".format(len(run), k))
        else:
            res.extend(run)

    return "".join(res)
于 2013-09-22T20:36:37.310 回答
2

只需观察行为：

>>> runLengthEncode("abcd")
'abc'

最后一个字符被忽略。您必须附加您收集的内容。

>>> runLengthEncode("abbbbbcd")
'a/5b/5b'

糟糕，编码后出现问题。a=i即使找到足够长的序列，也应该设置。

于 2013-09-22T20:30:30.787 回答
1

您可以将groupby()函数与列表/生成器理解结合使用：

from itertools import groupby, imap

''.join(x if reps <= 4 else "/%02d%s" % (reps, x) for x, reps in imap(lambda x: (x[0], len(list(x[1]))), groupby(s)))
于 2013-09-22T21:18:22.840 回答
1 
def RLE_comp_encode(text):
    if text == text[0]*len(text) :
        return str(len(text))+text[0]
    else:
        comp_text , r = '' , 1
        for i in range (1,len(text)):
            if text[i]==text[i-1]:
                r +=1
                if i == len(text)-1:
                    comp_text += str(r)+text[i]
            else :
                comp_text += str(r)+text[i-1]
                r = 1
    return comp_text

这对我有用，

于 2019-03-16T12:01:55.307 回答
1 
Split=(list(input("Enter string: ")))
Split.append("")
a = 0
for i in range(len(Split)):
    try:
        if (Split[i] in Split) >0:
            a = a + 1
        if Split[i] != Split[i+1]:
            print(Split[i],a)
            a = 0
    except IndexError:
        print()

这更容易并且每次都有效

于 2019-01-24T17:20:04.007 回答
0

我知道这不是最有效的解决方案，但我们还没有研究过这样的函数，groupby()所以这就是我所做的：

def runLengthEncode (plainText):
    res=''
    a=''
    count = 0
    for i in plainText:
        count+=1
        if a.count(i)>0:
            a+=i
        else:
            if len(a)>4:
                if len(a)<10:
                    res+="/0"+str(len(a))+a[0][:1]
                else:
                    res+="/" + str(len(a)) + a[0][:1]
                a=i
            else:
                res+=a
                a=i
        if count == len(plainText):
            if len(a)>4:
                if len(a)<10:
                    res+="/0"+str(len(a))+a[0][:1]
                else:
                    res+="/" + str(len(a)) + a[0][:1]
            else:
                res+=a
    return(res)
于 2013-09-23T01:13:56.593 回答
0 
text=input("Please enter the string to encode")
encoded=[]
index=0
amount=1
while index<=(len(text)-1):  
  if index==(len(text)-1) or text[index]!=text[(index+1)]:
    encoded.append((text[index],amount))        
    amount=1
  else:
    amount=amount+1            
  index=index+1   
print(encoded)
于 2018-11-24T20:45:28.940 回答
-1

我能想到的运行长度编码的简单解决方案：

对于像这样的字符串编码"a4b5c6d7..."：

def encode(s):
    counts = {}
    for c in s:
        if counts.get(c) is None:
            counts[c] = s.count(c)
    return "".join(k+str(v) for k,v in counts.items())

用于解码类似的字符串"aaaaaabbbdddddccccc...."：

def decode(s):
    return "".join((map(lambda tup:  tup[0] * int(tup[1]), zip(s[0:len(s):2], s[1:len(s):2]))))

相当容易阅读和简单。

于 2018-11-02T18:22:27.490 回答