//
// E_66_PlusOne.swift
// AlgorithmLeetCode
//
// Created by okerivy on 2017/3/7.
// Copyright ? 2017年 okerivy. All rights reserved.
// https://leetcode.com/problems/plus-one
import Foundation
// MARK: - 題目名稱: 66. Plus One
/* MARK: - 所屬類別:
標(biāo)簽: Array, Math
相關(guān)題目:
(M) Multiply Strings
(E) Add Binary
(M) Plus One Linked List
*/
/* MARK: - 題目英文:
Given a non-negative integer represented as a non-empty array of digits, plus one to the integer.
You may assume the integer do not contain any leading zero, except the number 0 itself.
The digits are stored such that the most significant digit is at the head of the list.
*/
/* MARK: - 題目翻譯:
給定一個整數(shù)數(shù)組代表一個非負(fù)整數(shù)卷扮，將這個整數(shù)加1荡澎。
您可以假定這個整數(shù) 第一位不會是0,除了數(shù)字0本身。
數(shù)字在存儲的時候?qū)⒆钪匾臄?shù)字（即整數(shù)的最高位）放在數(shù)組的開頭晤锹。
*/
/* MARK: - 解題思路:
這是一道非常常規(guī)的整數(shù)加1的題目摩幔。根據(jù)題目意思整數(shù)123在數(shù)組中是這樣存儲的[1，2鞭铆，3]或衡。
所以，進(jìn)行加1操作的時候衔彻，需要倒著遍歷數(shù)組薇宠。
需要注意的一個地方就是要考慮進(jìn)位的問題。如果循環(huán)結(jié)束之后艰额，產(chǎn)生了進(jìn)位澄港，則數(shù)組需要在開頭插入1個值為1的新元素。
*/
/* MARK: - 復(fù)雜度分析:
分析
Java 中需要返回數(shù)組柄沮，而這個數(shù)組在處理之前是不知道大小的回梧，故需要對最后一個進(jìn)位單獨處理。
時間復(fù)雜度 O(n), 空間復(fù)雜度在最后一位有進(jìn)位時惡化為 O(n), 當(dāng)然也可以通過兩次循環(huán)使得空間復(fù)雜度為 O(1).
*/
// MARK: - 代碼:
private class Solution {
func plusOne(_ digits: [Int]) -> [Int] {
return plusDigit(digits, 1)
}
private func plusDigit(_ digits: [Int], _ digit: Int) -> [Int] {
if digits.count == 0 {
return []
}
// 用carry表示進(jìn)位
var carry = digit
// 初始化為0的數(shù)組
// var numArr = [Int](repeating: 0, count: digits.count)
// 直接賦值
var numArr = digits
// 從末尾開始遍歷
var index = digits.count - 1
while index >= 0 {
// 和 = 當(dāng)前數(shù)字 + 進(jìn)位
let sum = digits[index] + carry
// 重新賦值
numArr[index] = sum % 10
// 獲取進(jìn)位
carry = sum / 10
// 這個判斷可以 減少循環(huán)次數(shù)
if carry == 0 {
break
}
index -= 1
}
// 循環(huán)結(jié)束 如果還有進(jìn)位 就在數(shù)組前面添加一個元素
if carry == 1 {
// 在以前的0位前面插入一個數(shù)據(jù)
numArr.insert(1, at: 0)
}
return numArr;
}
}
// MARK: - 測試代碼:
func plusOne() {
let array = [1,2,3,4,5]
print("改變前的數(shù)組 \(array)")
let numArr = Solution().plusOne(array)
print("改變后的的數(shù)組為 \(numArr)") // [1,2,3,4,6]
}
