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

youngyangyang04 · youngyangyang04 · commit 81f74d8c481f · 2021-07-14T15:45:47.000+08:00
diff --git a/problems/0047.全排列II.md b/problems/0047.全排列II.md
@@ -296,7 +296,45 @@ var permuteUnique = function (nums) {
 };
 
 ```
-
+Go：
+回溯+本层去重+下层去重
+```golang
+func permuteUnique(nums []int) [][]int {
+ var subRes []int
+    var res [][]int
+    sort.Ints(nums)
+    used:=make([]bool,len(nums))
+    backTring(nums,subRes,&res,used)
+    return res
+}
+func backTring(nums,subRes []int,res *[][]int,used []bool){
+    if len(subRes)==len(nums){
+        tmp:=make([]int,len(nums))
+        copy(tmp,subRes)
+        *res=append(*res,tmp)
+        return
+    }
+    // used[i - 1] == true，说明同一树支candidates[i - 1]使用过
+    // used[i - 1] == false，说明同一树层candidates[i - 1]使用过
+    for  i:=0;i<len(nums);i++{
+        if i>0&&nums[i]==nums[i-1]&&used[i-1]==false{//当本层元素相同且前一个被使用过，则继续向后找（本层去重）
+            continue
+        }
+        //到达这里有两种情况：1.该层前后元素不同；2.该层前后元素相同但该层没有使用过
+        //所以只能对该层没有被使用过的抽取
+        if used[i]==false{
+            //首先将该元素置为使用过（即同一树枝使用过），下一层的元素就不能选择重复使用过的元素（下层去重）
+            used[i]=true
+            subRes=append(subRes,nums[i])
+            backTring(nums,subRes,res,used)
+            //回溯
+            //回溯回来，将该元素置为false，表示该元素在该层使用过
+             used[i]=false
+            subRes=subRes[:len(subRes)-1]
+        }
+    }
+}
+```
 
 
 
diff --git a/problems/0112.路径总和.md b/problems/0112.路径总和.md
@@ -13,8 +13,8 @@
 
 接下来我通过详细讲解如下两道题，来回答这个问题：
 
-* 112. 路径总和
-* 113. 路径总和II
+* 112.路径总和
+* 113.路径总和II
 
 ## 112. 路径总和
 
diff --git a/problems/0122.买卖股票的最佳时机II（动态规划）.md b/problems/0122.买卖股票的最佳时机II（动态规划）.md
@@ -201,6 +201,29 @@ class Solution:
 
 Go：
 
+Javascript：
+```javascript
+const maxProfit = (prices) => {
+    let dp = Array.from(Array(prices.length), () => Array(2).fill(0));
+    // dp[i][0] 表示第i天持有股票所得现金。
+    // dp[i][1] 表示第i天不持有股票所得最多现金
+    dp[0][0] = 0 - prices[0];
+    dp[0][1] = 0;
+    for(let i = 1; i < prices.length; i++) {
+        // 如果第i天持有股票即dp[i][0]， 那么可以由两个状态推出来
+        // 第i-1天就持有股票，那么就保持现状，所得现金就是昨天持有股票的所得现金 即：dp[i - 1][0]
+        // 第i天买入股票，所得现金就是昨天不持有股票的所得现金减去 今天的股票价格 即：dp[i - 1][1] - prices[i]
+        dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1] - prices[i]);
+        
+        // 在来看看如果第i天不持有股票即dp[i][1]的情况， 依然可以由两个状态推出来
+        // 第i-1天就不持有股票，那么就保持现状，所得现金就是昨天不持有股票的所得现金 即：dp[i - 1][1]
+        // 第i天卖出股票，所得现金就是按照今天股票佳价格卖出后所得现金即：prices[i] + dp[i - 1][0]
+        dp[i][1] = Math.max(dp[i-1][1], dp[i-1][0] + prices[i]);
+    }
+
+    return dp[prices.length -1][0];
+};
+```
 
 
 
diff --git a/problems/0188.买卖股票的最佳时机IV.md b/problems/0188.买卖股票的最佳时机IV.md
@@ -224,7 +224,7 @@ class Solution {
 
 
 Python：
-
+版本一
 ```python
 class Solution:
     def maxProfit(self, k: int, prices: List[int]) -> int:
