您现在的位置是:首页 > 正文

整数替换:将键盘输入的整数变成1,所用的最小次数 1)n是偶数,n=n/2 2)n是奇数,n=n-1/n=n+1 例如:7 -> 8 -> 4 -> 2 -> 1

2024-02-01 03:31:23阅读 2

初试:

import java.util.Scanner;
class 算法_整数替换 {
	/*
		将键盘输入的整数变成1,所用的最小次数
		1)n是偶数,n=n/2
		2)n是奇数,n=n-1/n=n+1
		例如:7 -> 8 -> 4 -> 2 -> 1
	*/

	/*
		踩坑解析
		一、n是偶数直接除以2
		二、n是奇数(优化:n+1或者n-1之后是偶数即可,
				没必要管他哪个次数更少,最后结果取小的即可。)
			1.n-1是2的次幂(降次更快)
			2.n+1是2的次幂(降次更快)
			3.n+1/n-1之后都不是2的次幂(没有分情况!!!)
				1)n-1/2、n+1/2仍都是偶数,选择n-1
				2)n-1/2仍是偶数,n+1/2不是偶数,选择n-1
				3)n+1/2仍是偶数,n-1/2不是偶数,选择n+1
				ps:只需要判断n+1/2仍是偶数,n-1/2不是偶数,即可。		
	*/
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int count = integerReplacement(n);
		System.out.println("最少的次数为:"+count);
	
	}

    public static int integerReplacement(int n) {
        int count =0;
        for(int i=0;n!=1;i++){
            if(n%2==0){//n是偶数
                n=n/2;
                count++;
            }
            else{//n不是偶数
                for(int j=1; ;j++){
                    if((n-1)==Math.pow(2,j)){//n-1之后是2的次幂
                        n=n-1;
                        count++;
                        break;
                    }
                    else if((n+1)==Math.pow(2,j)){//n+1之后是2的次幂
                        n=n+1;
                        count++;
                        break;
                    }
					else{//奇数n+1/n-1之后都不是2的次幂
						//1)n+1/2,n-1/2之后都是偶数,选择n-1
						//2)n+1/2之后不是偶数,n-1/2之后仍是偶数,选择n-1
						//3)n+1/2之后仍是偶数,n-1/2之后不是偶数,选择n+1
						if((n+1)/2%2==0&&(n-1)/2%2!=0){
							n = n+1;
							count++;
							break;
						}
						else{
							n = n-1;
							count++;
							break;
						}
					}
                }   
            }
        }
         return count;
    }
}

借鉴优化:

import java.util.Scanner;
class 算法_整数替换优化01 {
	/*
		踩坑解析
		一、n是偶数直接除以2
		二、n是奇数
			不需要具体分情况,分别对n-1和n+1求次数,取小		
	*/
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int count = integerReplacement(n);
		System.out.println("最少的次数为:"+count);
		sc.close();
	}

	public static int integerReplacement(int n) {
			int count = 0;
			//对偶数进行预处理
			while (n > 0 && n % 2 == 0){
				count += 1;//偶数直接处理n / 2
				n /= 2;
			}
			//然后处理两种特殊情况
			if (n == 0){
				return count + 1;
			}
			else if (n == 1){
				return count;
			}
			else{
				//最后分n + 1,n - 1进行两种处理
				//不需要管当前奇数n+1好,还是n-1好,每次都取最小值,结果一定是最小的
				count += Math.min(integerReplacement(n + 1), integerReplacement(n - 1));//奇数分别处理n + 1,n - 1取最小值
				return count + 1;//+1或者-1都处理了一次
			}
		}
}

疑惑:

//难道是进程原因,第一个(n-1)有错
   /* public static int integerReplacement(int n) {
        int jia=0,jian=0,nn=0;
		nn = n;//nn用于加,n用于减少
        for(int i=0; ;i++){//n且nn等于1,结束循环
			if(n<=1 || nn<=1)
				break;
            if(n%2==0||nn%2==0){//偶数:n/nn是偶数
				if(n%2==0){//n是偶数
					n = n/2;
					jian++;
				}
				if(nn%2==0){//nn是偶数
					nn = nn/2;
					jia++;
				}

            }
			if(n%2!=0||nn%2!=0){//奇数:n/nn是奇数
				if(n%2!=0){//n是奇数
					n = n-1;
					jian++;
				}
				if(nn%2!=0){//nn是奇数
					nn = nn+1;
					jia++;
				}
			}
			System.out.println(n+" "+nn);
            
        }
		System.out.println(jian+" "+jia);
         return jia>=jian ? jian :jia;
    }
}
*/

