【随想录】Day30—第七章 回溯算法part06

2024-04-24 03:36

本文主要是介绍【随想录】Day30—第七章 回溯算法part06,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

目录

  • 题目1: 重新安排行程
    • 1- 思路
    • 2- 题解
      • ⭐重新安排行程 ——题解思路
  • 题目2: N皇后
    • 1- 思路
    • 2- 题解
      • ⭐N皇后 ——题解思路
  • 题目3: 解数独(跳过)


题目1: 重新安排行程

  • 题目链接:332. 重新安排行程

1- 思路

思路:

  • 本题实际上是一个搜索的过程,即搜索满足输入条件 从起点到 一个终点可达的路径,同时路径要满足字典序小的排在前面。因此需要借助一个数据结构,实现存储当前机场可达到的 目的地机场,且存储可以达到的次数,即机票数。
  • 本题以输入:[[“JFK”, “KUL”], [“JFK”, “NRT”], [“NRT”, “JFK”]为例,抽象为树形结构如下:

引用carl:代码随想录


根据上述思路使用以下数据结构
数据结构:

  • 定义一个 HashMap 结构为 <String,Map<String,Integer>>:其中Map的第一个 String 存储的是出发点,第二个 String 存储的为目的地,Integer 存储的是从出发点到目的地的机票数。
  • List<String> res:收集最终的路线结果集

回溯三部曲

  • 1. 回溯函数参数及返回值
  • 本题主要通过将输入的 List<List> 存入 map 中,通过定义全局变量 map 的形式来进行回溯,因此回溯参数传入的是 ticketNum 即机票数量。
  • 函数返回值是 boolean
  • 因为我们只需要找到一个行程,就是在树形结构中唯一的一条通向叶子节点的路线,如图:

  • 所以找到了这个叶子节点了直接返回。
private boolean BackTracing(int ticketNum)
  • 其中 resmap 需要初始化
    • 定义 Map<String,Integer> temp ,用于对当前出发点的 目的地机票数 进行操作。
    • 如果当前出发点存在,则获取当前出发点,将现有 目的地 存入,或 +1
    • 如果当前出发点不存在,则利用 TreeMap的特性,保证 temp 中的目的地顺序是升序
for(List<String> t : tickets) {Map<String,Integer> temp;// 如果在if(map.containsKey(t.get(0))){temp = map.get(t.get(0));temp.put(t.get(1),temp.getOrDefault(t.get(1),0)+1);}else{// 不存在temp = new TreeMap();temp.put(t.get(1),1);}map.put(t.get(0),temp);
}
res.add("JFK");

  • **2. 回溯终止条件 **
  • 因为 res 记录的是 结果集,而 ticketNum 记录的是 路径数,路径比节点数少 1 ,因此终止条件是 res.size() == ticketNum+1
// 3.2 终止条件
if(res.size() == ticketNum+1){return true;
}
  • 3. 回溯逻辑
  • 获取 res 中的最后一个元素,通过 forEach 循环来遍历 key 为最后一个元素的 结果集
  • count为机票数,若机票数 count > 0 则进行 递归和回溯
    • res 收集当前 目的地
    • target 列表记录数减 1
    • 递归
    • 回溯 res
    • 回溯 target
if(map.containsKey(last)){// 遍历 mapfor(Map.Entry<String,Integer> target : map.get(last).entrySet()){int count = target.getValue();if(count>0){res.add(target.getKey());target.setValue(count-1);if(BackTracing(ticketNum)) return true;res.removeLast();target.setValue(count);}}}

2- 题解

⭐重新安排行程 ——题解思路

在这里插入图片描述

class Solution {List<String> res = new ArrayList<>();Map<String,Map<String,Integer>> map = new HashMap<>();public List<String> findItinerary(List<List<String>> tickets) {// 初始化for(List<String> t :tickets){Map<String,Integer> tmp;// 如果存在if(map.containsKey(t.get(0))){tmp = map.get(t.get(0));tmp.put(t.get(1),tmp.getOrDefault(t.get(1),0)+1);}else{tmp = new TreeMap();tmp.put(t.get(1),1);}map.put(t.get(0),tmp);}res.add("JFK");backTracing(tickets.size());return res;}// 回溯public boolean backTracing(int tNum){if(res.size() == tNum+1){return true;}// 回溯String last = res.getLast();// 如果有if(map.containsKey(last)){// 遍历 mapfor(Map.Entry<String,Integer> target : map.get(last).entrySet()){// 递归 && 回溯int count = target.getValue();if(count>0){res.add(target.getKey());target.setValue(count-1);if(backTracing(tNum)) return true;res.removeLast();target.setValue(count);}}}return false;}
}

题目2: N皇后

  • 题目链接:N 皇后

1- 思路

  • 题目所求,在 n*n 的棋盘中方 n 个皇后,且 n 皇后满足 不存在 _**同行、同列、同对角 **_的元素。

递归树

  • 递归树每层的结果实际上是每层皇后的所取的位置

思路:

  • 1. 数据结构
    • List<List<String>> res:收集结果
  • 2. 回溯三部曲
    • 2.1 回溯参数及返回值
      • int n:棋盘大小
      • int row:回溯到第几行
      • char[][] cheesboard: 棋盘数组
    • 2.2 回溯终止条件 && 结果收集
      • 如果 row 遍历到了 n 的大小,则证明已经求出一个解,此时直接收集结果
    • 2.3 回溯逻辑
      • 如果当前遍历的位置 符合(isValid) 结果则进行 递归+回溯
      • cheesboard[row][i] 进行放棋子
      • 递归 backTracing(n,i+1,cheesboard)
      • 回溯 cheesboard[row][i]
  • 3. 实现 isValid 函数判断是否有效
    • 行判断
    • 列判断
    • 左上判断
    • 右上判断
  • 4. 实现 Array2List 函数,收集 char 数组的结果
    public List Array2List(char[][] cheesboard){List<String> list = new ArrayList<>();for(char[] c:cheesboard){list.add(String.copyValueOf(c));}return list;}

2- 题解

⭐N皇后 ——题解思路

在这里插入图片描述

class Solution {List<List<String>> res = new ArrayList<>();public List<List<String>> solveNQueens(int n) {// 定义 cheesboard 并初始化char[][] cheesboard = new char[n][n];for(char[] c:cheesboard){Arrays.fill(c,'.');}backTracing(n,0,cheesboard);return res;}public void backTracing(int n,int row,char[][] cheesboard){// 终止if(row == n){res.add(Array2List(cheesboard));return ;}// 回溯for(int i = 0 ; i < n;i++){if(isValid(row,i,n,cheesboard)){cheesboard[row][i] = 'Q';backTracing(n,row+1,cheesboard);cheesboard[row][i] = '.';}}}public List Array2List(char[][] cheesboard){List<String> list = new ArrayList<>();for(char[] c:cheesboard){list.add(String.copyValueOf(c));}return list;}public boolean isValid(int row,int col,int n,char[][] cheesboard){// 列for(int i = 0;i<row;i++){if(cheesboard[i][col] =='Q' ){return false;}}// 行for(int i = 0;i<col;i++){if(cheesboard[row][i] =='Q' ){return false;}}// 45for(int i =row-1,j = col-1; i>=0 && j>=0 ;i--,j--){if(cheesboard[i][j]=='Q'){return false;}}for(int i =row-1,j = col+1; i>=0 && j<=n-1 ;i--,j++){if(cheesboard[i][j]=='Q'){return false;}}return true;}
}

题目3: 解数独(跳过)

  • 题目链接:37. 解数独

这篇关于【随想录】Day30—第七章 回溯算法part06的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/930653

相关文章

SpringBoot实现MD5加盐算法的示例代码

《SpringBoot实现MD5加盐算法的示例代码》加盐算法是一种用于增强密码安全性的技术,本文主要介绍了SpringBoot实现MD5加盐算法的示例代码,文中通过示例代码介绍的非常详细,对大家的学习... 目录一、什么是加盐算法二、如何实现加盐算法2.1 加盐算法代码实现2.2 注册页面中进行密码加盐2.

Java时间轮调度算法的代码实现

《Java时间轮调度算法的代码实现》时间轮是一种高效的定时调度算法,主要用于管理延时任务或周期性任务,它通过一个环形数组(时间轮)和指针来实现,将大量定时任务分摊到固定的时间槽中,极大地降低了时间复杂... 目录1、简述2、时间轮的原理3. 时间轮的实现步骤3.1 定义时间槽3.2 定义时间轮3.3 使用时

如何通过Golang的container/list实现LRU缓存算法

《如何通过Golang的container/list实现LRU缓存算法》文章介绍了Go语言中container/list包实现的双向链表,并探讨了如何使用链表实现LRU缓存,LRU缓存通过维护一个双向... 目录力扣:146. LRU 缓存主要结构 List 和 Element常用方法1. 初始化链表2.

golang字符串匹配算法解读

《golang字符串匹配算法解读》文章介绍了字符串匹配算法的原理,特别是Knuth-Morris-Pratt(KMP)算法,该算法通过构建模式串的前缀表来减少匹配时的不必要的字符比较,从而提高效率,在... 目录简介KMP实现代码总结简介字符串匹配算法主要用于在一个较长的文本串中查找一个较短的字符串(称为

通俗易懂的Java常见限流算法具体实现

《通俗易懂的Java常见限流算法具体实现》:本文主要介绍Java常见限流算法具体实现的相关资料,包括漏桶算法、令牌桶算法、Nginx限流和Redis+Lua限流的实现原理和具体步骤,并比较了它们的... 目录一、漏桶算法1.漏桶算法的思想和原理2.具体实现二、令牌桶算法1.令牌桶算法流程:2.具体实现2.1

Python中的随机森林算法与实战

《Python中的随机森林算法与实战》本文详细介绍了随机森林算法,包括其原理、实现步骤、分类和回归案例,并讨论了其优点和缺点,通过面向对象编程实现了一个简单的随机森林模型,并应用于鸢尾花分类和波士顿房... 目录1、随机森林算法概述2、随机森林的原理3、实现步骤4、分类案例:使用随机森林预测鸢尾花品种4.1

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例,告诉我们不懂推荐算法的产品,也能从产品侧出发, 设计出一款不错的推荐系统。 相信很多新手产品,看到算法二字,多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法(注:传统是指科班出身的产品都会接触过)。但对于推荐算法,多数产品对着网上搜到的资源,都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后,更是加大了理解的难度。 但,不了解推荐算法,就无法做推荐系

康拓展开(hash算法中会用到)

康拓展开是一个全排列到一个自然数的双射(也就是某个全排列与某个自然数一一对应) 公式: X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0! 其中,a[i]为整数,并且0<=a[i]<i,1<=i<=n。(a[i]在不同应用中的含义不同); 典型应用: 计算当前排列在所有由小到大全排列中的顺序,也就是说求当前排列是第

csu 1446 Problem J Modified LCS (扩展欧几里得算法的简单应用)

这是一道扩展欧几里得算法的简单应用题,这题是在湖南多校训练赛中队友ac的一道题,在比赛之后请教了队友,然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意:把题意转变下就变成了:求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点:求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个

综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

LntonAIServer视频质量诊断功能中的抖动检测是一个专门针对视频稳定性进行分析的功能。抖动通常是指视频帧之间的不必要运动,这种运动可能是由于摄像机的移动、传输中的错误或编解码问题导致的。抖动检测对于确保视频内容的平滑性和观看体验至关重要。 优势 1. 提高图像质量 - 清晰度提升:减少抖动,提高图像的清晰度和细节表现力,使得监控画面更加真实可信。 - 细节增强:在低光条件下,抖