初级算法-数组-加一

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

最高位数字存放在数组的首位， 数组中每个元素只存储单个数字。
你可以假设除了整数 0 之外，这个整数不会以零开头。

提示：
1 <= digits.length <= 100
0 <= digits[i] <= 9

摘一个示例做个说明.
示例 1：
输入：digits = [1,2,3]
输出：[1,2,4]
解释：输入数组表示数字 123。

条件分析:

1. 只存储单个数字 -> 每一个元素都是 0 - 9
2. 最高位存储在数组首位 -> 数字大小是从前往后的
3. 不会以0开头,除了单数字0

解决思路1:

1. 数组加一,说明从后往前加1
2. 根据分析1、2,当最后为9时,需要进1.

常规办法采用可变数组去承接,然后判断数据是否为9,为9则进1,然后存储求余10后的数据.不是则直接存储.

解决思路2:思路2也是思路1的优化

根据分析1、2,说明不需要全部循环完数组,只要最后一个不为9,则加1.这时候该数组就是返回的数据.

判断是否为9,不是则加1返回.是9则继续循环.全部为9的话,首部加1表示进位.

代码实现-Swift版本:

思路1代码:

func plusOne(_ digits: [Int]) -> [Int] {
    /**
     先定义变量是否进一,然后根据当前值判断是否继续进一,如果进一,则加0,不进一则直接加.对首位和末尾做判断处理
     */
    var array: [Int] = []
    var isAdd: Bool = (digits.last! == 9)
    
    for i in 0 ..< digits.count {
        let tmp = digits[digits.count - 1 - i]
        if isAdd {
            array.insert((tmp + 1) % 10, at: 0)
            isAdd = (tmp + 1) > 9
            if isAdd && i == digits.count - 1{
                array.insert(1, at: 0)
            }
        }else{
            if i != 0 {
                array.insert(tmp, at: 0)
            }else{
                array.insert(tmp + 1, at: 0)
            }
        }
    }
    
    return array
}

加一 标志位 提交结果.jpg

思路2代码:

func plusOne(_ digits: [Int]) -> [Int] {
    /**
     先定义可变数组,然后判断是否为9,
     如果是则该数据为0,继续循环,不是则加1返回.
     如果全部为9则在返回前加一.
     时间0ms, 100% 内存13.8MB, 20.2%
     */
    var array = digits
    for i in (0 ..< array.count).reversed() {
        // 是9则置零,然后继续
        if array[i] == 9 {
            array[i] = 0
        }else{
            // 不是9,直接加一结束
            array[i] += 1
            return array
        }
    }
    // 全是9则进1
    array.insert(1, at: 0)
    return array
}

加一 直接判断 提交结果.jpg

测试用例:

let array1 = [2,9,9]

考察要点:

• 数组
• 数学