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

lucifer · lucifer · commit 3704f7b4cc5b · 2020-01-19T18:32:10.000+08:00
diff --git a/problems/200.number-of-islands.md b/problems/200.number-of-islands.md
@@ -53,7 +53,7 @@ Output: 3
 
 ## 代码
 
-* 语言支持：JS
+* 语言支持：JS, python3
 
 Javascript Code:
 ```js
@@ -94,5 +94,32 @@ var numIslands = function(grid) {
 };
 ```
 
+python code:
+
+``` python
+class Solution:
+    def numIslands(self, grid: List[List[str]]) -> int:
+        if not grid: return 0
+        
+        count = 0
+        for i in range(len(grid)):
+            for j in range(len(grid[0])):
+                if grid[i][j] == '1':
+                    self.dfs(grid, i, j)
+                    count += 1
+                    
+        return count
+    
+    def dfs(self, grid, i, j):
+        if i < 0 or j < 0 or i >= len(grid) or j >= len(grid[0]) or grid[i][j] != '1':
+            return 
+        grid[i][j] = '0'
+        self.dfs(grid, i + 1, j)
+        self.dfs(grid, i - 1, j)
+        self.dfs(grid, i, j + 1)
+        self.dfs(grid, i, j - 1)
+
+```
+
 
 
diff --git a/problems/236.lowest-common-ancestor-of-a-binary-tree.md b/problems/236.lowest-common-ancestor-of-a-binary-tree.md
@@ -70,60 +70,11 @@ p and q are different and both values will exist in the binary tree.
 
 ## 代码
 
