LeetCode-Perfect Squares

2019/7/23 20:47:29 人评论 次浏览 分类:学习教程

Description:
Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, …) which sum to n.

Example 1:

Input: n = 12
Output: 3 
Explanation: 12 = 4 + 4 + 4.

Example 2:

Input: n = 13
Output: 2
Explanation: 13 = 4 + 9.

题意:给定一个正整数nn,令nn=a1+a2+…ai+…+an,其中ai为一个完全平方数,计算使上述等式满足的最小个数的ai

解法:这道题可以转为一个图的问题,假设此时的n=8n=8,那么我们就是要在下图中找到一条最短的路径到达00;即图中虚线的那个路径就是最短的;我们利用队列来实现,队列中的元素为<n, step>,即整数值和已走的步数,每到下一个节点,步数加1,直到到达n=0n=0的那个节点;

在这里插入图片描述

Java
class Solution {
    public int numSquares(int n) {
        LinkedList<List<Integer>> queue = new LinkedList<>();
        boolean[] visited = new boolean[n + 1];
        visited[n] = true;
        queue.addLast(Arrays.asList(n, 0));
        while (!queue.isEmpty()) {
            List<Integer> list = queue.poll();
            int num = list.get(0);
            int step = list.get(1);
            for (int i = 1; ; i++) {
                int ret = num - i * i;
                if (ret < 0) {
                    break;
                }
                if (ret == 0) {
                    return step + 1;
                }
                if (!visited[ret]) {
                    queue.addLast(Arrays.asList(ret, step + 1));
                    visited[ret] = true;
                }
            }
        }

        throw new RuntimeException("no solution");
    }
}

相关资讯

    暂无相关的资讯...

共有访客发表了评论 网友评论

验证码: 看不清楚?
    -->