@@ -239,11 +239,49 @@ class Solution:
                 dp[i][j+2] = max(dp[i-1][j+2], dp[i-1][j+1] + prices[i])
         return dp[-1][2*k]
 ```
-
+版本二
+```python3
+class Solution:
+    def maxProfit(self, k: int, prices: List[int]) -> int:
+        if len(prices) == 0: return 0
+        dp = [0] * (2*k + 1)
+        for i in range(1,2*k,2):
+            dp[i] = -prices[0]
+        for i in range(1,len(prices)):
+            for j in range(1,2*k + 1):
+                if j % 2:
+                    dp[j] = max(dp[j],dp[j-1]-prices[i])
+                else:
+                    dp[j] = max(dp[j],dp[j-1]+prices[i])
+        return dp[2*k]
+```
 Go：
 
 
+Javascript：
+
+```javascript
+const maxProfit = (k,prices) => {
+    if (prices == null || prices.length < 2 || k == 0) {
+        return 0;
+    }
+    
+    let dp = Array.from(Array(prices.length), () => Array(2*k+1).fill(0));
 
+    for (let j = 1; j < 2 * k; j += 2) {
+        dp[0][j] = 0 - prices[0];
+    }
+    
+    for(let i = 1; i < prices.length; i++) {
+        for (let j = 0; j < 2 * k; j += 2) {
+            dp[i][j+1] = Math.max(dp[i-1][j+1], dp[i-1][j] - prices[i]);
+            dp[i][j+2] = Math.max(dp[i-1][j+2], dp[i-1][j+1] + prices[i]);
+        }
+    }
+
+    return dp[prices.length - 1][2 * k];
+};
+```
 
 -----------------------
 * 作者微信：[程序员Carl](https://mp.weixin.qq.com/s/b66DFkOp8OOxdZC_xLZxfw)
diff --git a/problems/0309.最佳买卖股票时机含冷冻期.md b/problems/0309.最佳买卖股票时机含冷冻期.md
@@ -207,7 +207,29 @@ class Solution:
 
 Go：
 
+Javascript:
+
+```javascript
+const maxProfit = (prices) => {
+    if(prices.length < 2) {
+        return 0
+    } else if(prices.length < 3) {
+        return Math.max(0, prices[1] - prices[0]);
+    }
+
+    let dp = Array.from(Array(prices.length), () => Array(4).fill(0));
+    dp[0][0] = 0 - prices[0];
+
+    for(i = 1; i < prices.length; i++) {
+        dp[i][0] = Math.max(dp[i - 1][0], Math.max(dp[i-1][1], dp[i-1][3]) - prices[i]);
+        dp[i][1] = Math.max(dp[i -1][1], dp[i - 1][3]);
+        dp[i][2] = dp[i-1][0] + prices[i];
+        dp[i][3] = dp[i-1][2];
+    }
 
+    return Math.max(dp[prices.length - 1][1], dp[prices.length - 1][2], dp[prices.length - 1][3]);
+};
+```
 
 
 -----------------------
diff --git a/problems/0501.二叉搜索树中的众数.md b/problems/0501.二叉搜索树中的众数.md
@@ -435,7 +435,7 @@ Python：
 #         self.val = val
 #         self.left = left
 #         self.right = right
-//递归法
+# 递归法
 class Solution:
     def findMode(self, root: TreeNode) -> List[int]:
         if not root: return
@@ -460,6 +460,66 @@ class Solution:
             return
         findNumber(root)
         return self.res
+	
+
+# 迭代法-中序遍历-使用额外空间map的方法：
+class Solution:
+    def findMode(self, root: TreeNode) -> List[int]:
+        stack = []
+        cur = root
+        pre = None
+        dist = {}
+        while cur or stack:
+            if cur:  # 指针来访问节点，访问到最底层
+                stack.append(cur)
+                cur = cur.left
+            else:  # 逐一处理节点
+                cur = stack.pop()
+                if cur.val in dist:
+                    dist[cur.val] += 1
+                else:
+                    dist[cur.val] = 1
+                pre = cur
+                cur = cur.right
+
+        # 找出字典中最大的key
+        res = []
+        for key, value in dist.items():
+            if (value == max(dist.values())):
+                res.append(key)
+        return res
+
+# 迭代法-中序遍历-不使用额外空间，利用二叉搜索树特性：
+class Solution:
+    def findMode(self, root: TreeNode) -> List[int]:
+        stack = []
+        cur = root
+        pre = None
+        maxCount, count = 0, 0
+        res = []
+        while cur or stack:
+            if cur:  # 指针来访问节点，访问到最底层
+                stack.append(cur)
+                cur = cur.left
+            else:  # 逐一处理节点
+                cur = stack.pop()
+                if pre == None:  # 第一个节点
+                    count = 1
+                elif pre.val == cur.val:  # 与前一个节点数值相同
+                    count += 1
+                else:
+                    count = 1
+                if count == maxCount:
+                    res.append(cur.val)
+                if count > maxCount:
+                    maxCount = count
+                    res.clear()
+                    res.append(cur.val)
+
+                pre = cur
+                cur = cur.right
+        return res	
+	
 ```
 Go：
 暴力法（非BSL）
