数据结构与算法--其他算法

数据结构与算法--其他算法

  • 1 汉诺塔问题
  • 2 字符串的全部子序列
  • 3 字符串的全排列
  • 4 纸牌问题
  • 5 逆序栈问题
  • 6 数字和字符串转换问题
  • 7 背包问题
  • 8 N皇后问题

暴力递归就是尝试
1,把问题转化为规模缩小了的同类问题的子问题
2,有明确的不需要继续进行递归的条件(base case)
3,有当得到了子问题的结果之后的决策过程
4,不记录每一个子问题的解

 


 

1 汉诺塔问题

 

打印n层汉诺塔从最左边移动到最右边的全部过程

如下图所示,把 A 上的方块从移动到 C 上,要求 在移动的过程中 ,小的块在大的块上面

假设有三个点 : from to other,有 i 个方块
问题可以转换成 将 1 ~ i个圆盘从from点移动到to 点,过程如下 :

  1. 1 ~ (i - 1)个方块从 from 点移动到 other
  2. 将 第i个方块从 from点移动到 to
  3. i - 1个方块从 other点移动到 to

如下所示

1)
在这里插入图片描述
 

2)
在这里插入图片描述

 

3)
在这里插入图片描述

coding

public class HanoiTest {public static void main(String[] args) {hanoi(20);System.out.println(iCount);}public static int iCount = 0;public static void hanoi(int n) {if (n > 0) {func(n, "A", "B", "C");}}public static void func(int i, String start, String end, String other) {if (i == 1) {System.out.println("move 1 from " + start + " to " + end);iCount ++;} else {func(i - 1, start, other, end);iCount ++;System.out.println("move " + i + " from " + start + " to " + end);func(i - 1, other, end, start);}}
}

 


 

2 字符串的全部子序列

 

假设有字符串 abc ,要求打印出 abc的全部子序列

可根据包不包含每个字符 构建如图所示的二叉树
在这里插入图片描述

coding

