update

stonehank · stonehank · commit 9d1767e87024 · 2019-05-03T13:47:53.000+08:00
diff --git a/1-100/18.md b/1-100/18.md
@@ -35,6 +35,13 @@
 ```
 
 
+-----
+
+思路：
+
+时间复杂度`O(N^3)`，`3SUM`的基础上增加一个循环，参考`NO.15`。
+
+
 ```
 /**
  * @param {number[]} nums
diff --git a/1-100/20.md b/1-100/20.md
@@ -106,6 +106,13 @@
 ```
 
 
+-----
+
+思路：
+
+括号问题一般使用`stack`，按照开始必有结束的原则。
+
+
 ```
 /**
  * @param {string} s
diff --git a/1-100/22.md b/1-100/22.md
@@ -26,24 +26,36 @@
 ```
 
 
+-----
+
+思路：
+
+每一个位置都有2个选择，放置`(`或者`)`。
+
+如果`(`的数量超过了`n`说明一定不成立；
+
+如果`)`的数量超过了`(`的数量，也一定不成立；
+
+如果两个的数量都为`n`，那么就是一个有效的完整组合。
+
+
 ```
 /**
  * @param {number} n
  * @return {string[]}
  */
 var generateParenthesis = function(n) {
-    let s=''
-    let l="(",r=")"
-    let lN=0,rN=0
-    let res=[]
-    function dfs(s,n,lN,rN){
-      if(lN&gt;n || lN&lt;rN)return
-      if(lN===n &amp;&amp; rN===n)res.push(s)
-      dfs(s+l,n,lN+1,rN)
-      dfs(s+r,n,lN,rN+1)
-    }
-    dfs(s,n,lN,rN)
-    return res
+  let s=''
+  let l="(",r=")"
+  let res=[]
+  function dfs(s,n,lN,rN){
+    if(lN&gt;n || lN&lt;rN)return
+    if(lN===n &amp;&amp; rN===n)res.push(s)
+    dfs(s+l,n,lN+1,rN)
+    dfs(s+r,n,lN,rN+1)
+  }
+  dfs(s,n,0,0)
+  return res
 };
 
 