diff --git a/problems/0714.买卖股票的最佳时机含手续费（动态规划）.md b/problems/0714.买卖股票的最佳时机含手续费（动态规划）.md
@@ -153,7 +153,18 @@ class Solution:
 
 Go：
 
-
+Javascript：
+```javascript
+const maxProfit = (prices,fee) => {
+    let dp = Array.from(Array(prices.length), () => Array(2).fill(0));
+    dp[0][0] = 0 - prices[0];
+    for (let i = 1; i < prices.length; i++) {
+        dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] - prices[i]);
+        dp[i][1] = Math.max(dp[i - 1][0] + prices[i] - fee, dp[i - 1][1]);
+    }
+    return Math.max(dp[prices.length - 1][0], dp[prices.length - 1][1]);
+}
+```
 
 
 -----------------------
diff --git a/problems/0718.最长重复子数组.md b/problems/0718.最长重复子数组.md
@@ -20,7 +20,7 @@ B: [3,2,1,4,7]
 输出：3
 解释：
 长度最长的公共子数组是 [3, 2, 1] 。
- 
+
 提示：
 
 * 1 <= len(A), len(B) <= 1000
@@ -155,6 +155,7 @@ public:
 
 Java：
 ```java
+// 版本一
 class Solution {
     public int findLength(int[] nums1, int[] nums2) {
         int result = 0;
@@ -164,14 +165,34 @@ class Solution {
             for (int j = 1; j < nums2.length + 1; j++) {
                 if (nums1[i - 1] == nums2[j - 1]) {
                     dp[i][j] = dp[i - 1][j - 1] + 1;
-                    max = Math.max(max, dp[i][j]);
+                    result = Math.max(result, dp[i][j]);
                 }
             }
         }
         
         return result;
     }
 }
+
+// 版本二: 滚动数组
+class Solution {
+    public int findLength(int[] nums1, int[] nums2) {
+        int[] dp = new int[nums2.length + 1];
+        int result = 0;
+
+        for (int i = 1; i <= nums1.length; i++) {
+            for (int j = nums2.length; j > 0; j--) {
+                if (nums1[i - 1] == nums2[j - 1]) {
+                    dp[j] = dp[j - 1] + 1;
+                } else {
+                    dp[j] = 0;
+                }
+                result = Math.max(result, dp[j]);
+            }
+        }
+        return result;
+    }
+}
 ```
 
 Python：
diff --git a/problems/1035.不相交的线.md b/problems/1035.不相交的线.md
@@ -8,6 +8,8 @@
 
 ## 1035.不相交的线
 
+题目链接: https://leetcode-cn.com/problems/uncrossed-lines/
+
 我们在两条独立的水平线上按给定的顺序写下 A 和 B 中的整数。
 
 现在，我们可以绘制一些连接两个数字 A[i] 和 B[j] 的直线，只要 A[i] == B[j]，且我们绘制的直线不与任何其他连线（非水平线）相交。
