Commit112d5b9

committed

add new solution

1 parent4a3de00 commit112d5b9Copy full SHA for 112d5b9

File tree

6 files changed

+87

-20

lines changed

6 files changed

+87

-20

lines changed

`‎动态规划/1143. 最长公共子序列.md`

Lines changed: 1 addition & 1 deletion

Original file line number	Diff line number	Diff line change
`@@ -40,7 +40,7 @@`
`40`	`40`	```python
`41`	`41`	`classSolution:`
`42`	`42`	`deflongestCommonSubsequence(self,text1:str,text2:str) ->int:`
`43`		`- max_len=0`
	`43`	`+`
`44`	`44`	`l1=len(text1)`
`45`	`45`	`l2=len(text2)`
`46`	`46`	`dp= [[0]*(l2+1)for iinrange(l1+1)]`

`‎双指针/0.双指针总结.md`

Lines changed: 1 addition & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -34,3 +34,4 @@`
`34`	`34`	`-[ ] 28 实现 strStr() ：KMP算法`
`35`	`35`	`-[ ] 31 下一个排列`
`36`	`36`	`-[ ] 75 颜色分类：双指针/三指针swap`
	`37`	`+-[ ] 264 丑数II`

`‎双指针/264.丑数II.md`

Lines changed: 13 additions & 18 deletions

Original file line number	Diff line number	Diff line change
`@@ -30,23 +30,17 @@`
`30`	`30`	```python
`31`	`31`	`classSolution:`
`32`	`32`	`defnthUglyNumber(self,n:int) ->int:`
`33`		`- ans= [0]* (n+1)`
`34`		`- ans[1]=1`
`35`		`- idx1, idx2,idx3=1,1,1`
`36`		`- idx=2`
`37`		`-while idx<=n:`
`38`		`- a,b,c= ans[idx1]2, ans[idx2]3, ans[idx3]*5`
`39`		`- m=min(a,b,c)`
`40`		`-if m==a:`
`41`		`- idx1+=1`
`42`		`-if m==b:`
`43`		`- idx2+=1`
`44`		`-if m==c:`
`45`		`- idx3+=1`
`46`		`- ans[idx]=m`
`47`		`- idx+=1`
`48`		`-print(ans)`
`49`		`-return ans[n]`
	`33`	`+ index2, index3, index5=0,0,0`
	`34`	`+ dp= [1]* n`
	`35`	`+for iinrange(1,n):`
	`36`	`+ dp[i]=min(dp[index2]2, dp[index3]3, dp[index5]*5)`
	`37`	`+if dp[i]==dp[index2]*2:`
	`38`	`+ index2+=1`
	`39`	`+if dp[i]== dp[index3]*3:`
	`40`	`+ index3+=1`
	`41`	`+if dp[i]==dp[index5]*5:`
	`42`	`+ index5+=1`
	`43`	`+return dp[-1]`
`50`	`44`	```
`51`	`45`
`52`	`46`
`@@ -56,4 +50,5 @@ class Solution:`
`56`	`50`	`Tips`
`57`	`51`
`58`	`52`	`1. 归并排序问题，这里放在双指针了，因为需要三个指针分别指向丑数2，丑数3，丑数*5下一个最小的位置，合并是每次选择最小的并移动指针`
`59`		`-2. 需要注意的是因为同一个丑数可能来源于不同的指针，例如6，同时是丑数2的倍数，也是丑数3的倍数，所以指针移动时是不是互斥的`
	`53`	`+2. 需要注意的是因为同一个丑数可能来源于不同的指针，例如6，同时是丑数2的倍数，也是丑数3的倍数，所以指针移动时是不是互斥的`
	`54`	`+`

`‎排序/0.排序总结.md`

Lines changed: 2 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -138,6 +138,8 @@ def merge_sort(nums):`
`138`	`138`
`139`	`139`	`-[ ] 215 数组中的第K个最大元素`
`140`	`140`
	`141`	`+-[ ] 347 前K个高频元素`
	`142`	`+`
`141`	`143`	`-[ ] 703 数据流中的第K大元素`
`142`	`144`
`143`	`145`	`-[ ] 40剑指offer. 最小的k个数`

`‎排序/347 前K个高频元素.md`

Lines changed: 69 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -0,0 +1,69 @@`
	`1`	+```
	`2`	`+# 给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按任意顺序返回答案。`
	`3`	`+#`
	`4`	`+#`
	`5`	`+#`
	`6`	`+# 示例 1:`
	`7`	`+#`
	`8`	`+#`
	`9`	`+# 输入: nums = [1,1,1,2,2,3], k = 2`
	`10`	`+# 输出: [1,2]`
	`11`	`+#`
	`12`	`+#`
	`13`	`+# 示例 2:`
	`14`	`+#`
	`15`	`+#`
	`16`	`+# 输入: nums = [1], k = 1`
	`17`	`+# 输出: [1]`
	`18`	`+#`
	`19`	`+#`
	`20`	`+#`
	`21`	`+# 提示：`
	`22`	`+#`
	`23`	`+#`
	`24`	`+# 1 <= nums.length <= 105`
	`25`	`+# k 的取值范围是 [1, 数组中不相同的元素的个数]`
	`26`	`+# 题目数据保证答案唯一，换句话说，数组中前 k 个高频元素的集合是唯一的`
	`27`	`+#`
	`28`	`+#`
	`29`	`+#`
	`30`	`+#`
	`31`	`+# 进阶：你所设计算法的时间复杂度必须优于 O(n log n) ，其中 n 是数组大小。`
	`32`	`+# Related Topics 数组哈希表分治桶排序计数快速选择排序堆（优先队列）`
	`33`	`+# 👍 1067 👎 0`
	`34`	`+`
	`35`	`+`
	`36`	`+# leetcode submit region begin(Prohibit modification and deletion)`
	`37`	`+class Solution:`
	`38`	`+ def topKFrequent(self, nums: List[int], k: int) -> List[int]:`
	`39`	`+ counter = collections.Counter(nums)`
	`40`	`+ counter = list(counter.items())`
	`41`	`+`
	`42`	`+ def topK(nums, k, left, right):`
	`43`	`+ def partition(nums, left, right):`
	`44`	`+ key = left`
	`45`	`+ while left < right:`
	`46`	`+ while left < right and nums[right][1] >= nums[key][1]:`
	`47`	`+ right -= 1`
	`48`	`+ while left < right and nums[left][1] <= nums[key][1]:`
	`49`	`+ left += 1`
	`50`	`+ nums[right], nums[left] = nums[left], nums[right]`
	`51`	`+ nums[key], nums[left] = nums[left], nums[key]`
	`52`	`+ return left`
	`53`	`+`
	`54`	`+ if left >= right:`
	`55`	`+ return`
	`56`	`+ mid = partition(nums, left, right)`
	`57`	`+ if mid == k:`
	`58`	`+ return`
	`59`	`+ elif mid > k:`
	`60`	`+ topK(nums, k, left, mid-1)`
	`61`	`+ else:`
	`62`	`+ topK(nums, k, mid+1, right)`
	`63`	`+ l = len(counter)`
	`64`	`+ topK(counter, l-k, 0, len(counter) - 1)`
	`65`	`+ return [i[0] for i in counter[-k:]]`
	`66`	`+# leetcode submit region end(Prohibit modification and deletion)`
	`67`	+```
	`68`	`+`
	`69`	`+快速跑徐`

`‎树/0.总结.md`

Lines changed: 1 addition & 1 deletion

Original file line number	Diff line number	Diff line change
`@@ -1,9 +1,9 @@`
`1`	`1`	`- 前序遍历`
`2`	`2`	`-[ ] 114 二叉树展开为链表`
`3`		`-`
`4`	`3`	`-[ ] 129 求根节点到叶节点数字之和`
`5`	`4`	`-[ ] 144 二叉树的前序遍历`
`6`	`5`	`-[ ] 257 二叉树的所有路径`
	`6`	`+-[ ] 437 路经总和 III`
`7`	`7`	`-[ ] 589 N 叉树的前序遍历`
`8`	`8`	`-[ ] 606 根据二叉树构建字符串`
`9`	`9`	`-[ ] 653 两数之和 IV`

0 commit comments

Comments

(0)

Movatterモバイル変換

Navigation Menu

Search code, repositories, users, issues, pull requests...

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Uh oh!

Commit112d5b9

File tree

6 files changed

6 files changed

`‎动态规划/1143. 最长公共子序列.md`

`‎双指针/0.双指针总结.md`

`‎双指针/264.丑数II.md`

`‎排序/0.排序总结.md`

`‎排序/347 前K个高频元素.md`

`‎树/0.总结.md`

0 commit comments