【java刷算法】牛客—剑指offer4DFS与BFS两种思路的碰撞,一起来练习吧

简介: ✨今日二剑JZ12 矩阵中的路径JZ13 机器人的运动范围

✨今日二剑


JZ12 矩阵中的路径

JZ13 机器人的运动范围


文章目录

✨今日二剑

JZ12 矩阵中的路径

JZ13 机器人的运动范围

JZ12 矩阵中的路径

题目描述

思路详解

代码与结果

JZ13 机器人的运动范围

题目描述

思路详解

DFS(深度优先搜索)

BFS(广度优先搜索)

代码与结果

DFS(深度优先搜索)

BFS(广度优先搜索)

✨总结

文章目录

JZ12 矩阵中的路径

JZ13 机器人的运动范围


JZ12 矩阵中的路径



题目描述

思路详解


本题我们用回溯算法解决。

我们看到他是从矩形中的一个点开始往他的上下左右四个方向查找,这个点可以是矩形中的任何一个点,就是遍历矩形所有的点,然后从这个点开始往他的4个方向走,因为是二维数组,所以有两个for循环。

我们接下来写一个dfs方法,对其控制判断和方向的转变。

详细见注释哦!!!


代码与结果

import java.util.*;
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     * 
     * @param matrix char字符型二维数组 
     * @param word string字符串 
     * @return bool布尔型
     */
   public boolean hasPath(char[][] matrix, String word) {
    char[] words = word.toCharArray();
    for (int i = 0; i < matrix.length; i++) {
        for (int j = 0; j < matrix[0].length; j++) {
            //从[i,j]这个坐标开始查找
            if (dfs(matrix, words, i, j, 0))
                return true;
        }
    }
    return false;
}
boolean dfs(char[][] matrix, char[] word, int i, int j, int index) {
    //边界的判断,如果越界直接返回false。index表示的是查找到字符串word的第几个字符,
    //如果这个字符不等于matrix[i][j],说明验证这个坐标路径是走不通的,直接返回false
    if (i >= matrix.length || i < 0 || j >= matrix[0].length || j < 0 || matrix[i][j] != word[index])
        return false;
    //如果word的每个字符都查找完了,直接返回true
    if (index == word.length - 1)
        return true;
    //把当前坐标的值保存下来,为了在最后复原
    char tmp = matrix[i][j];
    //然后修改当前坐标的值
    matrix[i][j] = '.';
    //走递归,沿着当前坐标的上下左右4个方向查找
    boolean res = dfs(matrix, word, i + 1, j, index + 1)
            || dfs(matrix, word, i - 1, j, index + 1)
            || dfs(matrix, word, i, j + 1, index + 1)
            || dfs(matrix, word, i, j - 1, index + 1);
    //递归之后再把当前的坐标复原
    matrix[i][j] = tmp;
    return res;
}
}


JZ13 机器人的运动范围


题目描述


思路详解


本题是一个机器人从左上角开始,他可以沿着上下左右四个方向走,并且走到的每个格子坐标的数字和不大于k,问可以走多少个格子。那么就想到本题就有两种解法,DFS 和 BFS,下面都列出来大家看下效率和具体实现方法。


DFS(深度优先搜索)


根据题目得出,机器人不能往回走,并且每个格子还有一个进入的方向,那么机器人可以走的就只有3个方向。但是我们用的是DFS(深度优先搜索),就像不撞南墙不回头的牛一样。实际上只有向右,向下,两个方向。

我们试想一下,他会一直沿着一个方向走到不能走,然后回溯。那么这个时候回溯的时候我们在进行向下,向右,就可以达到所有的地方。

详解见代码哦!!!


BFS(广度优先搜索)


当然也可以用BFS(广度优先搜索),相比于DFS,BFS就比较灵活咯。

BFS不是一条道走下去,他会把离他最近的都访问一遍,访问完之后才开始访问第二近的……,直到访问完全部的。

BFS使用最好的一种数据结构就是使用队列,因为队列是先进先出,离他最近的访问完之后加入到队列中,最先入队的也是最先出队的。

具体代码与DFS相差不多,详见代码注释哦!!!


代码与结果


DFS(深度优先搜索)

