程序员最近都爱上了这个网站  程序员们快来瞅瞅吧!  it98k网:it98k.com

本站消息

站长简介/公众号

  出租广告位,需要合作请联系站长


+关注
已关注

分类  

暂无分类

标签  

暂无标签

日期归档  

2023-06(2)

JAVA(2021-11-19)leetcode每日一题---- 整数替换

发布于2021-11-21 21:14     阅读(848)     评论(0)     点赞(30)     收藏(5)


本题我采用的贪心算法,一个数要么是偶数,要么是奇数,这显而易见,所以我们就要根据这两个条件分类讨论,如果是偶数,那么直接就除以二,操作数加1就好了

如果是奇数,就要讨论一番,举一个例子,如果n为7 ,那么他变成8更容易,仅仅需要一次操作数就可以,但是要是变成4,就需要三次操作数,我们需要快速的判断出来要变大还是变小。

我们可以通过%4操作做到,一个奇数%4,要么是3,要么是1,如果是1,比如5%4,那么我们肯定要将其变成4,即n=(n-1)/ 2,反之如果%4得3,比如7,那么一定是变成8,即n=(n+1)/2.

  1. class Solution {
  2. public int integerReplacement(int n) {
  3. int res = 0;
  4. while(n!=1){
  5. if((n&1)==0){
  6. n/=2;
  7. res++;
  8. } else if(n % 4 ==1){
  9. n/=2;
  10. res+=2;
  11. } else{
  12. if(n==3){
  13. res+=2;
  14. n=1;
  15. } else{
  16. res+=2;
  17. n = n / 2 + 1;
  18. }
  19. }
  20. }
  21. return res;
  22. }
  23. }



所属网站分类: 技术文章 > 博客

作者:听说你很拽

链接:http://www.javaheidong.com/blog/article/326632/fee45f330976e233cc53/

来源:java黑洞网

任何形式的转载都请注明出处,如有侵权 一经发现 必将追究其法律责任

30 0
收藏该文
已收藏

评论内容:(最多支持255个字符)