//
// 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: - 題目翻譯:
給定一個(gè)整數(shù)數(shù)組代表一個(gè)非負(fù)整數(shù)，將這個(gè)整數(shù)加1。
您可以假定這個(gè)整數(shù) 第一位不會(huì)是0,除了數(shù)字0本身。
數(shù)字在存儲的時(shí)候?qū)⒆钪匾臄?shù)字（即整數(shù)的最高位）放在數(shù)組的開頭。
*/
/* MARK: - 解題思路:
這是一道非常常規(guī)的整數(shù)加1的題目。根據(jù)題目意思整數(shù)123在數(shù)組中是這樣存儲的[1，2，3]。
所以，進(jìn)行加1操作的時(shí)候，需要倒著遍歷數(shù)組。
需要注意的一個(gè)地方就是要考慮進(jìn)位的問題。如果循環(huán)結(jié)束之后，產(chǎn)生了進(jìn)位，則數(shù)組需要在開頭插入1個(gè)值為1的新元素。
*/
/* MARK: - 復(fù)雜度分析:
分析
Java 中需要返回?cái)?shù)組，而這個(gè)數(shù)組在處理之前是不知道大小的，故需要對最后一個(gè)進(jìn)位單獨(dú)處理。
時(shí)間復(fù)雜度 O(n), 空間復(fù)雜度在最后一位有進(jìn)位時(shí)惡化為 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
// 這個(gè)判斷可以 減少循環(huán)次數(shù)
if carry == 0 {
break
}
index -= 1
}
// 循環(huán)結(jié)束 如果還有進(jìn)位 就在數(shù)組前面添加一個(gè)元素
if carry == 1 {
// 在以前的0位前面插入一個(gè)數(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]
}
