当前位置: 首页 > news >正文

回溯算法-Java【力扣】【算法学习day.14】

前言

###我做这类文档一个重要的目的还是给正在学习的大家提供方向(例如想要掌握基础用法,该刷哪些题?)我的解析也不会做的非常详细,只会提供思路和一些关键点,力扣上的大佬们的题解质量是非常非常高滴!!!


什么是回溯算法

        回溯搜索法是一种搜索方式,它通过不断尝试各种可能的选择,当发现当前选择不满足条件时,就回溯到上一个状态,重新进行选择,直到找到满足条件的解或者遍历完所有可能的情况。例如在解决迷宫问题时,可以使用回溯搜索法,从一个起始位置开始尝试不同的方向前进,如果遇到死路就回溯到上一个位置,重新选择其他方向。


习题

1.组合

题目链接:77. 组合 - 力扣(LeetCode)

题面:

基本分析:抽象成树的结构进行递归

代码:

class Solution {int len;public List<List<Integer>> combine(int n, int k) {List<List<Integer>> ans = new ArrayList<>();Stack<Integer> stack = new Stack<>();len = k;recursion(1,n,ans,stack);return ans;}public void recursion(int start,int end,List<List<Integer>> ans,Stack<Integer> stack){if(stack.size()==len){ans.add(new ArrayList<>(stack));return;}for(int i = start;i<=end - (len - stack.size()) + 1;i++){stack.push(i);recursion(i+1,end,ans,stack);stack.pop();}}
}

2.组合总和III

题目链接:216. 组合总和 III - 力扣(LeetCode)

题面:

基本分析:和上一题类似,只不过多一个判断相加之和 

代码:

class Solution {int len;int target;public List<List<Integer>> combinationSum3(int k, int n) {List<List<Integer>> ans = new ArrayList<>();len = k;target = n;Stack<Integer> stack = new Stack<>();recursion(1,9,stack,ans,0);return ans;}public void recursion(int l,int r,Stack<Integer> stack,List<List<Integer>> ans,int sum){if(sum>target)return;if(stack.size()>len)return;if(sum==target&&stack.size()==len)ans.add(new ArrayList<>(stack));for(int i = l;i<=r-(len-stack.size())+1;i++){stack.push(i);recursion(i+1,r,stack,ans,sum+i);stack.pop();}}
}

3.电话号码的字母组合

题目链接:17. 电话号码的字母组合 - 力扣(LeetCode)

题面:

基本分析:暴力递归

代码:

class Solution {char[][] arr = {{'d'},{'a'},{'a','b','c'},{'d','e','f'},{'g','h','i'},{'j','k','l'},{'m','n','o'},{'p','q','r','s'},{'t','u','v'},{'w','x','y','z'}};int count = -1;int len;public List<String> letterCombinations(String digits) {List<String> list = new ArrayList<>();if(digits.equals(""))return list;              char[] brr = digits.toCharArray();int n = brr.length;len = n;char[] crr = new char[n];recursion(0,brr,crr,list);return list;}public void recursion(int u,char[] brr,char[] crr,List<String> list){if(u==len){list.add(new String(crr));return;}char c = brr[u];char[] drr = arr[c-'0'];int m = drr.length;for(int i = 0;i<m;i++){crr[++count]=drr[i];recursion(u+1,brr,crr,list);count--;}}
}

4.组合总和

题目链接:39. 组合总和 - 力扣(LeetCode)

题面:

基本分析:注意剪枝来去重

代码:

class Solution {int[] arr;int len;int t;public List<List<Integer>> combinationSum(int[] candidates, int target) {arr = candidates;List<List<Integer>> list = new ArrayList<>();List<Integer> stack = new Stack<>();len = candidates.length;t = target;Arrays.sort(arr);recursion(list,stack,0,0);return list;}public void recursion(List<List<Integer>> list,List<Integer> stack,int sum,int l){if(sum==t){list.add(new ArrayList<>(stack));return;}for(int i = l;i<len;i++){if(sum+arr[i]>t)return;stack.add(arr[i]);recursion(list,stack,sum+arr[i],i);stack.remove(stack.size()-1);}}
}

5.组合总和II

题目链接:40. 组合总和 II - 力扣(LeetCode)

题面:

基本分析:注意重复元素导致的重复,用set是一种解决办法但是会超时

代码:

