Leetcode 038報数構想詳細python実現
2251 ワード
私はずっとLeetcodeの上でPythonで実現した問題を蓄積して、しかも全力を尽くしてすべての問題の原理をはっきり言って、決して他のいくつかのブログのように簡単に持っていません.はっきり言っていると思ったら、注目してください.
報数シーケンスとは、1つの整数シーケンスを指し、その中の整数の順序で報数を行い、次の数を得る.最初の5つは次のとおりです.
正の整数nが与えられ、報数シーケンスのn番目の項が出力される.
注:整数の順序は文字列として表示されます.
例1:
例2:
まずテーマを説明する.どうしてこの問題は簡単だが、評価が悪いのか.問題は問題をはっきり説明していないことだと思います.
1読one
11 oneone oneを読まずにtwo oneを読むと、同じ数につながっているので、まず数を言ってから値をつけます.
以上が基礎です.次の結果をどうやって得るか見てみましょう.タイトルから与えられた例4:1211から5:111221まで.1211位は1なので、one、つまり1 1と読みます.2 onetwoと読みますので12です.11続けてtwo oneと読みますので21です.このすべてを合わせると答え111221です.
考え方:新聞数の特徴に基づいて、前の結果に基づいて次の項目を導くことができます.前の項目を巡り、カウント変数を補助していくつかの数字が現れた回数を統計します.同時に、前の項目を保存し続けなければなりません.
難点:問題の意味を理解し、次の項目がどのように発生したのかを知って、forサイクルのたびに今回の結果を保存して次の計算に敷き詰める必要があります.
報数シーケンスとは、1つの整数シーケンスを指し、その中の整数の順序で報数を行い、次の数を得る.最初の5つは次のとおりです.
1. 1
2. 11
3. 21
4. 1211
5. 111221
1
は、"one 1"
(" "
)、すなわち11
と読まれる.11
は、"two 1s"
(" "
)、すなわち21
と読まれる.21
は、"one 2"
、「one 1"
(" "
、" "
)、すなわち1211
と読まれる.正の整数nが与えられ、報数シーケンスのn番目の項が出力される.
注:整数の順序は文字列として表示されます.
例1:
: 1
: "1"
例2:
: 4
: "1211"
まずテーマを説明する.どうしてこの問題は簡単だが、評価が悪いのか.問題は問題をはっきり説明していないことだと思います.
1読one
11 oneone oneを読まずにtwo oneを読むと、同じ数につながっているので、まず数を言ってから値をつけます.
以上が基礎です.次の結果をどうやって得るか見てみましょう.タイトルから与えられた例4:1211から5:111221まで.1211位は1なので、one、つまり1 1と読みます.2 onetwoと読みますので12です.11続けてtwo oneと読みますので21です.このすべてを合わせると答え111221です.
考え方:新聞数の特徴に基づいて、前の結果に基づいて次の項目を導くことができます.前の項目を巡り、カウント変数を補助していくつかの数字が現れた回数を統計します.同時に、前の項目を保存し続けなければなりません.
class Solution:
def countAndSay(self, n):
"""
:type n: int
:rtype: str
"""
if n==1:# ,
return '1'
if n==2:
return '11'
# i=3 , '11'
pre='11'
# for
for i in range(3,n+1):
res=''# ,
cnt=1#
length=len(pre)# ,
for j in range(1,length):
if pre[j-1]==pre[j]:#
cnt+=1
else:
# ,
res+=str(cnt)+pre[j-1]
cnt=1# 1
#
res+=str(cnt)+pre[j]
pre=res#
return res
難点:問題の意味を理解し、次の項目がどのように発生したのかを知って、forサイクルのたびに今回の結果を保存して次の計算に敷き詰める必要があります.