【Py/Java/C++三种语言OD2023C卷真题】20天拿下华为OD笔试之【回溯】2023C-找到它【欧弟算法】全网注释最详细分类最全的华为OD真题题解

2024-04-12 06:28
文章标签 java 算法 c++ 全网 笔试 分类 三种 华为 py 真题 注释 20 题解 回溯 最全 od 拿下 欧弟 od2023c 2023c

本文主要是介绍【Py/Java/C++三种语言OD2023C卷真题】20天拿下华为OD笔试之【回溯】2023C-找到它【欧弟算法】全网注释最详细分类最全的华为OD真题题解，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

有LeetCode算法/华为OD考试扣扣交流群可加 948025485
可上全网独家的 欧弟OJ系统 练习华子OD、大厂真题
绿色聊天软件戳 od1336了解算法冲刺训练

文章目录

  • 题目描述与示例
    • 题目描述
    • 输入描述
    • 输出描述
    • 示例一
      • 输入
      • 输出
    • 示例二
      • 输入
      • 输出
  • 解题思路
    • 状态更新和回滚写在横向遍历for循环内的回溯写法
    • 状态更新和回滚写在横向遍历for循环外的回溯写法
  • 代码
    • python
    • java
    • cpp
    • 时空复杂度
  • 华为OD算法/大厂面试高频题算法练习冲刺训练

题目描述与示例

题目描述

找到它是个小游戏，你需要在一个矩阵中找到给定的单词 假设给定单词HELLOWORLD，在矩阵中只要能找HELLOWORLD就算通过 注意区分英文字母大小写，并且你只能上下左右行走，不能走回头路

输入描述

输入第一行包含两个整数N M (0 < N, M < 21) 分别表示N行M列的矩阵 第二行是长度不超过100的单词W 在整个矩阵中给定单词W只会出现一次 从第3行到第N+2是只包含大小写英文字母的长度为M的字符串矩阵

输出描述

如果能在矩阵中连成给定的单词，则输出给定单词首字母在矩阵中的位置为第几行第几列 否则输出 NO

示例一

输入

5 5
HELLOWORLD
CPUCY
EKLQH
CHELL
LROWO
DGRBC

输出

3 2

示例二

输入

5 5
Helloworld
CPUCh
wolle
orldO
EKLQo
PGRBC

输出

NO

解题思路

注意，本题和LeetCode79. 单词搜索几乎完全一致，唯一的区别在于前者只要求判断是否能够找到该单词，本题还需要输出起始位置。

状态更新和回滚写在横向遍历for循环内的回溯写法

我们需要思考的是，对于这种二维网格如何进行回溯？换句话说，如何构建回溯函数？

在回溯过程中我们需要知道以下信息：

  1. 当前进行到了单词中的哪一个字符？
  2. 当前在网格中搜索到了哪一个位置？
  3. 由于网格中的字符不能重复使用，那么哪一些字符是已经使用过的？
  4. 是否已经在网格中找到了这个单词？

对于第一点，我们的回溯函数中需要存在参数word_idx，来表示待搜索的单词此时遍历到的索引位置。

对于第二点，我们的回溯函数需要传入当前搜索的点的位置(x, y)

对于第三点，这个在二维网格类型的搜索问题中是非常常用的技巧，即构建一个大小和grid一样的check_list

对于第四点，我们可以直接声明一个全局变量isFind来表示是否已经找到该单词

除了这些参数之外，我们还需要传入二维矩阵grid本身，它的大小N和M等等。

容易构建出回溯函数如下

DIRECTIONS = [(0,1), (1,0), (-1,0), (0,-1)]def backtracking(grid, N, M, check_list, x, y, word, word_idx):global isFindif word_idx == len(word) - 1:isFind = Truereturnfor dx, dy in DIRECTIONS:nx, ny = x+dx, y+dyif (0 <= nx < len(grid) and 0 <= ny < len(grid[0]) and check_list[nx][ny] == False and grid[nx][ny] == word[word_idx+1]):check_list[nx][ny] = Truebacktracking(grid, N, M, check_list, nx, ny, word, word_idx+1)check_list[nx][ny] = False

容易发现，此处回溯函数的写法，和我们用DFS做二维网格搜索类型的题目是非常类似的。

换句话说，在当前点(x, y)的近邻点上下左右四个方向的选取的这个for循环，实际上就对应着回溯过程中状态树的横向遍历。

和常规DFS解法的区别在于，我们现在搜索的是一条路径，所以我们需要在递归调用backtracking()函数的前后，进行check_list[nx][ny]的状态更新和回滚，来表示近邻点(nx, ny)已经被使用过以及回滚之后再次可以被使用的情况。

在递归调用回溯函数的时候，我们需要将下一个点(nx, ny)以及word的下一个字符索引word_idx+1传入函数中。

