Create 66.plus-one.md

daydaygo · daydaygo · commit 25d06945e87b · 2020-11-10T17:21:43.000+08:00
diff --git a/problems/66.plus-one.md b/problems/66.plus-one.md
@@ -0,0 +1,191 @@
+# 题目地址(66. 加一)
+
+https://leetcode-cn.com/problems/plus-one
+
+## 题目描述
+
+```
+给定一个由整数组成的非空数组所表示的非负整数，在该数的基础上加一。
+
+最高位数字存放在数组的首位， 数组中每个元素只存储单个数字。
+
+你可以假设除了整数 0 之外，这个整数不会以零开头。
+
+示例 1:
+
+输入: [1,2,3]
+输出: [1,2,4]
+解释: 输入数组表示数字 123。
+示例 2:
+
+输入: [4,3,2,1]
+输出: [4,3,2,2]
+解释: 输入数组表示数字 4321。
+```
+
+> lucifer 提示： 不要加直接数组转化为数字做加法再转回来。
+
+## 前置知识
+
+- 数组的遍历(正向遍历和反向遍历)
+
+## 思路
+
+这道题其实我们可以把它想象成小学生练习加法，只不过现在是固定的“加一”那么我们只需要考虑如何通过遍历来实现这个加法的过程就好了。
+
+加法我们知道要从低位到高位进行运算，那么只需要对数组进行一次反向遍历即可。
+
+伪代码：
+
+```java
+for(int i = n - 1; i > - 1; i --) {
+  内部逻辑
+}
+
+```
+
+内部逻辑的话，其实有三种情况：
+
+```
+1. 个位上的数字小于9
+    17
++   1
+= 18
+2. 个位数上等于9，其他位数可以是0-9的任何数，但是首位不等于9
+    199
++     1
+=  200
+
+    109
++      1
+=  110
+3. 所有位数都为9
+    99
++    1
+= 100
+
+      999
++       1
+=  1000
+```
+
+第一种情况是最简单的，我们只需将数组的最后一位进行+1 操作就好了
+
+第二种情况稍微多了一个步骤：我们需要把个位的 carry 向前进一位并在计算是否有更多的进位
+
+第三种其实和第二种是一样的操作，只是由于我们知道数组的长度是固定的，所以当我们遇到情况三的时候需要扩大数组的长度。我们只需要在结果数组前多加上一位就好了。
+
+```js
+// 首先我们要从数组的最后一位开始我们的计算得出我们新的sum
+sum = arr[arr.length - 1] + 1
+
+// 接下来我们需要判断这个新的sum是否超过9
+sum > 9 ?
+
+// 假如大于 9, 那么我们会更新这一位为 0 并且将carry值更改为1
+carry = 1
+arr[i] = 0
+
+// 假如不大于 9，更新最后一位为sum并直接返回数组
+arr[arr.length - 1] = sum
+return arr
+
+// 接着我们要继续向数组的倒数第二位重复进行我们上一步的操作
+...
+
+// 当我们完成以后，如果数组第一位时的sum大于0，那么我们就要给数组的首位增添一个1
+result = new array with size of arr.length + 1
+result[0] = 1
+result[1] ...... result[result.length - 1]  = 0
+```
+
+## 代码
+
+代码支持：Python3，JS, Go, PHP
+
+Python3 Code：
+
+```py
+class Solution:
+    def plusOne(self, digits: List[int]) -> List[int]:
+        carry = 1
+        for i in range(len(digits) - 1, -1, -1):
+            digits[i], carry = (carry + digits[i]) % 10, (carry + digits[i]) // 10
+        return [carry] + digits if carry else digits
+```
+
+JS Code：
+
+```js
+var plusOne = function (digits) {
+  var carry = 1; // 我们将初始的 +1 也当做是一个在个位的 carry
+  for (var i = digits.length - 1; i > -1; i--) {
+    if (carry) {
+      var sum = carry + digits[i];
+      digits[i] = sum % 10;
+      carry = sum > 9 ? 1 : 0; // 每次计算都会更新下一步需要用到的 carry
+    }
+  }
+  if (carry === 1) {
+    digits.unshift(1); // 如果carry最后停留在1，说明有需要额外的一个长度 所以我们就在首位增添一个 1
+  }
+  return digits;
+};
+```
+
+Go code:
+
+```go
+func plusOne(digits []int) []int {
+	for i := len(digits) - 1; i >= 0; i-- {
+		digits[i]++
+		if digits[i] != 10 { // 不产生进位, 直接返回
+			return digits
+		}
+		digits[i] = 0 // 产生进位, 继续计算下一位
+	}
+	// 全部产生进位
+	digits[0] = 1
+	digits = append(digits, 0)
+	return digits
+}
+```
+
+PHP code:
+
+```php
+class Solution {
+
+    /**
+     * @param Integer[] $digits
+     * @return Integer[]
+     */
+    function plusOne($digits) {
+        $len = count($digits);
+        for ($i = $len - 1; $i >= 0; $i--) {
+            $digits[$i]++;
+            if ($digits[$i] != 10) { // 不产生进位, 直接返回
+                return $digits;
+            }
+            $digits[$i] = 0; // 产生进位, 继续计算下一位
+        }
+        // 全部产生进位
+        $digits[0] = 1;
+        $digits[$len] = 0;
+        return $digits;
+    }
+}
+```
+
+**复杂度分析**
+
+- 时间复杂度：$O(N)$
+- 空间复杂度：$O(1)$
+
+## 相关题目
+
+- [面试题 02.05. 链表求和](https://leetcode-cn.com/problems/sum-lists-lcci/)
+
+大家对此有何看法，欢迎给我留言，我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库：https://github.com/azl397985856/leetcode 。 目前已经 37K star 啦。
+
+大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。
