实习算法准备之BFSDFS

这里写目录标题

  • 1 理论
    • 1.1 BFS框架
  • 2 例题
    • 2.1 二叉树的最小高度
    • 2.2 打开转盘锁
    • 2.3 滑动谜题

1 理论

BFS和DFS是两个遍历算法,其中DFS之前已经接触过,就是回溯,忘记的话请回顾回溯篇的例题(全排列,N皇后)
BFS 的核心思想应该不难理解的,就是把一些问题抽象成图,从一个点开始,向四周开始扩散。一般来说,我们写 BFS 算法都是用「队列」这种数据结构,每次将一个节点周围的所有节点加入队列。
BFS 相对 DFS 的最主要的区别是:BFS 找到的路径一定是最短的,但代价就是空间复杂度可能比 DFS 大很多,至于为什么,我们后面介绍了框架就很容易看出来了。

1.1 BFS框架

我们先举例一下 BFS 出现的常见场景好吧,问题的本质就是让你在一幅「图」中找到从起点 start 到终点 target 的最近距离,这个例子听起来很枯燥,但是 BFS 算法问题其实都是在干这个事儿。

// 计算从起点 start 到终点 target 的最近距离
int BFS(Node start, Node target) {
    Queue<Node> q; // 核心数据结构
    Set<Node> visited; // 避免走回头路
    
    q.offer(start); // 将起点加入队列
    visited.add(start);

    while (q not empty) {
        int sz = q.size();
        /* 将当前队列中的所有节点向四周扩散 */
        for (int i = 0; i < sz; i++) {
            Node cur = q.poll();
            /* 划重点:这里判断是否到达终点 */
            if (cur is target)
                return step;
            /* 将 cur 的相邻节点加入队列 */
            for (Node x : cur.adj()) {
                if (x not in visited) {
                    q.offer(x);
                    visited.add(x);
                }
            }
        }
    }
    // 如果走到这里,说明在图中没有找到目标节点
}

2 例题

2.1 二叉树的最小高度

给定一个二叉树,找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
说明:叶子节点是指没有子节点的节点。

示例1:
在这里插入图片描述
输入:root = [3,9,20,null,null,15,7]
输出:2
示例 2:
输入:root = [2,null,3,null,4,null,5,null,6]
输出:5

思路以及代码:

class Solution {
    public int minDepth(TreeNode root) {
        return bfs(root);
    }

    public int bfs(TreeNode root){
        if(root == null){
            return 0;
        }
        Queue<TreeNode> q = new LinkedList<>();
        q.offer(root);
        int depth = 1;
        while(!q.isEmpty()){
            int sz = q.size();
            for(int i = 0;i<sz;i++){
                TreeNode cur = q.poll();
                if(cur.left == null && cur.right == null){
                    return depth;
                }
                if(cur.left != null){
                    q.offer(cur.left);
                }
                if(cur.right != null){
                    q.offer(cur.right);
                }
            }
            depth++;
        }
        return depth;
    }
}

这里注意这个 while 循环和 for 循环的配合,while 循环控制一层一层往下走,for 循环利用 sz 变量控制从左到右遍历每一层二叉树节点:
在这里插入图片描述

2.2 打开转盘锁

你有一个带有四个圆形拨轮的转盘锁。每个拨轮都有10个数字: ‘0’, ‘1’, ‘2’, ‘3’, ‘4’, ‘5’, ‘6’, ‘7’, ‘8’, ‘9’ 。每个拨轮可以自由旋转:例如把 ‘9’ 变为 ‘0’,‘0’ 变为 ‘9’ 。每次旋转都只能旋转一个拨轮的一位数字。
锁的初始数字为 ‘0000’ ,一个代表四个拨轮的数字的字符串。
列表 deadends 包含了一组死亡数字,一旦拨轮的数字和列表里的任何一个元素相同,这个锁将会被永久锁定,无法再被旋转。
字符串 target 代表可以解锁的数字,你需要给出解锁需要的最小旋转次数,如果无论如何不能解锁,返回 -1 。

