回溯是怎么回事(算法村第十八关青铜挑战)
组合
77. 组合 - 力扣(LeetCode)
给定两个整数 n 和 k,返回范围 [1, n] 中所有可能的 k 个数的组合。
你可以按 任何顺序 返回答案。
示例 1:
输入:n = 4, k = 2
输出:
[[2,4],[3,4],[2,3],[1,2],[1,3],[1,4],
]
解

public List<List<Integer>> combine(int n, int k)
{List<List<Integer>> resList = new ArrayList<>();Deque<Integer> paths = new ArrayDeque<>();//数字集[1,n],每条路径有k个数dfs(n, k, 1, paths, resList);return resList;
}public void dfs(int n, int k, int startIndex, Deque<Integer> paths, List<List<Integer>> resList)
{if (paths.size() == k){resList.add(new ArrayList<>(paths));return;}for (int i = startIndex; i <= n; i++){paths.addLast(i);dfs(n, k, i + 1, paths, resList);//回溯清除paths.removeLast(); //双端列表才有的方法}
}
二叉树的所有路径
257. 二叉树的所有路径 - 力扣(LeetCode)
给你一个二叉树的根节点 root ,按 任意顺序 ,返回所有从根节点到叶子节点的路径。
叶子节点 是指没有子节点的节点。
示例 1:

输入:root = [1,2,3,null,5]
输出:["1->2->5","1->3"]
从回溯的角度看之前的代码
String ans的值传递特性,帮我们实现了回溯的关键一步:撤销。
public void preOrder(TreeNode root, List<String> list, String ans)
{if (root == null)return;//找到一个叶子结点后,将路径添加到列表,返回if (root.left == null && root.right == null){ans = ans + String.format("%s",root.val);list.add(ans);return;}//保存路径上的节点ans = ans + String.format("%s->",root.val);preOrder(root.left, list, ans);preOrder(root.right, list, ans);
}
路径总和 II
113. 路径总和 II - 力扣(LeetCode)
给你二叉树的根节点 root 和一个整数目标和 targetSum ,找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。
叶子节点 是指没有子节点的节点。
示例 1:

输入:root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
输出:[[5,4,11,2],[5,8,4,5]]
解
static List<List<Integer>> resPaths = new ArrayList<>();public static List<List<Integer>> pathSum(TreeNode root, int targetSum)
{LinkedList<Integer> path = new LinkedList<>();dfs(root, targetSum, path);return resPaths;
}public static void dfs(TreeNode root, int targetSum, LinkedList<Integer> path)
{if (root == null)return;targetSum -= root.val;path.add(root.val);if (targetSum == 0 && root.left == null && root.right == null)resPaths.add(new ArrayList<>(path));dfs(root.left, targetSum, path);dfs(root.right, targetSum, path);path.removeLast(); //撤销当前访问的结点,回溯到上一层,访问、添加下一个结点
}
相关文章:
回溯是怎么回事(算法村第十八关青铜挑战)
组合 77. 组合 - 力扣(LeetCode) 给定两个整数 n 和 k,返回范围 [1, n] 中所有可能的 k 个数的组合。 你可以按 任何顺序 返回答案。 示例 1: 输入:n 4, k 2 输出: [[2,4],[3,4],[2,3],[1,2],[1,3],…...
向爬虫而生---Redis 探究篇5<Redis集群刨根问底(1)>
前言: Redis集群是一种可靠和高性能的分布式数据库解决方案。随着互联网的迅速发展和数据规模的增长,传统的单机Redis已经无法满足大规模应用的需求。Redis集群的出现填补了这一空白,提供了更高的可扩展性和容错性。 大家都知道,Redis是一种基于内存的高性能键值存储数据库,…...
系统集成Prometheus+Grafana
根据产品需求在自己的系统中添加一个系统监控的页面,其中有主机信息的显示,也有一些业务信息的显示。调研后的方案是 主机信息通过Prometheus采集和存储,业务信息通过自己系统的调度任务统计后存储在Mysql中,使用Grafana对接Prome…...
实例驱动计算机网络
文章目录 计算机网络的层次结构应用层DNSHTTP协议HTTP请求响应过程 运输层TCP协议TCP协议面向连接实现TCP的三次握手连接TCP的四次挥手断开连接 TCP协议可靠性实现TCP的流量控制TCP的拥塞控制TCP的重传机制 UDP协议 网际层IP协议(主机与主机)IP地址的分类…...
Unity 报错:SSL CA certificate error
使用UnityWebRequest时出现如下报错: SSL CA certificate error Curl error 60: Cert verify failed: UNITYTLS_X509VERIFY_FLAG_USER_ERROR1 原因: 证书验证失败 和 SSL CA证书错误 解决方法: 创建一个如下的类: /// <…...
算法刷题Day1 | 704.二分查找、27.移除元素
目录 0 引言1 二分查找1.1 我的解题1.2 修改后1.3 总结 2 移除元素2.1 暴力求解2.2 双指针法(快慢指针) 🙋♂️ 作者:海码007📜 专栏:算法专栏💥 标题:代码随想录算法训练营第一天…...
大数据技术学习笔记(五)—— MapReduce(2)
目录 1 MapReduce 的数据流1.1 数据流走向1.2 InputFormat 数据输入1.2.1 FileInputFormat 切片源码、机制1.2.2 TextInputFormat 读数据源码、机制1.2.3 CombineTextInputFormat 切片机制 1.3 OutputFormat 数据输出1.3.1 OutputFormat 实现类1.3.2 自定义 OutputFormat 2 Map…...
北斗导航 | 同步双星故障的BDS/GPS接收机自主完好性监测算法
===================================================== github:https://github.com/MichaelBeechan CSDN:https://blog.csdn.net/u011344545 ===================================================== 同步双星故障的BDS/GPS接收机自主完好性监测算法 1 引言2 同步双星故障…...
2024金三银四必看前端面试题!简答版精品!
文章目录 导文面试题 导文 2024金三银四必看前端面试题!2w字精品!简答版 金三银四黄金期来了 想要跳槽的小伙伴快来看啊 面试题 基于您给出的方向,我将为您生成20个面试题和答案。请注意,由于面试题的答案可能因个人经验和理解而…...
Python-sklearn.datasets-make_blobs
sklearn.datasets.make_blobs()函数形参详解 """ Title: datasets for regression Time: 2024/3/5 Author: Michael Jie """from sklearn import datasets import matplotlib.pyplot as plt# 产生服从正态分布的聚类数据 x, y, cen…...
[最佳实践] conda环境内安装cuda 和 Mamba的安装
Mamba安装失败的过程中,causal-conv1d安装报错为连接超时 key word: vision mamba, DL ,深度学习 ,mamba unet,mamba环境安装 Mamba安装 主要故障是 pip install causal-conv1d1.2.0和 pip install mamba-ssm1.2.0 安…...
【算法】顺时针打印矩阵(图文详解,代码详细注释
目录 题目 代码如下: 题目 输入一个矩阵,按照从外向里以顺时针的顺序依次打印出每一个数字。例如:如果输入如下矩阵: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 则打印出数字:1 2 3 4 8 12 16 15 14 13 9 5 6 7 11 10 这一道题乍一看,没有包含任何复杂的数据结构和…...
蚂蚁感冒c++
题目 思路 “两蚂蚁碰面会掉头,若其中一只蚂蚁感冒了,会把感冒传染给碰到的蚂蚁”,这句话看作是“两蚂蚁碰面会互相穿过,只是把感冒的状态传给了另一只蚂蚁”,因为哪只蚂蚁感冒了并不是题目的重点,重点是有…...
python Plotly可视化
文章目录 Plotly常用函数PolarPlotlymake_subplotsadd_tracego.Scatterpolarglupdate_tracesupdate_layout综合示例 完整版 Python在数据可视化方面有着丰富的库和函数,其中一些常用的库包括 Matplotlib、Seaborn、Plotly、Bokeh等。 Plotly是一个交互式绘图库&…...
刷题第10天
代码随想录刷题第10天 |● 239. 滑动窗口最大值 ● 347.前 K 个高频元素 239. 滑动窗口最大值 唉,好难,先记个思路吧 class Solution { private:class MyQueue { //单调队列(从大到小)public:deque<int> que; // 使用deq…...
Bililive-go 实现直播自动监控录制
前言 最近有直播录制的需求,但是自己手动录制太麻烦繁琐,于是用了开源项目Bililive-go进行全自动监控录制,目前这个项目已经有3K stars了 部署 为了方便我使用了docker compose 部署 version: 3.8 services:bililive:image: chigusa/bilil…...
【Redis】Redis持久化模式RDB
目录 引子 RDB RDB的优缺点 小节一下 引子 不论把Redis作为数据库还是缓存来使用,他肯定有数据需要持久化,这里我们就来聊聊两种持久化机制。这两种机制,其实是 快照 与 日志 的形式。快照:就是当前数据的备份,我可以拷贝到磁…...
Java基础 - 模拟医院挂号系统
模拟医院挂号系统功能 1. 科室管理:新增科室,删除科室(如果有医生在,则不能删除该科室),修改科室 2. 医生管理:录入医生信息以及科室信息,修改医生信息(主要是修改个人…...
【论文精读】基于知识图谱关系路径的多跳智能问答模型研究
💗💗💗欢迎来到我的博客,你将找到有关如何使用技术解决问题的文章,也会找到某个技术的学习路线。无论你是何种职业,我都希望我的博客对你有所帮助。最后不要忘记订阅我的博客以获取最新文章,也欢…...
uni app 微信小程序微信支付
使用方法 接口传参 使用wx.requestPayment方法是一个统一各平台的客户端支付API,不管是在某家小程序还是在App中,客户端均使用本API调用支付...
TDengine 快速体验(Docker 镜像方式)
简介 TDengine 可以通过安装包、Docker 镜像 及云服务快速体验 TDengine 的功能,本节首先介绍如何通过 Docker 快速体验 TDengine,然后介绍如何在 Docker 环境下体验 TDengine 的写入和查询功能。如果你不熟悉 Docker,请使用 安装包的方式快…...
3403. 从盒子中找出字典序最大的字符串 I
3403. 从盒子中找出字典序最大的字符串 I 题目链接:3403. 从盒子中找出字典序最大的字符串 I 代码如下: class Solution { public:string answerString(string word, int numFriends) {if (numFriends 1) {return word;}string res;for (int i 0;i &…...
【JavaSE】绘图与事件入门学习笔记
-Java绘图坐标体系 坐标体系-介绍 坐标原点位于左上角,以像素为单位。 在Java坐标系中,第一个是x坐标,表示当前位置为水平方向,距离坐标原点x个像素;第二个是y坐标,表示当前位置为垂直方向,距离坐标原点y个像素。 坐标体系-像素 …...
【HTTP三个基础问题】
面试官您好!HTTP是超文本传输协议,是互联网上客户端和服务器之间传输超文本数据(比如文字、图片、音频、视频等)的核心协议,当前互联网应用最广泛的版本是HTTP1.1,它基于经典的C/S模型,也就是客…...
【HarmonyOS 5 开发速记】如何获取用户信息(头像/昵称/手机号)
1.获取 authorizationCode: 2.利用 authorizationCode 获取 accessToken:文档中心 3.获取手机:文档中心 4.获取昵称头像:文档中心 首先创建 request 若要获取手机号,scope必填 phone,permissions 必填 …...
laravel8+vue3.0+element-plus搭建方法
创建 laravel8 项目 composer create-project --prefer-dist laravel/laravel laravel8 8.* 安装 laravel/ui composer require laravel/ui 修改 package.json 文件 "devDependencies": {"vue/compiler-sfc": "^3.0.7","axios": …...
云原生玩法三问:构建自定义开发环境
云原生玩法三问:构建自定义开发环境 引言 临时运维一个古董项目,无文档,无环境,无交接人,俗称三无。 运行设备的环境老,本地环境版本高,ssh不过去。正好最近对 腾讯出品的云原生 cnb 感兴趣&…...
【C++特殊工具与技术】优化内存分配(一):C++中的内存分配
目录 一、C 内存的基本概念 1.1 内存的物理与逻辑结构 1.2 C 程序的内存区域划分 二、栈内存分配 2.1 栈内存的特点 2.2 栈内存分配示例 三、堆内存分配 3.1 new和delete操作符 4.2 内存泄漏与悬空指针问题 4.3 new和delete的重载 四、智能指针…...
作为测试我们应该关注redis哪些方面
1、功能测试 数据结构操作:验证字符串、列表、哈希、集合和有序的基本操作是否正确 持久化:测试aof和aof持久化机制,确保数据在开启后正确恢复。 事务:检查事务的原子性和回滚机制。 发布订阅:确保消息正确传递。 2、性…...
手机平板能效生态设计指令EU 2023/1670标准解读
手机平板能效生态设计指令EU 2023/1670标准解读 以下是针对欧盟《手机和平板电脑生态设计法规》(EU) 2023/1670 的核心解读,综合法规核心要求、最新修正及企业合规要点: 一、法规背景与目标 生效与强制时间 发布于2023年8月31日(OJ公报&…...