public class PrintAllSubSequenceTest {public static void main(String[] args) {List<String> list = processIteration("abc".toCharArray());for (String s : list) {System.out.println(s);}}public static List<String> characterList = new ArrayList<>();public static List<String> getAllSubSequence(String parentStr) {characterList.clear();process(parentStr.toCharArray(), 0);return characterList;}/*** 当前来到了 i 位置 子序列中要和不要改字符走两条路** @param chars* @param i*/public static void process(char[] chars, int i) {// 到了最后一个位置if (i == chars.length) {characterList.add(String.valueOf(chars));return;}process(chars, i + 1);// 要 i 位置字符的路char temp = chars[i];chars[i] = 0;process(chars, i + 1);// 要 i 位置字符的路chars[i] = temp; //把字符串还原}/*** 使用迭代的方法** @param chars*/public static List<String>  processIteration(char[] chars) {List<String> retList = new ArrayList<>();for (int i = 0; i < chars.length;i++) {String str = "";for (int j = i ; j < chars.length;j++){str += chars[j];retList.add(str);}}return retList;}
}

 


 

3 字符串的全排列

 

打印一个字符串的全部排列

public class StringPermutationTest {public static void main(String[] args) {List<String> strings = getAllSubPermutation("abc");for (String s : strings) {System.out.println(s);}}public static List<String> getAllSubPermutation(String str){List<String> subPermutationList = new ArrayList<>();if (str == null || str.length() == 0){return subPermutationList;}process(0,str.toCharArray(),subPermutationList);return subPermutationList;}/*** 当前来到的是 i 位置* str[0..i-1]是之前做的选择* @param i* @param str* @param retList*/public static void process(int i,char[] str,List<String> retList){if (i == str.length){retList.add(String.valueOf(str));}for (int j = i; j < str.length;j++){swap(str,i,j);process(i + 1,str,retList);// 交换回来swap(str,i,j);}}public static void swap(char[] chars,int i,int j){char temp = chars[i];chars[i] = chars[j];chars[j] = temp;}
}

打印一个字符串的全部排列,要求不能出现重复的排列

public class StringPermutationTest {public static void main(String[] args) {List<String> strings = getAllSubPermutation("abc");for (String s : strings) {System.out.println(s);}}public static List<String> getAllSubPermutation(String str){List<String> subPermutationList = new ArrayList<>();if (str == null || str.length() == 0){return subPermutationList;}process(0,str.toCharArray(),subPermutationList);return subPermutationList;}/*** 当前来到的是 i 位置* str[0..i-1]是之前做的选择* @param i* @param str* @param retList*/public static void process(int i,char[] str,List<String> retList){if (i == str.length){retList.add(String.valueOf(str));}boolean[] bVisited = new boolean[26];for (int j = i; j < str.length;j++){//字符串没有被试过 才进行处理 if (!bVisited[str[j] - 'a']) {bVisited[str[j] - 'a'] = true;swap(str,i,j);process(i + 1,str,retList);// 交换回来swap(str,i,j);}}}public static void swap(char[] chars,int i,int j){char temp = chars[i];chars[i] = chars[j];chars[j] = temp;}
}

 


 

4 纸牌问题

 

给定一个整型数组arr,代表数值不同的纸牌排成一条线。玩家A和玩家B依次拿走每张纸牌,规定玩家A先拿,玩家B后拿,但是每个玩家每次只能拿走最左或最右的纸牌,玩家A和玩家B都绝顶聪明。请返回最后获胜者的分数

例如 :
arr=[1,2,100,4]。
开始时,玩家A只能拿走1或4。如果开始时玩家A拿走1,则排列变为[2,100,4],接下来玩家 B可以拿走2或4,然后继续轮到玩家A… 如果开始时玩家A拿走4,则排列变为[1,2,100],接下来玩家B可以拿走1或100,然后继续轮到玩家A… 玩家A作为绝顶聪明的人不会先拿4,因为拿4之后,玩家B将拿走100。所以玩家A会先拿1,
让排列变为[2,100,4],接下来玩家B不管怎么选,100都会被玩家 A拿走。玩家A会获胜,分数为101。所以返回101。

arr=[1,100,2]。
开始时,玩家A不管拿1还是2,玩家B作为绝顶聪明的人,都会把100拿走。玩家B会获胜,分数为100。所以返回100。

ooding

public class CardInLineTest {public static void main(String[] args) {int[] arr = {1,2,100,4};int iWinScore = win(arr);System.out.println(iWinScore);}/*** 先手函数* 在 L..R范围上先手拿牌 返回最大值* @param arr* @param L* @param R* @return*/public static int first(int[] arr, int L, int R) {// 如果只有一个数 直接拿走if (L == R) {return arr[L];}// 返回一个最大值return Math.max(arr[L] + second(arr, L + 1, R), // 先手拿走最左侧的数 后手在 (L + 1)..R范围上arr[R] + second(arr, L, R - 1)// 先手拿走最右侧的数 后手在 L..(R - 1)范围上);}/*** 后手函数** @param arr* @param L* @param R* @return*/public static int second(int[] arr, int L, int R) {// 因为是后手 L == R时 被别人拿走 因此直接返回if (L == R){return 0;}// 因为是别人决定的  因此会别人会把最小的留给自己return Math.min(first(arr,L + 1,R),// 别人拿走了L上 先手在 (L + 1)..R范围上first(arr,L,R -1));}public static int win(int[] arr){if (arr == null || arr.length == 0){return 0;}return Math.max(first(arr,0,arr.length - 1),second(arr,0,arr.length -1));}
}

 


 

5 逆序栈问题

 

给你一个栈,请你逆序这个栈,不能申请额外的数据结构,只能使用递归函数。
如何实现?

coding

public class ReverseStackNoRecurTest {public static void main(String[] args) {Stack<Integer> stack = new Stack<>();stack.push(3);stack.push(2);stack.push(1);reverseStack(stack);while (!stack.isEmpty()){System.out.println(stack.pop());}}/*** 反转栈* @param stack*/public static void reverseStack(Stack<Integer> stack){if (stack.isEmpty()){return;}// 每次调用都从栈中移除栈底元素int bottomEle = getBottomEle(stack);// 继续反转栈reverseStack(stack);stack.push(bottomEle);}/*** 从栈中移除栈底的元素* @param stack* @return*/public static int getBottomEle(Stack<Integer> stack){int ret = stack.pop();if (stack.isEmpty()){return ret;} else {int last = getBottomEle(stack);stack.push(ret);return last;}}
}

 


 

6 数字和字符串转换问题

 
规定1和A对应、2和B对应、3和C对应… 那么一个数字字符串比如"111",就可以转化为"AAA"、“KA"和"AK”。
给定一个只有数字字符组成的字符串str,返回有多少种转化结果

public class ConvertToLetterStringTest {public static void main(String[] args) {String str = "111";int count = convertToLetterString(str);System.out.println(count);}public static int convertToLetterString(String str){if (str == null || str.length() == 0){return 0;}return process(str.toCharArray(),0);}/*** [0..index-1]位置的字符已经做过决定* 当前来到 index位置* @param chr* @param index* @return*/public static int process(char[] chr,int index){if (index == chr.length){ //来到字符串的最后位置return 1;}if (chr[index] == '0') { // 出现 0 则无效 返回 0return 0;}if (chr[index] == '1'){int ret = process(chr,index + 1);// index 位置自己作为单独的部分 后续有多少种if (index + 1 < chr.length){ret += process(chr,index + 2);// (index 和 index + 1)作为单独的部分 后续有多少种}return ret;}if (chr[index] == '2'){int ret = process(chr,index + 1); //  index 位置自己作为单独的部分 后续有多少种if (index + 1 < chr.length && (chr[index + 1] <= '6' && chr[index] >= '0')) {ret += process(chr,index + 2);// (index 和 index + 1)作为单独的部分 后续有多少种}return ret;}// index位置的字符为 3..9的情况return process(chr,index + 1);}
}

 


 

7 背包问题

 

给定两个长度都为N的数组weightsvaluesweights[i]values[i]分别代表
i号物品的重量和价值。给定一个正数bag,表示一个载重bag的袋子,你装的物
品不能超过这个重量。返回你能装下最多的价值是多少?

coding

public class KnapsackQuesTest {/*** index... 之后的货物随意选择,形成的最大价值返回* 重量不能超过 bagWeight* @param weights index号货物的价值* @param values index 号货物的重量* @param index* @param alreadyWeight 之前做的决定 所达到的重量* @param bagWeight 背包载重* @return*/public static int process(int[] weights,int[] values,int index,int alreadyWeight,int bagWeight){if (alreadyWeight > bagWeight){return 0;}if (index == weights.length){return 0;}return Math.max(// 不要index位置的货物process(weights, values, index + 1, alreadyWeight, bagWeight),// 要index位置的货物values[index] + process(weights, values, index + 1, weights[index] + alreadyWeight,bagWeight));}
}

 


 

8 N皇后问题

 

N皇后问题是指在N*N的棋盘上要摆N个皇后,要求任何两个皇后不同行、不同列,也不在同一条斜线上。
给定一个整数n,返回n皇后的摆法有多少种。

n=1,返回1

n=232皇后和3皇后问题无论怎么摆都不行,返回0

n=8,返回92。

coding

public class NQueuesQues {public static void main(String[] args) {System.out.println(num(8));}/**** @param n 皇后的个数* @return*/public static int num(int n){if (n < 1){return 0;}int[] rec = new int[n]; // rec[index] index行的皇后放在了第几列return process(0,rec,n);}/**** @param index 当前来到的行* @param rec index 行放在了哪一列* @param n 行数* @return*/public static int process(int index,int[] rec,int n){if (index == n){ // 到最后一行的下一行  则说明之前有一种选择是正确的 找到了一种摆放的方法return 1;}int ret = 0;// 每一列进行尝试for (int col = 0; col < n;col++){if (isValid(rec,index,col)){// 有效 则将 index 行的皇后放在 col列rec[index] = col;//继续处理 下一行ret += process(index + 1,rec,n);}}return ret;}/***  判断 r 行的皇后 放在 c 列 是否有效 只需要判断 rec[0..r-1]即可* @param rec rec[]* @param r* @param c* @return*/public static boolean isValid(int[] rec,int r,int c){for (int k = 0; k < r;k++){// 共列if (rec[k] == c){return false;}// 共斜线// Math.abs(r - k) 竖直方向 r行到 k行的距离// rec[k] - c 水平方向 c行到 rec[k]列的距离if (Math.abs(r - k) == Math.abs(rec[k] - c)) {return false;}}return true;}
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/159498.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

使用Elasticsearch来进行简单的DDL搜索数据

说明&#xff1a;Elasticsearch提供了多种多样的搜索方式来满足不同使用场景的需求&#xff0c;我们可以使用Elasticsearch来进行各种复制的查询&#xff0c;进行数据的检索。 1.1 精准查询 用来查询索引中某个类型为keyword的文本字段&#xff0c;类似于SQL的“”查询。 创…

【ElasticSearch】使用 Java 客户端 RestClient 实现对文档的查询操作,以及对搜索结果的排序、分页、高亮处理

文章目录 前言&#xff1a;RestClient 查询文档的 RestAPI一、全文检索查询1.1 match_all 查询1.2 match 查询1.3 multi_match 查询 二、精确查询2.1 term 查询2.2 range 查询 三、复合查询&#xff1a;Boolean 查询与 function score 查询的综合案例四、对查询结果的处理4.1 将…

050:mapboxGL加载geojson数据,同时包含点、多边形的处理示例

第050个 点击查看专栏目录 本示例的目的是介绍演示如何在vue+mapbox中加载geojson数据,既显示点又显示多边形。这个示例是显示了一种处理方式,通过过滤的方式将数据分离化,点和多边形通过两个不同的图层来加载表示。 直接复制下面的 vue+mapbox源代码,操作2分钟即可运行实…

2018-2019 ACM-ICPC, Asia Nanjing Regional Contest G. Pyramid(组合数学 计数)

题目 t(t<1e6)组样例&#xff0c;每次给定一个n(n<1e9)&#xff0c;统计边长为n的上述三角形的等边三角形个数 其中等边三角形的三个顶点&#xff0c;可以在所有黑色三角形&白色三角形的顶点中任取&#xff0c; 答案对1e97取模 思路来源 申老师 & oeis A0003…

本地生活将成快手新的营收增长点

监制 | 何玺 排版 | 叶媛 快手本地生活开始强化B端市场。 据了解&#xff0c;快手 “本地商家”APP已经正式上线。这是快手为本地生活商家推出的独立工作平台&#xff0c;有助于商家提升经营效率。 新APP的上线&#xff0c;标志着快手本地生活业务布局&#xff0c;正从过去侧…

深入理解Kafka分区副本机制

1. Kafka集群 Kafka 使用 Zookeeper 来维护集群成员 (brokers) 的信息。每个 broker 都有一个唯一标识 broker.id&#xff0c;用于标识自己在集群中的身份&#xff0c;可以在配置文件 server.properties 中进行配置&#xff0c;或者由程序自动生成。下面是 Kafka brokers 集群自…

TLS/SSL 详解

目录 基础理论入门HTTPS对称加密非对称加密证书TLS握手过程握手总结 TLS 定义(记录层/握手层)HTTPS HTTP over TLS加密记录层分片 (Fragmentation)记录压缩和解压缩 (Record compression and decompression)空或标准流加密 (Null or standard stream cipher)CBC 块加密 (分组加…

VS2022新建项目时没有ASP.NET Web应用程序 (.NET Framework)

问题&#xff1a;如图&#xff0c;VS2022新建项目时没有“ASP.NET Web应用程序 &#xff08;.NET Framework&#xff09;”的选项解决方法&#xff1a;点击跳转至修改安装选项界面选择安装该项即可&#xff1a;

k8s-13 存储之secret

Secret 对象类型用来保存敏感信息&#xff0c;例如密码、OAuth 令牌和 ssh key。 敏感信息放在 secret 中比放在 Pod 的定义或者容器镜像中来说更加安全和灵活 。 Pod 可以用两种方式使用 secret:作为 volume 中的文件被挂载到 pod 中的一个或者多个容器里 当 kubelet 为 pod 拉…

python:从Excel或者CSV中读取因变量与多个自变量,用于训练机器学习回归模型,并输出预测结果

作者:CSDN @ _养乐多_ 本文详细记录了从Excel读取用于训练机器学习模型的数据,包括独立变量和因变量数据,以供用于机器学习模型的训练。这些机器学习模型包括但不限于随机森林回归模型(RF)和支持向量机回归模型(SVM)。随后,我们将测试数据集应用于这些模型,进行预测和…

[开源]基于Vue+ElementUI+G2Plot+Echarts的仪表盘设计器

一、开源项目简介 基于SpringBoot、MyBatisPlus、ElementUI、G2Plot、Echarts等技术栈的仪表盘设计器&#xff0c;具备仪表盘目录管理、仪表盘设计、仪表盘预览能力&#xff0c;支持MySQL、Oracle、PostgreSQL、MSSQL、JSON等数据集接入&#xff0c;对于复杂数据处理还可以使用…

彩虹易支付 9.27 最新版加订单查询 sy 更新版

彩虹易支付 9.27 最新版加订单查询 sy 更新版 修复客服 2023/09/25&#xff1a; 1. 新增支付宝红包支付插件 2. 新增支付宝 APP 支付转 H5 支付 3. 更新了几个支付插件 安装教程&#xff1a; 环境&#xff1a;php7.2 上传后访问域名进行安装即可 源码下载&#xff1a;ht…

KdMapper扩展实现之SOKNO S.R.L(speedfan.sys)

1.背景 KdMapper是一个利用intel的驱动漏洞可以无痕的加载未经签名的驱动&#xff0c;本文是利用其它漏洞&#xff08;参考《【转载】利用签名驱动漏洞加载未签名驱动》&#xff09;做相应的修改以实现类似功能。需要大家对KdMapper的代码有一定了解。 2.驱动信息 驱动名称spee…

POI报表的高级应用

POI报表的高级应用 掌握基于模板打印的POI报表导出理解自定义工具类的执行流程 熟练使用SXSSFWorkbook完成百万数据报表打印理解基于事件驱动的POI报表导入 模板打印 概述 自定义生成Excel报表文件还是有很多不尽如意的地方&#xff0c;特别是针对复杂报表头&#xff0c;单…

macbook电脑删除app怎么才能彻底清理?

macBook是苹果公司推出的一款笔记本电脑&#xff0c;它的操作系统是macOS。在macBook上安装的app可能会占用大量的存储空间&#xff0c;因此&#xff0c;当我们不再需要某个app时&#xff0c;需要将其彻底删除。macbook删除app&#xff0c;怎么才能彻底呢&#xff1f;本文将给大…

c#设计模式-行为型模式 之 备忘录模式

&#x1f680;简介 备忘录模式&#xff08;Memento Pattern&#xff09;是一种行为型设计模式&#xff0c;它保存一个对象的某个状态&#xff0c;以便在适当的时候恢复对象。所谓备忘录模式就是在不破坏封装的前提下&#xff0c;捕获一个对象的内部状态&#xff0c;并在该对象…

测试中Android与IOS分别关注的点

目录 1、自身不同点 2、测试注重点 3、其他测试点 主要从本身系统的不同点、系统造成的不同点、和注意的测试点做总结 1、自身不同点 研发商&#xff1a;Adroid是google公司做的手机系统&#xff0c;IOS是苹果公司做的手机系统   开源程度&#xff1a;Android是开源的&a…

06-React的路由

06-React的路由 1.相关理解 1).SPA的理解 单页Web应用&#xff08;single page web application&#xff0c;SPA&#xff09;。整个应用只有一个完整的页面。点击页面中的链接不会刷新页面&#xff0c;只会做页面的局部更新。数据都需要通过ajax请求获取, 并在前端异步展现。…

在pycharm中运行js文件,附加node.js下载步骤

文章目录 一、前言二、node.js安装和配置(如果之前就安装好了可以直接跳过)1、进入官网下载安装包2、在本地安装node.js3、环境配置4、验证是否安装成功5、修改下载位置(默认是在c盘&#xff0c;这个根据个人需求)6、设置默认模块包7、测试一下是否修改成功(要进入管理员模式的…

Qt 布局(QSplitter 类QDockWidget 类) 总结

一、QSplitter 类(窗口分割) QSplitter类是一个Qt框架提供的基础窗口控件类&#xff0c;用于分割窗口&#xff0c;使得用户可以通过拖动分隔条来调节子窗口的大小。QSplitter在用户界面设计中非常常见&#xff0c;经常用于划分窗口区域&#xff0c;使得程序可以同时显示多个子…