示例 1:
输入:deadends = [“0201”,“0101”,“0102”,“1212”,“2002”], target = “0202”
输出:6
解释:
可能的移动序列为 “0000” -> “1000” -> “1100” -> “1200” -> “1201” -> “1202” -> “0202”。
注意 “0000” -> “0001” -> “0002” -> “0102” -> “0202” 这样的序列是不能解锁的,
因为当拨动到 “0102” 时这个锁就会被锁定。
示例 2:
输入: deadends = [“8888”], target = “0009”
输出:1
解释:把最后一位反向旋转一次即可 “0000” -> “0009”。
示例 3:
输入: deadends = [“8887”,“8889”,“8878”,“8898”,“8788”,“8988”,“7888”,“9888”], target = “8888”
输出:-1
解释:无法旋转到目标数字且不被锁定。

思路以及代码:
第一步,我们不管所有的限制条件,不管 deadends 和 target 的限制,就思考一个问题:如果让你设计一个算法,穷举所有可能的密码组合,你怎么做?
穷举呗,再简单一点,如果你只转一下锁,有几种可能?总共有 4 个位置,每个位置可以向上转,也可以向下转,也就是有 8 种可能对吧。
比如说从 “0000” 开始,转一次,可以穷举出 “1000”, “9000”, “0100”, “0900”… 共 8 种密码。然后,再以这 8 种密码作为基础,对每个密码再转一下,穷举出所有可能…

仔细想想,这就可以抽象成一幅图,每个节点有 8 个相邻的节点,又让你求最短距离,这不就是典型的 BFS 嘛,框架就可以派上用场了,先写出一个「简陋」的 BFS 框架代码再说别的:

    //密码锁上拨一次
    public String upone(String s,int i){
        char[] ch = s.toCharArray();
        if(ch[i] == '9'){
            ch[i] = '0';
        }else{
            ch[i] += 1;
        }
        return new String(ch);
    }
    //密码锁向下转一下
    public String downone(String s,int i){
        char[] ch = s.toCharArray();
        if(ch[i] == '0'){
            ch[i] = '9';
        }else{
            ch[i] += 1;
        }
        return new String(ch);
    }

    public int bfs(String[] deadends, String target){
        Queue<String> q = new LinkedList();
        q.offer("0000");
        while(!q.isEmpty()){
            int sz = q.size();
            for(int i = 0;i<sz;i++){
                String cur = q.poll();
                    
                for(int j = 0;j<4;j++){
                    String up = upone(cur,j);
                    String down = downone(cur,j);
                    q.offer(up);
                    q.offer(down);
                }
            }
        }
    }

这段 BFS 代码已经能够穷举所有可能的密码组合了,但是显然不能完成题目,有如下问题需要解决:
1、会走回头路。比如说我们从 “0000” 拨到 “1000”,但是等从队列拿出 “1000” 时,还会拨出一个 “0000”,这样的话会产生死循环。

2、没有终止条件,按照题目要求,我们找到 target 就应该结束并返回拨动的次数。

3、没有对 deadends 的处理,按道理这些「死亡密码」是不能出现的,也就是说你遇到这些密码的时候需要跳过。

因此,我们根据上面三点去完善这个bfs代码:

class Solution {
    public int openLock(String[] deadends, String target) {
        return bfs(deadends,target);
    }

    //密码锁上拨一次
    public String upone(String s,int i){
        char[] ch = s.toCharArray();
        if(ch[i] == '9'){
            ch[i] = '0';
        }else{
            ch[i] += 1;
        }
        return new String(ch);
    }
    //密码锁向下转一下
    public String downone(String s,int i){
        char[] ch = s.toCharArray();
        if(ch[i] == '0'){
            ch[i] = '9';
        }else{
            ch[i] += 1;
        }
        return new String(ch);
    }