回溯的终止条件也非常简单，就是当word_idx已经等于len(word)-1了，说明整个word的所有字符都能够在二维网格中找到，那么修改isFind为True，同时退出搜索。

而递归入口则需要这样调用

isFind = False
check_list = [[False] * M for _ in range(N)]for i in range(N):for j in range(M):if grid[i][j] == word[0]:check_list[i][j] = Truebacktracking(grid, N, M, check_list, i, j, word, 0)check_list[i][j] = Falseif isFind:print("{} {}".format(i+1, j+1))breakif isFind:break

注意到，由于在回溯函数中修改check_list始终是对(nx, ny)进行修改，所以我们在做起始点搜索的双重循环的时候，在递归函数入口处，需要对起始点(i, j)额外地进行check_list的状态更新和回滚。

状态更新和回滚写在横向遍历for循环外的回溯写法

如果你想直接修改check_list[x][y]而不是修改check_list[nx][ny]，那么回溯函数也可以改成这样

DIRECTIONS = [(0,1), (1,0), (-1,0), (0,-1)]def backtracking(grid, N, M, check_list, x, y, word, word_idx):global isFindif word_idx == len(word) - 1:isFind = Truereturncheck_list[x][y] = Truefor dx, dy in DIRECTIONS:nx, ny = x+dx, y+dyif (0 <= nx < len(grid) and 0 <= ny < len(grid[0]) and check_list[nx][ny] == False and grid[nx][ny] == word[word_idx+1]):backtracking(grid, N, M, check_list, nx, ny, word, word_idx+1)check_list[x][y] = False

这样就跟常规的DFS解法更加接近，但和常规的回溯题目的相似性就没那么高了。

因为状态更新和回滚写在了横向遍历for循环的外部。

对应的，由于此处状态的是(x, y)而非(nx, ny)，那么在递归入口处就可以不用单独进行(i, j)的更新了。即递归入口可以写为

isFind = False
check_list = [[False] * M for _ in range(N)]for i in range(N):for j in range(M):if grid[i][j] == word[0]:backtracking(grid, N, M, check_list, i, j, word, 0)if isFind:print("{} {}".format(i+1, j+1))breakif isFind:break

代码

python

# 题目：2023B-找到它
# 分值：200
# 作者：许老师-闭着眼睛学数理化
# 算法：回溯
# 代码看不懂的地方，请直接在群上提问# 全局的方向数组，表示上下左右移动四个方向
DIRECTIONS = [(0,1), (1,0), (-1,0), (0,-1)]# 构建回溯函数，各个参数的含义为
# grid：         原二维矩阵
# N,M：          原二维矩阵的行数、列数
# check_list：   大小和grid一样的检查列表，用于判断某个点是否已经检查过
# x,y：          当前在grid中的点的坐标
# word：         待搜索的单词
# word_idx：     待搜索的单词此时遍历到的索引位置
def backtracking(grid, N, M, check_list, x, y, word, word_idx):# 声明全局变量isFindglobal isFind# 若此时word_idx等于word的长度-1# 说明word中的所有字母都在grid中找到了# 修改isFind为True，同时终止递归if word_idx == len(word) - 1:isFind = Truereturn# 遍历四个方向，获得点(x,y)的近邻点(nx,ny)for dx, dy in DIRECTIONS:nx, ny = x+dx, y+dy# (nx,ny)必须满足以下三个条件，才可以继续进行回溯函数的递归调用# 1. 不越界；2. 尚未检查过；# 3.在grid中的值grid[nx][ny]为word的下一个字符word[word_idx+1]if 0 <= nx < len(grid) and 0 <= ny < len(grid[0]) and check_list[nx][ny] == False and grid[nx][ny] == word[word_idx+1]:# 状态更新，将点(nx,ny)在check_list中的状态更新为Truecheck_list[nx][ny] = True# 回溯，将点(nx,ny)传入回溯函数中，注意此时word_idx需要+1backtracking(grid, N, M, check_list, nx, ny, word, word_idx+1)# 回滚，将点(nx,ny)在check_list中的状态重新修改回Falsecheck_list[nx][ny] = False# 输入行数和列数
N, M = map(int, input().split())
# 输入待查找的单词
word = input()
# 构建二维网格
grid = list()
for _ in range(N):grid.append(input())# 构建全局变量isFind，初始化为False
isFind = False
# 构建大小和grid一样的检查数组check_list
# 用于避免出现重复检查的情况
check_list = [[False] * M for _ in range(N)]
# 双重遍历整个二维网格grid
for i in range(N):for j in range(M):# 找到点(i,j)等于word的第一个字母# 则点(i,j)可以作为递归的起始位置if grid[i][j] == word[0]:# 将点(i,j)在check_list中设置为已检查过check_list[i][j] = True# 回溯函数递归入口backtracking(grid, N, M, check_list, i, j, word, 0)# 将点(i,j)在check_list中重置为未检查过，因为本次回溯不一定找到答案check_list[i][j] = False# 如果在回溯中，全局变量isFind被改为True，说明找到了单词if isFind:# 输出行数和列数，注意在问题中行数和列数是从1开始计数的# 所以存在一个+1操作print("{} {}".format(i+1, j+1))# 同时可以直接退出循环breakif isFind:breakif not isFind:print("NO")

