Mar 16, 2022 · Mar 16, 2022
diff --git a/动态规划/1143. 最长公共子序列.md b/动态规划/1143. 最长公共子序列.md
 ```python
 class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        max_len = 0

        l1 = len(text1)
        l2 = len(text2)
        dp = [[0] *(l2+1)for i in range(l1+1)]
diff --git a/双指针/0.双指针总结.md b/双指针/0.双指针总结.md
  - [ ] 28 实现 strStr() ：KMP算法
  - [ ] 31 下一个排列
  - [ ] 75 颜色分类：双指针/三指针swap
  - [ ] 264 丑数II
diff --git a/双指针/264.丑数II.md b/双指针/264.丑数II.md
 ```python
 class Solution:
    def nthUglyNumber(self, n: int) -> int:
        ans = [0] * (n+1)
        ans[1] = 1
        idx1, idx2,idx3 = 1,1,1
        idx = 2
        while idx<=n:
            a,b,c = ans[idx1] * 2, ans[idx2]*3, ans[idx3]*5
            m = min(a,b,c)
            if m==a:
                idx1+=1
            if m==b:
                idx2+=1
            if m==c:
                idx3+=1
            ans[idx]=m
            idx+=1
        print(ans)
        return ans[n]
        index2, index3, index5=0,0,0
        dp = [1] * n
        for i in range(1,n):
            dp[i] = min(dp[index2]*2, dp[index3]*3, dp[index5]*5)
            if dp[i]==dp[index2]*2:
                index2+=1
            if dp[i] == dp[index3] * 3:
                index3 += 1
            if dp[i]==dp[index5]*5:
                index5+=1
        return dp[-1]
 ```


 Tips

 1. 归并排序问题，这里放在双指针了，因为需要三个指针分别指向丑数*2， 丑数*3，丑数*5下一个最小的位置，合并是每次选择最小的并移动指针
 2. 需要注意的是因为同一个丑数可能来源于不同的指针，例如6，同时是丑数2的倍数，也是丑数3的倍数，所以指针移动时是不是互斥的
 2. 需要注意的是因为同一个丑数可能来源于不同的指针，例如6，同时是丑数2的倍数，也是丑数3的倍数，所以指针移动时是不是互斥的

diff --git a/排序/0.排序总结.md b/排序/0.排序总结.md

 - [ ] 215 数组中的第K个最大元素

 - [ ] 347 前K个高频元素

 - [ ] 703 数据流中的第K大元素

 - [ ] 40剑指offer. 最小的k个数
diff --git a/排序/347 前K个高频元素.md b/排序/347 前K个高频元素.md
 ```
 # 给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。
 #
 #
 #
 #  示例 1:
 #
 #
 # 输入: nums = [1,1,1,2,2,3], k = 2
 # 输出: [1,2]
 #
 #
 #  示例 2:
 #
 #
 # 输入: nums = [1], k = 1
 # 输出: [1]
 #
 #
 #
 #  提示：
 #
 #
 #  1 <= nums.length <= 105
 #  k 的取值范围是 [1, 数组中不相同的元素的个数]
 #  题目数据保证答案唯一，换句话说，数组中前 k 个高频元素的集合是唯一的
 #
 #
 #
 #
 #  进阶：你所设计算法的时间复杂度 必须 优于 O(n log n) ，其中 n 是数组大小。
 #  Related Topics 数组 哈希表 分治 桶排序 计数 快速选择 排序 堆（优先队列）
 #  👍 1067 👎 0


 # leetcode submit region begin(Prohibit modification and deletion)
 class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        counter = collections.Counter(nums)
        counter = list(counter.items())

        def topK(nums, k, left, right):
            def partition(nums, left, right):
                key = left
                while left < right:
                    while left < right and nums[right][1] >= nums[key][1]:
                        right -= 1
                    while left < right and nums[left][1] <= nums[key][1]:
                        left += 1
                    nums[right], nums[left] = nums[left], nums[right]
                nums[key], nums[left] = nums[left], nums[key]
                return left

            if left >= right:
                return
            mid = partition(nums, left, right)
            if mid == k:
                return
            elif mid > k:
                topK(nums, k, left, mid-1)
            else:
                topK(nums, k, mid+1, right)
        l = len(counter)
        topK(counter, l-k, 0, len(counter) - 1)
        return [i[0] for i in counter[-k:]]
 # leetcode submit region end(Prohibit modification and deletion)
 ```

 快速跑徐
diff --git a/树/0.总结.md b/树/0.总结.md
 - 前序遍历
  - [ ] 114 二叉树展开为链表

  - [ ] 129 求根节点到叶节点数字之和
  - [ ]  144 二叉树的前序遍历
  - [ ] 257 二叉树的所有路径
  - [ ] 437 路经总和 III
  - [ ] 589 N 叉树的前序遍历
  - [ ] 606 根据二叉树构建字符串
  - [ ] 653 两数之和 IV
Original file line number	Diff line number	Diff line change
Expand Up		@@ -40,7 +40,7 @@
		```python
		class Solution:
		def longestCommonSubsequence(self, text1: str, text2: str) -> int:
		max_len = 0

		l1 = len(text1)
		l2 = len(text2)
		dp = [[0] *(l2+1)for i in range(l1+1)]
Expand Down
Original file line number	Diff line number	Diff line change
Expand Up		@@ -34,3 +34,4 @@
		- [ ] 28 实现 strStr() ：KMP算法
		- [ ] 31 下一个排列
		- [ ] 75 颜色分类：双指针/三指针swap
		- [ ] 264 丑数II
Original file line number	Diff line number	Diff line change
Expand Up		@@ -30,23 +30,17 @@
		```python
		class Solution:
		def nthUglyNumber(self, n: int) -> int:
		ans = [0] * (n+1)
		ans[1] = 1
		idx1, idx2,idx3 = 1,1,1
		idx = 2
		while idx<=n:
		a,b,c = ans[idx1] * 2, ans[idx2]3, ans[idx3]5
		m = min(a,b,c)
		if m==a:
		idx1+=1
		if m==b:
		idx2+=1
		if m==c:
		idx3+=1
		ans[idx]=m
		idx+=1
		print(ans)
		return ans[n]
		index2, index3, index5=0,0,0
		dp = [1] * n
		for i in range(1,n):
		dp[i] = min(dp[index2]2, dp[index3]3, dp[index5]*5)
		if dp[i]==dp[index2]*2:
		index2+=1
		if dp[i] == dp[index3] * 3:
		index3 += 1
		if dp[i]==dp[index5]*5:
		index5+=1
		return dp[-1]
		```


Expand All		@@ -56,4 +50,5 @@ class Solution:
		Tips

		1. 归并排序问题，这里放在双指针了，因为需要三个指针分别指向丑数2，丑数3，丑数*5下一个最小的位置，合并是每次选择最小的并移动指针
		2. 需要注意的是因为同一个丑数可能来源于不同的指针，例如6，同时是丑数2的倍数，也是丑数3的倍数，所以指针移动时是不是互斥的
		2. 需要注意的是因为同一个丑数可能来源于不同的指针，例如6，同时是丑数2的倍数，也是丑数3的倍数，所以指针移动时是不是互斥的
Original file line number	Diff line number	Diff line change
Expand Up		@@ -138,6 +138,8 @@ def merge_sort(nums):

		- [ ] 215 数组中的第K个最大元素

		- [ ] 347 前K个高频元素

		- [ ] 703 数据流中的第K大元素

		- [ ] 40剑指offer. 最小的k个数
Expand Down
Original file line number	Diff line number	Diff line change
		@@ -0,0 +1,69 @@
		```
		# 给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按任意顺序返回答案。
		#
		#
		#
		# 示例 1:
		#
		#
		# 输入: nums = [1,1,1,2,2,3], k = 2
		# 输出: [1,2]
		#
		#
		# 示例 2:
		#
		#
		# 输入: nums = [1], k = 1
		# 输出: [1]
		#
		#
		#
		# 提示：
		#
		#
		# 1 <= nums.length <= 105
		# k 的取值范围是 [1, 数组中不相同的元素的个数]
		# 题目数据保证答案唯一，换句话说，数组中前 k 个高频元素的集合是唯一的
		#
		#
		#
		#
		# 进阶：你所设计算法的时间复杂度必须优于 O(n log n) ，其中 n 是数组大小。
		# Related Topics 数组哈希表分治桶排序计数快速选择排序堆（优先队列）
		# 👍 1067 👎 0


		# leetcode submit region begin(Prohibit modification and deletion)
		class Solution:
		def topKFrequent(self, nums: List[int], k: int) -> List[int]:
		counter = collections.Counter(nums)
		counter = list(counter.items())

		def topK(nums, k, left, right):
		def partition(nums, left, right):
		key = left
		while left < right:
		while left < right and nums[right][1] >= nums[key][1]:
		right -= 1
		while left < right and nums[left][1] <= nums[key][1]:
		left += 1
		nums[right], nums[left] = nums[left], nums[right]
		nums[key], nums[left] = nums[left], nums[key]
		return left

		if left >= right:
		return
		mid = partition(nums, left, right)
		if mid == k:
		return
		elif mid > k:
		topK(nums, k, left, mid-1)
		else:
		topK(nums, k, mid+1, right)
		l = len(counter)
		topK(counter, l-k, 0, len(counter) - 1)
		return [i[0] for i in counter[-k:]]
		# leetcode submit region end(Prohibit modification and deletion)
		```

		快速跑徐
Original file line number	Diff line number	Diff line change
		@@ -1,9 +1,9 @@
		- 前序遍历
		- [ ] 114 二叉树展开为链表

		- [ ] 129 求根节点到叶节点数字之和
		- [ ] 144 二叉树的前序遍历
		- [ ] 257 二叉树的所有路径
		- [ ] 437 路经总和 III
		- [ ] 589 N 叉树的前序遍历
		- [ ] 606 根据二叉树构建字符串
		- [ ] 653 两数之和 IV
Expand Down