diff --git a/1-100/26.md b/1-100/26.md
@@ -108,6 +108,15 @@ for (int i = 0; i &lt; len; i++) {
 ```
 
 
+-----
+
+思路：
+
+对`nums`进行原地重排序，设定一个索引`k`，表示当前需要改变的位置，从`k=0`开始，如果发现有效(不重复)，则`nums[k++]=nums[i]`。
+
+最终前`k`位的都是无重复的数字。
+
+
 ```
 /**
  * @param {number[]} nums
diff --git a/1-100/27.md b/1-100/27.md
@@ -121,19 +121,26 @@ for (int i = 0; i &lt; len; i++) {
 ```
 
 
+-----
+
+思路：
+
+和`NO.26`基本一致，检查条件改变为只要当前`nums[i]!==val`，那么就可以添加到`k`对应的索引中。
+
+
 ```
 /**
  * @param {number[]} nums
  * @param {number} val
  * @return {number}
  */
 var removeElement = function(nums, val) {
-    let i=0,j=0
-    for(i=0;i&lt;nums.length;i++){
-        if(nums[i]!==val)
-            nums[j++]=nums[i]
-    }
-    return j
+  let k=0
+  for(let i=0;i&lt;nums.length;i++){
+    if(nums[i]!==val)
+      nums[k++]=nums[i]
+  }
+  return k
 };
 
 
diff --git a/1-100/29.md b/1-100/29.md
@@ -59,44 +59,89 @@
 
 
 
-```
+-----
+
+思路：
+
+* 使用减法，最直观的就是每次从被除数`dividend`中减去除数`divisor`，直到`dividend<divisor`，但是效率太低，因为数值是`32`位的数值，很容易`TLE`。
+
+* 使用叠加减法，和上面的思路差不多，但并不是每一次都只减去`divisor`，设定变量`m`，`n`分别为`dividend`还剩下的值，和当前被减的值。
+
+   每一次都减去`divisor*i`，直到`m<0`，重置`n`，继续重复。
+
+```js
 /**
  * @param {number} dividend
  * @param {number} divisor
  * @return {number}
  */
 var divide = function(dividend, divisor) {
-
-  // 0:+ 1:-
-  let neg=0
-  if(dividend&lt;0){neg=neg^1; dividend=-dividend}
-  if(divisor&lt;0){neg=neg^1; divisor=-divisor}
-  if(dividend&lt;divisor)return 0
-  let res=0
-  let count=0
+  let negative=(dividend ^ divisor)<0,
+      limit=Math.pow(2,31)
+  
+  if(dividend<divisor)return 0
+  
+  let res=0,count=0
   let n=0, m=dividend
   while(true){
     n+=divisor
-    if(m-n&gt;0){
+    if(m-n>0){
       count+=1
       m=m-n
       res+=count
     }else {
+      // 已经减到0了
       if(n===divisor){
         if(m-n===0)res++
         break
       }
+      // 重置
       count=0
       n=0
     }
   }
-  let limit=Math.pow(2,31)
-  if(neg===1){
-    if(res&gt;limit)return -limit
-    return -res
+  if(negative){
+    return Math.max(-res,-limit)
+  }else{
+    return Math.min(res,limit-1)
+  }
+};
+```
+* 使用位操作，位操作中`>>`相当于`/2`，`<<`相当于`*2`，因此对于`dividend`，找出一个`idx`，使得`dividend>>idx`后，刚好还比`divisor`大。
+
+    这说明`idx`对应的除数是有效的，这个除数就是`1<<idx`，再将`dividend`减去当前除数`divisor * ((1 << idx))`，也就是`(divisor << idx)`。
+
+    另外，由于`js`存在位溢出问题，因此在执行位运算时，计算绝对值`let absBit=Math.abs((dividend >> idx))`。    
+    
+
+
+```
+/**
+ * @param {number} dividend
+ * @param {number} divisor
+ * @return {number}
+ */
+var divide = function(dividend, divisor) {
+  let negative=(dividend ^ divisor)&lt;0,
+      limit=Math.pow(2,31)
+  dividend=Math.abs(dividend)
+  divisor=Math.abs(divisor)
+  if(dividend&lt;divisor)return 0
+  
+  let res=0,idx=32
+  while(idx&gt;=0){
+    // JS避免位溢出
+    let absBit=Math.abs((dividend &gt;&gt; idx))
+    if(absBit &gt;= divisor){
+      res+=(1 &lt;&lt; idx)
+      dividend-=(divisor &lt;&lt; idx)
+    }
+    idx--
+  }
+  if(negative){
+    return Math.max(-res,-limit)
   }else{
-    if(res&gt;limit-1)return limit-1
-    return res
+    return Math.min(res,limit-1)
   }
 };
 
diff --git a/1001-1100/1033.md b/1001-1100/1033.md
@@ -2,7 +2,7 @@
 
 难度：Easy
 
-相关话题：
+相关话题：`脑筋急转弯`
 
 三枚石子放置在数轴上，位置分别为  `a` ， `b` ， `c` 。
 
diff --git a/1001-1100/1034.md b/1001-1100/1034.md
@@ -2,7 +2,7 @@
 
 难度：Middle
 
-相关话题：
+相关话题：`深度优先搜索`
 
 给出一个二维整数网格 `grid` ，网格中的每个值表示该位置处的网格块的颜色。
 
diff --git a/1001-1100/1035.md b/1001-1100/1035.md
@@ -2,7 +2,7 @@
 
 难度：Middle
 
-相关话题：
+相关话题：`数组`
 
 我们在两条独立的水平线上按给定的顺序写下 `A` 和 `B` 中的整数。
 
diff --git a/1001-1100/1036.md b/1001-1100/1036.md
@@ -2,7 +2,7 @@
 
 难度：Hard
 
-相关话题：
+相关话题：`广度优先搜索`
 
 在一个 10^6 x 10^6 的网格中，每个网格块的坐标为 `(x, y)` ，其中 `0 &lt;= x, y &lt; 10^6` 。
 
