215:第k个最大元素
链接:215. 数组中的第K个最大元素 - 力扣（LeetCode）
em~~怎么说呢，快速选择，随机定一个目标值，开始找，左边比目标小，右边比目标大，左右同时不满足时，交换左右位置，直到左指针比右指针大，交换目标和右指针位置的值，此时右指针位置即时目标值的在排序好数组中的位置，如果k在右边，左边界右移，k在左边，右边界左移
快排
1 class Solution: 2 def findKthLargest(self, nums: List[int], k: int) -> int: 3 if(not nums): return 0 4 lens=len(nums) 5 #倒数第k大，正数位置lens-k 6 tager=lens-k 7 left,right=0,lens-1 8 while left<=right: 9 i,j=left+1,right 10 flage=0 11 while i<=j: 12 #如果左大于目标，并且右小于目标，交换左右 13 if(nums[i]>=nums[left] and nums[j]<=nums[left]): 14 nums[i],nums[j]=nums[j],nums[i] 15 i+=1 16 j-=1 17 else: 18 #左小于目标，左+1，右大于目标，右-1 19 if(nums[i]<=nums[left]): i+=1 20 if(nums[j]>=nums[left]): j-=1 21 #目标比右大，交换目标和右 22 nums[left],nums[j]=nums[j],nums[left] 23 #如果结束的位置是tager,结束，大了找左，小了找右 24 if(j==tager): return nums[j] 25 elif(j>tager): right=j-1 26 else: left=j+1findKthLargest
347:前k个高频元素
链接：347. 前 K 个高频元素 - 力扣（LeetCode）
em~~没啥
1 class Solution:
2 def topKFrequent(self, nums: List[int], k: int) -> List[int]:
3 if(not nums): return nums
4 data={x:0 for x in nums}
5 for item in data:
6 data[item]+=nums.count(item)
7 data=sorted(data.items(),key=lambda x:x[1] ,reverse=True)
8 re=[]
9 for i in range(k):
10 re.append(data[i][0])
11 return re
12
topKFrequent
451:根据字符出现频率排序
链接451. 根据字符出现频率排序 - 力扣（LeetCode）
347一样
1 class Solution:
2 def frequencySort(self, s: str) -> str:
3 data={x:0 for x in s}
4 for item in data:
5 data[item]+=s.count(item)
6 data=sorted(data.items(),key=lambda x:x[1],reverse=True)
7 re=''
8 for item in data:
9 re+=item[0]*item[1]
10 return re
frequencySort
75:颜色分类
后一个数小于前一个，交换，i-1，否做i+1
1 class Solution: 2 def sortColors(self, nums: List[int]) -> None: 3 """ 4 Do not return anything, modify nums in-place instead. 5 """ 6 if (not nums): return nums 7 lens=len(nums) 8 i=1 9 while i<lens: 10 if(i==0): i+=1 11 if(nums[i]<nums[i-1]): 12 nums[i],nums[i-1]=nums[i-1],nums[i] 13 i-=1 14 else: 15 i+=1 16 print(nums)sortColors
开启回溯之旅
回溯理论知识引用：代码随想录 (programmercarl.com)
void backtracking(参数) {
if (终止条件) {
存放结果;
return;
}
for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
处理节点;
backtracking(路径，选择列表); // 递归
回溯，撤销处理结果
}
}77:组合
for i in (1,2,3,4)遍历
递归：每个结果长度=k，结束递归
1 class Solution: 2 def combine(self, n: int, k: int) -> List[List[int]]: 3 if(n==0): return [] 4 re=[] 5 self.backtracking(n+1,k,1,[],re) 6 return re 7 def backtracking(self,n,k,startId,path,re): 8 if(len(path)==k): 9 re.append(path[:]) 10 return 11 for i in range(startId,n): 12 path.append(i) 13 self.backtracking(n,k,i+1,path,re) 14 path.pop()combine
1 class Solution: 2 def combine(self, n: int, k: int) -> List[List[int]]: 3 if(n==0): return [] 4 re=[] 5 self.backtracking(n+1,k,1,[],re) 6 return re 7 def backtracking(self,n,k,startId,path,re): 8 if(len(path)==k): 9 re.append(path[:]) 10 return 11 #说实话，这步减枝优化没看懂，在找一道题试试 12 #for i in range(startId,n-(k-len(path))+1): 13 for i in range(startId,n): 14 print(i,path) 15 path.append(i) 16 self.backtracking(n,k,i+1,path,re) 17 path.pop()combine(优化)
216:组合总和III
链接：216. 组合总和 III - 力扣（LeetCode）
for i in (1-9)遍历
递归：相加，和大于n直接返回，小于n放入单次结果中
1 class Solution: 2 def combinationSum3(self, k: int, n: int) -> List[List[int]]: 3 if(not k or not n): return[] 4 re=[] 5 self.backtracking(1,n,k,[],re) 6 return re 7 def backtracking(self,startId,n,k,path,re): 8 if(len(path)==k): 9 if(sum(path)==n): 10 re.append(path[:]) 11 return 12 for i in range(startId,10-(k-len(path))): 13 #如果和大于n，后面就没有必要做了,小于n 14 if(i+sum(path)<=n): 15 path.append(i) 16 self.backtracking(i+1,n,k,path,re) 17 path.pop() 18 else: returncombinationSum3
17:电话号码的字母组合
链接：17. 电话号码的字母组合 - 力扣（LeetCode）
for i in (一个数字对应的字母表)遍历
递归：单次结果的字符串按digits顺序相加
1 dicts={2:'abc',3:'def',4:'ghi',5:'jkl',6:'mno',7:'pqsr',8:'tuv',9:'wxyz'}
2 class Solution:
3 def letterCombinations(self, digits: str) -> List[str]:
4 if(not digits): return []
5 re=[]
6 self.backtracking(digits,'',re,0)
7 return re
8 def backtracking(self,digits,path,re,index):
9 global dicts
10 if(index==len(digits)):
11 re.append(path)
12 return
13 for strs in dicts[int(digits[index])]:
14 self.backtracking(digits,path+strs,re,index+1)
15
16
17
letterCombinations
39:组合总和
还是要传个index，第一个元素的下标，当前元素可以重复用，但是不能回头往前找
1 class Solution: 2 def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]: 3 if(not candidates): return [] 4 re=[] 5 self.backtracking(candidates,target,[],re,0) 6 return re 7 def backtracking(self,candidates,target,path,re,index): 8 if(sum(path)==target): 9 re.append(path[:]) 10 return 11 for i in range(index,len(candidates)): 12 num=candidates[i] 13 if(sum(path)<target): 14 path.append(num) 15 self.backtracking(candidates,target,path,re,i) 16 path.pop() 17 else: returncombinationSum
40：组合总和II
需要注意的是：每一层不能重复使用相同的元素，但是下一层可以重复用
1 class Solution: 2 def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]: 3 if(not candidates): return [] 4 candidates.sort() 5 re=[] 6 self.backtracking(candidates,target,[],re,0) 7 return re 8 def backtracking(self,candidates,target,path,re,index): 9 if(sum(path)==target): 10 re.append(path[:]) 11 return 12 for i in range(index,len(candidates)): 13 #每一次的迭代元素，不能重复，但是下一层递归中可以用 14 if(i>index and candidates[i]==candidates[i-1] ): continue 15 if(sum(path)<target): 16 path.append(candidates[i]) 17 self.backtracking(candidates,target,path,re,i+1) 18 path.pop() 19 else: returncombinationSum2
标签：return,nums,int,self,二分法,re,path,Leetcode,刷题 From： https://www.cnblogs.com/xiaoruru/p/17995494