2021-11-19

刚开始觉得很简单，最小直接取n-1不就行了，觉得是一道简单题，后来发现大意了，应该是n+1,n-1两种情况选择一种最小的方案，于是程序写成了递归更方便，java版本参考了官方记忆化搜索，在之前的基础上加了个hashmap，感觉并没有大的区别。

Go版本：

import "fmt"
func integerReplacement(n int) int {
    return dfs(n);
}

func dfs(n int)int{
    if n==1{
        return 0
    }
    if n%2==0{
        return 1+dfs(n/2)
    }
    return  1+min(dfs((n-1)),dfs((n+1)))
    
}
func min(num1 int,num2 int)int{
    if num1>num2{
        return num2
    }
    return num1
}

java版本：

class Solution {
    HashMap<Integer,Integer> hashmap=new HashMap<Integer,Integer>();
    public int integerReplacement(int n) {
        if(n==1){
            return 0;
        }

        if(!hashmap.containsKey(n)){
            if(n%2==0){
                hashmap.put(n,1+integerReplacement(n/2));
            }else{
                hashmap.put(n,2+Math.min(integerReplacement(n/2),integerReplacement(n/2+1)));
            }

        }
        return hashmap.get(n);

    }
}