pythonブルーブリッジカップ深さ探索(DFS)を実現するBit Compressor
12653 ワード
pythonブルーブリッジカップ深さ探索(DFS)を実現するBit Compressor
問題の説明
問題の説明
データ圧縮の目的は、データの格納と交換時に発生する冗長性を低減することです.これにより、有効データの比重が増加し、伝送速度が向上する.連続するn個1をnに置換するバイナリ表現(注:置換が発生し、この置換がバイナリ列の全長を減少させた場合のみ)を圧縮する方法がある(訳者注:連続するn個1の左右は0または列の先頭、末尾でなければならない).例えば、11111111111001001111111111111110011は1000000101110011に圧縮される.原列長は32である、圧縮後の列長は17である.この方法の弊害は,解凍アルゴリズムが1つ以上の可能な原列を得る場合があり,原列が何であるかを決定できないことである.圧縮された情報を利用して元の列を特定できるかどうかを判定するプログラムを書いてください.原列長L,原列中の1の個数N,圧縮後の列を与える.L<=16 Kbytes、圧縮後のシリアル長<=40 bits.
入力フォーマット
第1行の2つの整数L,Nは、問題と同じ意味で第2行の1つのバイナリ列を記述し、圧縮後の列を表す.
出力フォーマット
出力「YES」または「NO」または「NOT UNIQUE」(引用符を含まない)は、それぞれYES:原列一意NO:原列は存在しないNOT UNIQUE:原列は存在するが一意ではない
サンプル入力
サンプル1:32 26 1000000101110011サンプル2:9 7 1010101サンプル3:14 111111
サンプル出力
サンプル1:YESサンプル2:NOT UNIQUEサンプル3:NO
テーマ解析
この問題は圧縮後のバイナリを復元し、復元後のバイナリ列が一意かどうかを確認し、一意であればYESを出力し、一意でなければNOT UNIQUEを出力し、存在しなければNOを出力することである.
構想
パラメータの説明
nowIndex:処理中の文字の下付き文字
getZero:現在取得されている0の数
getOne:取得した1の数
l:原列の長さ
l_one:原串1の個数
lzero:原列0の個数
answer:答えが一意かどうかをマーク
temptZero:一時変数
temptOne:一時変数
InitNum:最初のグループのパラメータを格納
InitString:圧縮されたパスをリスト形式で格納します.
まず、私たちはケース入力の最初のケースを分析して、この問題の最初の難点は、もし1つの後ろに多くの0がついていたら、私たちはどのように切断するかを判断できないと思います.そして、バイナリはどのように10進数に変換されますか.2つ目の難点は、状況を分けて議論することです.まず、この問題についてどのような条件で議論するかについてお話しします.
最初のケース
まず、元の1の長さをバイナリで表すので、ここで問題に直面します.まず、元が0110であれば、圧縮しなくてもいいです.圧縮後は0010という長さと元の長さに何の変化もないので、この変形は意味がありません.しかし、もし私たちの元のバイナリスライスが01110で0110に圧縮されたら、これも可能であるという状況もあります.だから、最初の状況はこの2つの現象を区別して、それぞれ討論することです.
2つ目のケース
つまり、もし010に出会ったら、私たちは圧縮する必要はありません.それを動かす必要もありません.確かに圧縮する必要はありませんから.
枝を切る
もちろん、時間の複雑さを減らすためには、枝を切る必要があります.
まず、私たちがアクセスしている現在の文字の下付き文字が境界を越えていれば、直接戻ることができます.
そして,answerの値が1より大きい場合,我々も直接戻り,これ以上議論する必要はない.
次に,我々が受信した0が元の0を超えていれば,議論する必要はない.
最後に、もし私たちが受け取った1も元の1を超えたら、私たちもこれ以上続ける必要はありません.
ベースライン条件
アクセスした下付き文字が圧縮後の長さに等しい場合、下付き文字は0から始めようとしたが、圧縮後の長さから1を減らすはずだったが、最後の再帰で下付き文字に1を加えるので、ちょうど元の長さに等しいことに注意してください.pythonでリストを初期化するのは面倒で、内部のコストが平坦なメモリ管理メカニズムのため、ここではリストを初期化してから、一つ一つ値を割り当てる必要はありません.リストの一番後ろに任意の整数を追加すればいいです.これはリストの下付きの境界を越えるのを防ぐためにエラーを報告します.
判定条件
我々が探した1および0の個数と原列が等しいと,この条件は一致すると考えられる.我々は順番に列挙しているので,我々が議論した状況も必ず原列の配列,あるいは別の展開方式である.個数は正確ではありませんが、配列が全く間違っている場合はありません.
バイナリ10進数の変換方法
私たちは左から右へ遍歴しているので、バイナリを10進数に変えるには、いくつかの変化が必要です.
この2行のコードはバイナリ10進法です.私たちは左から右に移動するので、移動するたびに10進数の値に2倍を乗じます.これが最初の行の意味です.また、00010010では意味がないので、私たちが移動するたびに必ず0011が左から右に移動したり、0111や1111が移動したりします.この場合、0010+1を与えて右に移動しなければなりません.これが2行目の大まかな意味です.だから2行目は後ろの0を加えるか、後ろの1を加えるかです.この処理方法はやはりすばらしい.
コード#コード#
ブログ参照 https://blog.csdn.net/weixin_43856851/article/details/104933960 https://blog.csdn.net/Raymond_YP/article/details/104450936 https://blog.csdn.net/yi_qing_z/article/details/88084875
問題の説明
問題の説明
データ圧縮の目的は、データの格納と交換時に発生する冗長性を低減することです.これにより、有効データの比重が増加し、伝送速度が向上する.連続するn個1をnに置換するバイナリ表現(注:置換が発生し、この置換がバイナリ列の全長を減少させた場合のみ)を圧縮する方法がある(訳者注:連続するn個1の左右は0または列の先頭、末尾でなければならない).例えば、11111111111001001111111111111110011は1000000101110011に圧縮される.原列長は32である、圧縮後の列長は17である.この方法の弊害は,解凍アルゴリズムが1つ以上の可能な原列を得る場合があり,原列が何であるかを決定できないことである.圧縮された情報を利用して元の列を特定できるかどうかを判定するプログラムを書いてください.原列長L,原列中の1の個数N,圧縮後の列を与える.L<=16 Kbytes、圧縮後のシリアル長<=40 bits.
入力フォーマット
第1行の2つの整数L,Nは、問題と同じ意味で第2行の1つのバイナリ列を記述し、圧縮後の列を表す.
出力フォーマット
出力「YES」または「NO」または「NOT UNIQUE」(引用符を含まない)は、それぞれYES:原列一意NO:原列は存在しないNOT UNIQUE:原列は存在するが一意ではない
サンプル入力
サンプル1:32 26 1000000101110011サンプル2:9 7 1010101サンプル3:14 111111
サンプル出力
サンプル1:YESサンプル2:NOT UNIQUEサンプル3:NO
テーマ解析
この問題は圧縮後のバイナリを復元し、復元後のバイナリ列が一意かどうかを確認し、一意であればYESを出力し、一意でなければNOT UNIQUEを出力し、存在しなければNOを出力することである.
構想
パラメータの説明
nowIndex:処理中の文字の下付き文字
getZero:現在取得されている0の数
getOne:取得した1の数
l:原列の長さ
l_one:原串1の個数
lzero:原列0の個数
answer:答えが一意かどうかをマーク
temptZero:一時変数
temptOne:一時変数
InitNum:最初のグループのパラメータを格納
InitString:圧縮されたパスをリスト形式で格納します.
まず、私たちはケース入力の最初のケースを分析して、この問題の最初の難点は、もし1つの後ろに多くの0がついていたら、私たちはどのように切断するかを判断できないと思います.そして、バイナリはどのように10進数に変換されますか.2つ目の難点は、状況を分けて議論することです.まず、この問題についてどのような条件で議論するかについてお話しします.
最初のケース
まず、元の1の長さをバイナリで表すので、ここで問題に直面します.まず、元が0110であれば、圧縮しなくてもいいです.圧縮後は0010という長さと元の長さに何の変化もないので、この変形は意味がありません.しかし、もし私たちの元のバイナリスライスが01110で0110に圧縮されたら、これも可能であるという状況もあります.だから、最初の状況はこの2つの現象を区別して、それぞれ討論することです.
2つ目のケース
つまり、もし010に出会ったら、私たちは圧縮する必要はありません.それを動かす必要もありません.確かに圧縮する必要はありませんから.
枝を切る
もちろん、時間の複雑さを減らすためには、枝を切る必要があります.
まず、私たちがアクセスしている現在の文字の下付き文字が境界を越えていれば、直接戻ることができます.
そして,answerの値が1より大きい場合,我々も直接戻り,これ以上議論する必要はない.
次に,我々が受信した0が元の0を超えていれば,議論する必要はない.
最後に、もし私たちが受け取った1も元の1を超えたら、私たちもこれ以上続ける必要はありません.
ベースライン条件
アクセスした下付き文字が圧縮後の長さに等しい場合、下付き文字は0から始めようとしたが、圧縮後の長さから1を減らすはずだったが、最後の再帰で下付き文字に1を加えるので、ちょうど元の長さに等しいことに注意してください.pythonでリストを初期化するのは面倒で、内部のコストが平坦なメモリ管理メカニズムのため、ここではリストを初期化してから、一つ一つ値を割り当てる必要はありません.リストの一番後ろに任意の整数を追加すればいいです.これはリストの下付きの境界を越えるのを防ぐためにエラーを報告します.
判定条件
我々が探した1および0の個数と原列が等しいと,この条件は一致すると考えられる.我々は順番に列挙しているので,我々が議論した状況も必ず原列の配列,あるいは別の展開方式である.個数は正確ではありませんが、配列が全く間違っている場合はありません.
バイナリ10進数の変換方法
私たちは左から右へ遍歴しているので、バイナリを10進数に変えるには、いくつかの変化が必要です.
temptOne = 2*temptOne
temptOne += int(initString[i])
この2行のコードはバイナリ10進法です.私たちは左から右に移動するので、移動するたびに10進数の値に2倍を乗じます.これが最初の行の意味です.また、00010010では意味がないので、私たちが移動するたびに必ず0011が左から右に移動したり、0111や1111が移動したりします.この場合、0010+1を与えて右に移動しなければなりません.これが2行目の大まかな意味です.だから2行目は後ろの0を加えるか、後ろの1を加えるかです.この処理方法はやはりすばらしい.
コード#コード#
def dfs(nowIndex,getZero,getOne):
"""
:param nowIndex:
:param getZero: 0
:param getOne: 1
:return: ，
"""
global l,lzero,l_one,answer #
''' '''
if answer > 1: return
if nowIndex > l: return
if getZero > lzero: return
if getOne > l_one : return
''' '''
if nowIndex == lcom:
if getZero == lzero and getOne == l_one:
answer += 1
return
''' '''
temptZero = getZero
while initString[nowIndex] == '0':
temptZero += 1
nowIndex += 1
temptOne = 0
for i in range(nowIndex,lcom):
temptOne = 2*temptOne
temptOne += int(initString[i])
# 0110
if temptOne == 2:
continue
if initString[i+1] == '1':
continue
next = i + 1
while initString[next]=='0':
next += 1
dfs(next,temptZero+next-i-1,getOne+temptOne)
if temptOne == 3:
dfs(next,temptZero+next-i-1,getOne+2)
if __name__ == '__main__':
# ， ， 1
initNum = input().split()
l = int(initNum[0])
l_one = int(initNum[1])
lzero = l-l_one
#
initString = list(input())
lcom = len(initString)
initString.append(5) # 17， 。
# : answer
answer = 0
dfs(0,0,0)
#
if answer == 1:
print("YES")
elif answer >=2:
print("NOT UNIQUE")
else:
print("NO")
ブログ参照