update 397

feiyutalk · feiyutalk · commit 0074d81f747a · 2018-04-13T11:14:42.000+08:00
diff --git a/problems/397. Integer Replacement/README.md b/problems/397. Integer Replacement/README.md
@@ -1,5 +1,15 @@
 # 397. Integer Replacement
 
+## #1 BFS[AC]
+
+### 思路
+
+把每个数字看做图中的一个节点，两个节点之间是否有边相连，通过`n %2 == 0 -> n/2`和`n % 2 != 0-> n+1, n-1`这个条件来判断，这样就把问题看做是一个图。最后，通过广度优先遍历找到最近的路径。
+
+![Screen Shot 2018-04-13 at 11.05.31](../../../../../../../Desktop/Screen Shot 2018-04-13 at 11.05.31.png)
+
+### 算法
+
 ```java
 class Solution {
     public int integerReplacement(int n) {
@@ -28,3 +38,33 @@ class Solution {
 }
 ```
 
+上面例子的执行方式如下所示：
+
+![Screen Shot 2018-04-13 at 11.07.08](../../../../../../../Desktop/Screen Shot 2018-04-13 at 11.07.08.png)
+
+### 复杂度分析：
+
+- ？
+- 空间复杂度：$O(logn)$
+
+## #2 位操作[AC]
+
+### 算法
+
+```java
+public int integerReplacement(int n) {
+    int c = 0;
+    while (n != 1) {
+        if ((n & 1) == 0) {
+            n >>>= 1;
+        } else if (n == 3 || Integer.bitCount(n + 1) > Integer.bitCount(n - 1)) {
+            --n;
+        } else {
+            ++n;
+        }
+        ++c;
+    }
+    return c;
+}
+```
+
