数据结构和算法分析

66.加一

2018-09-20  本文已影响3人  花果山松鼠

一、题目原型:

给定一个由整数组成的非空数组所表示的非负整数,在该数的基础上加一。
最高位数字存放在数组的首位, 数组中每个元素只存储一个数字。
你可以假设除了整数 0 之外,这个整数不会以零开头。

二、题目意思剖析:

示例 1:
输入: [1,2,3]
输出: [1,2,4]
解释: 输入数组表示数字 123。

示例 2:
输入: [4,3,2,1]
输出: [4,3,2,2]
解释: 输入数组表示数字 4321。

三、解题思路:

误区:我一开始的想法是把数字+1,然后再分。
但是题目的数字并没有限制,所以,当去取余数然后*10的多少次方时,就越界了崩溃了。所以,这题不能这么做。

正解:递归,只能通过递归来算。

其实我们考虑该题的核心,应该集中于一点:该位+1后,是否=10,这是问题的核心。递归算法也是根据这个来展开的。
1.在这里我们先要将最后一位先判断,是否+1后=10。如果=10,就需要进一位,再去判断接下来的情况;如果<10,那就直接返回原数组了。
2.至于除了最后一位的情况,其实也是和前面一样判断。
3.问题核心:iscarry:是否需要进位,也就是前一位+1后是否等于10

// 递归 iscarry:是否进位,也就是他前一个数是不是等于10
func isCarry(_ index: inout Int, _ digits: inout [Int], _ iscarry: Bool) -> [Int] {
    
    if index < 0  {
        if iscarry {
            // 如果这个时候数组已经遍历完了,但是iscarry=true,说明还是进位,在最前面加一个1
            digits.insert(1, at: 0)
        }
        return digits
    }
    
    var bool: Bool = true
    if index == digits.count - 1 {
        
        let num = digits[index] + 1
        if num == 10 {
            digits[index] = 0
            bool = true
        }else {
            digits[index] = num
            bool = false
            return digits
        }
    }else {
        var num: Int = 0
        if iscarry { //如果是进位
            num = digits[index] + 1
            if num == 10 {
                digits[index] = 0
                bool = true
            }else {
                digits[index] = num
                bool = false
                return digits
            }
        }
    }
    
    index = index - 1
    return isCarry(&index, &digits, bool)
}
func plusOne(_ digits: [Int]) -> [Int] {
    
    var nums: [Int] = digits
    // 默认 index = 最后一位
    var index: Int = digits.count-1
    
    return isCarry(&index, &nums, false)
}

四、小结

耗时16毫秒,超过77.09%的提交记录,总提交数109

上一篇下一篇

猜你喜欢

热点阅读