-```js
+代码支持： JavaScript， Python3
 
+- JavaScript Code:
 
-/*
- * @lc app=leetcode id=236 lang=javascript
- *
- * [236] Lowest Common Ancestor of a Binary Tree
- *
- * https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree/description/
- *
- * algorithms
- * Medium (35.63%)
- * Total Accepted:    267.3K
- * Total Submissions: 729.2K
- * Testcase Example:  '[3,5,1,6,2,0,8,null,null,7,4]\n5\n1'
- *
- * Given a binary tree, find the lowest common ancestor (LCA) of two given
- * nodes in the tree.
- *
- * According to the definition of LCA on Wikipedia: “The lowest common ancestor
- * is defined between two nodes p and q as the lowest node in T that has both p
- * and q as descendants (where we allow a node to be a descendant of itself).”
- *
- * Given the following binary tree:  root = [3,5,1,6,2,0,8,null,null,7,4]
- *
- *
- *
- * Example 1:
- *
- *
- * Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
- * Output: 3
- * Explanation: The LCA of nodes 5 and 1 is 3.
- *
- *
- * Example 2:
- *
- *
- * Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
- * Output: 5
- * Explanation: The LCA of nodes 5 and 4 is 5, since a node can be a descendant
- * of itself according to the LCA definition.
- *
- *
- *
- *
- * Note:
- *
- *
- * All of the nodes' values will be unique.
- * p and q are different and both values will exist in the binary tree.
- *
- *
- */
+```js
 /**
  * Definition for a binary tree node.
  * function TreeNode(val) {
@@ -147,6 +98,32 @@ var lowestCommonAncestor = function(root, p, q) {
 };
 ```
 
+- Python Code:
+
+``` python
+# Definition for a binary tree node.
+# class TreeNode:
+#     def __init__(self, x):
+#         self.val = x
+#         self.left = None
+#         self.right = None
+
+class Solution:
+    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
+        if not root or root == p or root == q:
+            return root
+        left = self.lowestCommonAncestor(root.left, p, q)
+        right = self.lowestCommonAncestor(root.right, p, q)
+        
+        if not left:
+            return right
+        if not right:
+            return left
+        else:
+            return root
+
+```
+
 ## 扩展
 如果递归的结束条件改为`if (!root || root.left === p || root.right === q) return root;` 代表的是什么意思，对结果有什么样的影响？
 
diff --git a/problems/75.sort-colors.md b/problems/75.sort-colors.md
@@ -19,77 +19,55 @@ First, iterate the array counting number of 0's, 1's, and 2's, then overwrite ar
 Could you come up with a one-pass algorithm using only constant space?
 
 ## 思路
+这个问题是典型的荷兰国旗问题 （https://en.wikipedia.org/wiki/Dutch_national_flag_problem）。 因为我们可以将红白蓝三色小球想象成条状物，有序排列后正好组成荷兰国旗。
 
-其实就是排序，而且没有要求稳定性，就是用啥排序算法都行。
-题目并没有给出数据规模，因此我默认数据量不大，直接选择了冒泡排序
-
-## 关键点解析
-
-冒泡排序的时间复杂度是N平方，无法优化，但是可以进一步优化常数项，
-比如循环的起止条件。 由于每一次遍历都会将最后一位“就位”，因此内层循环的截止条件就可以是
- `nums.length - i`， 而不是 `nums.length`, 可以省一半的时间。
-
-
-## 代码
-
-```js
-/*
- * @lc app=leetcode id=75 lang=javascript
- *
- * [75] Sort Colors
- *
- * https://leetcode.com/problems/sort-colors/description/
- *
- * algorithms
- * Medium (41.41%)
- * Total Accepted:    297K
- * Total Submissions: 716.1K
- * Testcase Example:  '[2,0,2,1,1,0]'
- *
- * Given an array with n objects colored red, white or blue, sort them in-place
- * so that objects of the same color are adjacent, with the colors in the order
- * red, white and blue.
- * 
- * Here, we will use the integers 0, 1, and 2 to represent the color red,
- * white, and blue respectively.
- * 
- * Note: You are not suppose to use the library's sort function for this
- * problem.
- * 
- * Example:
- * 
- * 
- * Input: [2,0,2,1,1,0]
- * Output: [0,0,1,1,2,2]
- * 
- * Follow up:
- * 
- * 
- * A rather straight forward solution is a two-pass algorithm using counting
- * sort.
- * First, iterate the array counting number of 0's, 1's, and 2's, then
- * overwrite array with total number of 0's, then 1's and followed by 2's.
- * Could you come up with a one-pass algorithm using only constant space?
- * 
- * 
- */
-/**
- * @param {number[]} nums
- * @return {void} Do not return anything, modify nums in-place instead.
- */
-var sortColors = function(nums) {
-    function swap(nums, i, j) {
-       const temp = nums[i];
-       nums[i] = nums[j];
-       nums[j] = temp; 
-    }
-    for (let i = 0; i < nums.length - 1; i++) {
-        for (let j = 0; j < nums.length - i; j++) {
-            if (nums[j] < nums[j -1]) {
-                swap(nums, j - 1 , j)
-            }
-            
-        }      
-    }
-};
+有两种解决思路。
+
+## 解法一
+- 遍历数组，统计红白蓝三色球（0，1，2）的个数
+- 根据红白蓝三色球（0，1，2）的个数重排数组
+
+这种思路的时间复杂度：$O(n)$，需要遍历数组两次。
+
+## 解法二
+
+我们可以把数组分成三部分，前部（全部是0），中部（全部是1）和后部（全部是2）三个部分。每一个元素（红白蓝分别对应0、1、2）必属于其中之一。将前部和后部各排在数组的前边和后边，中部自然就排好了。
+
+我们用三个指针，设置两个指针begin指向前部的末尾的下一个元素（刚开始默认前部无0，所以指向第一个位置），end指向后部开头的前一个位置（刚开始默认后部无2，所以指向最后一个位置），然后设置一个遍历指针current，从头开始进行遍历。
+
+这种思路的时间复杂度也是$O(n)$, 只需要遍历数组一次。
+
+### 关键点解析
+
+
+- 荷兰国旗问题
+- counting sort
+
+### 代码
+
+代码支持： Python3
+
+Python3 Code:
+
+``` python
+class Solution:
+    def sortColors(self, nums: List[int]) -> None:
+        """
+        Do not return anything, modify nums in-place instead.
+        """
+        p0 = cur = 0
+        p2 = len(nums) - 1
+        
+        while cur <= p2:
+            if nums[cur] == 0:
+                nums[cur], nums[p0] = nums[p0], nums[cur]
+                p0 += 1
+                cur += 1
+            elif nums[cur] == 2:
+                nums[cur], nums[p2] = nums[p2], nums[cur]
+                p2 -= 1
+            else:
+                cur += 1
 ```
+
+
diff --git a/problems/80.remove-duplicates-from-sorted-array-ii.md b/problems/80.remove-duplicates-from-sorted-array-ii.md
@@ -55,7 +55,7 @@ for (int i = 0; i < len; i++) {
 
 - 初始化快慢指针 slow ， fast ，全部指向索引为 0 的元素。
 - fast 每次移动一格
-- 满指针选择性移动，即只有写入数据之后才移动。是否写入数据取决于 slow - 2 对应的数字和 fast 对应的数字是否一致。
+- 慢指针选择性移动，即只有写入数据之后才移动。是否写入数据取决于 slow - 2 对应的数字和 fast 对应的数字是否一致。
 - 如果一致，我们不应该写。 否则我们就得到了三个相同的数字，不符合题意
 - 如果不一致，我们需要将 fast 指针的数据写入到 slow 指针。
 - 重复这个过程，直到 fast 走到头，说明我们已无数字可写。
