系列文章目录
代码随想录算法训练营第一天|数组理论基础,704. 二分查找,27. 移除元素
代码随想录算法训练营第二天|977.有序数组的平方 ,209.长度最小的子数组 ,59.螺旋矩阵II
代码随想录算法训练营第三天|链表理论基础,203.移除链表元素,707.设计链表,206.反转链表
代码随想录算法训练营第四天|24. 两两交换链表中的节点,19.删除链表的倒数第N个节点,面试题 02.07. 链表相交,142.环形链表II,总结
代码随想录算法训练营第五天|哈希表理论基础,242.有效的字母异位词,349. 两个数组的交集,202. 快乐数,1. 两数之和
代码随想录算法训练营第六天|454.四数相加II,383. 赎金信,15. 三数之和,18. 四数之和,总结
代码随想录算法训练营第七天|344.反转字符串,541. 反转字符串II,卡码网:54.替换数字,151.翻转字符串里的单词,卡码网:55.右旋转字符串
代码随想录算法训练营第八天|28. 实现 strStr(),459.重复的子字符串,字符串总结,双指针回顾
代码随想录算法训练营第九天|理论基础,232.用栈实现队列,225. 用队列实现栈
代码随想录算法训练营第十天|20. 有效的括号,1047. 删除字符串中的所有相邻重复项,150. 逆波兰表达式求值
代码随想录算法训练营第十一天|239. 滑动窗口最大值,347.前 K 个高频元素,总结
代码随想录算法训练营第十二天|理论基础,递归遍历,迭代遍历,统一迭代
代码随想录算法训练营第十三天|层序遍历10,226.翻转二叉树,101.对称二叉树
代码随想录算法训练营第十四天|104.二叉树的最大深度,559.n叉树的最大深度,111.二叉树的最小深度,222.完全二叉树的节点个数
代码随想录算法训练营第十五天|110.平衡二叉树,257. 二叉树的所有路径,404.左叶子之和
代码随想录算法训练营第十六天|513.找树左下角的值,112. 路径总和,113.路径总和ii,106.从中序与后序遍历序列构造二叉树,105.从前序与中序遍历序列构造二叉树
代码随想录算法训练营第十七天|654.最大二叉树,617.合并二叉树,700.二叉搜索树中的搜索,98.验证二叉搜索树
代码随想录算法训练营第十八天|530.二叉搜索树的最小绝对差,501.二叉搜索树中的众数,236. 二叉树的最近公共祖先
代码随想录算法训练营第十九天|235. 二叉搜索树的最近公共祖先,701.二叉搜索树中的插入操作,450.删除二叉搜索树中的节点
代码随想录算法训练营第二十天|669. 修剪二叉搜索树,108.将有序数组转换为二叉搜索树,538.把二叉搜索树转换为累加树,总结篇
代码随想录算法训练营第二十一天|回溯算法理论基础,77. 组合
文章目录
- 系列文章目录
- 216.组合总和III
- 17.电话号码的字母组合
216.组合总和III
题目链接: 216.组合总和III
题目内容: 找出所有相加之和为 n 的 k 个数的组合,且满足下列条件:只使用数字1到9,每个数字 最多使用一次 返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次,组合可以以任何顺序返回。
视频讲解: 和组合问题有啥区别?回溯算法如何剪枝?| LeetCode:216.组合总和III
class Solution:def combinationSum3(self, k: int, n: int) -> List[List[int]]:result=[]self.backtracking(k,n,0,1,[],result)return resultdef backtracking(self,k,targetSum,currentSum,startIndex,path,result):if currentSum>targetSum:return if len(path)==k:if currentSum == targetSum:result.append(path[:])returnfor i in range (startIndex,10):currentSum+=ipath.append(i)self.backtracking(k,targetSum,currentSum,i+1,path,result)currentSum-=ipath.pop()
17.电话号码的字母组合
题目链接: 17.电话号码的字母组合
题目内容: 给定一个仅包含数字 2-9 的字符串,返回所有它能表示的字母组合。答案可以按 任意顺序 返回。给出数字到字母的映射与电话按键相同。注意 1 不对应任何字母。
视频讲解: 还得用回溯算法!| LeetCode:17.电话号码的字母组合
class Solution:def __init__(self):self.letterMap = ["", # 0"", # 1"abc", # 2"def", # 3"ghi", # 4"jkl", # 5"mno", # 6"pqrs", # 7"tuv", # 8"wxyz" # 9]self.result = []self.s = ""def backtracking(self,digits,index): #index表示处理的数字序号if index == len(digits):self.result.append(self.s)return digit=int(digits[index])letters=self.letterMap[digit]#获取对应的字符集for i in range(len(letters)):self.s += letters[i]self.backtracking(digits,index+1)self.s=self.s[:-1]def letterCombinations(self, digits: str) -> List[str]:if len(digits)==0:return self.resultself.backtracking(digits,0)return self.result