66.加一

作者: 花果山松鼠 | 来源:发表于2018-09-20 20:12 被阅读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

    相关文章

      网友评论

        本文标题:66.加一

        本文链接:https://www.haomeiwen.com/subject/fvannftx.html