Merge branch 'master' of https://github.com/azl397985856/leetcode

lucifer · lucifer · commit 6c32aaff52cf · 2020-04-09T18:52:03.000+08:00
diff --git a/problems/25.reverse-nodes-in-k-groups-cn.md b/problems/25.reverse-nodes-in-k-groups-cn.md
@@ -65,7 +65,7 @@ curr = temp;
 ![reverse k nodes in linked list](../assets/problems/25.reverse-nodes-in-k-groups-2.PNG)
 
 
->**NOTE**: 一般情况下对链表的操作，都有可能会引入一个新的`dummy node`，因为`head`有可能会改变。这里`head 从1->3`, 
+>**NOTE**: 一般情况下对链表的操作，都有可能会引入一个新的`dummy node`，因为`head`有可能会改变。这里`head 从1->3`,
 `dummy (List(0)) `保持不变。
 
 #### 复杂度分析
@@ -78,7 +78,7 @@ curr = temp;
 3. 对每一组进行翻转，更换起始和最后的位置
 4. 返回`dummy.next`.
 
-## 代码 (`Java/Python3`)
+## 代码 (`Java/Python3/javascript`)
 *Java Code*
 ```java
 class ReverseKGroupsLinkedList {
@@ -88,7 +88,7 @@ class ReverseKGroupsLinkedList {
       }
       ListNode dummy = new ListNode(0);
       dummy.next = head;
-  
+
       ListNode start = dummy;
       ListNode end = head;
       int count = 0;
@@ -105,21 +105,21 @@ class ReverseKGroupsLinkedList {
       }
       return dummy.next;
     }
-  
-    /** 
+
+    /**
      * reverse linked list from range (start, end), return last node.
-     * for example: 
+     * for example:
      * 0->1->2->3->4->5->6->7->8
      * |           |
      * start       end
-     * 
+     *
      * After call start = reverse(start, end)
-     * 
+     *
      * 0->3->2->1->4->5->6->7->8
      *          |  |
      *       start end
      *       first
-     * 
+     *
      */
     private ListNode reverse(ListNode start, ListNode end) {
       ListNode curr = start.next;
@@ -157,7 +157,7 @@ class Solution:
             else:
                 end = end.next
         return dummy.next
-    
+
     def reverse(self, start, end):
         prev, curr = start, start.next
         first = curr
@@ -168,7 +168,49 @@ class Solution:
             curr = temp
         start.next = prev
         first.next = curr
-        return first   
+        return first
+```
+
+*javascript code*
+```js
+/**
+ * @param {ListNode} head
+ * @param {number} k
+ * @return {ListNode}
+ */
+var reverseKGroup = function(head, k) {
+  // 标兵
+  let dummy = new ListNode()
+  dummy.next = head
+  let [start, end] = [dummy, dummy.next]
+  let count = 0
+  while(end) {
+    count++
+    if (count % k === 0) {
+      start = reverseList(start, end.next)
+      end = start.next
+    } else {
+      end = end.next
+    }
+  }
+  return dummy.next
+
+  // 翻转stat -> end的链表
+  function reverseList(start, end) {
+    let [pre, cur] = [start, start.next]
+    const first = cur
+    while(cur !== end) {
+      let next = cur.next
+      cur.next = pre
+      pre = cur
+      cur = next
+    }
+    start.next = pre
+    first.next = cur
+    return first
+  }
+};
+
 ```
 
 ## 参考（References)
@@ -178,13 +220,13 @@ class Solution:
 
 - 要求从后往前以`k`个为一组进行翻转。**(字节跳动（ByteDance）面试题)**
 
-    例子，`1->2->3->4->5->6->7->8, k = 3`, 
-    
+    例子，`1->2->3->4->5->6->7->8, k = 3`,
+
     从后往前以`k=3`为一组，
-    - `6->7->8` 为一组翻转为`8->7->6`， 
-    - `3->4->5`为一组翻转为`5->4->3`. 
+    - `6->7->8` 为一组翻转为`8->7->6`，
+    - `3->4->5`为一组翻转为`5->4->3`.
     - `1->2`只有2个nodes少于`k=3`个，不翻转。
