C++实现LeetCode( 69.求平方根)

[LeetCode] 69. Sqrt(x) 求平方根

Implement int sqrt(int x).

Compute and return the square root of x, where x is guaranteed to be a non-negative integer.

Since the return type is an integer, the decimal digits are truncated and only the integer part of the result is returned.

Example 1:

Input: 4
Output: 2

Example 2:

Input: 8
Output: 2
Explanation: The square root of 8 is 2.82842..., and since
the decimal part is truncated, 2 is returned.

这道题要求我们求平方根，我们能想到的方法就是算一个候选值的平方，然后和x比较大小，为了缩短查找时间，我们采用二分搜索法来找平方根，找最后一个不大于目标值的数，这里细心的童鞋可能会有疑问，在总结贴中第三类博主的 right 用的是开区间，那么这里为啥 right 初始化为x，而不是 x+1 呢？因为总结帖里的 left 和 right 都是数组下标，这里的 left 和 right 直接就是数字本身了，一个数字的平方根是不可能比起本身还大的，所以不用加1，还有就是这里若x是整型最大值，再加1就会溢出。最后就是返回值是 right-1，因为题目中说了要把小数部分减去，只有减1才能得到正确的值，代码如下：

解法一：

class Solution {
public:
    int mySqrt(int x) {
        if (x <= 1) return x;
        int left = 0, right = x;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (x / mid >= mid) left = mid + 1;
            else right = mid;
        }
        return right - 1;
    }
};

这道题还有另一种解法，是利用牛顿迭代法，记得高数中好像讲到过这个方法，是用逼近法求方程根的神器，在这里也可以借用一下，因为要求 x2 = n 的解，令 f(x)=x2-n，相当于求解 f(x)=0 的解，可以求出递推式如下：

xi+1=xi - (xi2 - n) / (2xi) = xi - xi / 2 + n / (2xi) = xi / 2 + n / 2xi = (xi + n/xi) / 2

解法二：

class Solution {
public:
    int mySqrt(int x) {
        if (x == 0) return 0;
        double res = 1, pre = 0;
        while (abs(res - pre) > 1e-6) {
            pre = res;
            res = (res + x / res) / 2;
        }
        return int(res);
    }
};

也是牛顿迭代法，写法更加简洁一些，注意为了防止越界，声明为长整型，参见代码如下：

解法三：

class Solution {
public:
    int mySqrt(int x) {
        long res = x;
        while (res * res > x) {
            res = (res + x / res) / 2;
        }
        return res;
    }
};

到此这篇关于C++实现LeetCode( 69.求平方根)的文章就介绍到这了,更多相关C++实现求平方根内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！

赞 (0)

