リートコード:397。整数置換



Leetcode 397 Integer Replacement



正の整数が与えられた n 次のことができます。

場合 n 偶数の場合は、n / 2置換を使用します n
2.もし n 奇妙なことに、使用できますn + 1またはn - 1置換 n
n 1になるために必要な交換の最小数はいくつですか?



例1:

 Enter:  8  Output:  3  Explanation:  8 -> 4 -> 2 -> 1 

例2:



 Enter:  7  Output:  4  Explanation:  7 -> 8 -> 4 -> 2 -> 1 Or 7 -> 6 -> 3 -> 2 -> 1

ソリューションのアイデア:

動的な計画、再帰。 dp [n]を、数値nが1に変換された回数、具体的にはdp [1] = 1とします。質問の意味によれば、次の再帰関係を得ることができます。

  • nが奇数の場合、dp [n] = min(dp [n + 1]、dp [n-1])+ 1。
  • nが偶数の場合、dp [n] = dp [n / 2] +1。

奇数がこの再帰を書き込み、nがint型である場合、n + 1が整数をオーバーフローする可能性があるため、これは適切ではないことに注意してください。 n + 1は必ず偶数であるため、次の改善を行うことができます。



  • nが奇数の場合、dp [n] = min(dp [(n >> 1)+1] + 1、dp [n-1])+ 1。

これにより、オーバーフロー現象が回避されます。

また、再帰再帰には複数のパスがあり、同じnに繰り返しアクセスされる場合があります。繰り返しの再帰を回避するために、以前に再帰された値がハッシュテーブルに格納され、unordered_mapを使用できます。このように、アルゴリズムはほぼ完璧です。

C ++コード
クラスソリューション{
公衆:
int integerReplacement(int n){
if(mp [n]> 0)return mp [n]
それ以外の場合はmp.erase(n)
if(n == 1)return 0
if((n&1)== 0){
int num1 = integerReplacement(n >> 1)+ 1
mp[n] = num1
num1を返す
}
int add = integerReplacement((n >> 1)+ 1)+ 2
int del = integerReplacement(n --1)+ 1
int small = min(add、del)
mp [n] =小さい
小さく返す
}
unordered_map mp
}