class Solution {int t;int[] arr;int n;public List<List<Integer>> combinationSum2(int[] candidates, int target) {Arrays.sort(candidates);arr = candidates;Set<List<Integer>> list = new HashSet<>();List<Integer> stack = new ArrayList<>();n = arr.length;t = target;recursion(list,stack,0,0);return new ArrayList<>(list);}public void recursion(Set<List<Integer>> list,List<Integer> stack,int sum,int l){if(sum==t){list.add(new ArrayList<>(stack));return;}for(int i =l;i<n;i++){if(sum+arr[i]>t)return;if (i > l && arr[i] == arr[i - 1]) {continue;}stack.add(arr[i]);recursion(list,stack,sum+arr[i],i+1);stack.remove(stack.size()-1);}}
}

后言

上面是回溯算法的基本概念和部分习题,下一篇会讲解回溯算法的其他相关力扣习题,希望有所帮助,一同进步,共勉!  

相关文章:

回溯算法-Java【力扣】【算法学习day.14】

前言 ###我做这类文档一个重要的目的还是给正在学习的大家提供方向&#xff08;例如想要掌握基础用法&#xff0c;该刷哪些题&#xff1f;&#xff09;我的解析也不会做的非常详细&#xff0c;只会提供思路和一些关键点&#xff0c;力扣上的大佬们的题解质量是非常非常高滴&am…...

从本地到云端:跨用户请求问题的完美解决方案

对于某些单个请求或响应中含有多个用户信息的服务&#xff0c;SDK提供了一套基于统一的UCS拆分和聚合的解决方案供开发者使用。 请求拆分 对于跨用户服务的请求&#xff0c;我们提供了两个处理方案&#xff1a; 【1】根据用户信息拆分请求&#xff1a; 场景&#xff1a;请求内…...

leetcode day4 409+5

409 最长回文串 给定一个包含大写字母和小写字母的字符串 s &#xff0c;返回 通过这些字母构造成的 最长的 回文串 的长度。 在构造过程中&#xff0c;请注意 区分大小写 。比如 "Aa" 不能当做一个回文字符串。 示例 1: 输入:s "abccccdd" 输出:7 解…...

英语语法学习框架(考研)

一、简单句 英语都是由简单句构成&#xff0c;简单句共有五种基本句型&#xff1a;①主谓&#xff1b;②主谓宾&#xff1b;③主谓宾宾补&#xff1b;④主谓宾间宾&#xff08;间接宾语&#xff09;&#xff1b;⑤主系表&#xff1b; 其中谓语是句子最重要的部分&#xff0c;谓…...

基于neo4j的学术论文关系管理系统

正在为毕业设计头疼&#xff1f;又或者在学术研究中总是找不到像样的工具来管理浩瀚的文献资料&#xff1f;今天给大家介绍一款超实用的工具——基于Neo4j的学术论文关系管理系统&#xff0c;让你轻松搞定学术文献的管理与展示&#xff01;&#x1f389; 系统的核心是什么呢&a…...

C#中的委托、匿名方法、Lambda、Action和Func

委托 委托概述 委托是存有对某个方法的引用的一种引用类型变量。定义方法的类型&#xff0c;可以把一个方法当作另一方法的参数。所有的委托&#xff08;Delegate&#xff09;都派生自 System.Delegate 类。委托声明决定了可由该委托引用的方法。 # 声明委托类型 委托类型声…...

IDEA关联Tomcat——最新版本IDEA 2024

1.链接Tomcat到IDEA上 添加Tomcat到IDEA上有两种方式&#xff1a; 第一种&#xff1a; &#xff08;1&#xff09;首先&#xff0c;来到欢迎界面&#xff0c;找到左侧的Customize选项 &#xff08;2&#xff09;然后找到Build、Execution、Deployment选项 &#xff08;3&am…...

【如何获取股票数据18】Python、Java等多种主流语言实例演示获取股票行情api接口之沪深A股解禁限售数据获取实例演示及接口API说明文档

最近一两年内&#xff0c;股票量化分析逐渐成为热门话题。而从事这一领域工作的第一步&#xff0c;就是获取全面且准确的股票数据。因为无论是实时交易数据、历史交易记录、财务数据还是基本面信息&#xff0c;这些数据都是我们进行量化分析时不可或缺的宝贵资源。我们的主要任…...

NVR小程序接入平台/设备EasyNVR多品牌NVR管理工具/设备的多维拓展与灵活应用