相关推荐

  • C++实现LeetCode(63.不同的路径之二)

    C++实现LeetCode(63.不同的路径之二)

    [LeetCode] 63. Unique Paths II 不同的路径之二 A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram below). The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right c

  • C++实现LeetCode(70.爬楼梯问题)

    [LeetCode] 70. Climbing Stairs 爬楼梯问题 You are climbing a stair case. It takes n steps to reach to the top. Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top? Note: Given n will be a positive integer. Examp

  • C++实现LeetCode(64.最小路径和)

    [LeetCode] 64. Minimum Path Sum 最小路径和 Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path. Note: You can only move either down or right at any point in t

  • C++实现LeetCode(61.旋转链表)

    C++实现LeetCode(61.旋转链表)

    [LeetCode] 61. Rotate List 旋转链表 Given the head of a linked list, rotate the list to the right by k places. Example 1: Input: head = [1,2,3,4,5], k = 2 Output: [4,5,1,2,3] Example 2: Input: head = [0,1,2], k = 4 Output: [2,0,1] Constraints: The number

  • C++实现LeetCode(189.旋转数组)

    [LeetCode] 189. Rotate Array 旋转数组 Given an array, rotate the array to the right by k steps, where k is non-negative. Example 1: Input: [1,2,3,4,5,6,7] and k = 3 Output: [5,6,7,1,2,3,4] Explanation: rotate 1 steps to the right: [7,1,2,3,4,5,6] rotate

  • C++实现LeetCode(62.不同的路径)

    C++实现LeetCode(62.不同的路径)

    [LeetCode] 62. Unique Paths 不同的路径 A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram below). The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner

  • C++实现LeetCode(174.地牢游戏)

    [LeetCode] 174. Dungeon Game 地牢游戏 The demons had captured the princess (P) and imprisoned her in the bottom-right corner of a dungeon. The dungeon consists of M x N rooms laid out in a 2D grid. Our valiant knight (K) was initially positioned in the t

  • C++实现LeetCode( 69.求平方根)

    [LeetCode] 69. Sqrt(x) 求平方根 Implement int sqrt(int x). Compute and return the square root of x, where x is guaranteed to be a non-negative integer. Since the return type is an integer, the decimal digits are truncated and only the integer part of the

  • 易语言求平方根命令使用讲解

    易语言求平方根命令使用讲解

    求平方根命令 操作系统支持:Windows.Linux  所属类别:算术运算 返回指定参数的平方根. 语法:  双精度小数型  求平方根(欲求其平方根的数值) 例程 说明: 将数值编辑框的内容转换到数值型,把转换后的数据求平方根, 再把返回的双精度小数型数据转换到文本型,放入求平方根标签的标题中. 运行结果: 总结 以上就是这篇文章的全部内容了,希望本文的内容对大家的学习或者工作具有一定的参考学习价值,谢谢大家对我们的支持.如果你想了解更多相关内容请查看下面相关链接

  • Python编程实现二分法和牛顿迭代法求平方根代码

    求一个数的平方根函数sqrt(int num) ,在大多数语言中都提供实现.那么要求一个数的平方根,是怎么实现的呢? 实际上求平方根的算法方法主要有两种:二分法(binary search)和牛顿迭代法(Newton iteration) 1:二分法 求根号5 a:折半: 5/2=2.5 b:平方校验: 2.5*2.5=6.25>5,并且得到当前上限2.5 c:再次向下折半:2.5/2=1.25 d:平方校验:1.25*1.25=1.5625<5,得到当前下限1.25 e:再次折半:2.5-(

  • C++实现LeetCode(50.求x的n次方)

    [LeetCode] 50. Pow(x, n) 求x的n次方 Implement pow(x, n), which calculates x raised to the power n(xn). Example 1: Input: 2.00000, 10 Output: 1024.00000 Example 2: Input: 2.10000, 3 Output: 9.26100 Example 3: Input: 2.00000, -2 Output: 0.25000 Explanation

  • C++实现LeetCode(58.求末尾单词的长度)

    [LeetCode] 58. Length of Last Word 求末尾单词的长度 Given a string s consists of upper/lower-case alphabets and empty space characters ' ', return the length of last word in the string. If the last word does not exist, return 0. Note: A word is defined as a

  • C++实现LeetCode(187.求重复的DNA序列)

    [LeetCode] 187. Repeated DNA Sequences 求重复的DNA序列 All DNA is composed of a series of nucleotides abbreviated as A, C, G, and T, for example: "ACGAATTCCG". When studying DNA, it is sometimes useful to identify repeated sequences within the DNA. Wr

  • C++实现LeetCode(124.求二叉树的最大路径和)

    [LeetCode] 124. Binary Tree Maximum Path Sum 求二叉树的最大路径和 Given a non-empty binary tree, find the maximum path sum. For this problem, a path is defined as any sequence of nodes from some starting node to any node in the tree along the parent-child conn

  • C++实现LeetCode(129.求根到叶节点数字之和)

    [LeetCode] 129. Sum Root to Leaf Numbers 求根到叶节点数字之和 Given a binary tree containing digits from 0-9 only, each root-to-leaf path could represent a number. An example is the root-to-leaf path 1->2->3 which represents the number 123. Find the total sum

  • C++实现LeetCode(128.求最长连续序列)

    [LeetCode] 128.Longest Consecutive Sequence 求最长连续序列 Given an unsorted array of integers, find the length of the longest consecutive elements sequence. Your algorithm should run in O(n) complexity. Example: Input: [100, 4, 200, 1, 3, 2] Output: 4 Expl

  • C++实现LeetCode(152.求最大子数组乘积)

    [LeetCode] 152. Maximum Product Subarray 求最大子数组乘积 Given an integer array nums, find the contiguous subarray within an array (containing at least one number) which has the largest product. Example 1: Input: [2,3,-2,4] Output: 6 Explanation: [2,3] has

随机推荐