    public int bfs(String[] deadends, String target){
        Set<String> deads = new HashSet();
        for(String s:deadends){
            deads.add(s);
        }
        Set<String> visited = new HashSet();
        Queue<String> q = new LinkedList();

        q.offer("0000");
        visited.add("0000");
        int step = 0;

        while(!q.isEmpty()){
            int sz = q.size();
            for(int i = 0;i<sz;i++){
                String cur = q.poll();
                if(deads.contains(cur)){
                    continue;
                }
                if(cur.equals(target)){
                    return step;
                }
                for(int j = 0;j<4;j++){
                    String up = upone(cur,j);
                    String down = downone(cur,j);
                    if(!visited.contains(up)){
                        q.offer(up);
                        visited.add(up);
                    }
                    if(!visited.contains(down)){
                        q.offer(down);
                        visited.add(down);
                    }
                }
            }
            step++;
        }
        return -1;
    }
}

有一个比较小的优化:可以不需要 dead 这个哈希集合,可以直接将这些元素初始化到 visited 集合中,效果是一样的,可能更加优雅一些。

2.3 滑动谜题

在一个 2 x 3 的板上(board)有 5 块砖瓦,用数字 1~5 来表示, 以及一块空缺用 0 来表示。一次 移动 定义为选择 0 与一个相邻的数字(上下左右)进行交换.
最终当板 board 的结果是 [[1,2,3],[4,5,0]] 谜板被解开。
给出一个谜板的初始状态 board ,返回最少可以通过多少次移动解开谜板,如果不能解开谜板,则返回 -1 。

示例 1:
在这里插入图片描述
输入:board = [[1,2,3],[4,0,5]]
输出:1
解释:交换 0 和 5 ,1 步完成

示例 2:
在这里插入图片描述
输入:board = [[1,2,3],[5,4,0]]
输出:-1
解释:没有办法完成谜板

示例 3:
在这里插入图片描述
输入:board = [[4,1,2],[5,0,3]]
输出:5
解释:
最少完成谜板的最少移动次数是 5 ,
一种移动路径:
尚未移动: [[4,1,2],[5,0,3]]
移动 1 次: [[4,1,2],[0,5,3]]
移动 2 次: [[0,1,2],[4,5,3]]
移动 3 次: [[1,0,2],[4,5,3]]
移动 4 次: [[1,2,0],[4,5,3]]
移动 5 次: [[1,2,3],[4,5,0]]

思路以及代码:
对于这种计算最小步数的问题,我们就要敏感地想到 BFS 算法。
这个题目转化成 BFS 问题是有一些技巧的,我们面临如下问题:
1、一般的 BFS 算法,是从一个起点 start 开始,向终点 target 进行寻路,但是拼图问题不是在寻路,而是在不断交换数字,这应该怎么转化成 BFS 算法问题呢?
2、即便这个问题能够转化成 BFS 问题,如何处理起点 start 和终点 target?它们都是数组哎,把数组放进队列,套 BFS 框架,想想就比较麻烦且低效。

首先回答第一个问题,BFS 算法并不只是一个寻路算法,而是一种暴力搜索算法,只要涉及暴力穷举的问题,BFS 就可以用,而且可以最快地找到答案。
你想想计算机怎么解决问题的?哪有什么特殊技巧,本质上就是把所有可行解暴力穷举出来,然后从中找到一个最优解罢了。

明白了这个道理,我们的问题就转化成了:**如何穷举出 board 当前局面下可能衍生出的所有局面?**这就简单了,看数字 0 的位置呗,和上下左右的数字进行交换就行了:
这样其实就是一个 BFS 问题,每次先找到数字 0,然后和周围的数字进行交换,形成新的局面加入队列…… 当第一次到达 target 时,就得到了赢得游戏的最少步数。

对于第二个问题,我们这里的 board 仅仅是 2x3 的二维数组,所以可以压缩成一个一维字符串。其中比较有技巧性的点在于,二维数组有「上下左右」的概念,压缩成一维后,如何得到某一个索引上下左右的索引?

