文章修改网站,网站建设高端设计,装潢设计与工艺教育专业,山西城乡建设部网站首页文章目录1. 题目2. 解题2.1 递归2.2 记忆化递归2.3 贪心1. 题目
给定一个正整数 n#xff0c;你可以做如下操作#xff1a;
如果 n 是偶数#xff0c;则用 n / 2替换 n。如果 n 是奇数#xff0c;则可以用 n 1或n - 1替换 n。
n 变为 1 所需的最小替换次数是多少#…
文章目录1. 题目2. 解题2.1 递归2.2 记忆化递归2.3 贪心1. 题目
给定一个正整数 n你可以做如下操作
如果 n 是偶数则用 n / 2替换 n。如果 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来源力扣LeetCode 链接https://leetcode-cn.com/problems/integer-replacement 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。
2. 解题
2.1 递归
class Solution {
public:int integerReplacement(int n) {if(n 1)return 0;if(n 2147483647)//防止1溢出return 32;if(n%2 0)return 1integerReplacement(n1);elsereturn 1min(integerReplacement(n1), integerReplacement(n-1));}
};2.2 记忆化递归
class Solution {unordered_mapint,int map;
public:int integerReplacement(int n) {if(n 1)return 0;if(n 2147483647)//防止1溢出return 32;if(map.find(n) ! map.end())return map[n];int m;if(n%2 0)m 1integerReplacement(n1);elsem 1min(integerReplacement(n1), integerReplacement(n-1));map[n] m;return m;}
};2.3 贪心
偶数的时候没什么选择直接除以2 奇数的时候怎么选择1-1 操作后肯定为偶数2的倍数 为了让数更快的等于1更优的操作是操作后还为4的倍数就可以连续除以2两次
class Solution {
public:int integerReplacement(int n) {int count 0;if(n INT_MAX)return 32;while(n ! 1){if((n1) 0)//偶数{count;n 1;}else//奇数有两种情况0b01, 0b11{if(n 3)//特殊情况{count 2;break;}if((n3) 3)n 1;//操作后可以多除1次2elsen - 1;count;}}return count;}
};