public int movingCount(int threshold, int rows, int cols) {
    //临时变量visited记录格子是否被访问过
    boolean[][] visited = new boolean[rows][cols];
    return dfs(0, 0, rows, cols, threshold, visited);
}
public int dfs(int i, int j, int rows, int cols, int threshold, boolean[][] visited) {
    //i >= rows || j >= cols是边界条件的判断,threshold < sum(i, j)判断当前格子坐标是否
    // 满足条件,visited[i][j]判断这个格子是否被访问过
    if (i >= rows || j >= cols || threshold < sum(i, j) || visited[i][j])
        return 0;
    //标注这个格子被访问过
    visited[i][j] = true;
    //沿着当前格子的右边和下边继续访问
    return 1 + dfs(i + 1, j, rows, cols, threshold, visited) +
            dfs(i, j + 1, rows, cols, threshold, visited);
}
//计算两个坐标数字的和
private int sum(int i, int j) {
    int sum = 0;
    //计算坐标i所有数字的和
    while (i != 0) {
        sum += i % 10;
        i /= 10;
    }
    //计算坐标j所有数字的和
    while (j != 0) {
        sum += j % 10;
        j /= 10;
    }
    return sum;
}

BFS(广度优先搜索)

import java.util.LinkedList;
import java.util.Queue;
public class Solution {
    public int movingCount(int threshold, int rows, int cols) {
        //临时变量visited记录格子是否被访问过
        boolean[][] visited = new boolean[rows][cols];
        int res = 0;
        //创建一个队列,保存的是访问到的格子坐标,是个二维数组
        Queue<int[]> queue = new LinkedList<>();
        //从左上角坐标[0,0]点开始访问,add方法表示把坐标
        // 点加入到队列的队尾
        queue.add(new int[]{0, 0});
        while (queue.size() > 0) {
            //这里的poll()函数表示的是移除队列头部元素,因为队列
            // 是先进先出,从尾部添加,从头部移除
            int[] x = queue.poll();
            int i = x[0], j = x[1];
            //i >= rows || j >= cols是边界条件的判断,threshold < sum(i, j)判断当前格子坐标是否
            // 满足条件,visited[i][j]判断这个格子是否被访问过
            if (i >= rows || j >= cols || threshold < sum(i, j) || visited[i][j])
                continue;
            //标注这个格子被访问过
            visited[i][j] = true;
            res++;
            //把当前格子右边格子的坐标加入到队列中
            queue.add(new int[]{i + 1, j});
            //把当前格子下边格子的坐标加入到队列中
            queue.add(new int[]{i, j + 1});
        }
        return res;
    }
    //计算两个坐标数字的和
    private int sum(int i, int j) {
        int sum = 0;
        //计算坐标i所有数字的和
        while (i != 0) {
            sum += i % 10;
            i /= 10;
        }
        //计算坐标j所有数字的和
        while (j != 0) {
            sum += j % 10;
            j /= 10;
        }
        return sum;
    }
}


✨总结


本来今天要刷三题的,但是今天的DFS 和 BFS比较重要,就写的详细一点,也下去多练几题。

本题也是面试官最喜欢考的题型,代码不多却体现了两种不同的思路。

一起来多练习几遍吧,等你哦!!!



