首页 > 其他分享 >69. x 的平方根

69. x 的平方根

时间:2023-03-08 22:56:25浏览次数:48  
标签:示例 ll mid 整数 69 平方根 小数

https://leetcode.cn/problems/sqrtx/

 

给你一个非负整数 x ,计算并返回 x 的 算术平方根 。

由于返回类型是整数,结果只保留 整数部分 ,小数部分将被 舍去 。

注意:不允许使用任何内置指数函数和算符,例如 pow(x, 0.5) 或者 x ** 0.5 。

 

示例 1:

输入:x = 4
输出:2
示例 2:

输入:x = 8
输出:2
解释:8 的算术平方根是 2.82842..., 由于返回类型是整数,小数部分将被舍去。
 

提示:

0 <= x <= 231 - 1
通过次数700,657提交次数1,815,1

来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/sqrtx
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

 

类似题目:log N

思路:二分查找,当l==r查找结束。

要点在于l=mid  r=mid-1 or l=mid+1 r=mid,本题舍小数,答案靠左 故选择l=mid r=mid-1

#define ll long long
class Solution {
public:

    int mySqrt(int x) {
        ll l=0, r = x;
        while(l!=r){
            ll mid = (l+r+1)/2;
            if(mid*mid==x)
                return mid;
            else if(mid*mid>x){
                // l = mid;
                r = mid-1;
            }
            else
                l = mid;
        }
        return l;
    }
};

 

标签:示例,ll,mid,整数,69,平方根,小数
From: https://www.cnblogs.com/ygtzds/p/17196542.html

相关文章

  • Leetcode69(牛顿迭代)
    给你一个非负整数 x ,计算并返回 x 的 算术平方根 。由于返回类型是整数,结果只保留 整数部分 ,小数部分将被 舍去。注意:不允许使用任何内置指数函数和算符,例如 ......
  • 数组-Leetcode-697
    ​​0️⃣python数据结构与算法学习路线​​学习内容:基本算法:枚举、排序、搜索、递归、分治、优先搜索、贪心、双指针、动态规划等…数据结构:字符串(string)、列表(list)、元......
  • 169_技巧_Power BI 依据促销日历计算销售金额
    169_技巧_PowerBI依据促销日历计算销售金额一、背景在各位表格表姐们计算销售金额的时候,有一个绕不开的问题:商品有促销的问题,需要使用对应的促销价来计算销售额。按照......
  • 精粤X99M-PLUS D3+ E5-2696 v3电脑 Hackintosh 黑苹果efi引导文件
    原文来源于黑果魏叔官网,转载需注明出处。硬件型号驱动情况主板精粤X99M-PLUSD3处理器E5-2696v3已驱动内存64GBECCDDR31866MHz(16GB*4)已驱动硬盘TOPMORECAPRICORNUS......
  • 力扣中695 岛屿的最大面积
      classSolution{publicintmaxAreaOfIsland(int[][]grid){intcount=0;//岛屿大小inttempcount=0;int[]dx={0......
  • poj-3669
    http://poj.org/problem?id=3669广搜#include<stdio.h>#include<iostream>#include<math.h>#include<stdlib.h>#include<ctype.h>#include<algorithm>#include......
  • 位运算-洛谷P1469 找筷子
    位运算的符号:与(&) and当两个数在二进制下对应位数上均为 11 时,得到的结果为 11.或(|) or当两个数在二进制下对应位数上有一个为 11 时,得到的结果为 11.......
  • [gym102769D]Defend City
    以下描述部分方向代指该方向的塔,建议画图理解不妨假设左下的塔数\(\ge2\),这些塔覆盖区域构成阶梯形考虑阶梯的交点,若其被左上/右下覆盖,则总可以去掉其中一个左下换言之......
  • Leetcode 2569 Handling Sum Queries After Update
    2569. HandlingSumQueriesAfterUpdatYouaregiventwo 0-indexed arrays nums1 and nums2 anda2Darray queries ofqueries.Therearethr......
  • 算法随想Day21【二叉树】| LC669-修剪二叉搜索树、LC108-将有序数组转换为二叉搜索树
    LC669.修剪二叉搜索树相当于一个中序遍历吧,当某个节点<low时,其右子树的各个节点值虽然都比该节点值大,但仍可能存在<low的,所以要据于次节点,向其右子树进军遍历,等回溯时,del......