-    
+
     最后返回： `1->2->5->4->3->8->7->6`
 
 这里的思路跟从前往后以`k`个为一组进行翻转类似，可以进行预处理：
diff --git a/problems/283.move-zeroes.md b/problems/283.move-zeroes.md
@@ -18,7 +18,7 @@ Minimize the total number of operations.
 ```
 ## 思路
 
-如果题目没有要求 modify in-place 的话，我们可以先遍历一遍将包含 0 的和不包含 0 的存到两个数字，
+如果题目没有要求 modify in-place 的话，我们可以先遍历一遍将包含 0 的和不包含 0 的存到两个数组，
 然后拼接两个数组即可。  但是题目要求 modify in-place， 也就是不需要借助额外的存储空间，刚才的方法
 空间复杂度是 O(n).
 
diff --git a/problems/32.longest-valid-parentheses.md b/problems/32.longest-valid-parentheses.md
@@ -44,9 +44,15 @@ s = '(())())'
 1. 第3点特征, 需要检查的字符是s[i-1]和s[i-2-dp[i-1]], 根据定义可知: i-1 >= dp[i-1], 但是i-2不一定大于dp[i-1], 因此, 需要检查越界;
 3. 第4点特征最容易遗漏, 还有就是不需要检查越界, 因为根据定义可知: i >= dp[i], 所以dp[i-dp[i]]的边界情况是dp[0];
 
+## 思路(栈)
+主要思路和常规的括号解法一样，遇到'('入栈，遇到')'出栈，并计算两个括号之间的长度。
+因为这个题存在非法括号对的情况且求是合法括号对的最大长度 所以有两个注意点是:
+1. **栈中存的是符号的下标**
+2. **当栈为空时且当前扫描到的符号是')'时，需要将这个符号入栈作为分割符**
+
 ## 代码
 
-* 语言支持: Python
+* 语言支持: Python, javascript
 
 Python Code:
 ```
@@ -75,6 +81,29 @@ class Solution:
         return mlen
 ```
 
+javascript code:
+```js
+// 用栈来解
+var longestValidParentheses = function(s) {
+  let stack = new Array()
+  let longest = 0
+  stack.push(-1)
+  for(let i = 0; i < s.length; i++) {
+    if (s[i] === '(') {
+      stack.push(i)
+    } else {
+      stack.pop()
+      if (stack.length === 0) {
+        stack.push(i)
+      } else {
+        longest = Math.max(longest, i - stack[stack.length - 1])
+      }
+    }
+  }
+  return longest
+};
+```
+
 ## 扩展
 
 1. 如果判断的不仅仅只有'('和')', 还有'[', ']', '{'和'}', 该怎么办?
diff --git a/problems/4.median-of-two-sorted-array.md b/problems/4.median-of-two-sorted-array.md
@@ -35,12 +35,12 @@ The median is (2 + 3)/2 = 2.5
 #### 解法一 - 暴力 （Brute Force）
 暴力解主要是要merge两个排序的数组`（A，B）`成一个排序的数组。
 
-用两个`pointer（i，j）`，`i` 从数组`A`起始位置开始，即`i=0`开始，`j` 从数组`B`起始位置， 即`j=0`开始. 
-一一比较 `A[i] 和 B[j]`, 
+用两个`pointer（i，j）`，`i` 从数组`A`起始位置开始，即`i=0`开始，`j` 从数组`B`起始位置， 即`j=0`开始.
+一一比较 `A[i] 和 B[j]`,
 1. 如果`A[i] <= B[j]`, 则把`A[i]` 放入新的数组中，i往后移一位，即 `i+1`.
 2. 如果`A[i] > B[j]`, 则把`B[j]` 放入新的数组中，j往后移一位，即 `j+1`.
 3. 重复步骤#1 和 #2，直到`i`移到`A`最后，或者`j`移到`B`最后。
-4. 如果`j`移动到`B`数组最后，那么直接把剩下的所有`A`依次放入新的数组中. 
+4. 如果`j`移动到`B`数组最后，那么直接把剩下的所有`A`依次放入新的数组中.
 5. 如果`i`移动到`A`数组最后，那么直接把剩下的所有`B`依次放入新的数组中.
 
 Merge的过程如下图。
@@ -76,7 +76,7 @@ Merge的过程如下图。
 1. 暴力求解，在线性时间内merge两个排好序的数组成一个数组。
 2. 二分查找，关键点在于
   - 要partition两个排好序的数组成左右两等份，partition需要满足`len(Aleft)+len(Bleft)=(m+n+1)/2 - m是数组A的长度， n是数组B的长度`
- 
+
   - 并且partition后 A左边最大(`maxLeftA`), A右边最小（`minRightA`), B左边最大（`maxLeftB`), B右边最小（`minRightB`) 满足
 `(maxLeftA <= minRightB && maxLeftB <= minRightA)`
 
@@ -127,7 +127,7 @@ class MedianTwoSortedArrayBruteForce {
     }
 }
 ```