对于这道题,题目说输入的数组大小都是 2 x 3,所以我们可以直接手动写出来这个映射:

// neighbor 表示在一维字符串中,索引 i 在二维数组中的的相邻索引
int[][] neighbor = new int[][]{
        {1, 3},
        {0, 4, 2},
        {1, 5},
        {0, 4},
        {3, 1, 5},
        {4, 2}
};

在这里插入图片描述
观察上图就能发现,如果二维数组中的某个元素 e 在一维数组中的索引为 i,那么 e 的左右相邻元素在一维数组中的索引就是 i - 1 和 i + 1,而 e 的上下相邻元素在一维数组中的索引就是 i - n 和 i + n,其中 n 为二维数组的列数。

这样,对于 m x n 的二维数组,我们可以写一个函数来生成它的 neighbor 索引映射:

int[][] generateNeighborMapping(int m, int n) {
    int[][] neighbor = new int[m * n][];
    for (int i = 0; i < m * n; i++) {
        List<Integer> neighbors = new ArrayList<>();

        // 如果不是第一列,有左侧邻居
        if (i % n != 0) neighbors.add(i - 1);
        // 如果不是最后一列,有右侧邻居
        if (i % n != n - 1) neighbors.add(i + 1);
        // 如果不是第一行,有上方邻居
        if (i - n >= 0) neighbors.add(i - n);
        // 如果不是最后一行,有下方邻居
        if (i + n < m * n) neighbors.add(i + n);

        // Java 语言特性,将 List 类型转为 int[] 数组
        neighbor[i] = neighbors.stream().mapToInt(Integer::intValue).toArray();
    }
    return neighbor;
}

至此,我们就把这个问题完全转化成标准的 BFS 问题了,借助前文 BFS 算法框架 的代码框架,直接就可以套出解法代码了

class Solution {
    public int slidingPuzzle(int[][] board) {
        int m = 2, n = 3;
        StringBuilder sb = new StringBuilder();
        String target = "123450";
        // 将 2x3 的数组转化成字符串作为 BFS 的起点
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                sb.append(board[i][j]);
            }
        }
        String start = sb.toString();

        // 记录一维字符串的相邻索引
        int[][] neighbor = new int[][]{/**<extend up -200><div class="img-content"><img src="/algo/images/sliding_puzzle/4.jpeg" class="myimage"/></div> */
                {1, 3},
                {0, 4, 2},
                {1, 5},
                {0, 4},
                {3, 1, 5},
                {4, 2}
        };

        /******* BFS 算法框架开始 *******/
        Queue<String> q = new LinkedList<>();
        HashSet<String> visited = new HashSet<>();
        // 从起点开始 BFS 搜索
        q.offer(start);
        visited.add(start);

        int step = 0;
        while (!q.isEmpty()) {/**<extend up -200><div class="img-content"><img src="/algo/images/sliding_puzzle/3.jpeg" class="myimage"/></div> */
            int sz = q.size();
            for (int i = 0; i < sz; i++) {
                String cur = q.poll();
                // 判断是否达到目标局面
                if (target.equals(cur)) {
                    return step;
                }
                // 找到数字 0 的索引
                int idx = 0;
                for (; cur.charAt(idx) != '0'; idx++) ;
                // 将数字 0 和相邻的数字交换位置
                for (int adj : neighbor[idx]) {
                    String new_board = swap(cur.toCharArray(), adj, idx);
                    // 防止走回头路
                    if (!visited.contains(new_board)) {
                        q.offer(new_board);
                        visited.add(new_board);
                    }
                }
            }
            step++;
        }
        /******* BFS 算法框架结束 *******/
        return -1;
    }

    private String swap(char[] chars, int i, int j) {
        char temp = chars[i];
        chars[i] = chars[j];
        chars[j] = temp;
        return new String(chars);
    }
}

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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

C++解方程组的库

