Leetcode:397.整数替换
给定一个正整数 n,你可以做如下操作:
1. 如果 n 是偶数,则用 n / 2
替换 n。
2. 如果 n 是奇数,则可以用 n + 1
或n - 1
替换 n。
n 变为 1 所需的最小替换次数是多少?
示例 1:
输入: 8 输出: 3 解释: 8 -> 4 -> 2 -> 1
示例 2:
输入: 7 输出: 4 解释: 7 -> 8 -> 4 -> 2 -> 1 或 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,int>即可。这样一来算法就几乎完美了。
class Solution { public: int integerReplacement(int n) { if (mp[n] > 0) return mp[n]; else mp.erase(n); if (n == 1) return 0; if ((n & 1) == 0) { int num1=integerReplacement(n >> 1) + 1; mp[n] = num1; return num1; } int add = integerReplacement((n >> 1) + 1) + 2; int del = integerReplacement(n - 1) + 1; int small= min(add, del); mp[n] = small; return small; } unordered_map<int, int> mp; }; |