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

算法练习(6):牛客在线编程06 递归/回溯

package jz.bm;import java.io.PushbackInputStream;
import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.Arrays;public class bm6 {/*** BM55 没有重复项数字的全排列*/ArrayList<ArrayList<Integer>> res = new ArrayList<>();public ArrayList<ArrayList<Integer>> permute(int[] num) {if (num.length == 0) {return res;}Arrays.sort(num);boolean[] used = new boolean[num.length];Arrays.fill(used, false);dfs(num, used, new ArrayList<>());return res;}private void dfs(int[] num, boolean[] used, ArrayList<Integer> list) {if (list.size() == num.length) {res.add(new ArrayList<>(list));} else {for (int i = 0; i < num.length; i++) {if (used[i]) {continue;}used[i] = true;list.add(num[i]);dfs(num, used, list);used[i] = false;list.remove(list.size() - 1);}}}/*** BM56 有重复项数字的全排列*/public ArrayList<ArrayList<Integer>> permuteUnique(int[] num) {if (num.length == 0) {return res;}Arrays.sort(num);boolean[] used = new boolean[num.length];Arrays.fill(used, false);dfs56(num, used, new ArrayList<>());return res;}private void dfs56(int[] num, boolean[] used, ArrayList<Integer> list) {if (list.size() == num.length) {res.add(new ArrayList<>(list));} else {for (int i = 0; i < num.length; i++) {if (used[i]) {continue;}if (i > 0 && num[i] == num[i - 1] && used[i - 1]) {continue;}used[i]  = true;list.add(num[i]);dfs56(num, used, list);used[i] = false;list.remove(list.size() - 1);}}}/*** BM57 岛屿数量*/public int solve (char[][] grid) {int m = grid.length;if (m == 0) {return 0;}int n = grid[0].length;if (n == 0) {return 0;}int res = 0;for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {if (grid[i][j] == '1') {res++;dfs57(grid, m, n, i, j);}}}return res;}private void dfs57(char[][] grid, int m, int n, int i, int j) {grid[i][j] = '0';if (i - 1 >= 0 && grid[i - 1][j] == '1') {dfs57(grid, m, n, i - 1, j);}if (i + 1 < m && grid[i + 1][j] == '1') {dfs57(grid, m, n, i + 1, j);}if (j - 1 >= 0 && grid[i][j - 1] == '1') {dfs57(grid, m, n, i, j - 1);}if (j + 1 < n && grid[i][j + 1] == '1') {dfs57(grid, m, n, i, j + 1);}}/*** BM58 字符串的排列*/ArrayList<String> strings = new ArrayList<>();public ArrayList<String> Permutation(String str) {if (str == null || "".equals(str)) {return strings;}char[] chars = str.toCharArray();Arrays.sort(chars);boolean[] used = new boolean[chars.length];Arrays.fill(used, false);dfs58(chars, used, new StringBuilder());return strings;}private void dfs58(char[] chars, boolean[] used, StringBuilder stringBuilder) {if (stringBuilder.length() == chars.length) {strings.add(new String(stringBuilder));} else {for (int i = 0; i < chars.length; i++) {if (used[i]) {continue;}if (i > 0 && chars[i] == chars[i - 1] && used[i - 1]) {continue;}stringBuilder.append(chars[i]);used[i] = true;dfs58(chars, used, stringBuilder);used[i] = false;stringBuilder.deleteCharAt(stringBuilder.length() - 1);}}}/*** BM60 括号生成*/ArrayList<String> arrayList = new ArrayList<>();public ArrayList<String> generateParenthesis (int n) {if (n == 0) {return arrayList;}dfs60(n, 0, 0, new StringBuilder());return arrayList;}private void dfs60(int n, int left, int right, StringBuilder stringBuilder) {if (left == n && right == n) {arrayList.add(new String(stringBuilder));return;}if (left < n) {stringBuilder.append("(");dfs60(n, left + 1, right, stringBuilder);stringBuilder.deleteCharAt(left + right);}if (right < left && right < n) {stringBuilder.append(")");dfs60(n, left, right + 1, stringBuilder);stringBuilder.deleteCharAt(left + right);}}/*** BM61 矩阵最长递增路径*/int max = 0;public int solve (int[][] matrix) {int m = matrix.length;int n = matrix[0].length;//这题dfs不需要记录visited, 因为能走的路径是单向的for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {dfs61(matrix, m, n, i, j, 1);}}return max;}private void dfs61(int[][] matrix, int m, int n, int i, int j, int count) {if (i - 1 >= 0 && matrix[i - 1][j] > matrix[i][j]) {max = Math.max(count + 1, max);dfs61(matrix, m, n, i - 1, j, count + 1);}if (i + 1 < m &&  matrix[i + 1][j] > matrix[i][j]) {max = Math.max(count + 1, max);dfs61(matrix, m, n, i + 1, j, count + 1);}if (j - 1 >= 0 && matrix[i][j - 1] > matrix[i][j]) {max = Math.max(count + 1, max);dfs61(matrix, m, n, i, j - 1, count + 1);}if (j + 1 < n && matrix[i][j + 1] > matrix[i][j]) {max = Math.max(count + 1, max);dfs61(matrix, m, n, i, j + 1, count + 1);}}
}

