594.最長調和サブシーケンス(Python)
946 ワード
タイトル
難易度:★☆☆☆タイプ:配列
調和配列とは、1つの配列の要素の最大値と最小値の差がちょうど1であることを意味します.
整数配列を指定すると、可能なすべてのサブシーケンスの中で最も長い調和のとれたサブシーケンスの長さを見つける必要があります.
例
入力:[1,3,2,2,2,5,2,3,7]出力:5原因:最も長い調和配列は[3,2,2,2,3]である.説明:入力配列の長さは最大20000を超えない.
に答える
この問題には,配列中の要素の前後順序を考慮する必要がなく,解析プロセスを大幅に簡素化し,配列を集合処理と見なすことができるという利点がある.
配列内の各要素の出現回数を統計し、辞書に保存し、辞書内の各レコードについて、ある要素num+1が辞書に現れるかどうかを確認し、辞書にも現れるとnumとnum+1は調和のとれた配列を構成し、すべての調和のとれた配列の長さの最大値を計算することができる.
ここではpythonのCounter関数を用いて要素の高速統計を行う.
質問やアドバイスがあれば、コメントエリアへようこそ~
難易度:★☆☆☆タイプ:配列
調和配列とは、1つの配列の要素の最大値と最小値の差がちょうど1であることを意味します.
整数配列を指定すると、可能なすべてのサブシーケンスの中で最も長い調和のとれたサブシーケンスの長さを見つける必要があります.
例
入力:[1,3,2,2,2,5,2,3,7]出力:5原因:最も長い調和配列は[3,2,2,2,3]である.説明:入力配列の長さは最大20000を超えない.
に答える
この問題には,配列中の要素の前後順序を考慮する必要がなく,解析プロセスを大幅に簡素化し,配列を集合処理と見なすことができるという利点がある.
配列内の各要素の出現回数を統計し、辞書に保存し、辞書内の各レコードについて、ある要素num+1が辞書に現れるかどうかを確認し、辞書にも現れるとnumとnum+1は調和のとれた配列を構成し、すべての調和のとれた配列の長さの最大値を計算することができる.
ここではpythonのCounter関数を用いて要素の高速統計を行う.
class Solution:
def findLHS(self, nums):
num_count, res = Counter(nums), 0 # ,
for num, count in num_count.items(): # -
if num+1 in num_count.keys(): # +1
res = max(num_count[num]+num_count[num+1], res) #
return res
質問やアドバイスがあれば、コメントエリアへようこそ~