解決:最長の調和したサブシーケンス
4098 ワード
これは一連のleetcode解決説明の一部です.あなたがこの解決法が好きであるか、それが役に立つとわかるならば、このポストと同様に/または上告my solution post on Leetcode's forumsをしてください.
Leetcode Problem #594 (Easy): Longest Harmonious Subsequence
説明
その最大値と最小値の差が
整数配列
配列のサブシーケンスは、残りの要素の順序を変更せずに、配列からいくつかの要素を削除することによって配列から派生できるシーケンスです.
例:
例1 :
入力
nums =[ 1 , 3 , 2 , 2 , 5 , 2 , 3 , 7 ]
出力:
5
解説
最も長いHarmoniousSubsequenceは[ 3 , 2 , 2 , 2 , 3 ]です.
例2 :
入力
nums =[ 1 , 2 , 3 , 4 ]
出力:
2
例3 :
入力
NUM = [ 1 , 1 , 1 , 1 ]
出力:
0
制約 1 <= nums.長さ<= 2 * 10 ^ 4 - 10 ^ 9 <= nums [ i ] <= 10 ^ 9 考え
我々の目標の調和した配列がその要素の絶対値を扱うので、それが我々の数Array(N)の下位配列であるので、我々はNの数の順序またはインデックスを心配する必要はありません.
我々が気にかけるすべてが何であるかがnで、そして、彼らの順序またはインデックスでないということであるならば、それはNから周波数マップを構築することによって始めるべきであるということを意味します.
その後、我々はちょうど我々の周波数マップ(FMAP)のエントリを繰り返すことができますし、最大の値を追跡するキーの周波数(1)の周波数(Val)の周波数(Val)の周波数を追加することによって見つかりました.
次に最善の結果を返すべきです.
実装
JavaScriptのmap ()は、そのキーを文字列として格納するため、キーを1にする前にキーに変換するメソッドを使用する必要があります.これを行う通常の方法はparseInt ()ですが、double - bitwise not (~)を適用すると、数が- 2 ^ 31より大きく、2 ^ 31より小さい限り、効率的に同じことを行います.
JavaScriptコード
Leetcode Problem #594 (Easy): Longest Harmonious Subsequence
説明
その最大値と最小値の差が
1
であるアレイとして調和アレイを定義した.整数配列
nums
を考えて、その可能なサブシーケンスの中で最も長い調和しているサブシーケンスの長さを返してください.配列のサブシーケンスは、残りの要素の順序を変更せずに、配列からいくつかの要素を削除することによって配列から派生できるシーケンスです.
例:
例1 :
入力
nums =[ 1 , 3 , 2 , 2 , 5 , 2 , 3 , 7 ]
出力:
5
解説
最も長いHarmoniousSubsequenceは[ 3 , 2 , 2 , 2 , 3 ]です.
例2 :
入力
nums =[ 1 , 2 , 3 , 4 ]
出力:
2
例3 :
入力
NUM = [ 1 , 1 , 1 , 1 ]
出力:
0
制約
我々の目標の調和した配列がその要素の絶対値を扱うので、それが我々の数Array(N)の下位配列であるので、我々はNの数の順序またはインデックスを心配する必要はありません.
我々が気にかけるすべてが何であるかがnで、そして、彼らの順序またはインデックスでないということであるならば、それはNから周波数マップを構築することによって始めるべきであるということを意味します.
その後、我々はちょうど我々の周波数マップ(FMAP)のエントリを繰り返すことができますし、最大の値を追跡するキーの周波数(1)の周波数(Val)の周波数(Val)の周波数を追加することによって見つかりました.
次に最善の結果を返すべきです.
実装
JavaScriptのmap ()は、そのキーを文字列として格納するため、キーを1にする前にキーに変換するメソッドを使用する必要があります.これを行う通常の方法はparseInt ()ですが、double - bitwise not (~)を適用すると、数が- 2 ^ 31より大きく、2 ^ 31より小さい限り、効率的に同じことを行います.
JavaScriptコード
var findLHS = function(N) {
let fmap = new Map(), ans = 0
for (let num of N)
fmap.set(num, (fmap.get(num) || 0) + 1)
for (let [key,val] of fmap)
if (fmap.has(~~key+1))
ans = Math.max(ans, val + fmap.get(~~key+1))
return ans
};
Reference
この問題について(解決:最長の調和したサブシーケンス), 我々は、より多くの情報をここで見つけました https://dev.to/seanpgallivan/solution-longest-harmonious-subsequence-4b1eテキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol