リートコード: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を使用できます。このように、アルゴリズムはほぼ完璧です。
クラスソリューション{ 公衆: 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 } |