网站文章

  • Android阴影绘制的方式

    不管是自定义View也还是自定义ViewGroup,都是一样的效果,我们都是通过Paint画笔自己画出阴影,本质都是操作onDraw方法。核心类就是 BlurMaskFilter 类,它的兼容性比较好...

    2024-02-01 03:30:53
  • Spark作业执行原理(六)——获取执行结果

    Spark作业执行原理(六)——获取执行结果

    对于Executor的计算结果,会根据结果的大小使用不同的处理策略:计算结果在(0,128MB-200KB)区间内:通过Netty直接发送给Driver终端;计算结果在[128MB, 1GB]区间内:将结果以taskId为编号存入到BlockManager中,然后通过Netty把编号发送给Driver终端;阈值可通过Netty框架传输参数设置spark.a...

    2024-02-01 03:30:47
  • python变量的内建方法3——String型

    #a=整数型变量1.a.capitalize()#此方法返回的字符串只有它的第一个字符大写的副本。例:In [40]: a=&#39;abc&#39;In [41]: a.capitalize()Ou...

    2024-02-01 03:30:40
  • JNDI注入

    JNDI注入

    JNDI(The Java Naming and Directory Interface,Java命名和目录接口)是一组在Java应用中访问命名和目录服务的API,命名服务将名称和对象联系起来,使得我们可以用名称访问对象。

    2024-02-01 03:30:12
  • ES6学习——set map数据结构 、 DOM classlist属性、创建对象 、Symbol应用

    ES6学习——set map数据结构 、 DOM classlist属性、创建对象 、Symbol应用

    对象方法就是把对象中的属性,用匿名函数的形式编程方法(之前就有)。

    2024-02-01 03:30:07
  • 如何在SQLServer中处理每天四亿三千万记录的(数据库大数据处理)

    项目背景这是给某数据中心做的一个项目,项目难度之大令人发指,这个项目真正的让我感觉到了,商场如战场,而我只是其中的一个小兵,太多的战术,太多的高层之间的较量,太多的内幕了。具体这个项目的情况,我有空再写相关的博文出来。这个项目是要求做环境监控,我们暂且把受监控的设备称为采集设备,采集设备的属性称为监控指标。项目要求:系统支持不少于10w个监控指标,每个监控指标的数据更新不大于20秒,存储延迟...

    2024-02-01 03:30:00
  • 《软件开发的201个原则》

    《软件开发的201个原则》

    作为一名从事软件开发工作的读者,深刻体会到《软件开发原则》书中的系列原则,在我开发过程中处处可见。如果遵循这些原则,那么对你的开发是十分有效的。在项目开发过程格遵守开发流程,让一切异常都有迹可循,有法可解,工作效率显著提示。

    2024-02-01 03:29:28
  • ThreadLocal 详解

    ThreadLocal 详解

    如果key使用强引用:业务代码中使用完ThreadLocal ,ThreadLocal Ref被回收了,因为ThreadLocalMap的Entry强引用了threadLocal,造成threadLo...

    2024-02-01 03:29:20
  • 【unlink】 zctf2016_note2

    【unlink】 zctf2016_note2

    【unlink】 zctf2016_note2 1.ida分析 堆溢出,unsigned int用于判断条件,导致的堆溢出 指针数组 2.思路 创建3个chunk,chunk0、chunk1、chun...

    2024-02-01 03:29:12
  • android Preference之android:dependency

    android Preference之android:dependency

    在开发软件设置界面的时候,我们可以采用android系统提供的PreferenceActivity来实现,下面给出一个简单的例子: 1、Activity 代码如下: public class ConfigActivity extends PreferenceActivity { @Override public void onCreate(Bundle save...

    2024-02-01 03:29:05