专栏首页大白技术控的技术自留地C#版 - Leetcode 633. 平方数之和 - 题解

C#版 - Leetcode 633. 平方数之和 - 题解

C#版 - Leetcode 633. 平方数之和 - 题解

Leetcode 633 - Sum of square number

在线提交: https://leetcode.com/problems/sum-of-square-numbers/

题目描述

给定一个非负整数 c ,你要判断是否存在两个整数 a和 b,使得 a2+b2=ca2+b2=ca^2 + b^2 = c。

示例1:

输入: 5
输出: True
解释: 1 * 1 + 2 * 2 = 5

示例2:

输入: 3
输出: False

Input: 5 2 100

Expected answer: true true true



思路:

做一次循环,用目标和减去循环变量的平方,如果剩下的部分依然是完全平方的情形存在,就返回true,否则返回false。循环变量i满足 i2⋅2<c2i2⋅2<c2i^2 \cdot 2 < c^2 .

已AC代码: 最初版本:

public class Solution
{
    public bool JudgeSquareSum(int c)
    {           
        for (int i = 0; c - 2 * i * i >= 0; i++)
        {
            double diff = c - i*i;
            if ((int)(Math.Ceiling(Math.Sqrt(diff))) == (int)(Math.Floor(Math.Sqrt(diff))))
                return true;
        }

        return false;
    }
}

Rank:

You are here! Your runtime beats 56.14% of csharp submissions. 优化1:

public class Solution
{
    public bool JudgeSquareSum(int c)
    {           
        for (int i = 0; c - 2 * i * i >= 0; i++)
        {
            int diff = c - i*i;
            if (IsPerfectSquare(diff))
                return true;
        }

        return false;
    }
    private bool IsPerfectSquare(int num)
    {
        double sq1 = Math.Sqrt(num);
        int sq2 = (int)Math.Sqrt(num);
        if (Math.Abs(sq1 - (double)sq2) < 10e-10)
            return true;
        return false;
    }
}

Rank: You are here! Your runtime beats 85.96% of csharp submissions.

优化2:

public class Solution
{
    public bool JudgeSquareSum(int c)
    {           
        for (int i = 0; i <= c && c - i * i >= 0; i++)
        {
            int diff = c - i*i;
            if (IsPerfectSquare(diff))
                return true;
        }

        return false;
    }
    public bool IsPerfectSquare(int num)
    {
        if ((0x0213 & (1 << (num & 15))) != 0)
        {
            int t = (int)Math.Floor(Math.Sqrt((double)num) + 0.5);
            return t * t == num;
        }
        return false;
    }
}

Rank: You are here! Your runtime beats 85.96% of csharp submissions.

优化3:

public class Solution
{
    public bool JudgeSquareSum(int c)
    {           
        for (int i = 0; c - i * i >= 0; i++)
        {
            long diff = c - i*i;
            if (IsSquareFast(diff))
                return true;
        }

        return false;
    }

    bool IsSquareFast(long n)
    {
        if ((0x2030213 & (1 << (int)(n & 31))) > 0)
        {
            long t = (long)Math.Round(Math.Sqrt((double)n));
            bool result = t * t == n;
            return result;
        }
        return false;
    }
}

Rank: You are here! Your runtime beats 85.96% of csharp submissions.

另外,stackoverflow上还推荐了一种写法:

public class Solution
{
    public bool JudgeSquareSum(int c)
    {           
        for (int i = 0; c - 2 * i * i >= 0; i++)
        {
            double diff = c - i*i;
            if (Math.Abs(Math.Sqrt(diff) % 1) < 0.000001)
                return true;
        }

        return false;
    }
}

事实上,速度并不快: Rank: You are here! Your runtime beats 29.82% of csharp submissions.

Reference:

Fast way to test whether a number is a square https://www.johndcook.com/blog/2008/11/17/fast-way-to-test-whether-a-number-is-a-square/

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • C#版 - Leetcode 593. 有效的正方形 - 题解

    在线提交: https://leetcode.com/problems/valid-square/

    Enjoy233
  • 滴滴2016.09.06校招 在线笔试 - 2道编程题

    一个数组有N个元素,求连续子数组的最大和。例如:[-1,2,1],和最大的连续子数组为[2,1],其和为3。

    Enjoy233
  • C#刷遍Leetcode面试题系列连载(4): No.633 - 平方数之和

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 ...

    Enjoy233
  • Leetcode#70. Climbing Stairs(爬楼梯)

    武培轩
  • 欧拉计划 Problem10

    题目; 素数的和 所有小于10的素数的和是2 + 3 + 5 + 7 = 17。

    用户4492257
  • C#版 - Leetcode 593. 有效的正方形 - 题解

    在线提交: https://leetcode.com/problems/valid-square/

    Enjoy233
  • ECJTUACM16 Winter vacation training #4 题解&源码

    https://vjudge.net/contest/149692#overview 这周一VJ比赛,题解&源码已完成! A.....................

    Angel_Kitty
  • 扩展随机数

    随机数生成 (1)可使用random等系统函数,构造函rand 15 :在[1,5]范围,均匀分布随机函数  (2)不可使用random,仅仅基于rand15构...

    ShenduCC
  • 1089 狼人杀-简单版 (20 分)

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。

    韩旭051
  • 【leetcode刷题】T159-爬楼梯

    https://leetcode-cn.com/problems/climbing-stairs/

    木又AI帮

扫码关注云+社区

领取腾讯云代金券