目录
打赏
0
0
0
0
0
分享
相关文章
大数据大厂之MySQL数据库课程设计:揭秘MySQL集群架构负载均衡核心算法:从理论到Java代码实战,让你的数据库性能飙升!
本文聚焦 MySQL 集群架构中的负载均衡算法,阐述其重要性。详细介绍轮询、加权轮询、最少连接、加权最少连接、随机、源地址哈希等常用算法,分析各自优缺点及适用场景。并提供 Java 语言代码实现示例,助力直观理解。文章结构清晰,语言通俗易懂,对理解和应用负载均衡算法具有实用价值和参考价值。
大数据大厂之MySQL数据库课程设计:揭秘MySQL集群架构负载均衡核心算法:从理论到Java代码实战,让你的数据库性能飙升!
上网行为监控系统剖析:基于 Java LinkedHashMap 算法的时间序列追踪机制探究
数字化办公蓬勃发展的背景下,上网行为监控系统已成为企业维护信息安全、提升工作效能的关键手段。该系统需实时记录并深入分析员工的网络访问行为,如何高效存储和管理这些处于动态变化中的数据,便成为亟待解决的核心问题。Java 语言中的LinkedHashMap数据结构,凭借其独有的有序性特征以及可灵活配置的淘汰策略,为上网行为监控系统提供了一种兼顾性能与功能需求的数据管理方案。本文将对LinkedHashMap在上网行为监控系统中的应用原理、实现路径及其应用价值展开深入探究。
62 3
LRU算法的Java实现
LRU(Least Recently Used)算法用于淘汰最近最少使用的数据,常应用于内存管理策略中。在Redis中,通过`maxmemory-policy`配置实现不同淘汰策略,如`allkeys-lru`和`volatile-lru`等,采用采样方式近似LRU以优化性能。Java中可通过`LinkedHashMap`轻松实现LRUCache,利用其`accessOrder`特性和`removeEldestEntry`方法完成缓存淘汰逻辑,代码简洁高效。
算法系列之搜索算法-深度优先搜索DFS
深度优先搜索和广度优先搜索一样,都是对图进行搜索的算法,目的也都是从起点开始搜索,直到到达顶点。深度优先搜索会沿着一条路径不断的往下搜索,直到不能够在继续为止,然后在折返,开始搜索下一条候补路径。
225 62
算法系列之搜索算法-深度优先搜索DFS
如何监控员工的电脑——基于滑动时间窗口的Java事件聚合算法实现探析​
在企业管理场景中,如何监控员工的电脑操作行为是一个涉及效率与合规性的重要课题。传统方法依赖日志采集或屏幕截图,但数据量庞大且实时性不足。本文提出一种基于滑动时间窗口的事件聚合算法,通过Java语言实现高效、低资源占用的监控逻辑,为如何监控员工的电脑提供一种轻量化解决方案。
72 3
解锁“分享文件”高效密码:探秘 Java 二叉搜索树算法
在信息爆炸的时代,文件分享至关重要。二叉搜索树(BST)以其高效的查找性能,为文件分享优化提供了新路径。本文聚焦Java环境下BST的应用,介绍其基础结构、实现示例及进阶优化。BST通过有序节点快速定位文件,结合自平衡树、多线程和权限管理,大幅提升文件分享效率与安全性。代码示例展示了文件插入与查找的基本操作,适用于大规模并发场景,确保分享过程流畅高效。掌握BST算法,助力文件分享创新发展。
解锁分布式文件分享的 Java 一致性哈希算法密码
在数字化时代,文件分享成为信息传播与协同办公的关键环节。本文深入探讨基于Java的一致性哈希算法,该算法通过引入虚拟节点和环形哈希空间,解决了传统哈希算法在分布式存储中的“哈希雪崩”问题,确保文件分配稳定高效。文章还展示了Java实现代码,并展望了其在未来文件分享技术中的应用前景,如结合AI优化节点布局和区块链增强数据安全。
基于WOA鲸鱼优化的BiLSTM双向长短期记忆网络序列预测算法matlab仿真,对比BiLSTM和LSTM
本项目基于MATLAB 2022a/2024b实现,采用WOA优化的BiLSTM算法进行序列预测。核心代码包含完整中文注释与操作视频,展示从参数优化到模型训练、预测的全流程。BiLSTM通过前向与后向LSTM结合,有效捕捉序列前后文信息,解决传统RNN梯度消失问题。WOA优化超参数(如学习率、隐藏层神经元数),提升模型性能,避免局部最优解。附有运行效果图预览,最终输出预测值与实际值对比,RMSE评估精度。适合研究时序数据分析与深度学习优化的开发者参考。
基于PSO粒子群优化的BiLSTM双向长短期记忆网络序列预测算法matlab仿真,对比BiLSTM和LSTM
本项目基于MATLAB2022a/2024b开发,结合粒子群优化(PSO)算法与双向长短期记忆网络(BiLSTM),用于优化序列预测任务中的模型参数。核心代码包含详细中文注释及操作视频,涵盖遗传算法优化过程、BiLSTM网络构建、训练及预测分析。通过PSO优化BiLSTM的超参数(如学习率、隐藏层神经元数等),显著提升模型捕捉长期依赖关系和上下文信息的能力,适用于气象、交通流量等场景。附有运行效果图预览,展示适应度值、RMSE变化及预测结果对比,验证方法有效性。
基于遗传算法的256QAM星座图的最优概率整形matlab仿真,对比优化前后整形星座图和误码率
本内容展示了基于GA(遗传算法)优化的256QAM概率星座整形(PCS)技术的研究与实现。通过Matlab仿真,分析了优化前后星座图和误码率(BER)的变化。256QAM采用非均匀概率分布(Maxwell-Boltzman分布)降低外圈星座点出现频率,减小平均功率并增加最小欧氏距离,从而提升传输性能。GA算法以BER为适应度函数,搜索最优整形参数v,显著降低误码率。核心程序实现了GA优化过程,包括种群初始化、选择、交叉、变异等步骤,并绘制了优化曲线。此研究有助于提高频谱效率和传输灵活性,适用于不同信道环境。
48 10
AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等