leetcode279-完全平方数

原题

给定正整数 n,找到若干个完全平方数(比如 1, 4, 9, 16, …)使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。

示例 1:

输入: n = 12
输出: 3
解释: 12 = 4 + 4 + 4.

示例 2:

输入: n = 13
输出: 2
解释: 13 = 4 + 9.

解法

思想

以12为例。

这道题确实对时间要求比较严格,如果不过滤掉重复计算的部分会无法通过。

从目标数出发自顶向下:

leetcode279-完全平方数

由已知的目标数出发,减去比它小的平方数,这样一层一层减下去,直到获得0的那一层的层数就是答案。

需要过滤掉数值重复的节点,比如11-4和8-1。

从平方数出发自底向上:

leetcode279-完全平方数

由比已知目标数小的所有平方数出发,每层做一个组合加法,但是有一些地方需要处理:

  1. 遇到数值相等的节点,如1+4和4+1,跳过该节点。
  2. 在组合的时候遇到从一个数开始,加上它就会大于目标数,那么它之后的平方数都可以不做组合了,因为都比它大。

代码

自顶向下:

class Node{
    public int value;
    public int depth;
    public Node(int value,int depth){
        this.value = value;
        this.depth = depth;
    }
}

class Solution {
    public int numSquares(int n) {
        int mark[] = new int[n];
        if(n<4) return n;
        Queue<Node> queue = new LinkedList<>();
        queue.offer(new Node(n,0));
        while(!queue.isEmpty()){
            Node node = queue.poll();
            if(node.value==0) return node.depth; 
            int sqrt = (int)Math.sqrt(node.value);
            for(int i = sqrt; i > 0 ; i--){
                if(mark[node.value-i*i]==0){
                    queue.offer(new Node(node.value-i*i,node.depth+1));
                    mark[node.value-i*i] = 1;
                }
            }

        }
        return -1;
    }
}

自底向上

class Node{
    public int value;
    public int depth;
    public Node(int value,int depth){
        this.value = value;
        this.depth = depth;
    }
}

class Solution {
    public int numSquares(int n) {
        Queue<Node> queue = new LinkedList<>();
        int a = (int)Math.sqrt(n);
        int[] mark = new int[n+1];
        for(int i = a;i>a/2;i--){
            queue.offer(new Node(i*i,1));
            mark[i*i] = 1;
        }

        while(!queue.isEmpty()){
            Node node = queue.poll();
            int value = node.value;
            if(value==n) return node.depth;
            for(int i = 1;i<=a;i++){
                if(value+i*i>n) break;
                if(mark[value+i*i]==1) continue;
                queue.offer(new Node(value+i*i,node.depth+1));
                mark[value+i*i] = 1;
            }
        }
        return -1;
    }
}

原创文章,作者:彭晨涛,如若转载,请注明出处:https://www.codetool.top/article/leetcode279-%e5%ae%8c%e5%85%a8%e5%b9%b3%e6%96%b9%e6%95%b0/

(0)
彭晨涛彭晨涛管理者
上一篇 2019年12月10日 18:05
下一篇 2019年12月12日 18:05

相关推荐

  • leetcode57-插入区间

    原题 给出一个无重叠的 ,按照区间起始端点排序的区间列表。 在列表中插入一个新的区间,你需要确保列表中的区间仍然有序且不重叠(如果有必要的话,可以合并区间)。 示例 1: 输入: …

    算法 2020年5月12日
    0290
  • leetcode154-寻找旋转排序数组中的最小值II

    原题 假设按照升序排序的数组在预先未知的某个点上进行了旋转。 ( 例如,数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。 请找出其中最小的元素。…

    算法 2020年1月7日
    090
  • leetcode557-反转字符串中的单词III

    原题 给定一个字符串,你需要反转字符串中每个单词的字符顺序,同时仍保留空格和单词的初始顺序。 示例1: 输入: “Let’s take LeetCode contest” 输出: …

    算法 2019年11月23日
    0120
  • leetcode67-二进制求和

    原题 给定两个二进制字符串,返回他们的和(用二进制表示)。 输入为非空字符串且只包含数字 1 和 0。 示例 1: 输入: a = “11”, b = “1” 输出: “100” …

    算法 2019年11月15日
    0100
  • leetcode540-有序数组中的单一元素

    原题 给定一个只包含整数的有序数组,每个元素都会出现两次,唯有一个数只会出现一次,找出这个数。 示例1: 输入: [1,1,2,3,3,4,4,8,8] 输出: 2 示例2: 输入…

    2020年2月25日
    0700
  • leetcode199-二叉树的右视图

    原题 给定一棵二叉树,想象自己站在它的右侧,按照从顶部到底部的顺序,返回从右侧所能看到的节点值。 示例: 输入: [1,2,3,null,5,null,4] 输出:&nb…

    算法 2020年4月22日
    0110
  • leetcode79-单词搜索

    原题 给定一个二维网格和一个单词,找出该单词是否存在于网格中。 单词必须按照字母顺序,通过相邻的单元格内的字母构成,其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格…

    算法 2020年4月12日
    0130
  • leetcode8-字符串转换整数 (atoi)

    原题 请你来实现一个 atoi 函数,使其能将字符串转换成整数。 首先,该函数会根据需要丢弃无用的开头空格字符,直到寻找到第一个非空格的字符为止。接下来的转化规则如下: 如果第一个…

    算法 2020年4月3日
    0270
  • leetcode820-单词的压缩编码

    原题 给定一个单词列表,我们将这个列表编码成一个索引字符串 S 与一个索引列表 A。 例如,如果这个列表是 ["time", "me", "bell"],我们就可以将其表示为 S …

    算法 2020年3月28日
    090
  • leetcode100-相同的树

    原题 给定两个二叉树,编写一个函数来检验它们是否相同。 如果两个树在结构上相同,并且节点具有相同的值,则认为它们是相同的。 示例 1: 输入: 1 1 / \ / \ 2 3 2 …

    算法 2020年5月7日
    0210

发表回复

登录后才能评论