LeetCode - 069 - x 的平方根(sqrtx)

栏目: IT技术 · 发布时间: 5年前

内容简介:LeetCode - 069 - x 的平方根(sqrtx)

Create by jsliang on 2019-06-11 15:17:21
Recently revised in 2019-06-11 16:23:30

一 目录

不折腾的前端,和咸鱼有什么区别

| 目录 | | --- | | 一 目录 | | 二 前言 | | 三 解题 | |  3.1 解题 - JS API | |  3.2 解法 - 暴力破解 | |  3.3 解法 - 二分查找 |

二 前言

  • 难度:简单

  • 涉及知识:数学、二分查找

  • 题目地址:https://leetcode-cn.com/problems/sqrtx/

  • 题目内容

  1. 实现 int sqrt(int x) 函数。

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

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

  4. 示例 1:

  5. 输入: 4

  6. 输出: 2

  7. 示例 2:

  8. 输入: 8

  9. 输出: 2

  10. 说明: 8 的平方根是 2.82842...,

  11.   由于返回类型是整数,小数部分将被舍去。

三 解题

小伙伴可以先自己在本地尝试解题,再回来看看 jsliang 讲解下使用 JavaScript 的解题思路。

3.1 解法 - JS API

  • 解题代码

  1. var mySqrt = function(x) {

  2. return Math.floor(Math.sqrt(x));

  3. };

  • 执行测试

  1. x: 8

  2. return

  1. 2

  • LeetCode Submit

  1. Accepted

  2. 1017/1017 cases passed (92 ms)

  3. Your runtime beats 98.33 % of javascript submissions

  4. Your memory usage beats 77.02 % of javascript submissions (35.3 MB)

  • 知识点

  1. Math:JS 中的内置对象,具有数学常数和函数的属性和方法。 Math 详细介绍

  • 解题思路

直接使用 JS 原生 API 刷题,帅的嘛就不谈了,一分钟看题,两分钟解题,一分钟测试,搞定!

3.2 解法 - 暴力破解

  • 解题代码

  1. var mySqrt = function(x) {

  2. if (x === 0 || x === 1) {

  3. return x;

  4. }

  5. for (let i = 0; i < x; i++) {

  6. if (i * i <= x && (i + 1) * (i + 1) > x) {

  7. return i;

  8. }

  9. }

  10. };

  • 执行测试

  1. x: 8

  2. return

  1. 2

  • LeetCode Submit

  1. Accepted

  2. 1017/1017 cases passed (200 ms)

  3. Your runtime beats 14.4 % of javascript submissions

  4. Your memory usage beats 39.85 % of javascript submissions (35.7 MB)

  • 解题思路

暴力破解一时爽,一直暴力一直爽

思路非常简单,由于忽略了负数情况,所以直接: i²<=x<=(i+1 即可。

不过暴力破解忽略了时间和空间,所以效率是相当低下。

  • 进一步思考

3.3 解法 - 二分查找

  • 解题代码

  1. var mySqrt = function(x) {

  2. if (x === 0 || x === 1) {

  3. return x;

  4. }

  5. let left = 1;

  6. let right = x;

  7. while (left <= right) {

  8. let middle = Math.floor((left + right) / 2);

  9. if (middle * middle > x) {

  10. right = middle;

  11. }

  12. if (middle * middle < x) {

  13. left = middle;

  14. }

  15. if (middle * middle === x) {

  16. return middle;

  17. }

  18. if (left === right - 1 && left * left <= x && right * right >= x) {

  19. return left;

  20. }

  21. }

  22. };

  • 执行测试

  1. x: 8

  2. return

  1. 2

  • LeetCode Submit

  1. Accepted

  2. 1017/1017 cases passed (92 ms)

  3. Your runtime beats 98.33 % of javascript submissions

  4. Your memory usage beats 19.07 % of javascript submissions (35.9 MB)

  • 知识点

  1. Math:JS 中的内置对象,具有数学常数和函数的属性和方法。 Math 详细介绍

  • 解题思路

首先,判断是不是 0 或者 1 这两种特殊情况,如果是,则返回这两个数字。

然后,开始二分,设置左侧为 1,右侧范围为 x,形成闭区间 [1,x](数学表示,而不是数组)。

  1. 输入 8,形成闭区间 [1,8]

  2. 第一次遍历, Math.floor((1+8)/2) 的值为 4,因为 4*4=16,该值大于 8,所以这时候闭区间变成: [1,4]

  3. 第二次遍历, Math.floor((1+4)/2) 的值为 2,因为 2*2=4,该值小于 8,所以这时候闭区间变成: [2,4]

  4. 第三次遍历, Math.floor((1+4)/2) 的值为 3,因为 3*3=9,该值大于 8,所以这时候闭区间变成: [2,3]

  5. 此时,因为 2===3-1&&2²<=8&&3²>8,所以我们找到了最终值,即 2

最后,我们便通过三种方法:JS 原生 API、暴力破解、二分法,完成了本次解题。


不折腾的前端,和咸鱼有什么区别!

LeetCode - 069 - x 的平方根(sqrtx)

jsliang 会每天更新一道 LeetCode 题解,从而帮助小伙伴们夯实原生 JS 基础,了解与学习算法与数据结构。

扫描上方二维码,关注 jsliang 的公众号,让我们一起折腾!

LeetCode - 069 - x 的平方根(sqrtx)
jsliang 的文档库 由 梁峻荣 采用 知识共享 署名-非商业性使用-相同方式共享 4.0 国际 许可协议进行许可。
基于https://github.com/LiangJunrong/document-library上的作品创作。
本许可协议授权之外的使用权限可以从 https://creativecommons.org/licenses/by-nc-sa/2.5/cn/ 处获得。


以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

视觉SLAM十四讲

视觉SLAM十四讲

高翔、张涛、等 / 电子工业出版社 / 2017-3 / 75

《视觉SLAM十四讲:从理论到实践》系统介绍了视觉SLAM(同时定位与地图构建)所需的基本知识与核心算法,既包括数学理论基础,如三维空间的刚体运动、非线性优化,又包括计算机视觉的算法实现,例如多视图几何、回环检测等。此外,还提供了大量的实例代码供读者学习研究,从而更深入地掌握这些内容。 《视觉SLAM十四讲:从理论到实践》可以作为对SLAM 感兴趣的研究人员的入门自学材料,也可以作为SLAM......一起来看看 《视觉SLAM十四讲》 这本书的介绍吧!

图片转BASE64编码
图片转BASE64编码

在线图片转Base64编码工具

UNIX 时间戳转换
UNIX 时间戳转换

UNIX 时间戳转换