在数字化安防时代&#xff0c;NVR批量管理软件/平台EasyNVR作为一种先进的视频监控系统设备&#xff0c;正逐步成为各个领域监控解决方案的首选。NVR批量管理软件/平台EasyNVR作为一款基于端-边-云一体化架构的国标视频融合云平台&#xff0c;凭借其部署简单轻量、功能多样、兼…...

GPT-4o 和 GPT-4 Turbo 模型之间的对比

GPT-4o 和 GPT-4 Turbo 之间的对比 备注 要弄 AI &#xff0c;不同模型之间的对比就比较重要。 GPT-4o 是 GPT-4 Turbo 的升级版本&#xff0c;能够提供比 GPT-4 Turbo 更多的内容和信息&#xff0c;但成功相对来说更高一些。 第三方引用 在 2024 年 5 月 13 日&#xff0…...

gin入门教程(10):实现jwt认证

使用 github.com/golang-jwt/jwt 实现 JWT&#xff08;JSON Web Token&#xff09;可以有效地进行用户身份验证,这个功能往往在接口前后端分离的应用中经常用到。以下是一个基本的示例&#xff0c;演示如何在 Gin 框架中实现 JWT 认证。 目录结构 /hello-gin │ ├── cmd/ …...

Python 基础语法 - 数据类型

顾名思义&#xff0c;计算机就是用来做数学计算的机器&#xff0c;因此&#xff0c;计算机程序理所当然的可以处理各种数值。但是&#xff0c;计算机能处理的远远不止数值&#xff0c;还可以处理文本&#xff0c;图形&#xff0c;音频&#xff0c;视频&#xff0c;网页等各种各…...

自托管无代码数据库Undb

什么是 Undb &#xff1f; Undb 是一个无代码平台&#xff0c;也可以作为后端即服务 (BaaS)。它基于 SQLite&#xff0c;可以使用 Bun 打包成二进制文件用于后端服务。此外&#xff0c;它可以通过 Docker 部署为服务&#xff0c;提供表管理的 UI。 软件特点&#xff1a; ⚡ 无…...

正则的正向前瞻断言和负向前瞻断言

正则的正向前瞻断言和负向前瞻断言 一. 正向前瞻断言二. 负向前瞻断言三. 总结 这是我在这个网站整理的笔记,有错误的地方请指出&#xff0c;关注我&#xff0c;接下来还会持续更新。 作者&#xff1a;神的孩子都在歌唱 正向前瞻断言和负向前瞻断言是正则表达式中用于检查后续字…...

大厂物联网(IoT)高频面试题及参考答案

目录 解释物联网 (IoT) 的基本概念 物联网的主要组成部分有哪些? 描述物联网的基本架构。 IoT 与传统网络有什么区别? 物联网中常用的传感器类型有哪些? 描述物联网的三个主要层次。 简述物联网中数据安全的重要性 描述物联网安全的主要威胁 解释端到端加密在 IoT 中…...

react hook

react hook 最近实习有点忙&#xff0c;所以学习记录没来得及写。 HOC higher order components(HOC) 高阶组件是一个组件&#xff0c;接受一个参数作为组件&#xff0c;返回值也是一个组件的函数。高阶组件作用域强化组件&#xff0c;服用逻辑&#xff0c;提升渲染性能等。…...

Jetpack架构组件_LiveData组件

1.LiveData初识 LiveData:ViewModel管理要展示的数据&#xff08;VM层类似于原MVP中的P层&#xff09;&#xff0c;处理业务逻辑&#xff0c;比如调用服务器的登陆接口业务。通过LiveData观察者模式&#xff0c;只要数据的值发生了改变&#xff0c;就会自动通知VIEW层&#xf…...

Etcd 可观测最佳实践

简介 Etcd 是一个高可用的分布式键值存储系统&#xff0c;它提供了一个可靠的、强一致性的存储服务&#xff0c;用于配置管理和服务发现。它最初由 CoreOS 开发&#xff0c;现在由 Cloud Native Computing Foundation (CNCF) 维护。Etcd 使用 Raft 算法来实现数据的一致性&…...

钉钉录播抓取视频

爬取钉钉视频 免责声明 此脚本仅供学习参考&#xff0c;切勿违法使用下载他人资源进行售卖&#xff0c;本人不但任何责任! 仓库地址: GItee 源码仓库 执行顺序 poxyM3u8开启代理getM3u8url用于获取m3u8文件userAgent随机请求头downVideo|downVideoThreadTqdm单线程下载和…...

centos下面的jdk17的安装配置