解决多元多次方程组的问题&#xff0c;你可以考虑以下几个C库&#xff1a; Eigen: Eigen库是一个高性能的C模板库&#xff0c;用于线性代数运算。它提供了强大的矩阵运算功能&#xff0c;可以用来解多元一次方程组。对于多次方程组&#xff0c;你可能需要结合Eigen和一些数值优…

Rust网络请求神器reqwest介绍和使用,5分钟速学

在 Rust 生态中&#xff0c;reqwest 可以说是最流行的 HTTP 客户端库了。它提供了一个高层级的、人性化的 API&#xff0c;让我们可以非常轻松地发送各种 HTTP 请求和处理响应。无论是 quickstart、自定义请求头、cookie 管理&#xff0c;还是文件上传&#xff0c;reqwest 都能…

了解Cookie登录:原理、实践与安全指南

什么是Cookie登录&#xff1f; Cookie是什么 当你首次登录网站时&#xff0c;你会输入用户名和密码。在后台&#xff0c;网站的服务器验证这些凭据是否正确。一旦确认你的身份无误&#xff0c;服务器就会创建一个Cookie&#xff0c;并将其发送到你的浏览器。这了解Cookie登录…

38-数组 _ 一维数组

38-1 数组的创建 数组是一组相同类型元素的集合。 数组的创建方式&#xff1a; type_t arr_name [const_n]; //type_t 是指数组的元素类型 //const_n是一个常量表达式&#xff0c;用来指定数组的大小 举例&#xff1a; int arr[10]; char ch[5]; double data[20]; 问&…

HarmonyOS 实战开发-MindSpore Lite引擎进行模型推理

场景介绍 MindSpore Lite 是一款 AI 引擎&#xff0c;它提供了面向不同硬件设备 AI 模型推理的功能&#xff0c;目前已经在图像分类、目标识别、人脸识别、文字识别等应用中广泛使用。 本文介绍使用 MindSpore Lite 推理引擎进行模型推理的通用开发流程。 基本概念 在进行开…

vscode连接远程Linux服务器时,没有权限新建文件夹或者文件

参考链接&#xff1a; VS code 保存或新建文件没有权限的问题 vscode连接远程Linux服务器时&#xff0c;没有权限新建文件夹或者文件&#xff1a; 用一条命令解决&#xff1a; sudo chown -R myuser /path/to/foldermyuser是当前用户名&#xff0c; /path/to/folder是 需要操…

编程学习路线

Java最强学习路线 快来官网定制一套属于自己的学习路线吧 官方网址&#xff1a; Learn to become a modern Java developerCommunity driven, articles, resources, guides, interview questions, quizzes for java development. Learn to become a modern Java developer by…

运维笔记:基于阿里云跨地域服务器通信(上)

运维笔记 阿里云&#xff1a;跨地域服务器通信&#xff08;上&#xff09; - 文章信息 - Author: 李俊才 (jcLee95) Visit me at CSDN: https://jclee95.blog.csdn.netMy WebSite&#xff1a;http://thispage.tech/Email: 291148484163.com. Shenzhen ChinaAddress of this a…

【嵌入式AI开发】轻量级卷积神经网络MobileNet项目实战——文末完整源码工程文件

前言:本文介绍轻量级卷积神经网络MobileNet网络实战,包含MobileNetV1、MobileNetV2、ResNet50三个预训练模型可供选择。 实现:1.预训练MobileNet图像分类,2.调用摄像头实时MobileNet图像分类,3.MobileNet视频图像分类。 MobileNet网络理论详解:【嵌入式AI开发】轻量级卷…

git提交常用

git config --global user.name "你的名字或昵称" git config --global user.email "你的邮箱" 第一次上传到码云 1.找到要提交到码云的文件夹 右击打开Git Bash Here 2.用命令行创建本地仓库 git init 3.将待全部文件放入缓冲区 git add . 4.提交缓…

优化贪吃蛇在前进过程中,前进和后退的问题

