【七十六】【算法分析与设计】2435. 矩阵中和能被 K 整除的路径,87. 扰乱字符串,三维动态规划

本文主要是介绍【七十六】【算法分析与设计】2435. 矩阵中和能被 K 整除的路径,87. 扰乱字符串,三维动态规划,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

2435. 矩阵中和能被 K 整除的路径

给你一个下标从 0 开始的 m x n 整数矩阵 grid 和一个整数 k 。你从起点 (0, 0) 出发,每一步只能往 或者往 ,你想要到达终点 (m - 1, n - 1)

  • 请你返回路径和能被 k 整除的路径数目,由于答案可能很大,返回答案对 10(9)7 取余 的结果。

示例 1:

输入:grid = [[5,2,4],[3,0,5],[0,7,2]], k = 3 输出:2 解释:有两条路径满足路径上元素的和能被 k 整除。 第一条路径为上图中用红色标注的路径,和为 5 + 2 + 4 + 5 + 2 = 18 ,能被 3 整除。 第二条路径为上图中用蓝色标注的路径,和为 5 + 3 + 0 + 5 + 2 = 15 ,能被 3 整除。

示例 2:

输入:grid = [[0,0]], k = 5 输出:1 解释:红色标注的路径和为 0 + 0 = 0 ,能被 5 整除。

示例 3:

输入:grid = [[7,3,4,9],[2,3,6,2],[2,3,7,0]], k = 1 输出:10 解释:每个数字都能被 1 整除,所以每一条路径的和都能被 k 整除。

提示:

  • m == grid.length

  • n == grid[i].length

  • 1 <= m, n <= 5 * 10(4)

  • 1 <= m * n <= 5 * 10(4)

  • 0 <= grid[i][j] <= 100

  • 1 <= k <= 50

1.

定义f函数,希望将已知信息扔进去加工出我们希望的结果.

我们希望得到从(0,0)位置开始到右下角路径和对k取余为0的路径数.

可以定义f函数从(i,j)位置开始到右下角路径和对k取余为r的路径数.

因此我们需要得到f(0,0,0)的结果.

2.

我们只走一步,从(i,j)位置开始到右下角路径和对k取余为r的路径数.

走一步的结果是(i+1,j)位置或者(i,j+1)位置,能不能找到两者的等价关系.

可以将(i,j)位置的元素值假设为a,走一步位置到右下角的路径和假设为b.

(a+b)%k=r,等价于(a%k+b%k)%k=r.

a%k范围是[0,k-1],b%k范围是[0,k-1].

a%k+b%k范围是[0,2*k-1].

r的范围是[0,k-1].

因此a%k+b%k=r或者r+k.

b%k=r-a%k或者r+k-a%k

b%k=(r+k-a%k)%k.

因此从(i,j)位置开始到右下角路径和对k取余为r的路径数.等价于走一步开始到右下角路径和对k取余为(r+k-a%k)%k的路径数.

3.

处理边界情况,先把状态转移方程写出来,dp[i][j][r]=dp[i+1][j][(r+k-a%k)%k]+dp[i][j+1][(r+k-a%k)%k].

越界的情况是i或者j.很容易知道越界返回0即可.

思考basecase情况,也就是最基本的可以直接得出答案的情况.

也就是当前位置是右下角位置,此时对k取余为r的路径数只需要判断当前元素对k取余是不是等于r即可.

#include <vector>
using namespace std;class Solution {
public:vector<vector<int>> grid; // 定义一个二维数组用于存储输入的网格int k, n, m; // k为路径和需要被整除的数,n和m分别为网格的行数和列数vector<vector<vector<int>>> dp; // 定义一个三维动态规划数组,用于存储中间结果const int MOD = 1e9 + 7; // 定义一个大数作为模数,以防止结果过大// 初始化动态规划数组的辅助函数void solveInit() {n = grid.size(), m = grid[0].size(); // 更新网格的行数和列数dp.clear(); // 清空之前的动态规划数组// 重新初始化动态规划数组的大小为n*m*kdp.resize(n, vector<vector<int>>(m, vector<int>(k, -1)));}// 深度优先搜索的递归函数,用于计算满足条件的路径数目int dfs(int i, int j, int r) {// 如果当前位置超出网格范围,则无法继续移动,返回0if (i >= n || j >= m)return 0;// 如果到达终点,检查路径和是否能被k整除if (i == n - 1 && j == m - 1)return (grid[i][j] % k == r) ? 1 : 0;// 如果当前状态已经在dp数组中计算过,则直接返回结果if (dp[i][j][r] != -1)return dp[i][j][r];int newR = (r + k - (grid[i][j] % k)) % k; // 计算新的路径和对应的余数// 递归计算向下移动和向右移动到达终点的路径数目,并取模dp[i][j][r] = (dfs(i + 1, j, newR) + dfs(i, j + 1, newR)) % MOD;return dp[i][j][r];}// 主函数,用于计算满足条件的路径数目int numberOfPaths(vector<vector<int>>& _grid, int _k) {grid = _grid; // 更新输入的网格k = _k; // 更新k的值solveInit(); // 初始化动态规划数组// 从起点(0, 0)开始,路径和的初始余数为0,递归计算路径数目return dfs(0, 0, 0);}
};

