代码随想录算法训练营day24 | leetcode 77. 组合
2024-10-21 02:59:30
基础知识
回溯法解决的问题都可以抽象为树形结构,集合的大小就构成了树的宽度,递归的深度构成的树的深度
void backtracking(参数) {
if (终止条件) {
存放结果;
return;
}
for (选择:本层集合中元素(树中节点孩子的数量就是集合的大小)) {
处理节点;
backtracking(路径,选择列表); // 递归
回溯,撤销处理结果
}
}
LeetCode 77. 组合
分析1.0
class Solution {
List<List<Integer>> res = new ArrayList();
LinkedList<Integer> path = new LinkedList();
public List<List<Integer>> combine(int n, int k) {
backTracking(n, k, 1);
return res;
}
// 模拟人脑
public void backTracking(int n, int k, int start){
if(path.size() == k){
//res.add(path);
res.add(new LinkedList(path));
return;
}
// 剪枝优化
for(int i = start; i <= n-(k-path.size())+1; i++){
path.add(i);
// backTracking(n, k, start++); 有状态 会持续作用
backTracking(n, k, i+1);
path.removeLast();
}
}
}
总结
- path始终在变化,要将某一刻的状态保留下去只能把path赋值给另一个容器
- 参数++会改变状态 而单纯+1仅仅意味着某个数
常用变量名增量更新
size、val、ans、cnt、cur、pre、next、left、right、index、gap、tar、res、src、len、start、end、flag、ch、path
最新文章
- jeesz源码下载
- hmtl的标签属性
- [推荐]DataX、DbSync和Timetunnel学习贴
- iOS项目重构日记
- django通过middleware计算每个页面的详细执行时间
- C# int.Parse()与int.TryParse()
- HDU 5234 Happy birthday --- 三维01背包
- 从视频文件中读入数据-->;将数据转换为灰度图-->;对图像做canny边缘检测-->;将这三个结构显示在一个图像中
- PSP0表格
- hdu 4685 二分匹配+强连通分量
- Spring三种实例化Bean的方法
- velocity-字母序号 list
- wamp的mysql密码修改
- Http,Https (SSL)的Url绝对路径,相对路径解决方案Security Switch 4.2 中文帮助文档 分类: ASP.NET 2014-10-28 14:09 177人阅读 评论(1) 收藏
- 一道Python练习题
- Android 让他们自己控制开发的定义(一个)
- SIGPIPE信号
- 【HTML】谈谈html的meta标签
- WebGL展示3D房屋内景
- Vue &; webpack
热门文章
- 【Hadoop学习】补充:优化、新特性
- 【企业流行新数仓】Day03:SuperSet图表,Ranger权限、脱敏、行级别过滤,Atlas元数据、查询和查看全表/字段血缘依赖,Zabbix告警
- python 之集合(set)
- ubuntu系统wireshark源码编译与安装
- apt install protobuf
- CH579-Lwip-2.12移植
- linux 基础之输入输出重定向
- Linux c 程序自动启动自己
- AI换脸实战教学(FaceSwap的使用)---------第二步Tools:处理输入数据集。
- 图文并茂学习记录--从零开始进行微信小程序开发+引入Vant Weapp组件