:-: 4.1 加一 * * * * * **题干：** 给定一个由整数组成的非空数组所表示的非负整数，在该数的基础上加一。最高位数字存放在数组的首位， 数组中每个元素只存储一个数字。你可以假设除了整数 0 之外，这个整数不会以零开头。 示例 1: ~~~ 输入: [1,2,3] 输出: [1,2,4] 解释: 输入数组表示数字 123。 ~~~ 示例 2: ~~~ 输入: [4,3,2,1] 输出: [4,3,2,2] 解释: 输入数组表示数字 4321。 ~~~ **题目分析：** 该题的题图也就是末尾数字加一而已。 **新手有可能遇到的解题思路陷阱：** 有可能我们在两个点上出错：满十进一，和数组数字都为九，首位数字满十进一时位进一，同时数组长度要加一。 **解题思路分析以及代码实现：** 第一种思路：首先判断加一后是否需要进位，如果进位则继续循环，如不进位则循环结束，返回数组，在循环中设下进位标识符，若进位则进位标识符为true，当循环从头到尾，如果首位数字还需进位，此时应该新建数组，同时数组首位置为一，其他默认为零（这是所有原数组所有数字都为九的情况）。 第一种思路代码： ~~~ public static int[] plusOne(int[] digits) { boolean sign = false; for (int i = digits.length - 1; i >= 0; i--) { sign = false; if (digits[i] + 1 == 10) { digits[i] = 0; sign = true; continue; } else { digits[i] = digits[i] + 1; break; } } if (sign) { int nums[] = new int[digits.length + 1]; nums[0] = 1; return nums; } return digits; ~~~ **复杂度分析** 时间复杂度：O(n)。 空间复杂度：O(1)。 第二种思路：不需进位标识符，我们只要从末尾数字到首位数字关注是否为九或者是否加一为十，首先判断末尾数字是否为九，若为九，则置为零，继续循环判断，直至到某一位置数字不为九，加一后返回数组或者直至循环结束，另外创建数字，首位数字置为一，其他默认为零（这是所有原数组所有数字都为九的情况）。 第二种思路代码： ~~~ public static int[] plusOne(int[] digits) { int len = digits.length; for (int i = len - 1; i >= 0; i--) { if (digits[i] == 9) { digits[i] = 0; } else { digits[i] += 1; return digits; } } int[] sum = new int[len + 1]; sum[0] = 1; return sum; } ~~~ **复杂度分析** 时间复杂度：O(n)。 空间复杂度：O(1)。 **若有理解错误的、写错的地方、更好的思路，方法，望各位读者评论或者发邮件指正或指点我，不胜感激。**