文章目录 1.基本指令回顾2.jdk17的安装到这个centos上面2.1首先切换到这个root下面去2.2查看系统jdk版本2.3首先到官网找到进行下载2.4安装包的上传2.5jdk17的安装包的解压过程2.6配置环境变量2.7是否设置成功&#xff0c;查看版本 1.基本指令回顾 ls:list也就是列出来这个目录…...

挑战杯推荐项目

“人工智能”创意赛 - 智能艺术创作助手&#xff1a;借助大模型技术&#xff0c;开发能根据用户输入的主题、风格等要求&#xff0c;生成绘画、音乐、文学作品等多种形式艺术创作灵感或初稿的应用&#xff0c;帮助艺术家和创意爱好者激发创意、提高创作效率。 ​ - 个性化梦境…...

Java 语言特性(面试系列2)

一、SQL 基础 1. 复杂查询 &#xff08;1&#xff09;连接查询&#xff08;JOIN&#xff09; 内连接&#xff08;INNER JOIN&#xff09;&#xff1a;返回两表匹配的记录。 SELECT e.name, d.dept_name FROM employees e INNER JOIN departments d ON e.dept_id d.dept_id; 左…...

零门槛NAS搭建:WinNAS如何让普通电脑秒变私有云?

一、核心优势&#xff1a;专为Windows用户设计的极简NAS WinNAS由深圳耘想存储科技开发&#xff0c;是一款收费低廉但功能全面的Windows NAS工具&#xff0c;主打“无学习成本部署” 。与其他NAS软件相比&#xff0c;其优势在于&#xff1a; 无需硬件改造&#xff1a;将任意W…...

深入浅出:JavaScript 中的 `window.crypto.getRandomValues()` 方法

深入浅出&#xff1a;JavaScript 中的 window.crypto.getRandomValues() 方法 在现代 Web 开发中&#xff0c;随机数的生成看似简单&#xff0c;却隐藏着许多玄机。无论是生成密码、加密密钥&#xff0c;还是创建安全令牌&#xff0c;随机数的质量直接关系到系统的安全性。Jav…...

HTML 列表、表格、表单

1 列表标签 作用&#xff1a;布局内容排列整齐的区域 列表分类&#xff1a;无序列表、有序列表、定义列表。 例如&#xff1a; 1.1 无序列表 标签&#xff1a;ul 嵌套 li&#xff0c;ul是无序列表&#xff0c;li是列表条目。 注意事项&#xff1a; ul 标签里面只能包裹 li…...

oracle与MySQL数据库之间数据同步的技术要点

Oracle与MySQL数据库之间的数据同步是一个涉及多个技术要点的复杂任务。由于Oracle和MySQL的架构差异&#xff0c;它们的数据同步要求既要保持数据的准确性和一致性&#xff0c;又要处理好性能问题。以下是一些主要的技术要点&#xff1a; 数据结构差异 数据类型差异&#xff…...

【电力电子】基于STM32F103C8T6单片机双极性SPWM逆变(硬件篇)

本项目是基于 STM32F103C8T6 微控制器的 SPWM(正弦脉宽调制)电源模块,能够生成可调频率和幅值的正弦波交流电源输出。该项目适用于逆变器、UPS电源、变频器等应用场景。 供电电源 输入电压采集 上图为本设计的电源电路,图中 D1 为二极管, 其目的是防止正负极电源反接, …...

前端开发者常用网站

Can I use网站&#xff1a;一个查询网页技术兼容性的网站 一个查询网页技术兼容性的网站Can I use&#xff1a;Can I use... Support tables for HTML5, CSS3, etc (查询浏览器对HTML5的支持情况) 权威网站&#xff1a;MDN JavaScript权威网站&#xff1a;JavaScript | MDN...

02.运算符

目录 什么是运算符 算术运算符 1.基本四则运算符 2.增量运算符 3.自增/自减运算符 关系运算符 逻辑运算符 &&&#xff1a;逻辑与 ||&#xff1a;逻辑或 &#xff01;&#xff1a;逻辑非 短路求值 位运算符 按位与&&#xff1a; 按位或 | 按位取反~ …...

Linux-进程间的通信

1、IPC&#xff1a; Inter Process Communication&#xff08;进程间通信&#xff09;&#xff1a; 由于每个进程在操作系统中有独立的地址空间&#xff0c;它们不能像线程那样直接访问彼此的内存&#xff0c;所以必须通过某种方式进行通信。 常见的 IPC 方式包括&#…...