头像
梦心尘
发布于 2020-07-10 15:48
+ 关注

B题

public class Solution {
    /**
     * 返回最后要输出的答案
     * @param n int整型 表示牛牛的数字
     * @param m int整型 表示牛妹的数字
     * @return int整型
     */
    public int solve (int n, int m) {
        // write code here
        if(n>m) return n-m;
        int[] dp = new int[m+1];
        for(int i = n; i>0; i--){
            dp[i] = n-i;
        }
        for(int i = n+1; i<m+1;i++){
            dp[i] = findshortpath(dp, i);
        }
        return dp[m];


    }

    public int findshortpath(int[] dp, int now){
        int sq = (int)Math.sqrt(now);
        int low = sq*sq;
        int high = (sq+1)*(sq+1);
        if (low==now) return Math.min(dp[sq]+1,dp[now-1]+1);
        int l1 = now-low + dp[sq]+1;
        int l2 = high-now + dp[sq+1]+1;
        if (l1<l2) return Math.min(l1,dp[now-1]+1);
        return Math.min(l2,dp[now-1]+1);
    }

    
}
小于n的数,只能做减一操作得到,而大于n的数可以从n-1 转化而来,也可以从Sqrt(k)转化而来


全部评论

(0) 回帖
加载中...
话题 回帖

本文相关内容

等你来战

查看全部

热门推荐