题目描述（简单难度）

66. Plus One - 图1

数组代表一个数字，[ 1, 2, 3 ] 就代表 123，然后给它加上 1，输出新的数组。数组每个位置只保存 1 位，也就是 0 到 9。

解法一 递归

先用递归，好理解一些。

  1. public int[] plusOne(int[] digits) {
  2.     return plusOneAtIndex(digits, digits.length - 1);
  3. }
  5. private int[] plusOneAtIndex(int[] digits, int index) {
  6.     //说明每一位都是 9 
  7.     if (index < 0) {
  8.         //新建一个更大的数组，最高位赋值为 1
  9.         int[] ans = new int[digits.length + 1];
  10.         ans[0] = 1;
  11.         //其他位赋值为 0，因为 java 里默认是 0，所以不需要管了 
  12.         return ans;
  13.     }
  14.     //如果当前位小于 9，直接加 1 返回
  15.     if (digits[index] < 9) {
  16.         digits[index] += 1;
  17.         return digits;
  18.     }
  20.     //否则的话当前位置为 0,
  21.     digits[index] = 0;
  22.     //考虑给前一位加 1
  23.     return plusOneAtIndex(digits, index - 1);
  25. }

时间复杂度：O（n）。

空间复杂度：

解法二 迭代

上边的递归，属于尾递归，完全没必要压栈，直接改成迭代的形式吧。

  1. public int[] plusOne(int[] digits) {
  2.     //从最低位遍历
  3.     for (int i = digits.length - 1; i >= 0; i--) {
  4.         //小于 9 的话，直接加 1，结束循环
  5.         if (digits[i] < 9) {
  6.             digits[i] += 1;
  7.             break;
  8.         } 
  9.         //否则的话置为 0
  10.         digits[i] = 0; 
  11.     }
  12.     //最高位如果置为 0 了，说明最高位产生了进位
  13.     if (digits[0] == 0) {
  14.         int[] ans = new int[digits.length + 1];
  15.         ans[0] = 1; 
  16.         digits = ans;
  17.     }
  18.     return digits;
  19. }

时间复杂度：O（n）。

空间复杂度：

总

很简单的一道题，理解题意就可以了。有的编译器不进行尾递归优化，他遇到这种尾递归还是不停压栈压栈压栈，所以这种简单的我们直接用迭代就行。

windliang wechat

添加好友一起进步~

如果觉得有帮助的话，可以点击 这里 给一个 star 哦 ^^

如果想系统的学习数据结构和算法，强烈推荐一个我之前学过的课程，可以点击 这里 查看详情