·
·
文章目录
  1. 题目介绍
  2. 复杂度
  3. 解题思路

Plus One

题目介绍

LeetCode 66. Plus One,题目的意思给定一个非负数组表示一个数字,从高位向低位排,加一之后输出结果。

复杂度

时间复杂度: O(n), 空间复杂度: O(n)

解题思路

先把数组反向然后遍历,如果是 index == 0 就加一,记录下进位值 carry = sum / 10 和加一后的当前数字 reDigits[index] = sum % 10

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
func plusOne(_ digits: [Int]) -> [Int] {
var reDigits: [Int] = digits.reversed()
var carry = 0

for (index, digit) in reDigits.enumerated() {
let sum = index == 0 ? digit + 1 + carry : digit + carry
carry = sum / 10
reDigits[index] = sum % 10
}

if carry > 0 {
reDigits.append(carry)
}

return reDigits.reversed()
}
}

有个巧妙点的解法,按逆序遍历,把当前位置 + 1 后取余,并且如果当前位置 + 1 后不进位就直接返回数组,因为后面都不会进位了。走出循环还不返回说明还要在 index = 0 补上一位。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
import Foundation

class Solution {
func plusOne(_ digits: [Int]) -> [Int] {
var s: [Int] = digits
for i in s.enumerated().reversed() {
s[i.offset] += 1
s[i.offset] %= 10
if s[i.offset] != 0 {
return s
}
}
// 还没 return 说明要加 1
s.insert(1, at: 0)
return s
}
}
**版权声明**

Ivan’s Blog by Ivan Ye is licensed under a Creative Commons BY-NC-ND 4.0 International License.
叶帆创作并维护的叶帆的博客博客采用创作共用保留署名-非商业-禁止演绎4.0国际许可证

本文首发于Ivan’s Blog | 叶帆的博客博客( http://yeziahehe.com ),版权所有,侵权必究。

本文链接:http://yeziahehe.com/2017/11/07/PlusOne/

支持一下
扫一扫,支持yeziahehe
  • 微信扫一扫
  • 支付宝扫一扫