數據結構3.3

Problem: Compress a string such that AAABCCDDDD becomes A3BC2D4. Only compress the string if it saves space.

測試用例：

assert_equal(func(None), None)

assert_equal(func(), )

assert_equal(func(ABC), ABC)

assert_equal(func(AABBCC), AABBCC)

assert_equal(func(AAABCCDDDDE), A3BC2D4E)

assert_equal(func(BAAACCDDDD), BA3C2D4)

assert_equal(func(AAABAACCDDDD), A3BA2C2D4)

from collections import Counterfrom collections import defaultdictclass CompressString(object): def compress(self, string): #我一開始的解法是對所有的字元進行統計，與答案不符# if string==None:# return None# if string==:# return # word=[x for x in string]# word_cnt=Counter(word)# a=word_cnt.most_common() # if a[0][1]<=2:# return string# else:# addr_to = list(set(word))# addr_to.sort(key=word.index)# print(addr_to)# str1=# for w in addr_to:# str1+=w# if word_cnt[w]==1:# str1+=# else:# str1+=str(word_cnt[w])# return str1 #正確的方法 if string==None or type(string)!=str: return string if string==: return st=[] st_num=[] prev_st=string[0] cnt=1 for ss in string[1:]: if prev_st!=ss: st_num.append(cnt) st.append(prev_st) cnt=1 prev_st=ss else: cnt+=1 prev_st=ss st_num.append(cnt) st.append(prev_st) if len(st_num)+len(st)>len(string) or max(st_num)==2: return string else: ss= for i in zip(st,st_num): ss+=i[0] if i[1]>1: ss+=str(i[1]) else: ss+= return ss

Problem: Implement a function to reverse a string (a list of characters), in-place.

def reverse(self, chars): # TODO: Implement me if chars: return chars[::-1] else: return chars

推薦閱讀：