美文网首页LeetCode蹂躏集
2018-05-12 633. Sum of Square Nu

2018-05-12 633. Sum of Square Nu

作者: alexsssu | 来源:发表于2018-05-12 17:58 被阅读0次

    题意:给你一个非负数c,判断该数是不是两个完全平方数的和(a^2 + b^2) = c.
    解题思路:
    思路一:暴力。筛选a,b:a^2 <= c, b ^2 <= c,然后组合a^2 + b^2与c比较,时间复杂度O(sqrt(c)*sqrt(c) = O(c),会TLE.
    思路二:使用sqrt函数或自己写二分查找。先筛选a需满足a^2 <= c,再判断c-a^2 是否为完全平方数,令b = (c-a^2),判断sqrt(b) == int( sqrt(b) ) ?
    时间复杂度:O(sqrt(c) * log(c)),找a需要O(sqrt(c)),判断b的sqrt函数需要O(log=(c))。查看ac detail时发现运行时间为12ms,还算可以接受。
    空间复杂度:O(log(c)),sqrt函数需要logc空间。

    class Solution {
    public:
        bool judgeSquareSum(int c) {
            for(long long a = 0; a * a <= c; a++)   //使用long long 防止溢出
            {
                double b = sqrt(c - a * a);
                if(b == int(b) ) 
                    return true;
            }
            return false;
        }
    };
    

    思路三:使用hashmap,将所有小于c的完全平方数存为hashmap的键,对应的n存为值,因为在hashmap中寻找键时间复杂度是O(1)。
    时间复杂度:O(sqrt(c)),但是查看ac detail的时候发现运行时间为249ms,是最慢ac程序。
    空间复杂度:因为开始的时候编译器会自动为hashmap分配一部分内存,当hashmap内存不够的时候,编译器会进行hashmap的内存扩充resize,所以大体也可以将空间复杂度看做O(c).

    class Solution {
    public:
        bool judgeSquareSum(int c) {
            map<long long, int> m;
            for(long long a = 0; a * a <= c; a++)          //使用long long防止溢出
            {
                m[a * a] = a;                              //一边添加键值对
                if(m.find(c - a * a) != m.end())           //一边查找更快
                    return true;
            }
            return false;
        }
    };
    

    相关文章

      网友评论

        本文标题:2018-05-12 633. Sum of Square Nu

        本文链接:https://www.haomeiwen.com/subject/hadhdftx.html