java

import java.util.Scanner;public class Main {// Global directions array to represent four directions: up, down, left, rightprivate static final int[][] DIRECTIONS = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}};private static boolean isFind = false;public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int N = scanner.nextInt();int M = scanner.nextInt();scanner.nextLine(); // Consume newlineString word = scanner.nextLine();char[][] grid = new char[N][M];for (int i = 0; i < N; i++) {String row = scanner.nextLine();for (int j = 0; j < M; j++) {grid[i][j] = row.charAt(j);}}boolean[][] checkList = new boolean[N][M];for (int i = 0; i < N; i++) {for (int j = 0; j < M; j++) {if (grid[i][j] == word.charAt(0)) {checkList[i][j] = true;backtracking(grid, N, M, checkList, i, j, word, 0);checkList[i][j] = false;if (isFind) {System.out.println((i + 1) + " " + (j + 1));return;}}}}if (!isFind) {System.out.println("NO");}}private static void backtracking(char[][] grid, int N, int M, boolean[][] checkList, int x, int y, String word, int wordIdx) {if (wordIdx == word.length() - 1) {isFind = true;return;}for (int[] dir : DIRECTIONS) {int nx = x + dir[0];int ny = y + dir[1];if (nx >= 0 && nx < N && ny >= 0 && ny < M && !checkList[nx][ny] && grid[nx][ny] == word.charAt(wordIdx + 1)) {checkList[nx][ny] = true;backtracking(grid, N, M, checkList, nx, ny, word, wordIdx + 1);checkList[nx][ny] = false;}}}
}

cpp

#include <iostream>
#include <vector>using namespace std;// Global directions array to represent four directions: up, down, left, right
const vector<pair<int, int>> DIRECTIONS = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}};
bool isFind = false;// Backtracking function
void backtracking(vector<vector<char>>& grid, int N, int M, vector<vector<bool>>& checkList, int x, int y, string& word, int wordIdx) {if (wordIdx == word.length() - 1) {isFind = true;return;}for (const auto& dir : DIRECTIONS) {int nx = x + dir.first;int ny = y + dir.second;if (nx >= 0 && nx < N && ny >= 0 && ny < M && !checkList[nx][ny] && grid[nx][ny] == word[wordIdx + 1]) {checkList[nx][ny] = true;backtracking(grid, N, M, checkList, nx, ny, word, wordIdx + 1);checkList[nx][ny] = false;}}
}int main() {int N, M;cin >> N >> M;string word;cin >> word;vector<vector<char>> grid(N, vector<char>(M));for (int i = 0; i < N; i++) {for (int j = 0; j < M; j++) {cin >> grid[i][j];}}vector<vector<bool>> checkList(N, vector<bool>(M, false));for (int i = 0; i < N; i++) {for (int j = 0; j < M; j++) {if (grid[i][j] == word[0]) {checkList[i][j] = true;backtracking(grid, N, M, checkList, i, j, word, 0);checkList[i][j] = false;if (isFind) {cout << i + 1 << " " << j + 1 << endl;return 0;}}}}if (!isFind) {cout << "NO" << endl;}return 0;
}

时空复杂度

时间复杂度：O(NM3^L)。其中L为单词word的长度，这是一个比较宽松的上界，回溯过程中每一个点都最多有三个分支可以进入。

空间复杂度：O(NM)。check_list所占空间。

华为OD算法/大厂面试高频题算法练习冲刺训练

  • 华为OD算法/大厂面试高频题算法冲刺训练目前开始常态化报名！目前已服务300+同学成功上岸！

  • 课程讲师为全网50w+粉丝编程博主@吴师兄学算法 以及小红书头部编程博主@闭着眼睛学数理化

  • 每期人数维持在20人内，保证能够最大限度地满足到每一个同学的需求，达到和1v1同样的学习效果！

  • 60+天陪伴式学习，40+直播课时，300+动画图解视频，300+LeetCode经典题，200+华为OD真题/大厂真题，还有简历修改、模拟面试、专属HR对接将为你解锁

  • 可上全网独家的欧弟OJ系统练习华子OD、大厂真题

  • 可查看链接 大厂真题汇总 & OD真题汇总(持续更新)

  • 绿色聊天软件戳 od1336了解更多

这篇关于【Py/Java/C++三种语言OD2023C卷真题】20天拿下华为OD笔试之【回溯】2023C-找到它【欧弟算法】全网注释最详细分类最全的华为OD真题题解的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/896354。