相关文章:

算法练习(6):牛客在线编程06 递归/回溯

package jz.bm;import java.io.PushbackInputStream; import java.lang.reflect.Array; import java.util.ArrayList; import java.util.Arrays;public class bm6 {/*** BM55 没有重复项数字的全排列*/ArrayList<ArrayList<Integer>> res new ArrayList<>()…...

C#使用OpenCv(OpenCVSharp)图像局部二值化处理实例

本文实例演示C#语言中如何使用OpenCv(OpenCVSharp)对图像进行局部二值化处理。 目录 图像二值化原理 局部二值化 自适应阈值 实例 效果...

MySQL多表关联查询

目录 1. inner join&#xff1a; 2. left join&#xff1a; 3. right join&#xff1a; 4.自连接 5.交叉连接&#xff1a; 6、联合查询 7、子查询 1. inner join&#xff1a; 代表选择的是两个表的交差部分。 内连接就是表间的主键与外键相连&#xff0c;只取得键值一致…...

flutter开发实战-CustomClipper裁剪长图帧动画效果

flutter开发实战-CustomClipper裁剪长图帧动画效果 在开发过程中&#xff0c;经常遇到帧动画的每一帧图显示在超长图上&#xff0c;需要处理这种帧动画效果。我这里使用的是CustomClipper 一、CustomClipper CustomClipper继承于Listenable abstract class CustomClipper e…...

CSS 中的优先级规则是怎样的?

聚沙成塔每天进步一点点 ⭐ 专栏简介⭐内联样式&#xff08;Inline Styles&#xff09;⭐ID 选择器&#xff08;ID Selectors&#xff09;⭐类选择器、属性选择器和伪类选择器&#xff08;Class, Attribute, and Pseudo-class Selectors&#xff09;⭐元素选择器和伪元素选择器…...

概率图模型(Probabilistic Graphical Model,PGM)

概率图模型&#xff08;Probabilistic Graphical Model&#xff0c;PGM&#xff09;&#xff0c;是一种用图结构来描述多元随机变量之间条件独立性的概率模型。它可以用来表示复杂的概率分布&#xff0c;进行有效的推理和学习&#xff0c;以及解决各种实际问题&#xff0c;如图…...

Oracle 知识篇+会话级全局临时表在不同连接模式中的表现

标签&#xff1a;会话级临时表、全局临时表、幻读释义&#xff1a;Oracle 全局临时表又叫GTT ★ 结论 ✔ 专用服务器模式&#xff1a;不同应用会话只能访问自己的数据 ✔ 共享服务器模式&#xff1a;不同应用会话只能访问自己的数据 ✔ 数据库驻留连接池模式&#xff1a;不同应…...

MySQL 数据库文件的导入导出

目录 数据库的导出 导出整个数据库 导出数据库中的数据表 导出数据库结构 导出数据库中表的表结构 导出多个数据库 导出所有数据库 数据库的导入 数据库的导出 mysqldump -h IP地址 -P 端口 -u 用户名 -p 数据库名 > 导出的文件名 用管理员权限打开cmd进入MySQL的bi…...

找不到资产文件project.assets.json

NuGet 在“obj”文件夹中写入名为 project.assets.json 的文件&#xff0c;.NET SDK 使用该文件来获取有关要传递到编译器的包的信息 。 如果在生成过程中找不到资产文件 project.assets.json&#xff0c;则会发生此错误。 1.执行命令的方式解决 点击工具&#xff0c;分别展开命…...

【python】python将json字符串导出excel | pandas处理json字符串保存为csv

如何将json转为csv 1、通过json直接转为csv 在Python中&#xff0c;你可以使用pandas库来处理DataFrame&#xff08;数据帧&#xff09;和将JSON数据转换为CSV格式。下面是一个简单的示例代码&#xff0c;展示了如何使用pandas库将JSON数据转换为CSV文件&#xff1a; import p…...

opencv 基础54-利用形状场景算法比较轮廓-cv2.createShapeContextDistanceExtractor()

注意&#xff1a;新版本的opencv 4 已经没有这个函数 cv2.createShapeContextDistanceExtractor() 形状场景算法是一种用于比较轮廓或形状的方法。这种算法通常用于计算两个形状之间的相似性或差异性&#xff0c;以及找到最佳的匹配方式。 下面是一种基本的比较轮廓的流程&…...

分布式系统理论

以前的架构...

Gartner发布2023年的存储技术成熟曲线

技术路线说明 Gartner自1995年起开始采用技术成熟度曲线&#xff0c;它描述创新的典型发展过程&#xff0c;即从过热期发展到幻灭低谷期&#xff0c;再到人们最终理解创新在市场或领域内的意义和角色。 一项技术 (或相关创新)在发展到最终成熟期的过程中经历多个阶段&#xff1…...

c++ 有元

友元分为两部分内容 友元函数友元类 友元函数 问题&#xff1a;当我们尝试去重载operator<<&#xff0c;然后发现没办法将operator<<重载成成员函数。因为cout的输出流对象和隐含的this指针在抢占第一个参数的位置。this指针默认是第一个参数也就是左操作 数了。…...

安卓:网络框架okhttp

目录 一、okhttp介绍 1. OkHttpClient类&#xff1a; 常用方法&#xff1a; 2. Request类&#xff1a; 常用方法&#xff1a; 3. Response类&#xff1a; 常用方法&#xff1a; 4. Call类&#xff1a; 常用方法&#xff1a; 5. Interceptor接口&#xff1a; 常用方法&…...

Python爬虫 爬取图片

在我们日常上网浏览网页的时候&#xff0c;经常会看到一些好看的图片&#xff0c;我们就希望把这些图片保存下载&#xff0c;或者用户用来做桌面壁纸&#xff0c;或者用来做设计的素材。 我们最常规的做法就是通过鼠标右键&#xff0c;选择另存为。但有些图片鼠标右键的时候并没…...

【云原生】Pod详讲

目录 一、Pod基础概念1.1//在Kubrenetes集群中Pod有如下两种使用方式&#xff1a;1.2pause容器使得Pod中的所有容器可以共享两种资源&#xff1a;网络和存储。1.3kubernetes中的pause容器主要为每个容器提供以下功能&#xff1a;1.4Kubernetes设计这样的Pod概念和特殊组成结构有…...

先进先出的队

文章目录 队列特点队列实现 队列特点 先进先出&#xff0c;后进后出 队列实现 queue.c#define _CRT_SECURE_NO_WARNINGS 1 #include"Queue.h" //初始化 void QueInit(Queue* pq) {assert(pq);pq->head NULL;pq->tail NULL;pq->size 0; } //入队&#…...

怎样学会单片机

0、学单片机首先要明白&#xff0c;一个单片机啥也干不了&#xff0c;学单片机的目的是学习怎么用单片机驱动外部设备&#xff0c;比如数码管&#xff0c;电机&#xff0c;液晶屏等&#xff0c;这个需要外围电路的配合&#xff0c;所以学习单片机在这个层面上可以等同为学习单片…...

数据结构笔记--常见二叉树分类及判断实现

目录 1--搜索二叉树 2--完全二叉树 3--平衡二叉树 4--满二叉树 1--搜索二叉树 搜索二叉树的性质&#xff1a;左子树的节点值都比根节点小&#xff0c;右子树的节点值都比根节点大&#xff1b; 如何判断一颗二叉树是搜索二叉树&#xff1f; 主要思路&#xff1a; 递归自底向…...

深入剖析AI大模型:大模型时代的 Prompt 工程全解析

今天聊的内容&#xff0c;我认为是AI开发里面非常重要的内容。它在AI开发里无处不在&#xff0c;当你对 AI 助手说 "用李白的风格写一首关于人工智能的诗"&#xff0c;或者让翻译模型 "将这段合同翻译成商务日语" 时&#xff0c;输入的这句话就是 Prompt。…...

线程同步:确保多线程程序的安全与高效!

全文目录&#xff1a; 开篇语前序前言第一部分&#xff1a;线程同步的概念与问题1.1 线程同步的概念1.2 线程同步的问题1.3 线程同步的解决方案 第二部分&#xff1a;synchronized关键字的使用2.1 使用 synchronized修饰方法2.2 使用 synchronized修饰代码块 第三部分&#xff…...

从深圳崛起的“机器之眼”:赴港乐动机器人的万亿赛道赶考路

进入2025年以来&#xff0c;尽管围绕人形机器人、具身智能等机器人赛道的质疑声不断&#xff0c;但全球市场热度依然高涨&#xff0c;入局者持续增加。 以国内市场为例&#xff0c;天眼查专业版数据显示&#xff0c;截至5月底&#xff0c;我国现存在业、存续状态的机器人相关企…...

五年级数学知识边界总结思考-下册

目录 一、背景二、过程1.观察物体小学五年级下册“观察物体”知识点详解&#xff1a;由来、作用与意义**一、知识点核心内容****二、知识点的由来&#xff1a;从生活实践到数学抽象****三、知识的作用&#xff1a;解决实际问题的工具****四、学习的意义&#xff1a;培养核心素养…...

自然语言处理——Transformer

自然语言处理——Transformer 自注意力机制多头注意力机制Transformer 虽然循环神经网络可以对具有序列特性的数据非常有效&#xff0c;它能挖掘数据中的时序信息以及语义信息&#xff0c;但是它有一个很大的缺陷——很难并行化。 我们可以考虑用CNN来替代RNN&#xff0c;但是…...

如何理解 IP 数据报中的 TTL?

目录 前言理解 前言 面试灵魂一问&#xff1a;说说对 IP 数据报中 TTL 的理解&#xff1f;我们都知道&#xff0c;IP 数据报由首部和数据两部分组成&#xff0c;首部又分为两部分&#xff1a;固定部分和可变部分&#xff0c;共占 20 字节&#xff0c;而即将讨论的 TTL 就位于首…...

学校时钟系统,标准考场时钟系统,AI亮相2025高考,赛思时钟系统为教育公平筑起“精准防线”

2025年#高考 将在近日拉开帷幕&#xff0c;#AI 监考一度冲上热搜。当AI深度融入高考&#xff0c;#时间同步 不再是辅助功能&#xff0c;而是决定AI监考系统成败的“生命线”。 AI亮相2025高考&#xff0c;40种异常行为0.5秒精准识别 2025年高考即将拉开帷幕&#xff0c;江西、…...

Hive 存储格式深度解析:从 TextFile 到 ORC,如何选对数据存储方案?

在大数据处理领域&#xff0c;Hive 作为 Hadoop 生态中重要的数据仓库工具&#xff0c;其存储格式的选择直接影响数据存储成本、查询效率和计算资源消耗。面对 TextFile、SequenceFile、Parquet、RCFile、ORC 等多种存储格式&#xff0c;很多开发者常常陷入选择困境。本文将从底…...

Xen Server服务器释放磁盘空间

disk.sh #!/bin/bashcd /run/sr-mount/e54f0646-ae11-0457-b64f-eba4673b824c # 全部虚拟机物理磁盘文件存储 a$(ls -l | awk {print $NF} | cut -d. -f1) # 使用中的虚拟机物理磁盘文件 b$(xe vm-disk-list --multiple | grep uuid | awk {print $NF})printf "%s\n"…...

三分算法与DeepSeek辅助证明是单峰函数

前置 单峰函数有唯一的最大值&#xff0c;最大值左侧的数值严格单调递增&#xff0c;最大值右侧的数值严格单调递减。 单谷函数有唯一的最小值&#xff0c;最小值左侧的数值严格单调递减&#xff0c;最小值右侧的数值严格单调递增。 三分的本质 三分和二分一样都是通过不断缩…...