87. 扰乱字符串

使用下面描述的算法可以扰乱字符串 s 得到字符串 t

  1. 如果字符串的长度为 1 ,算法停止

  2. 如果字符串的长度 > 1 ,执行下述步骤:

    1. 在一个随机下标处将字符串分割成两个非空的子字符串。即,如果已知字符串 s ,则可以将其分成两个子字符串 xy ,且满足 s = x + y

    2. 随机 决定是要「交换两个子字符串」还是要「保持这两个子字符串的顺序不变」。即,在执行这一步骤之后,s 可能是 s = x + y 或者 s = y + x

    3. xy 这两个子字符串上继续从步骤 1 开始递归执行此算法。

给你两个 长度相等 的字符串 s1 s2,判断 s2 是否是 s1 的扰乱字符串。如果是,返回 true ;否则,返回 false

示例 1:

输入:s1 = "great", s2 = "rgeat" 输出:true 解释:s1 上可能发生的一种情形是: "great" --> "gr/eat" // 在一个随机下标处分割得到两个子字符串 "gr/eat" --> "gr/eat" // 随机决定:「保持这两个子字符串的顺序不变」 "gr/eat" --> "g/r / e/at" // 在子字符串上递归执行此算法。两个子字符串分别在随机下标处进行一轮分割 "g/r / e/at" --> "r/g / e/at" // 随机决定:第一组「交换两个子字符串」,第二组「保持这两个子字符串的顺序不变」 "r/g / e/at" --> "r/g / e/ a/t" // 继续递归执行此算法,将 "at" 分割得到 "a/t" "r/g / e/ a/t" --> "r/g / e/ a/t" // 随机决定:「保持这两个子字符串的顺序不变」 算法终止,结果字符串和 s2 相同,都是 "rgeat" 这是一种能够扰乱 s1 得到 s2 的情形,可以认为 s2 是 s1 的扰乱字符串,返回 true

示例 2:

输入:s1 = "abcde", s2 = "caebd" 输出:false

示例 3:

输入:s1 = "a", s2 = "a" 输出:true

提示:

  • s1.length == s2.length

  • 1 <= s1.length <= 30

  • s1s2 由小写英文字母组成

1.

s1[i,j]区间是否可以转化为s2[x,y]区间.f函数定义.

走一步,枚举所有分割的情况,对于每一种情况考虑交换或者不交换.

class Solution {
public:string s1, s2; // 声明两个字符串s1和s2int n; // 字符串的长度vector<vector<vector<vector<int>>>> dp; // 声明一个四维动态规划数组dp// 初始化动态规划数组的辅助函数void solveinit() {n = s1.size(); // 获取字符串s1的长度dp.clear(), // 清空之前的动态规划数组dp.resize(n, vector<vector<vector<int>>>(n, vector<vector<int>>(n, vector<int>(n, -1)))); // 初始化dp数组}// 深度优先搜索的递归函数,用于判断s2是否是s1的扰乱字符串bool dfs(int i, int j, int x, int y) {// 如果当前状态已经在dp数组中计算过,则直接返回结果if (dp[i][j][x][y] != -1)return dp[i][j][x][y];// 如果子串长度为1,判断对应字符是否相等if (i == j) {dp[i][j][x][y] = s1[i] == s2[x];return s1[i] == s2[x];}bool flag = false; // 初始化标志位为false// 枚举s1的子串分割点for (int k = 0; k < j - i; k++) {// 情况1:保持s1的子串顺序,判断s2的对应子串是否满足条件flag |= (dfs(i, i + k, x, x + k) && dfs(i + k + 1, j, x + k + 1, y));// 情况2:交换s1的子串顺序,判断s2的对应子串是否满足条件flag |= (dfs(i, i + k, y - k, y) && dfs(i + k + 1, j, x, y - k - 1));}// 存储当前状态的计算结果dp[i][j][x][y] = flag;return flag; // 返回当前状态的计算结果}// 主函数,用于判断s2是否是s1的扰乱字符串bool isScramble(string _s1, string _s2) {s1 = _s1, s2 = _s2; // 更新输入的两个字符串solveinit(); // 初始化动态规划数组// 从整个字符串的起始位置开始判断return dfs(0, n - 1, 0, n - 1);}
};

