网站添加百度商桥,如何在云服务器上搭建网站,足球排行榜前十名,桥梁建设工程网站有LeetCode算法/华为OD考试扣扣交流群可加 948025485 可上全网独家的 欧弟OJ系统 练习华子OD、大厂真题 绿色聊天软件戳 od1336了解算法冲刺训练 文章目录 题目描述与示例题目描述输入描述输出描述示例一输入输出 示例二输入输出 解题思路代码pythonJavaC时空复杂度 华为OD算法… 有LeetCode算法/华为OD考试扣扣交流群可加 948025485 可上全网独家的 欧弟OJ系统 练习华子OD、大厂真题 绿色聊天软件戳 od1336了解算法冲刺训练 文章目录 题目描述与示例题目描述输入描述输出描述示例一输入输出 示例二输入输出 解题思路代码pythonJavaC时空复杂度 华为OD算法/大厂面试高频题算法练习冲刺训练 题目描述与示例
题目描述
有一种特殊的加密算法明文为一段数字串经过密码本查找转换生成另一段密文数字串。规则如下
明文为一段数字串由0-9组成密码本为数字0-9组成的二维数组需要按明文串的数字顺序在密码本里找到同样的数字串密码本里的数字串是由相邻的单元格数字组成上下和左右是相邻的注意:对角线不相邻同一个单元格的数字不能重复使用。每一位明文对应密文即为密码本中找到的单元格所在的行和列序号(序号从0开始)组成的两个数字。如明文第i位Data[i]对应密码本单元格为Book[X][Y]则明文第i位对应的密文为X YX和Y之间用空格隔开。如果有多条密文返回字符序最小的密文。如果密码本无法匹配返回error.
请你设计这个加密程序。
示例 1:
密码本:
{0,0,2},
{1,3,4},
{6,6,4}明文3密文1 1
示例 2:
密码本:
{0,0,2},
{1,3,4},
{6,6,4}明文0 3,密文0 1 1 1
示例 3:
密码本:
{0,0,2,4}
{1,3,4,6}
{3,4,1,5}
{6,6,6,5}明文0 0 2 4密文0 0 0 1 0 2 0 3和0 0 0 1 0 2 1 2返回字典序小的0 0 0 1 0 2 0 3
输入描述
第一行输入1个正整数N代表明文的长度(1 N 9)
第二行输入N个明文数字组成的序列Data[i](整数0 Data[i] 9)
第三行输入1个正整数M(1 M 9)
接下来输入一个M*M的矩阵代表密码本Book[i][i](整数0 Book[i][i] 9)
输出描述
如明文 第i位Data[i]对应密码本单元格为Book[i][j]则明文第i位对应的密文为X YX和Y之间用空格隔开。如果有多条密文返回字符序最小的密文。如果密码本无法匹配返回error。
示例一
输入
2
0 3
3
0 0 2
1 3 4
6 6 4输出
0 1 1 1示例二
输入
4
0 0 2 4
4
0 0 2 4
1 3 4 6
3 4 1 5
6 6 6 5输出
0 0 0 1 0 2 0 3解题思路 注意本题和LeetCode79. 单词搜索、【回溯】2023C-找到它非常类似。唯一的区别是题目不保证答案是唯一的当存在多个合适的密文的时候需要返回字典序最小的那个。 本题基本思路和【回溯】2023C-找到它一致。本题需要着重考虑最小字典序的问题。
这个时候搜索的方向数组DIRECTIONS里的顺序就非常重要了。假设当前点为(x, y)那么其近邻点为
上方(x-1, y)左方(x, y-1)右方(x, y1)下方(x1, y)
显然如果存在多个近邻点同时满足下一个字符的时候按照上、左、右、下这个顺序来搜索的话一定能够得到最小的字典序因为坐标为更小字典序的近邻点被优先搜索了。
这也是极少数的我们需要特别注意方向数组DIRECTIONS的顺序的题目。即
DIRECTIONS [(-1, 0), (0, -1), (0, 1), (1, 0)]代码
python
# 题目2023C-加密算法
# 分值200
# 作者许老师-闭着眼睛学数理化
# 算法回溯
# 代码看不懂的地方请直接在群上提问# 全局的方向数组表示上下左右移动四个方向
# 【特别注意】此处的顺序是非常重要的必须按照【上、左、右、下】来排布
# 这样才能使得计算得到的密文一定是字典序最小
DIRECTIONS [(-1, 0), (0, -1), (0, 1), (1, 0)]# 构建回溯函数各个参数的含义为
# grid 原二维矩阵
# M 原二维矩阵的大小M
# check_list 大小和grid一样的检查列表用于判断某个点是否已经检查过
# x,y 当前在grid中的点的坐标
# s 待搜索的明文
# s_idx 待搜索的明文此时遍历到的索引位置
# path 当前路径
def backtracking(grid, M, check_list, x, y, s, s_idx, path):# 声明全局变量isFindglobal isFind# 如果在之前的回溯中已经找到了最小字典序的密文直接返回if isFind:return# 若此时s_idx等于s的长度-1即N-1# 说明s中的所有数字都在grid中找到了# 修改isFind为True输出答案同时终止递归if s_idx N - 1:isFind Trueprint( .join(f{item[0]} {item[1]} for item in path))return# 遍历四个方向获得点(x,y)的近邻点(nx,ny)for dx, dy in DIRECTIONS:nx, ny xdx, ydy# (nx,ny)必须满足以下三个条件才可以继续进行回溯函数的递归调用# 1. 不越界2. 尚未检查过# 3.在grid中的值grid[nx][ny]为s的下一个字符s[s_idx1]if 0 nx M and 0 ny M and check_list[nx][ny] False and grid[nx][ny] s[s_idx1]:# 状态更新将点(nx,ny)在check_list中的状态更新为True更新path末尾check_list[nx][ny] Truepath.append((nx, ny))# 回溯将点(nx,ny)传入回溯函数中注意此时s_idx需要1backtracking(grid, M, check_list, nx, ny, s, s_idx1, path)# 回滚将点(nx,ny)在check_list中的状态重新修改回False将path末尾的函数弹出check_list[nx][ny] Falsepath.pop()# 输入明文长度N
N int(input())
# 输入待查找的明文
s input().split()
# 输入密码本的行数列数M
M int(input())
# 构建密码本二维网格
grid list()
for _ in range(M):grid.append(input().split())# 构建全局变量isFind初始化为False
isFind False# 构建大小和grid一样的检查数组check_list
# 用于避免出现重复检查的情况
check_list [[False] * M for _ in range(M)]
# 双重遍历整个二维网格grid
for i in range(M):for j in range(M):# 找到点(i,j)等于s的第一个数字# 则点(i,j)可以作为递归的起始位置if grid[i][j] s[0]:# 将点(i,j)在check_list中设置为已检查过check_list[i][j] True# 回溯函数递归入口path初始为储存点(i,j)backtracking(grid, M, check_list, i, j, s, 0, [(i, j)])# 将点(i,j)在check_list中重置为未检查过因为本次回溯不一定找到答案check_list[i][j] False# 如果在回溯中全局变量isFind被改为True说明找到了明文直接退出循环if isFind:break# 关于i的循环同理找到明文之后直接退出循环if isFind:break# 如果最终没找到明文输出error
if not isFind:print(error)Java
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;public class Main {// 全局的方向数组表示上下左右移动四个方向// 【特别注意】此处的顺序是非常重要的必须按照【上、左、右、下】来排布// 这样才能使得计算得到的密文一定是字典序最小static final int[][] DIRECTIONS {{-1, 0}, {0, -1}, {0, 1}, {1, 0}};static boolean isFind false;// 构建回溯函数static void backtracking(String[][] grid, int M, boolean[][] checkList, int x, int y, String[] s, int sIdx, ListListInteger path) {// 如果在之前的回溯中已经找到了最小字典序的密文直接返回if (isFind) return;// 若此时sIdx等于s的长度-1即N-1// 说明s中的所有数字都在grid中找到了// 修改isFind为True输出答案同时终止递归if (sIdx s.length - 1) {isFind true;StringBuilder sb new StringBuilder();for (ListInteger point : path) {sb.append(point.get(0)).append( ).append(point.get(1)).append( );}System.out.println(sb);return;}// 遍历四个方向获得点(x,y)的近邻点(nx,ny)for (int[] dir : DIRECTIONS) {int nx x dir[0];int ny y dir[1];// (nx,ny)必须满足以下三个条件才可以继续进行回溯函数的递归调用// 1. 不越界2. 尚未检查过// 3.在grid中的值grid[nx][ny]为s的下一个字符s[sIdx1]if (nx 0 nx M ny 0 ny M !checkList[nx][ny] grid[nx][ny].equals(s[sIdx 1])) {// 状态更新将点(nx,ny)在checkList中的状态更新为True更新path末尾checkList[nx][ny] true;ListInteger point new ArrayList();point.add(nx);point.add(ny);path.add(point);// 回溯将点(nx,ny)传入回溯函数中注意此时sIdx需要1backtracking(grid, M, checkList, nx, ny, s, sIdx 1, path);// 回滚将点(nx,ny)在checkList中的状态重新修改回False将path末尾的点弹出checkList[nx][ny] false;path.remove(path.size() - 1);}}}public static void main(String[] args) {Scanner scanner new Scanner(System.in);int N scanner.nextInt();String[] s new String[N];for (int i 0; i N; i) {s[i] scanner.next();}int M scanner.nextInt();String[][] grid new String[M][M];for (int i 0; i M; i) {for (int j 0; j M; j) {grid[i][j] scanner.next();}}// 构建大小和grid一样的检查数组checkList// 用于避免出现重复检查的情况boolean[][] checkList new boolean[M][M];// 双重遍历整个二维网格gridfor (int i 0; i M; i) {for (int j 0; j M; j) {// 找到点(i,j)等于s的第一个数字// 则点(i,j)可以作为递归的起始位置if (grid[i][j].equals(s[0])) {// 将点(i,j)在checkList中设置为已检查过checkList[i][j] true;ListListInteger path new ArrayList();ListInteger point new ArrayList();point.add(i);point.add(j);path.add(point);// 回溯函数递归入口path初始为储存点(i,j)backtracking(grid, M, checkList, i, j, s, 0, path);// 将点(i,j)在checkList中重置为未检查过因为本次回溯不一定找到答案checkList[i][j] false;// 如果在回溯中全局变量isFind被改为True说明找到了明文直接退出循环if (isFind) {break;}}}// 关于i的循环同理找到明文之后直接退出循环if (isFind) {break;}}// 如果最终没找到明文输出errorif (!isFind) {System.out.println(error);}}
}C
#include iostream
#include vector
#include stringusing namespace std;// 全局的方向数组表示上下左右移动四个方向
// 【特别注意】此处的顺序是非常重要的必须按照【上、左、右、下】来排布
// 这样才能使得计算得到的密文一定是字典序最小
const vectorvectorint DIRECTIONS {{-1, 0}, {0, -1}, {0, 1}, {1, 0}};
bool isFind false;// 构建回溯函数
void backtracking(vectorvectorstring grid, int M, vectorvectorbool checkList, int x, int y, vectorstring s, int sIdx, vectorvectorint path) {// 如果在之前的回溯中已经找到了最小字典序的密文直接返回if (isFind) return;// 若此时sIdx等于s的长度-1即N-1// 说明s中的所有数字都在grid中找到了// 修改isFind为True输出答案同时终止递归if (sIdx s.size() - 1) {isFind true;for (int i 0; i path.size(); i) {cout path[i][0] path[i][1] ;}cout endl;return;}// 遍历四个方向获得点(x,y)的近邻点(nx,ny)for (auto dir : DIRECTIONS) {int nx x dir[0];int ny y dir[1];// (nx,ny)必须满足以下三个条件才可以继续进行回溯函数的递归调用// 1. 不越界2. 尚未检查过// 3.在grid中的值grid[nx][ny]为s的下一个字符s[sIdx1]if (nx 0 nx M ny 0 ny M !checkList[nx][ny] grid[nx][ny] s[sIdx 1]) {// 状态更新将点(nx,ny)在checkList中的状态更新为True更新path末尾checkList[nx][ny] true;path.push_back({nx, ny});// 回溯将点(nx,ny)传入回溯函数中注意此时sIdx需要1backtracking(grid, M, checkList, nx, ny, s, sIdx 1, path);// 回滚将点(nx,ny)在checkList中的状态重新修改回False将path末尾的点弹出checkList[nx][ny] false;path.pop_back();}}
}int main() {int N;cin N;vectorstring s(N);for (int i 0; i N; i) {cin s[i];}int M;cin M;vectorvectorstring grid(M, vectorstring(M));for (int i 0; i M; i) {for (int j 0; j M; j) {cin grid[i][j];}}// 构建大小和grid一样的检查数组checkList// 用于避免出现重复检查的情况vectorvectorbool checkList(M, vectorbool(M, false));// 双重遍历整个二维网格gridfor (int i 0; i M; i) {for (int j 0; j M; j) {// 找到点(i,j)等于s的第一个数字// 则点(i,j)可以作为递归的起始位置if (grid[i][j] s[0]) {// 将点(i,j)在checkList中设置为已检查过checkList[i][j] true;vectorvectorint path {{i, j}};// 回溯函数递归入口path初始为储存点(i,j)backtracking(grid, M, checkList, i, j, s, 0, path);// 将点(i,j)在checkList中重置为未检查过因为本次回溯不一定找到答案checkList[i][j] false;// 如果在回溯中全局变量isFind被改为True说明找到了明文直接退出循环if (isFind) {break;}}}// 关于i的循环同理找到明文之后直接退出循环if (isFind) {break;}}// 如果最终没找到明文输出errorif (!isFind) {cout error endl;}return 0;
}时空复杂度
时间复杂度O(M^2*3^N)。其中N为密文s的长度这是一个比较宽松的上界回溯过程中每一个点都最多有三个分支可以进入。
空间复杂度O(M^2)。check_list所占空间。 华为OD算法/大厂面试高频题算法练习冲刺训练 华为OD算法/大厂面试高频题算法冲刺训练目前开始常态化报名目前已服务300同学成功上岸 课程讲师为全网50w粉丝编程博主吴师兄学算法 以及小红书头部编程博主闭着眼睛学数理化 每期人数维持在20人内保证能够最大限度地满足到每一个同学的需求达到和1v1同样的学习效果 60天陪伴式学习40直播课时300动画图解视频300LeetCode经典题200华为OD真题/大厂真题还有简历修改、模拟面试、专属HR对接将为你解锁 可上全网独家的欧弟OJ系统练习华子OD、大厂真题 可查看链接 大厂真题汇总 OD真题汇总(持续更新) 绿色聊天软件戳 od1336了解更多