相关文章

Java数组初始化的五种方式

Java数组初始化的五种方式

《Java数组初始化的五种方式》数组是Java中最基础且常用的数据结构之一,其初始化方式多样且各具特点,本文详细讲解Java数组初始化的五种方式,分析其适用场景、优劣势对比及注意事项,帮助避免常见陷阱... 目录1. 静态初始化：简洁但固定代码示例核心特点适用场景注意事项2. 动态初始化：灵活但需手动管理代
阅读更多...
Java使用SLF4J记录不同级别日志的示例详解

Java使用SLF4J记录不同级别日志的示例详解

《Java使用SLF4J记录不同级别日志的示例详解》SLF4J是一个简单的日志门面,它允许在运行时选择不同的日志实现,这篇文章主要为大家详细介绍了如何使用SLF4J记录不同级别日志,感兴趣的可以了解下... 目录一、SLF4J简介二、添加依赖三、配置Logback四、记录不同级别的日志五、总结一、SLF4J
阅读更多...
将Java项目提交到云服务器的流程步骤

将Java项目提交到云服务器的流程步骤

《将Java项目提交到云服务器的流程步骤》所谓将项目提交到云服务器即将你的项目打成一个jar包然后提交到云服务器即可,因此我们需要准备服务器环境为：Linux+JDK+MariDB（MySQL）+Gi... 目录1. 安装 jdk1.1 查看 jdk 版本1.2 下载 jdk2. 安装 mariadb(my
阅读更多...
SpringBoot中配置Redis连接池的完整指南

SpringBoot中配置Redis连接池的完整指南

《SpringBoot中配置Redis连接池的完整指南》这篇文章主要为大家详细介绍了SpringBoot中配置Redis连接池的完整指南,文中的示例代码讲解详细,具有一定的借鉴价值,感兴趣的小伙伴可以... 目录一、添加依赖二、配置 Redis 连接池三、测试 Redis 操作四、完整示例代码（一）pom.
阅读更多...
Java 正则表达式URL 匹配与源码全解析

Java 正则表达式URL 匹配与源码全解析

《Java正则表达式URL匹配与源码全解析》在Web应用开发中,我们经常需要对URL进行格式验证,今天我们结合Java的Pattern和Matcher类,深入理解正则表达式在实际应用中... 目录1.正则表达式分解：2. 添加域名匹配 (2)3. 添加路径和查询参数匹配 (3) 4. 最终优化版本5.设计思
阅读更多...
Java使用ANTLR4对Lua脚本语法校验详解

Java使用ANTLR4对Lua脚本语法校验详解

《Java使用ANTLR4对Lua脚本语法校验详解》ANTLR是一个强大的解析器生成器,用于读取、处理、执行或翻译结构化文本或二进制文件,下面就跟随小编一起看看Java如何使用ANTLR4对Lua脚本... 目录什么是ANTLR？第一个例子ANTLR4 的工作流程Lua脚本语法校验准备一个Lua Gramm
阅读更多...
Java字符串操作技巧之语法、示例与应用场景分析

Java字符串操作技巧之语法、示例与应用场景分析

《Java字符串操作技巧之语法、示例与应用场景分析》在Java算法题和日常开发中,字符串处理是必备的核心技能,本文全面梳理Java中字符串的常用操作语法,结合代码示例、应用场景和避坑指南,可快速掌握字... 目录引言1. 基础操作1.1 创建字符串1.2 获取长度1.3 访问字符2. 字符串处理2.1 子字
阅读更多...
Java Optional的使用技巧与最佳实践

Java Optional的使用技巧与最佳实践

《JavaOptional的使用技巧与最佳实践》在Java中,Optional是用于优雅处理null的容器类,其核心目标是显式提醒开发者处理空值场景,避免NullPointerExce... 目录一、Optional 的核心用途二、使用技巧与最佳实践三、常见误区与反模式四、替代方案与扩展五、总结在 Java
阅读更多...
基于Java实现回调监听工具类

基于Java实现回调监听工具类

《基于Java实现回调监听工具类》这篇文章主要为大家详细介绍了如何基于Java实现一个回调监听工具类,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录监听接口类 Listenable实际用法打印结果首先，会用到 函数式接口 Consumer, 通过这个可以解耦回调方法，下面先写一个
阅读更多...
IDEA自动生成注释模板的配置教程

IDEA自动生成注释模板的配置教程

《IDEA自动生成注释模板的配置教程》本文介绍了如何在IntelliJIDEA中配置类和方法的注释模板,包括自动生成项目名称、包名、日期和时间等内容,以及如何定制参数和返回值的注释格式,需要的朋友可以... 目录项目场景配置方法类注释模板定义类开头的注释步骤类注释效果方法注释模板定义方法开头的注释步骤方法注
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2