结尾

最后,感谢您阅读我的文章,希望这些内容能够对您有所启发和帮助。如果您有任何问题或想要分享您的观点,请随时在评论区留言。

同时,不要忘记订阅我的博客以获取更多有趣的内容。在未来的文章中,我将继续探讨这个话题的不同方面,为您呈现更多深度和见解。

谢谢您的支持,期待与您在下一篇文章中再次相遇!

这篇关于【七十六】【算法分析与设计】2435. 矩阵中和能被 K 整除的路径,87. 扰乱字符串,三维动态规划的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

Redis连接失败:客户端IP不在白名单中的问题分析与解决方案

《Redis连接失败:客户端IP不在白名单中的问题分析与解决方案》在现代分布式系统中,Redis作为一种高性能的内存数据库,被广泛应用于缓存、消息队列、会话存储等场景,然而,在实际使用过程中,我们可能... 目录一、问题背景二、错误分析1. 错误信息解读2. 根本原因三、解决方案1. 将客户端IP添加到Re

JAVA中整型数组、字符串数组、整型数和字符串 的创建与转换的方法

《JAVA中整型数组、字符串数组、整型数和字符串的创建与转换的方法》本文介绍了Java中字符串、字符数组和整型数组的创建方法,以及它们之间的转换方法,还详细讲解了字符串中的一些常用方法,如index... 目录一、字符串、字符数组和整型数组的创建1、字符串的创建方法1.1 通过引用字符数组来创建字符串1.2

Redis主从复制实现原理分析

《Redis主从复制实现原理分析》Redis主从复制通过Sync和CommandPropagate阶段实现数据同步,2.8版本后引入Psync指令,根据复制偏移量进行全量或部分同步,优化了数据传输效率... 目录Redis主DodMIK从复制实现原理实现原理Psync: 2.8版本后总结Redis主从复制实

锐捷和腾达哪个好? 两个品牌路由器对比分析

《锐捷和腾达哪个好?两个品牌路由器对比分析》在选择路由器时,Tenda和锐捷都是备受关注的品牌,各自有独特的产品特点和市场定位,选择哪个品牌的路由器更合适,实际上取决于你的具体需求和使用场景,我们从... 在选购路由器时,锐捷和腾达都是市场上备受关注的品牌,但它们的定位和特点却有所不同。锐捷更偏向企业级和专

C#中字符串分割的多种方式

《C#中字符串分割的多种方式》在C#编程语言中,字符串处理是日常开发中不可或缺的一部分,字符串分割是处理文本数据时常用的操作,它允许我们将一个长字符串分解成多个子字符串,本文给大家介绍了C#中字符串分... 目录1. 使用 string.Split2. 使用正则表达式 (Regex.Split)3. 使用

如何用Python绘制简易动态圣诞树

《如何用Python绘制简易动态圣诞树》这篇文章主要给大家介绍了关于如何用Python绘制简易动态圣诞树,文中讲解了如何通过编写代码来实现特定的效果,包括代码的编写技巧和效果的展示,需要的朋友可以参考... 目录代码:效果:总结 代码:import randomimport timefrom math

python获取当前文件和目录路径的方法详解

《python获取当前文件和目录路径的方法详解》:本文主要介绍Python中获取当前文件路径和目录的方法,包括使用__file__关键字、os.path.abspath、os.path.realp... 目录1、获取当前文件路径2、获取当前文件所在目录3、os.path.abspath和os.path.re

Spring中Bean有关NullPointerException异常的原因分析

《Spring中Bean有关NullPointerException异常的原因分析》在Spring中使用@Autowired注解注入的bean不能在静态上下文中访问,否则会导致NullPointerE... 目录Spring中Bean有关NullPointerException异常的原因问题描述解决方案总结

python中的与时间相关的模块应用场景分析

《python中的与时间相关的模块应用场景分析》本文介绍了Python中与时间相关的几个重要模块:`time`、`datetime`、`calendar`、`timeit`、`pytz`和`dateu... 目录1. time 模块2. datetime 模块3. calendar 模块4. timeit

python-nmap实现python利用nmap进行扫描分析

《python-nmap实现python利用nmap进行扫描分析》Nmap是一个非常用的网络/端口扫描工具,如果想将nmap集成进你的工具里,可以使用python-nmap这个python库,它提供了... 目录前言python-nmap的基本使用PortScanner扫描PortScannerAsync异