-*解法二 - 二分查找（Binary Search*
+*解法二 - 二分查找（Binary Search)*
 ```java
 class MedianSortedTwoArrayBinarySearch {
   public static double findMedianSortedArraysBinarySearch(int[] nums1, int[] nums2) {
@@ -144,13 +144,13 @@ class MedianSortedTwoArrayBinarySearch {
         int i = lo + (hi - lo) / 2;
         // partition B position j
         int j = (m + n + 1) / 2 - i;
-        
+
         int maxLeftA = i == 0 ? Integer.MIN_VALUE : nums1[i - 1];
         int minRightA = i == m ? Integer.MAX_VALUE : nums1[i];
-  
+
         int maxLeftB = j == 0 ? Integer.MIN_VALUE : nums2[j - 1];
         int minRightB = j == n ? Integer.MAX_VALUE : nums2[j];
-  
+
         if (maxLeftA <= minRightB && maxLeftB <= minRightA) {
           // total length is even
           if ((m + n) % 2 == 0) {
@@ -171,3 +171,76 @@ class MedianSortedTwoArrayBinarySearch {
     }
 }
 ```
+
+## 代码 (javascript code)
+*解法一 - 暴力解法（Brute force）*
+```js
+/**
+ * @param {number[]} nums1
+ * @param {number[]} nums2
+ * @return {number}
+ */
+var findMedianSortedArrays = function(nums1, nums2) {
+  // 归并排序
+  const merged = []
+  let i = 0
+  let j = 0
+  while(i < nums1.length && j < nums2.length) {
+    if (nums1[i] < nums2[j]) {
+      merged.push(nums1[i++])
+    } else {
+      merged.push(nums2[j++])
+    }
+  }
+  while(i < nums1.length) {
+    merged.push(nums1[i++])
+  }
+  while(j < nums2.length) {
+    merged.push(nums2[j++])
+  }
+
+  const { length } = merged
+  return length % 2 === 1
+    ? merged[Math.floor(length / 2)]
+    : (merged[length / 2] + merged[length / 2 - 1]) / 2
+};
+```
+
+*解法二 - 二分查找（Binary Search)*
+```js
+/**
+ * 二分解法
+ * @param {number[]} nums1
+ * @param {number[]} nums2
+ * @return {number}
+ */
+var findMedianSortedArrays = function(nums1, nums2) {
+  // make sure to do binary search for shorten array
+  if (nums1.length > nums2.length) {
+    [nums1, nums2] = [nums2, nums1]
+  }
+  const m = nums1.length
+  const n = nums2.length
+  let low = 0
+  let high = m
+  while(low <= high) {
+    const i = low + Math.floor((high - low) / 2)
+    const j = Math.floor((m + n + 1) / 2) - i
+
+    const maxLeftA = i === 0 ? -Infinity : nums1[i-1]
+    const minRightA = i === m ? Infinity : nums1[i]
+    const maxLeftB = j === 0 ? -Infinity : nums2[j-1]
+    const minRightB = j === n ? Infinity : nums2[j]
+
+    if (maxLeftA <= minRightB && minRightA >= maxLeftB) {
+      return (m + n) % 2 === 1
+        ? Math.max(maxLeftA, maxLeftB)
+        : (Math.max(maxLeftA, maxLeftB) + Math.min(minRightA, minRightB)) / 2
+    } else if (maxLeftA > minRightB) {
+      high = i - 1
+    } else {
+      low = low + 1
+    }
+  }
+};
+```
diff --git a/problems/42.trapping-rain-water.md b/problems/42.trapping-rain-water.md
@@ -96,26 +96,16 @@ var trap = function(height) {
 Python Code:
 
 ```python
-
 class Solution:
-    def trap(self, height: List[int]) -> int:
-        maxLeft, maxRight, volum = 0, 0, 0
-        maxLeftStack, maxRightStack = [], []
-        for h in height:
-            if h > maxLeft:
-                maxLeftStack.append(h)
-                maxLeft = h
-            else:
-                maxLeftStack.append(maxLeft)
-        for h in height[::-1]:
-            if h > maxRight:
-                maxRightStack.append(h)
-                maxRight = h
-            else:
-                maxRightStack.append(maxRight)
-        maxRightStack = maxRightStack[::-1]
-        for i in range(1, len(height) - 1):
-            minSide = min(maxLeftStack[i], maxRightStack[i])
-            volum += minSide - height[i]
-        return volum      
+    def trap(self, heights: List[int]) -> int:
+        n = len(heights)
+        l, r = [0] * (n + 1), [0] * (n + 1)
+        ans = 0
+        for i in range(1, len(heights) + 1):
+            l[i] = max(l[i - 1], heights[i - 1])
+        for i in range(len(heights) - 1, 0, -1):
+            r[i] = max(r[i + 1], heights[i])
+        for i in range(len(heights)):
+            ans += max(0, min(l[i + 1], r[i]) - heights[i])
+        return ans     
 ```
diff --git a/thinkings/basic-data-structure.md b/thinkings/basic-data-structure.md
@@ -171,7 +171,7 @@ foo();
 
 ![basic-data-structure-call-stack](../assets/thinkings/basic-data-structure-call-stack.png)
 
-> 我画的图没有画出执行上下文中其他部分（this 和 scope 等）， 这部分是闭包的关键，而我这里不是将闭包的，是为了讲解栈的。
+> 我画的图没有画出执行上下文中其他部分（this 和 scope 等）， 这部分是闭包的关键，而我这里不是讲闭包的，是为了讲解栈的。
 
 > 社区中有很多“执行上下文中的 scope 指的是执行栈中父级声明的变量”说法，这是完全错误的， JS 是词法作用域，scope 指的是函数定义时候的父级，和执行没关系
 
diff --git a/thinkings/run-length-encode-and-huffman-encode.md b/thinkings/run-length-encode-and-huffman-encode.md
@@ -81,7 +81,11 @@ AAAAABBBBCCC
 
 ## 总结
 
-实际情况，我们先用游程编码一遍，然后再用 Huffman 再次编码一次。
+游程编码和Huffman都是无损压缩算法，即解压缩过程不会损失原数据任何内容。 实际情况，我们先用游程编码一遍，然后再用 Huffman 再次编码一次。几乎所有的无损压缩格式都用到了它们，比如PNG，GIF，PDF，ZIP等。
+
+对于有损压缩，通常是去除了人类无法识别的颜色，听力频率范围等。也就是说损失了原来的数据。 但由于人类无法识别这部分信息，因此很多情况下都是值得的。这种删除了人类无法感知内容的编码，我们称之为“感知编码”（也许是一个自创的新名词），比如JPEG，MP3等。关于有损压缩不是本文的讨论范围，感兴趣的可以搜素相关资料。 
+
+实际上，视频压缩的原理也是类似，只不过视频压缩会用到一些额外的算法，比如“时间冗余”，即仅存储变化的部分，对于不变的部分，存储一次就够了。
 
 ## 相关题目
 
