leetcode69-x的平方根

原题

实现 int sqrt(int x) 函数。

计算并返回 x 的平方根,其中 x 是非负整数。

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

示例1:

输入: 4
输出: 2

示例2:

输入: 8
输出: 2
说明: 8 的平方根是 2.82842...,
由于返回类型是整数,小数部分将被舍去。

解法

思想

二分法

代码

class Solution {
    public int mySqrt(int x) {
        //为了防止end * end 超过int范围,这里统一使用使用long
        long longx = x;
        long start = 0;
        long end = x/2;
        long mid;
        while(start<=end){
            mid = (end+start)/2;
            if(mid*mid == longx) return (int)mid;
            if(mid*mid < longx) {
                start = mid + 1;
                if(start*start>longx) return (int)mid;
            }
            else if(mid*mid > longx) {
                end = mid - 1;
                if(end*end<longx) return (int)end;
            }
        }
        return (int)start;
    }
}

原创文章,作者:彭晨涛,如若转载,请注明出处:https://www.codetool.top/article/leetcode69-x%e7%9a%84%e5%b9%b3%e6%96%b9%e6%a0%b9/

(0)
彭晨涛彭晨涛管理者
上一篇 2019年12月29日
下一篇 2019年12月31日

相关推荐

  • leetcode111-二叉树的最小深度

    原题 给定一个二叉树,找出其最小深度。 最小深度是从根节点到最近叶子节点的最短路径上的节点数量。 说明: 叶子节点是指没有子节点的节点。 示例: 给定二叉树 [3,9,20,nul…

    算法 2020年3月25日
    0220
  • leetcode46-全排列

    原题 给定一个没有重复数字的序列,返回其所有可能的全排列。 示例: 输入: [1,2,3] 输出: [   [1,2,3],   [1,3,…

    算法 2020年3月3日
    0190
  • leetcode82-删除排序链表中的重复元素II

    原题 给定一个排序链表,删除所有含有重复数字的节点,只保留原始链表中 没有重复出现 的数字。 示例 1: 输入: 1->2->3->3->4->4->5 输出: 1->2->5 示…

    算法 2020年5月31日
    0240
  • leetcode430-扁平化多级双向链表

    原题 您将获得一个双向链表,除了下一个和前一个指针之外,它还有一个子指针,可能指向单独的双向链表。这些子列表可能有一个或多个自己的子项,依此类推,生成多级数据结构,如下面的示例所示…

    2019年12月17日
    0100
  • leetcode453-最小移动次数使数组元素相等

    原题 给定一个长度为 n 的非空整数数组,找到让数组所有元素相等的最小移动次数。每次移动将会使 n - 1 个元素增加 1。 示例: 输入: [1,2,3] 输出: 3 解释: 只…

    算法 2020年6月7日
    0140
  • leetcode445-两数相加II

    原题 给你两个 非空 链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。 你可以假设除了数字 0 之外,这两个数字都…

    算法 2020年4月14日
    0290
  • leetcode203-移除链表元素

    原题 删除链表中等于给定值 val 的所有节点。 示例: 输入: 1->2->6->3->4->5->6, val = 6 输出: 1->2->3->4->5 解法 思想 pre指…

    算法 2019年12月16日
    0360
  • leetcode378-有序矩阵中第K小的元素

    原题 给定一个 n x n 矩阵,其中每行和每列元素均按升序排序,找到矩阵中第k小的元素。请注意,它是排序后的第k小元素,而不是第k个元素。 示例: matrix = [ &nbs…

    算法 2020年2月14日
    0430
  • leetcode274-H指数

    原题 https://leetcode.cn/problems/h-index/description 题解 核心是求数组中,大于等于h的数的个数 大于等于 h,个数的最大值。 核…

    算法 2024年3月18日
    070
  • leetcode138-复制带随机指针的链表

    这道题和leetcode133-克隆图有异曲同工之妙。 原题 给定一个链表,每个节点包含一个额外增加的随机指针,该指针可以指向链表中的任何节点或空节点。 要求返回这个链表的深拷贝。…

    2019年12月17日
    0330

发表回复

登录后才能评论