leetcode 633. Sum of Square Numbers 二分查找+勾股定理

妖狐艹你老母 2022-06-03 05:37 116阅读 0赞

Given a non-negative integer c, your task is to decide whether there’re two integers a and b such that a2 + b2 = c.

Example 1:  
Input: 5  
Output: True  
Explanation: 1 \* 1 + 2 \* 2 = 5  
Example 2:  
Input: 3  
Output: False

本题很简单，就是寻找勾股数，我最初的想法是直接暴力求解但是发现太笨了，后来在网上看到了一个二分查找的做法，十分棒，值得学习

代码如下：

#include <iostream>
    #include <vector>
    #include <map>
    #include <set>
    #include <queue>
    #include <stack>
    #include <string>
    #include <climits>
    #include <algorithm>
    #include <sstream>
    #include <functional>
    #include <bitset>
    #include <numeric>
    #include <cmath>
    #include <regex>
    
    using namespace std;
    
    class Solution 
    {
    public:
        bool judgeSquareSum(int c) 
        {
            if (c < 0)
                return false;
            int left = 0, right = (int)sqrt(c);
            while (left <= right)
            {
                int res = left*left + right*right;
                if (res < c)
                    left++;
                else if (res > c)
                    right--;
                else
                    return true;
            }
            return false;
        }
    };

发表评论取消回复

表情：

评论列表（有 0 条评论，116人围观）

还没有评论，来说两句吧...

相关阅读

相关 LeetCode（Tree)1022. Sum of Root To Leaf Binary Numbers

1.问题 You are given the root of a binary tree where each node has a value 0 or 1. Each

迷南。/ 2023年09月26日 20:16/ 0 赞/ 73 阅读

相关 leetcode——二分查找

leetcode——二分查找 1.x的平方根(69) 2.在排序数组中查找元素的第一个和最后一个位置 3.搜

忘是亡心i/ 2022年10月31日 13:39/ 0 赞/ 132 阅读

相关 Leetcode 633. 平方数之和（DAY 187）---- 二分查找学习期

文章目录原题题目代码实现（首刷自解） -------------------- 原题题目 --------------------

待我称王封你为后i/ 2022年09月15日 11:52/ 0 赞/ 130 阅读

相关 leetcode 633. Sum of Square Numbers

1.题目 Given a non-negative integer c, your task is to decide whether there’re two inte

末蓝、/ 2022年06月08日 03:25/ 0 赞/ 94 阅读

相关 leetcode 633. Sum of Square Numbers 二分查找+勾股定理

Given a non-negative integer c, your task is to decide whether there’re two integers a a

妖狐艹你老母/ 2022年06月03日 05:37/ 0 赞/ 116 阅读

相关 1104. Sum of Number Segments (20)

Given a sequence of positive numbers, a segment is defined to be a consecutive subsequen

女爷i/ 2022年05月28日 07:26/ 0 赞/ 93 阅读

相关 Sum of Consecutive Prime Numbers

一些正整数能够表示为一个或多个连续素数的和。给定一个正整数，有多少个这样的表示？例如，整数53有两个表示5+7+11+13+17和53；整数20没有这样的表示。注意加法操

约定不等于承诺〃/ 2022年03月29日 12:58/ 0 赞/ 142 阅读

相关【leetcode】985. Sum of Even Numbers After Queries

题目如下： > We have an array `A` of integers, and an array `queries` of queries. > > For t

Bertha 。/ 2022年01月07日 11:25/ 0 赞/ 138 阅读

相关【LeetCode】二分查找

Java code class Solution { public int search(int[] nums, int tar

╰半橙微兮°/ 2021年11月08日 23:52/ 0 赞/ 206 阅读

相关 LeetCode : Sum of Square Numbers 两个数的平方和

试题： Given a non-negative integer c, your task is to decide whether there’re two intege

女爷i/ 2021年06月24日 16:10/ 0 赞/ 309 阅读