时间戳

首页 > 解决方案 > 关于 LeetCode 279. 完美正方形的问题

java - 关于 LeetCode 279. 完美正方形的问题

问题描述

给定一个正整数 n，找出总和为 n 的最小完美平方数（例如，1、4、9、16，...）。

示例 1：

输入：n = 12 输出：3 解释：12 = 4 + 4 + 4。

示例 2：

输入：n = 13 输出：2 解释：13 = 4 + 9。

import java.util.*;

public class Solution {
    public int numSquares(int n) {
        int i = 1;
        int ret = Integer.MAX_VALUE;
        while(i * i < (n / 2)) {
            int start = i * i;
            int step = BFS(start,n);
            if(step < ret)
                ret = step;         
            i++;
      }

        return ret;
    }

    public int BFS(int start, int n) {
        int step = 0;
        LinkedList<Integer> queue = new LinkedList<Integer>();
        queue.offer(start);
        while(!queue.isEmpty()){
             int node = queue.poll();
             step++;
             if(node == n)
                 break;
             for(int k=1;k*k <= n;k++){
                 if(k*k <= n)
                 queue.offer(k * k + node); 
                 if(node + k*k == n)
                     return step + 1;
             }          
        }
        return step;
    }


}

我在更新步长值时遇到问题。我想不出如何更新步长值的解决方案。任何人都可以帮忙吗？

标签： javaalgorithmbreadth-first-search

解决方案

恕我直言，我将尝试更新该step值，通过检测程序中的一些marker不同levels之处BFS，谁能告诉我们我们正在达到上一个级别的末尾并进入下一个级别。我通常使用一个null元素作为 this marker。

请参阅我的带有注释的代码，该代码已被接受：

public class Solution {
    public int numSquares(int n) {
        Queue<Integer> queue=new LinkedList();
        queue.add(n);
        queue.add(null);//a null element to show the gap between two levels,i.e., the step
        int res=1;
        while(true){
            Integer i=queue.element();

            if(queue.size()!=1&&i==null){// we are hitting the marker
                queue.remove();
                res++;//i.e., step+1
                queue.add(null);//think about why we need add an additional marker here.
            }else{
                Integer sqrt=(int)Math.round(Math.sqrt(i));
                if(sqrt*sqrt==i){
                    break;
                }else{
                    queue.remove();
                    for(int j=sqrt;1<=j;j--){
                        if(0<i-j*j)
                            queue.add(i-j*j);
                    }
                }
            }
        }
        return res;
    }
}

PS，如前所述：

为方便起见，大多数标准库头文件已自动包含在内。

所以我们不这样做import java.util.*，代码可以编译。

推荐阅读