LeetCode - 066 - 加一(plus-one)

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

内容简介:LeetCode - 066 - 加一(plus-one)

Create by jsliang on 2019-06-11 07:52:37
Recently revised in 2019-06-11 08:59:18

一 目录

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

| 目录 | | --- | | 一 目录 | | 二 前言 | | 三 解题 | |  3.1 解题 - 数学运算 |

二 前言

  • 难度:简单

  • 涉及知识:数组

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

  • 题目内容

  1. 给定一个由整数组成的非空数组所表示的非负整数,在该数的基础上加一。

  2. 最高位数字存放在数组的首位, 数组中每个元素只存储一个数字。

  3. 你可以假设除了整数 0 之外,这个整数不会以零开头。

  4. 示例 1:

  5. 输入: [1,2,3]

  6. 输出: [1,2,4]

  7. 解释: 输入数组表示数字 123

  8. 示例 2:

  9. 输入: [4,3,2,1]

  10. 输出: [4,3,2,2]

  11. 解释: 输入数组表示数字 4321

三 解题

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

3.1 解法 - 数学运算

  • 解题代码

  1. var plusOne = function(digits) {

  2. for (let i = digits.length - 1; i >=0; i--) {

  3. digits[i]++;

  4. digits[i] = digits[i] % 10;

  5. if (digits[i] > 0) {

  6. return digits;

  7. }

  8. }

  9. return [1, ...digits];

  10. };

  • 执行测试

  1. digits: [9,9,9]

  2. return

  1. [1, 0, 0, 0]

  • LeetCode Submit

  1. Accepted

  2. 109/109 cases passed (76 ms)

  3. Your runtime beats 94.21 % of javascript submissions

  4. Your memory usage beats 46.4 % of javascript submissions (33.7 MB)

  • 解题思路

看到题目,一开始 jsliang 觉得 so easy 啦,于是:

  1. var plusOne = function(digits) {

  2. return String(Number(digits.join('')) + 1).split('');

  3. };

然后它告诉我报错了:

  1. × Wrong Answer

  2. × 69/109 cases passed (N/A)

  3. × testcase: '[6,1,4,5,3,9,0,1,9,5,1,8,6,7,0,5,5,4,3]'

  4. × answer: [6,1,4,5,3,9,0,1,9,5,1,8,6,7,0,5,0,0,0]

  5. × expected_answer: [6,1,4,5,3,9,0,1,9,5,1,8,6,7,0,5,5,4,4]

  6. × stdout:

发愣了几秒,于是我百度了下 JS 的最大值: 9007199254740992(16 位数),而测试需要计算的数字为: 6145390195186705543(19 位数)。

众所周知,JS 超过最大值后,计算会出现不精确的问题,因此 6145390195186705543+1 后会出现答案: 6145390195186705000

所以想了另外一个法子:

  1. var plusOne = function(digits) {

  2. if (digits[digits.length - 1] === 9) {

  3. return String(Number(digits.join('')) + 1).split('');

  4. }

  5. digits[digits.length - 1] = digits[digits.length - 1] + 1;

  6. return digits;

  7. };

这个法子,对末尾是 9 的进行转字符串再转数字,加一后再转字符串并转成数组。对末尾不是 9 的,直接进行后面一位的操作。

我以为我能过,结果还是:so naive!

  1. × Wrong Answer

  2. × 104/109 cases passed (N/A)

  3. × testcase: '[5,2,2,6,5,7,1,9,0,3,8,6,8,6,5,2,1,8,7,9,8,3,8,4,7,2,5,8,9]'

  4. × answer: [5,NaN,2,2,6,5,7,1,9,0,3,8,6,8,6,5,2,NaN,NaN,2,8]

  5. × expected_answer: [5,2,2,6,5,7,1,9,0,3,8,6,8,6,5,2,1,8,7,9,8,3,8,4,7,2,5,9,0]

  6. × stdout:

还是输在了 JS 超过最大值的位置。

只能认输,寻求题解:

  1. var plusOne = function(digits) {

  2. for (let i = digits.length - 1; i >=0; i--) {

  3. digits[i]++;

  4. digits[i] = digits[i] % 10;

  5. if (digits[i] > 0) {

  6. return digits;

  7. }

  8. }

  9. return [1, ...digits];

  10. };

题解 中使用的是 Java 解题思路,不过无大碍,转换成 JavaScript 就行了。

那么它这个什么意思呢?

首先,末尾开始遍历,正常情况下直到 i 小于 0 的时候终止循环。

然后,当碰到 111236 这类末尾非 9 的情况时。

  1. 我们会先让其 (末位+1)%10。因为我们知道, 1 至 9 中任意的数 %10,得到的答案还是 1-9,但是 10%10,得到的答案是 0 !

  2. 所以当 111、 236 这种情况,末尾数字 (1+1)%10、 (6+1)%10 后,得到的数字 2 和 7 会大于 0。因为它大于 0 ,所以我们直接 return 出来即可。

  3. 综上,小伙伴们可以先想想 989 的计算情况。

最后,当碰到 999 这类情况时。循环会执行到最后一位,因为它是极致情况,最后遍历出来的是 [0,0,0],这时候,我们只需要往数组首位添加一个 1 即可,所以我们使用 ES6 的 [...] 扩展运算符来快速达到我们的目的。

如何使用 unshift() 方法来添加?

  1. var plusOne = function(digits) {

  2. for (let i = digits.length - 1; i >=0; i--) {

  3. digits[i]++;

  4. digits[i] = digits[i] % 10;

  5. if (digits[i] > 0) {

  6. return digits;

  7. }

  8. }

  9. digits.unshift(1);

  10. return digits;

  11. };


jsliang 广告推送:
也许小伙伴想了解下云服务器
或者小伙伴想买一台云服务器
或者小伙伴需要续费云服务器
欢迎点击 云服务器推广 查看!

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


以上所述就是小编给大家介绍的《LeetCode - 066 - 加一(plus-one)》,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持!

查看所有标签

猜你喜欢:

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

高性能网站建设指南(第二版)

高性能网站建设指南(第二版)

Steve Souders / 刘彦博 / 电子工业出版社 / 2015-5 / 55.00元

《高性能网站建设指南:前端工程师技能精髓》结合Web 2.0以来Web开发领域的最新形势和特点,介绍了网站性能问题的现状、产生的原因,以及改善或解决性能问题的原则、技术技巧和最佳实践。重点关注网页的行为特征,阐释优化Ajax、CSS、JavaScript、Flash和图片处理等要素的技术,全面涵盖浏览器端性能问题的方方面面。在《高性能网站建设指南:前端工程师技能精髓》中,作者给出了14条具体的优化......一起来看看 《高性能网站建设指南(第二版)》 这本书的介绍吧!

SHA 加密
SHA 加密

SHA 加密工具

XML、JSON 在线转换
XML、JSON 在线转换

在线XML、JSON转换工具

HEX HSV 转换工具
HEX HSV 转换工具

HEX HSV 互换工具