小明思考

Just a software engineer
posts - 124, comments - 36, trackbacks - 0, articles - 0
  BlogJava :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理

+1

Posted on 2013-04-15 11:22 小明 阅读(1357) 评论(3)  编辑  收藏 所属分类: 数据结构和算法
问题给定一个有由数字构成的数组表示的数,求该数加1的结果。
public class Solution {
    public int[] plusOne(int[] digits) {
    }
}

很简单的问题,但是一遍写通过,还是要求基本功比较扎实。注意进位的处理。
Input                       Output

[0]

[1]

[1]

[2]

[9]

[1,0]

[1,0]

[1,1]

[9,9]

[1,0,0]

[1,2,3]

[1,2,4]

[9,9,9]

[1,0,0,0]

[8,9,9,9]

[9,0,0,0]

[1,0,0,0,0]

[1,0,0,0,1]

[9,8,7,6,5,4,3,2,1,0]

[9,8,7,6,5,4,3,2,1,1]


代码如下:

public class Solution {
    public int[] plusOne(int[] digits) {
        int extra = 1;
        for(int i=digits.length-1;i>=0;--i){
            int t = digits[i]+extra;
            if(t>=10){
                extra = 1;
                digits[i] = t-10;
            }
            else if(extra!=0){
                extra = 0;
                digits[i] = t;
                break;
            }
        }
        if(extra>0){
            int[] newDigits = new int[digits.length+1];
            newDigits[0] = extra;
            System.arraycopy(digits,0,newDigits,1,digits.length);
            return newDigits;
        }
        return  digits;
    }
}




评论

# re: +1[未登录]  回复  更多评论   

2013-04-15 15:42 by Harry
in scala:
def plusOne(list: List[Int], rem: Int): List[Int] = {
val l = list.reverse
l match {
case x :: xs => x + rem match {
case y if y >= 10 => plusOne(xs.reverse, 1) ::: (y % 10) :: Nil
case z => plusOne(xs.reverse, 0) ::: z :: Nil
}
case Nil => Nil
}
}
def main(args: Array[String]): Unit = {
val l = List(1, 3, 4, 8, 9, 9)
println(plusOne(l, 1))
}

# re: +1  回复  更多评论   

2013-04-15 17:18 by 小明
@Harry

你这递归调用,效率不高吧

# re: +1[未登录]  回复  更多评论   

2013-04-16 13:25 by Harry
:)

只有注册用户登录后才能发表评论。


网站导航: