Merge branch 'youngyangyang04:master' into master

TwStarLord · Jun 29, 2021 · f940012 · f940012
2 parents dc03975 + 56045e0
commit f940012
Show file tree

Hide file tree

Showing 6 changed files with 159 additions and 113 deletions.
diff --git a/problems/0235.二叉搜索树的最近公共祖先.md b/problems/0235.二叉搜索树的最近公共祖先.md
@@ -313,65 +313,49 @@ func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
 }
 ```
 
-
-JavaScript版本
-> 递归
-
+JavaScript版本：
+1. 使用递归的方法
 ```javascript
-/**
- * Definition for a binary tree node.
- * function TreeNode(val) {
- *     this.val = val;
- *     this.left = this.right = null;
- * }
- */
-
-/**
- * @param {TreeNode} root
- * @param {TreeNode} p
- * @param {TreeNode} q
- * @return {TreeNode}
- */
 var lowestCommonAncestor = function(root, p, q) {
-    if(root.val > p.val && root.val > q.val)
-        return lowestCommonAncestor(root.left, p , q);
-    else if(root.val < p.val && root.val < q.val) 
-        return lowestCommonAncestor(root.right, p , q);
+    // 使用递归的方法
+    // 1. 使用给定的递归函数lowestCommonAncestor
+    // 2. 确定递归终止条件
+    if(root === null) {
+        return root;
+    }
+    if(root.val>p.val&&root.val>q.val) {
+        // 向左子树查询
+        let left = lowestCommonAncestor(root.left,p,q);
+        return left !== null&&left;
+    }
+    if(root.val<p.val&&root.val<q.val) {
+        // 向右子树查询
+        let right = lowestCommonAncestor(root.right,p,q);
+        return right !== null&&right;
+    }
     return root;
 };
 ```
-
-> 迭代
-
+2. 使用迭代的方法
 ```javascript
-/**
- * Definition for a binary tree node.
- * function TreeNode(val) {
- *     this.val = val;
- *     this.left = this.right = null;
- * }
- */
-
-/**
- * @param {TreeNode} root
- * @param {TreeNode} p
- * @param {TreeNode} q
- * @return {TreeNode}
- */
 var lowestCommonAncestor = function(root, p, q) {
-    while(1) {
-        if(root.val > p.val && root.val > q.val)
+    // 使用迭代的方法
+    while(root) {
+        if(root.val>p.val&&root.val>q.val) {
             root = root.left;
-        else if(root.val < p.val && root.val < q.val)
+        }else if(root.val<p.val&&root.val<q.val) {
             root = root.right;
-        else
-            break;
+        }else {
+            return root;
+        }
+
     }
-    return root;
+    return null;
 };
 ```
 
 
+
 -----------------------
 * 作者微信：[程序员Carl](https://mp.weixin.qq.com/s/b66DFkOp8OOxdZC_xLZxfw)
 * B站视频：[代码随想录](https://space.bilibili.com/525438321)

diff --git a/problems/0236.二叉树的最近公共祖先.md b/problems/0236.二叉树的最近公共祖先.md
@@ -311,35 +311,34 @@ func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
 }
 ```
 
-JavaScript版本
-
+JavaScript版本：
 ```javascript
-/**
- * Definition for a binary tree node.
- * function TreeNode(val) {
- *     this.val = val;
- *     this.left = this.right = null;
- * }
- */
-/**
- * @param {TreeNode} root
- * @param {TreeNode} p
- * @param {TreeNode} q
- * @return {TreeNode}
- */
 var lowestCommonAncestor = function(root, p, q) {
-    if(root === p || root === q || root === null)
-        return root;
-    let left = lowestCommonAncestor(root.left, p , q);
-    let right = lowestCommonAncestor(root.right, p, q);
-    if(left && right)
-        return root;
-    if(!left)
-        return right;
-    return left;
+    // 使用递归的方法
+    // 需要从下到上，所以使用后序遍历
+    // 1. 确定递归的函数
+    const travelTree = function(root,p,q) {
+        // 2. 确定递归终止条件
+        if(root === null || root === p||root === q) {
+            return root;
+        }
+        // 3. 确定递归单层逻辑
+        let left = travelTree(root.left,p,q);
+        let right = travelTree(root.right,p,q);
+        if(left !== null&&right !== null) {
+            return root;
+        }
+        if(left ===null) {
+            return right;
+        }
+        return left;
+    }
+   return  travelTree(root,p,q);
 };
 ```
 
+
+
 -----------------------
 * 作者微信：[程序员Carl](https://mp.weixin.qq.com/s/b66DFkOp8OOxdZC_xLZxfw)
 * B站视频：[代码随想录](https://space.bilibili.com/525438321)

diff --git a/problems/0279.完全平方数.md b/problems/0279.完全平方数.md
@@ -214,8 +214,26 @@ class Solution:
         return dp[n]
 ```
 
+Python3:
+```python
+class Solution:
+    def numSquares(self, n: int) -> int:
+        # 初始化
+        # 组成和的完全平方数的最多个数，就是只用1构成
+        # 因此，dp[i] = i
+        dp = [i for i in range(n + 1)]
+        # dp[0] = 0 无意义，只是为了方便记录特殊情况:
+        # n本身就是完全平方数，dp[n] = min(dp[n], dp[n - n] + 1) = 1
+
+        for i in range(1, n): # 遍历物品
+            if i * i > n:
+                break
+            num = i * i
+            for j in range(num, n + 1): # 遍历背包
+                dp[j] = min(dp[j], dp[j - num] + 1)
 
-
+        return dp[n]
+```
 
 Go：
 ```go

diff --git a/problems/0501.二叉搜索树中的众数.md b/problems/0501.二叉搜索树中的众数.md
@@ -523,52 +523,76 @@ func traversal(root *TreeNode,result *[]int,pre *TreeNode){//遍历统计
 }
 ```
 
-JavaScript版本
-
+JavaScript版本：
+使用额外空间map的方法：
 ```javascript
-/**
- * Definition for a binary tree node.
- * function TreeNode(val, left, right) {
- *     this.val = (val===undefined ? 0 : val)
- *     this.left = (left===undefined ? null : left)
- *     this.right = (right===undefined ? null : right)
- * }
- */
-/**
- * @param {TreeNode} root
- * @return {number[]}
- */
-var findMode = function (root) {
-    let maxCount = 0;
-    let curCount = 0;
-    let pre = null;
+var findMode = function(root) {
+    // 使用递归中序遍历
+    let map = new Map();
+    // 1. 确定递归函数以及函数参数
+    const traverTree = function(root) {
+        // 2. 确定递归终止条件
+        if(root === null) {
+            return ;
+        }
+        traverTree(root.left);
+         // 3. 单层递归逻辑
+        map.set(root.val,map.has(root.val)?map.get(root.val)+1:1);
+        traverTree(root.right);
+    }
+    traverTree(root);
+    //上面把数据都存储到map
+    //下面开始寻找map里面的
+    // 定义一个最大出现次数的初始值为root.val的出现次数
+    let maxCount = map.get(root.val);
+    // 定义一个存放结果的数组res
     let res = [];
-    const inOrder = (root) => {
-        if (root === null)
-            return;
-        inOrder(root.left);
-
-        if (pre === null)
-            curCount = 1;
-        else if (pre.val === root.val)
-            curCount++;
-        else
-            curCount = 1;
-        pre = root;
-
-        if (curCount === maxCount)
-            res.push(root.val);
-
-        if (curCount > maxCount) {
-            maxCount = curCount;
-            res.splice(0, res.length);
-            res.push(root.val);
+    for(let [key,value] of map) {
+        // 如果当前值等于最大出现次数就直接在res增加该值
+        if(value === maxCount) {
+            res.push(key);
         }
-
-        inOrder(root.right);
-        return;
+        // 如果value的值大于原本的maxCount就清空res的所有值，因为找到了更大的
+        if(value>maxCount) {
+            res = [];
+            maxCount = value;
+            res.push(key);
+        }
+    }
+    return res;
+};
+```
+不使用额外空间，利用二叉树性质，中序遍历(有序)：
+```javascript
+var findMode = function(root) {
+    // 不使用额外空间，使用中序遍历,设置出现最大次数初始值为1
+    let count = 0,maxCount = 1;
+    let pre = root,res = [];
+    // 1.确定递归函数及函数参数
+    const travelTree = function(cur) {
+        // 2. 确定递归终止条件
+        if(cur === null) {
+            return ;
+        }
+        travelTree(cur.left);
+        // 3. 单层递归逻辑
+        if(pre.val === cur.val) {
+            count++;
+        }else {
+            count = 1;
+        }
+        pre = cur;
+        if(count === maxCount) {
+            res.push(cur.val);
+        }
+        if(count > maxCount) {
+            res = [];
+            maxCount = count;
+            res.push(cur.val);
+        }
+        travelTree(cur.right);
     }
-    inOrder(root);
+    travelTree(root);
     return res;
 };
 ```

diff --git a/problems/剑指Offer58-II.左旋转字符串.md b/problems/剑指Offer58-II.左旋转字符串.md
@@ -118,6 +118,27 @@ class Solution {
 }
 ```
 
+```python
+# 方法一：可以使用切片方法
+class Solution:
+    def reverseLeftWords(self, s: str, n: int) -> str:
+        return s[n:] + s[0:n]
+
+# 方法二：也可以使用上文描述的方法，有些面试中不允许使用切片，那就使用上文作者提到的方法
+# class Solution:
+#     def reverseLeftWords(self, s: str, n: int) -> str:
+#         s = list(s)
+#         s[0:n] = list(reversed(s[0:n]))
+#         s[n:] = list(reversed(s[n:]))
+#         s.reverse()
+
+#         return "".join(s)
+
+
+# 时间复杂度：O(n)
+# 空间复杂度：O(n)，python的string为不可变，需要开辟同样大小的list空间来修改
+```
+
 Go：
 
 ```go

diff --git a/problems/背包理论基础01背包-1.md b/problems/背包理论基础01背包-1.md
@@ -82,7 +82,7 @@ leetcode上没有纯01背包的问题，都是01背包应用方面的题目，
 
 那么可以有两个方向推出来dp[i][j]，
 
-* 由dp[i - 1][j]推出，即背包容量为j，里面不放物品i的最大价值，此时dp[i][j]就是dp[i - 1][j]
+* 由dp[i - 1][j]推出，即背包容量为j，里面不放物品i的最大价值，此时dp[i][j]就是dp[i - 1][j]。(其实就是当物品i的重量大于背包j的重量时，物品i无法放进背包中，所以被背包内的价值依然和前面相同。)
 * 由dp[i - 1][j - weight[i]]推出，dp[i - 1][j - weight[i]] 为背包容量为j - weight[i]的时候不放物品i的最大价值，那么dp[i - 1][j - weight[i]] + value[i] （物品i的价值），就是背包放物品i得到的最大价值
 
 所以递归公式： dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);