1. 左边为head,右边为tail 定义相反数在abs&#xff08;&#xff09;绝对值函数中实现 2. 在转向函数turn()中&#xff0c;如果绝对值不相等的时候才赋予方向的值 3.贪吃蛇吃食物的思路 3.1 初始化食物initFood(), 蛇碰到食物函数hasFood&#xff08;&#xff09;,在移…

如何用Python实现智能客服问答系统

随着人工智能技术的不断发展&#xff0c;机器人客服与聊天系统成为了热门话题。Python作为一种简单易学、功能强大的编程语言&#xff0c;在机器人客服与聊天系统的开发中具有广泛应用。 本文将介绍如何使用Python实现机器人客服与聊天系统&#xff0c;包括实现方式、代码示例和…

Mysql-主从复制理解

环境&#xff1a;mysql&#xff0c;主从复制&#xff0c;必须有2个mysql实例&#xff0c;也就是说可以在一台电脑上安装2个msyql&#xff0c;或者2台服务器&#xff0c;一个主服务器&#xff0c;一个从服务器 在实际的生产中&#xff0c;为了解决Mysql的单点故障已经提高MySQL的…

【Unity动画系统】动画基本原理与Avater骨骼复用

动画基本原理 动画片段文件是一个描述物体变化状态的文本文件 在Unity中创建的资源文件大多都是YAML语言编写的文本文件 Curves表示一种变化状态&#xff0c;为空的话则没有记录任何内容 位置变化后的旋转变化状态&#xff1a; 动画文件里的Path名字要相同才能播放相同的动画 …

外贸财务挑战面面观:应对难题之道大揭秘!

出海也开始卷起来了。越来越多的中国企业投身海外市场&#xff0c;寻求更广阔的发展空间。然而&#xff0c;出海之路并非坦途&#xff0c;企业既需把握全球商机&#xff0c;又需应对数字化转型、本土化运营、文化差异性等多重挑战。企业出海&#xff0c;该如何应对这些风浪&…

GPU服务器和普通服务器有何区别?

众所周知&#xff0c;服务器是网络中的重要设备&#xff0c;要接受少至几十人、多至成千上万人的访问&#xff0c;因此对服务器具有大数据量的快速吞吐、超强的稳定性、长时间运行等严格要求。 GPU服务器和普通服务器的主要区别在于硬件配置和适用场景&#xff0c;特别是处理器…

C 函数递归

目录 什么是递归 递归的限制条件 递归的例子 1、用递归求n的阶乘 递归扩展学习 1、青蛙跳台阶 思路 代码实现 2、汉诺塔问题​ 思路 代码实现 总结 什么是递归 递归&#xff1a;“递推” “回归” 在C语言中&#xff0c;函数递归就是&#xff1a;函数自己调用自…

FANUC机器人SOCKET连接指令编写

一、创建一个.KL文件编写连接指令 创建一个KL文本来编写FANUC机器人socket连接指令 二、KAREL指令代码 fanuc机器人karel编辑器编辑的karel代码如下&#xff1a; PROGRAM SM_CON %COMMENT SOCKET连接 %STACKSIZE 4000 --堆栈大小 %INCLUDE klevccdfVAR status,data_type,in…

武汉星起航:成功挂牌新起点,董事长张振邦引领行业再攀高峰

2023年10月30日&#xff0c;对于武汉星起航电子商务有限公司而言&#xff0c;是一个具有里程碑意义的日子。这一天&#xff0c;公司在上海股权托管交易中心成功挂牌展示&#xff0c;正式登陆资本市场&#xff0c;开启了公司发展的新篇章。这一创举不仅彰显了公司在跨境电商领域…

刷题日记 ---- 顺序表与链表相关经典算法题(C语言版)

目录 1. 移除元素2. 合并两个有序数组3. 移除链表元素4. 反转链表5. 合并两个有序链表6. 链表的中间结点7. 环形链表的约瑟夫问题8. 分割链表总结 正文开始 1. 移除元素 题目链接: 移除元素 题目描述: 思路历程: 题目明确要求, 不能使用额外的数组空间, 也就是说不可以创建…