当前位置:   article > 正文

力扣 C++|一题多解之动态规划专题(2)

力扣 C++|一题多解之动态规划专题(2)

fe34a1c92c5f489689fd991ff5e0f559.png

动态规划

Dynamic Programming

简写为 DP,是运筹学的一个分支,是求解决策过程最优化的过程。20世纪50年代初,美国数学家贝尔曼(R.Bellman)等人在研究多阶段决策过程的优化问题时,提出了著名的最优化原理,从而创立了动态规划。动态规划的应用极其广泛,包括工程技术、经济、工业生产、军事以及自动化控制等领域,并在背包问题、生产经营问题、资金管理问题、资源分配问题、最短路径问题和复杂系统可靠性问题等中取得了显著的效果。

动态规划算法的基本步骤包括:

  1. 确定状态:确定需要求解的状态,并将其表示为变量。
  2. 确定状态转移方程:根据问题的特定约束条件和目标函数,确定状态之间的转移关系,并将其表示为数学公式。
  3. 初始化:为初始状态赋初值,并将其表示为初始条件。
  4. 递推计算:根据状态转移方程,使用循环依次计算各个状态的解,并将其保存在数组或表中。
  5. 求解最终结果:根据问题的目标,从计算得到的解中得出最终结果。

动态规划算法可以用于解决各种问题,例如最短路径问题、背包问题、最长公共子序列问题等。在实现动态规划算法时,需要根据具体问题的特点进行设计和调整,以确保算法的正确性和效率。

适用条件

任何思想方法都有一定的局限性,超出了特定条件,它就失去了作用。同样,动态规划也并不是万能的。适用动态规划的问题必须满足最优化原理和无后效性。

最优化原理(最优子结构性质)

最优化原理可这样阐述:一个最优化策略具有这样的性质,不论过去状态和决策如何,对前面的决策所形成的状态而言,余下的诸决策必须构成最优策略。简而言之,一个最优化策略的子策略总是最优的。一个问题满足最优化原理又称其具有最优子结构性质 [8] 。

无后效性

将各阶段按照一定的次序排列好之后,对于某个给定的阶段状态,它以前各阶段的状态无法直接影响它未来的决策,而只能通过当前的这个状态。换句话说,每个状态都是过去历史的一个完整总结。这就是无后向性,又称为无后效性 [8] 。

子问题的重叠性

动态规划算法的关键在于解决冗余,这是动态规划算法的根本目的。动态规划实质上是一种以空间换时间的技术,它在实现的过程中,不得不存储产生过程中的各种状态,所以它的空间复杂度要大于其他的算法。选择动态规划算法是因为动态规划算法在空间上可以承受,而搜索算法在时间上却无法承受,所以我们舍空间而取时间。

真题举例(2)

70. 爬楼梯

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢?

注意:给定 n 是一个正整数。

示例 1:

输入: 2
输出: 2
解释: 有两种方法可以爬到楼顶。
        1.  1 阶 + 1 阶
        2.  2 阶

示例 2:

输入: 3
输出: 3
解释: 有三种方法可以爬到楼顶。
        1.  1 阶 + 1 阶 + 1 阶
        2.  1 阶 + 2 阶
        3.  2 阶 + 1 阶

代码1: 

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. class Solution
  4. {
  5. public:
  6. int climbStairs(int n)
  7. {
  8. if (n == 1)
  9. {
  10. return 1;
  11. }
  12. int first = 1;
  13. int second = 2;
  14. for (int i = 3; i <= n; i++)
  15. {
  16. int third = first + second;
  17. first = second;
  18. second = third;
  19. }
  20. return second;
  21. }
  22. };
  23. int main()
  24. {
  25. Solution s;
  26. cout << s.climbStairs(2) << endl;
  27. cout << s.climbStairs(3) << endl;
  28. return 0;
  29. }

代码2:  

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. class Solution
  4. {
  5. public:
  6. int climbStairs(int n)
  7. {
  8. vector<int> res(n + 1, 0);
  9. res[1] = 1;
  10. res[2] = 2;
  11. for (int i = 3; i <= n; i++)
  12. res[i] = res[i - 1] + res[i - 2];
  13. return res[n];
  14. }
  15. };
  16. int main()
  17. {
  18. Solution s;
  19. cout << s.climbStairs(2) << endl;
  20. cout << s.climbStairs(3) << endl;
  21. return 0;
  22. }

代码3:  

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. class Solution
  4. {
  5. public:
  6. int climbStairs(int n)
  7. {
  8. vector<int> s;
  9. s.push_back(1);
  10. s.push_back(2);
  11. if (n == 1)
  12. return 1;
  13. if (n == 2)
  14. return 2;
  15. for (int i = 2; i < n; i++)
  16. {
  17. s.push_back(s[i - 1] + s[i - 2]);
  18. }
  19. return s[n - 1];
  20. }
  21. };
  22. int main()
  23. {
  24. Solution s;
  25. cout << s.climbStairs(2) << endl;
  26. cout << s.climbStairs(3) << endl;
  27. return 0;
  28. }

72. 编辑距离

给你两个单词 word1 和 word2,请你计算出将 word1 转换成 word2 所使用的最少操作数 。

你可以对一个单词进行如下三种操作:

  • 插入一个字符
  • 删除一个字符
  • 替换一个字符

示例 1:

输入:word1 = "horse", word2 = "ros"
输出:3
解释:horse -> rorse (将 'h' 替换为 'r')rorse -> rose (删除 'r')rose -> ros (删除 'e')

示例 2:

输入:word1 = "intention", word2 = "execution"
输出:5
解释:intention -> inention (删除 't')inention -> enention (将 'i' 替换为 'e')enention -> exention (将 'n' 替换为 'x')exention -> exection (将 'n' 替换为 'c')exection -> execution (插入 'u')

提示:

  • 0 <= word1.length, word2.length <= 500
  • word1 和 word2 由小写英文字母组成

代码1:  

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. class Solution
  4. {
  5. public:
  6. int minDistance(string word1, string word2)
  7. {
  8. int m = word1.size(), n = word2.size();
  9. if (m == 0)
  10. return n;
  11. if (n == 0)
  12. return m;
  13. int dp[m][n];
  14. bool w1 = false, w2 = false;
  15. if (word1[0] == word2[0])
  16. {
  17. w1 = true;
  18. w2 = true;
  19. dp[0][0] = 0;
  20. }
  21. else
  22. dp[0][0] = 1;
  23. for (int i = 1; i < m; i++)
  24. {
  25. if (!w1 && word1[i] == word2[0])
  26. {
  27. w1 = true;
  28. dp[i][0] = dp[i - 1][0];
  29. }
  30. else
  31. dp[i][0] = dp[i - 1][0] + 1;
  32. }
  33. for (int j = 1; j < n; j++)
  34. {
  35. if (!w2 && word1[0] == word2[j])
  36. {
  37. w2 = true;
  38. dp[0][j] = dp[0][j - 1];
  39. }
  40. else
  41. dp[0][j] = dp[0][j - 1] + 1;
  42. }
  43. for (int i = 1; i < m; i++)
  44. for (int j = 1; j < n; j++)
  45. if (word1[i] == word2[j])
  46. dp[i][j] = min(min(dp[i][j - 1], dp[i - 1][j]) + 1, dp[i - 1][j - 1]);
  47. else
  48. dp[i][j] = min(min(dp[i][j - 1], dp[i - 1][j]), dp[i - 1][j - 1]) + 1;
  49. return dp[m - 1][n - 1];
  50. }
  51. };
  52. int main()
  53. {
  54. Solution s;
  55. string word1 = "horse", word2 = "ros";
  56. cout << s.minDistance(word1, word2) << endl;
  57. word1 = "intention", word2 = "execution";
  58. cout << s.minDistance(word1, word2) << endl;
  59. return 0;
  60. }

代码2:  

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. class Solution
  4. {
  5. public:
  6. int minDistance(string word1, string word2)
  7. {
  8. int n = word1.size();
  9. int m = word2.size();
  10. if (n * m == 0)
  11. {
  12. return n + m;
  13. }
  14. int d[n + 1][m + 1];
  15. for (int i = 0; i < n + 1; ++i)
  16. {
  17. d[i][0] = i;
  18. }
  19. for (int i = 0; i < m + 1; ++i)
  20. {
  21. d[0][i] = i;
  22. }
  23. for (int i = 1; i < n + 1; ++i)
  24. {
  25. for (int j = 1; j < m + 1; ++j)
  26. {
  27. int left = d[i - 1][j] + 1;
  28. int down = d[i][j - 1] + 1;
  29. int left_down = d[i - 1][j - 1];
  30. if (word1[i - 1] != word2[j - 1])
  31. {
  32. left_down += 1;
  33. }
  34. d[i][j] = min(left, min(down, left_down));
  35. }
  36. }
  37. return d[n][m];
  38. }
  39. };
  40. int main()
  41. {
  42. Solution s;
  43. string word1 = "horse", word2 = "ros";
  44. cout << s.minDistance(word1, word2) << endl;
  45. word1 = "intention", word2 = "execution";
  46. cout << s.minDistance(word1, word2) << endl;
  47. return 0;
  48. }

代码3:  

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. class Solution
  4. {
  5. public:
  6. int minDistance(string word1, string word2)
  7. {
  8. int m = word1.size(), n = word2.size();
  9. vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
  10. for (int i = 1; i <= n; ++i)
  11. dp[0][i] = dp[0][i - 1] + 1;
  12. for (int i = 1; i <= m; ++i)
  13. dp[i][0] = dp[i - 1][0] + 1;
  14. for (int i = 1; i <= m; ++i)
  15. {
  16. for (int j = 1; j <= n; ++j)
  17. {
  18. if (word1[i - 1] == word2[j - 1])
  19. dp[i][j] = dp[i - 1][j - 1];
  20. else
  21. dp[i][j] = min(min(dp[i - 1][j - 1], dp[i - 1][j]), dp[i][j - 1]) + 1;
  22. }
  23. }
  24. return dp[m][n];
  25. }
  26. };
  27. int main()
  28. {
  29. Solution s;
  30. string word1 = "horse", word2 = "ros";
  31. cout << s.minDistance(word1, word2) << endl;
  32. word1 = "intention", word2 = "execution";
  33. cout << s.minDistance(word1, word2) << endl;
  34. return 0;
  35. }

代码4:  

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. class Solution {
  4. public:
  5. int minDistance(string word1, string word2) {
  6. int len1 = word1.size();
  7. int len2 = word2.size();
  8. int **dp = new int *[len1 + 1];
  9. for (int i = 0; i < len1 + 1; i++)
  10. dp[i] = new int[len2 + 1];
  11. for (int i = 0; i < len1 + 1; i++)
  12. dp[i][0] = i;
  13. for (int i = 0; i < len2 + 1; i++)
  14. dp[0][i] = i;
  15. for (int i = 1; i < len1 + 1; i++) {
  16. for (int j = 1; j < len2 + 1; j++) {
  17. if (word1[i - 1] == word2[j - 1])
  18. dp[i][j] = dp[i - 1][j - 1];
  19. else
  20. dp[i][j] = (min(dp[i - 1][j - 1], min(dp[i - 1][j], dp[i][j - 1])) + 1);
  21. }
  22. }
  23. int res = dp[len1][len2];
  24. for (int i = 0; i < len1 + 1; i++)
  25. delete[] dp[i];
  26. delete[] dp;
  27. return res;
  28. }
  29. };
  30. int main()
  31. {
  32. Solution s;
  33. string word1 = "horse", word2 = "ros";
  34. cout << s.minDistance(word1, word2) << endl;
  35. word1 = "intention", word2 = "execution";
  36. cout << s.minDistance(word1, word2) << endl;
  37. return 0;
  38. }

85. 最大矩形

给定一个仅包含 0 和 1 、大小为 rows x cols 的二维二进制矩阵,找出只包含 1 的最大矩形,并返回其面积。

示例 1:

输入:matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
输出:6
解释:最大矩形如上图所示。

示例 2:

输入:matrix = []
输出:0

示例 3:

输入:matrix = [["0"]]
输出:0

示例 4:

输入:matrix = [["1"]]
输出:1

示例 5:

输入:matrix = [["0","0"]]
输出:0

提示:

  • rows == matrix.length
  • cols == matrix[0].length
  • 0 <= row, cols <= 200
  • matrix[i][j] 为 '0' 或 '1'

代码1: 

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. class Solution
  4. {
  5. public:
  6. int maximalRectangle(vector<vector<char>> &matrix)
  7. {
  8. if (matrix.size() == 0)
  9. {
  10. return 0;
  11. }
  12. int maxarea = 0;
  13. int dp[matrix.size()][matrix[0].size()];
  14. memset(dp, 0, sizeof(dp));
  15. for (int i = 0; i < matrix.size(); ++i)
  16. {
  17. for (int j = 0; j < matrix[0].size(); ++j)
  18. {
  19. if (matrix[i][j] == '1')
  20. {
  21. dp[i][j] = j == 0 ? 1 : dp[i][j - 1] + 1;
  22. int width = dp[i][j];
  23. for (int k = i; k >= 0; k--)
  24. {
  25. width = min(width, dp[k][j]);
  26. maxarea = max(maxarea, width * (i - k + 1));
  27. }
  28. }
  29. }
  30. }
  31. return maxarea;
  32. }
  33. };
  34. int main()
  35. {
  36. Solution s;
  37. vector<vector<char>> matrix = {
  38. {'1','0','1','0','0'},
  39. {'1','0','1','1','1'},
  40. {'1','1','1','1','1'},
  41. {'1','0','0','1','0'}};
  42. cout << s.maximalRectangle(matrix) << endl;
  43. matrix = {};
  44. cout << s.maximalRectangle(matrix) << endl;
  45. matrix = {{'0'}};
  46. cout << s.maximalRectangle(matrix) << endl;
  47. matrix = {{'1'}};
  48. cout << s.maximalRectangle(matrix) << endl;
  49. matrix = {{'0','0'}};
  50. cout << s.maximalRectangle(matrix) << endl;
  51. return 0;
  52. }

代码2:  

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. class Solution
  4. {
  5. public:
  6. int maximalRectangle(vector<vector<char>> &matrix)
  7. {
  8. int res = 0;
  9. vector<int> height;
  10. for (int i = 0; i < matrix.size(); ++i)
  11. {
  12. height.resize(matrix[i].size());
  13. for (int j = 0; j < matrix[i].size(); ++j)
  14. {
  15. height[j] = matrix[i][j] == '0' ? 0 : (1 + height[j]);
  16. }
  17. res = max(res, largestRectangleArea(height));
  18. }
  19. return res;
  20. }
  21. int largestRectangleArea(vector<int> &heights)
  22. {
  23. if (heights.empty())
  24. return 0;
  25. stack<int> st;
  26. heights.push_back(0);
  27. int res0 = 0;
  28. for (int i = 0; i < heights.size(); i++)
  29. {
  30. while (!st.empty() && heights[i] < heights[st.top()])
  31. {
  32. int curHeight = heights[st.top()];
  33. st.pop();
  34. int width = st.empty() ? i : i - st.top() - 1;
  35. if (width * curHeight > res0)
  36. res0 = width * curHeight;
  37. }
  38. st.push(i);
  39. }
  40. return res0;
  41. }
  42. };
  43. int main()
  44. {
  45. Solution s;
  46. vector<vector<char>> matrix = {
  47. {'1','0','1','0','0'},
  48. {'1','0','1','1','1'},
  49. {'1','1','1','1','1'},
  50. {'1','0','0','1','0'}};
  51. cout << s.maximalRectangle(matrix) << endl;
  52. matrix = {};
  53. cout << s.maximalRectangle(matrix) << endl;
  54. matrix = {{'0'}};
  55. cout << s.maximalRectangle(matrix) << endl;
  56. matrix = {{'1'}};
  57. cout << s.maximalRectangle(matrix) << endl;
  58. matrix = {{'0','0'}};
  59. cout << s.maximalRectangle(matrix) << endl;
  60. return 0;
  61. }

代码3:  

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. class Solution
  4. {
  5. public:
  6. int largestRectangleArea(vector<int> &heights)
  7. {
  8. stack<int> h;
  9. heights.push_back(0);
  10. int ans = 0, hsize = heights.size();
  11. for (int i = 0; i < hsize; i++)
  12. {
  13. while (!h.empty() && heights[h.top()] > heights[i])
  14. {
  15. int top = h.top();
  16. h.pop();
  17. ans = max(ans, heights[top] * (h.empty() ? i : (i - h.top())));
  18. }
  19. h.push(i);
  20. }
  21. return ans;
  22. }
  23. int maximalRectangle(vector<vector<char>> &matrix)
  24. {
  25. if (matrix.empty())
  26. return 0;
  27. int n = matrix.size(), m = matrix[0].size(), ans = 0;
  28. vector<vector<int>> num(n, vector<int>(m, 0));
  29. for (int j = 0; j < m; j++)
  30. {
  31. num[0][j] = (matrix[0][j] == '0') ? 0 : 1;
  32. for (int i = 1; i < n; i++)
  33. num[i][j] = (matrix[i][j] == '0') ? 0 : num[i - 1][j] + 1;
  34. }
  35. for (int i = 0; i < n; i++)
  36. {
  37. int area = largestRectangleArea(num[i]);
  38. ans = max(ans, area);
  39. }
  40. return ans;
  41. }
  42. };
  43. int main()
  44. {
  45. Solution s;
  46. vector<vector<char>> matrix = {
  47. {'1','0','1','0','0'},
  48. {'1','0','1','1','1'},
  49. {'1','1','1','1','1'},
  50. {'1','0','0','1','0'}};
  51. cout << s.maximalRectangle(matrix) << endl;
  52. matrix = {};
  53. cout << s.maximalRectangle(matrix) << endl;
  54. matrix = {{'0'}};
  55. cout << s.maximalRectangle(matrix) << endl;
  56. matrix = {{'1'}};
  57. cout << s.maximalRectangle(matrix) << endl;
  58. matrix = {{'0','0'}};
  59. cout << s.maximalRectangle(matrix) << endl;
  60. return 0;
  61. }

87. 扰乱字符串

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

  1. 如果字符串的长度为 1 ,算法停止
  2. 如果字符串的长度 > 1 ,执行下述步骤:
    • 在一个随机下标处将字符串分割成两个非空的子字符串。即,如果已知字符串 s ,则可以将其分成两个子字符串 x 和 y ,且满足 s = x + y 。
    • 随机 决定是要「交换两个子字符串」还是要「保持这两个子字符串的顺序不变」。即,在执行这一步骤之后,s 可能是 s = x + y 或者 s = y + x 。
    • 在 x 和 y 这两个子字符串上继续从步骤 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
  • s1 和 s2 由小写英文字母组成

代码1:  

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. class Solution
  4. {
  5. public:
  6. bool isScramble(string s1, string s2)
  7. {
  8. if (s1.size() != s2.size())
  9. return false;
  10. if (s1 == s2)
  11. return true;
  12. vector<int> hash(26, 0);
  13. for (int i = 0; i < s1.size(); i++)
  14. hash.at(s1[i] - 'a')++;
  15. for (int j = 0; j < s2.size(); j++)
  16. hash.at(s2[j] - 'a')--;
  17. for (int k = 0; k < 26; k++)
  18. {
  19. if (hash.at(k) != 0)
  20. return false;
  21. }
  22. for (int i = 1; i < s1.size(); i++)
  23. {
  24. if (
  25. (isScramble(s1.substr(0, i), s2.substr(0, i)) && isScramble(s1.substr(i, s1.size() - i), s2.substr(i, s1.size() - i))) || (isScramble(s1.substr(0, i), s2.substr(s1.size() - i)) && isScramble(s1.substr(i), s2.substr(0, s1.size() - i))))
  26. return true;
  27. }
  28. return false;
  29. }
  30. };
  31. int main()
  32. {
  33. Solution s;
  34. cout << s.isScramble("great", "rgeat") << endl;
  35. cout << s.isScramble("abcde", "caebd") << endl;
  36. cout << s.isScramble("a", "a") << endl;
  37. return 0;
  38. }

代码2:  

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. class Solution
  4. {
  5. public:
  6. bool isScramble(string s1, string s2)
  7. {
  8. int n1 = s1.length(), n2 = s2.length();
  9. if (n1 != n2)
  10. return false;
  11. vector<vector<vector<bool>>> dp(n1 + 1, vector<vector<bool>>(n1 + 1, vector<bool>(n1 + 1, false)));
  12. int i, j, k;
  13. for (i = 1; i <= n1; i++)
  14. {
  15. for (j = 1; j <= n1; j++)
  16. {
  17. dp[i][j][1] = (s1[i - 1] == s2[j - 1]);
  18. }
  19. }
  20. for (int len = 2; len <= n1; len++)
  21. {
  22. for (i = 1; i <= n1 && i + len <= n1 + 1; i++)
  23. {
  24. for (j = 1; j <= n1 && j + len <= n1 + 1; j++)
  25. {
  26. for (k = 1; k < len; k++)
  27. {
  28. if (dp[i][j][k] && dp[i + k][j + k][len - k])
  29. {
  30. dp[i][j][len] = true;
  31. break;
  32. }
  33. if (dp[i][j + len - k][k] && dp[i + k][j][len - k])
  34. {
  35. dp[i][j][len] = true;
  36. break;
  37. }
  38. }
  39. }
  40. }
  41. }
  42. return dp[1][1][n1];
  43. }
  44. };
  45. int main()
  46. {
  47. Solution s;
  48. cout << s.isScramble("great", "rgeat") << endl;
  49. cout << s.isScramble("abcde", "caebd") << endl;
  50. cout << s.isScramble("a", "a") << endl;
  51. return 0;
  52. }

代码3:  

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. class Solution
  4. {
  5. public:
  6. bool isScramble(string s1, string s2)
  7. {
  8. if (s1.size() != s2.size())
  9. return false;
  10. if (s1 == s2)
  11. return true;
  12. string str1 = s1, str2 = s2;
  13. sort(str1.begin(), str1.end());
  14. sort(str2.begin(), str2.end());
  15. if (str1 != str2)
  16. return false;
  17. for (int i = 1; i < s1.size(); ++i)
  18. {
  19. string s11 = s1.substr(0, i);
  20. string s12 = s1.substr(i);
  21. string s21 = s2.substr(0, i);
  22. string s22 = s2.substr(i);
  23. if (isScramble(s11, s21) && isScramble(s12, s22))
  24. return true;
  25. s21 = s2.substr(s2.size() - i);
  26. s22 = s2.substr(0, s2.size() - i);
  27. if (isScramble(s11, s21) && isScramble(s12, s22))
  28. return true;
  29. }
  30. return false;
  31. }
  32. };
  33. int main()
  34. {
  35. Solution s;
  36. cout << s.isScramble("great", "rgeat") << endl;
  37. cout << s.isScramble("abcde", "caebd") << endl;
  38. cout << s.isScramble("a", "a") << endl;
  39. return 0;
  40. }

91. 解码方法

一条包含字母 A-Z 的消息通过以下映射进行了 编码 :

'A' -> 1'B' -> 2...'Z' -> 26

要 解码 已编码的消息,所有数字必须基于上述映射的方法,反向映射回字母(可能有多种方法)。例如,"11106" 可以映射为:

  • "AAJF" ,将消息分组为 (1 1 10 6)
  • "KJF" ,将消息分组为 (11 10 6)

注意,消息不能分组为  (1 11 06) ,因为 "06" 不能映射为 "F" ,这是由于 "6" 和 "06" 在映射中并不等价。

给你一个只含数字的 非空 字符串 s ,请计算并返回 解码 方法的 总数 。

题目数据保证答案肯定是一个 32 位 的整数。

示例 1:

输入:s = "12"
输出:2
解释:它可以解码为 "AB"(1 2)或者 "L"(12)。

示例 2:

输入:s = "226"
输出:3
解释:它可以解码为 "BZ" (2 26), "VF" (22 6), 或者 "BBF" (2 2 6) 。

示例 3:

输入:s = "0"
输出:0
解释:没有字符映射到以 0 开头的数字。含有 0 的有效映射是 'J' -> "10" 和 'T'-> "20" 。由于没有字符,因此没有有效的方法对此进行解码,因为所有数字都需要映射。

示例 4:

输入:s = "06"
输出:0
解释:"06" 不能映射到 "F" ,因为字符串含有前导 0("6" 和 "06" 在映射中并不等价)。

提示:

  • 1 <= s.length <= 100
  • s 只包含数字,并且可能包含前导零。

代码1: 

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. class Solution
  4. {
  5. public:
  6. int numDecodings(string s)
  7. {
  8. vector<int> nums(s.size());
  9. if (s[0] == '0')
  10. {
  11. return 0;
  12. }
  13. nums[0] = 1;
  14. if (s.size() > 1)
  15. {
  16. if (s[1] != '0')
  17. {
  18. nums[1] += 1;
  19. }
  20. if ((s[0] - '0') * 10 + (s[1] - '0') <= 26)
  21. {
  22. nums[1] += 1;
  23. }
  24. }
  25. for (int i = 2; i < s.size(); i++)
  26. {
  27. if (s[i] != '0')
  28. {
  29. nums[i] += nums[i - 1];
  30. }
  31. if (s[i - 1] != '0' && ((s[i - 1] - '0') * 10 + (s[i] - '0') <= 26))
  32. {
  33. nums[i] += nums[i - 2];
  34. }
  35. }
  36. return nums[s.size() - 1];
  37. }
  38. };
  39. int main()
  40. {
  41. Solution s;
  42. cout << s.numDecodings("12") << endl;
  43. cout << s.numDecodings("226") << endl;
  44. cout << s.numDecodings("0") << endl;
  45. cout << s.numDecodings("06") << endl;
  46. return 0;
  47. }

代码2:  

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. class Solution
  4. {
  5. public:
  6. int numDecodings(string s)
  7. {
  8. int n = s.size();
  9. if (s.empty())
  10. return 0;
  11. if (s[0] == '0')
  12. return 0;
  13. vector<int> info(n + 1, 0);
  14. info[0] = 1;
  15. info[1] = 1;
  16. for (int i = 2; i < n + 1; ++i)
  17. {
  18. if (s[i - 1] != '0')
  19. info[i] += info[i - 1];
  20. if (s.substr(i - 2, 2) <= "26" && s.substr(i - 2, 2) >= "10")
  21. info[i] += info[i - 2];
  22. }
  23. return info[n];
  24. }
  25. };
  26. int main()
  27. {
  28. Solution s;
  29. cout << s.numDecodings("12") << endl;
  30. cout << s.numDecodings("226") << endl;
  31. cout << s.numDecodings("0") << endl;
  32. cout << s.numDecodings("06") << endl;
  33. return 0;
  34. }

代码3:  

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. class Solution
  4. {
  5. public:
  6. int dp(string &s, int i, int j)
  7. {
  8. int n = j - i + 1;
  9. if (n == 0)
  10. return 0;
  11. if (n == 1)
  12. return s[i] == '0' ? 0 : 1;
  13. if (n == 2)
  14. {
  15. if (s[i] == '0')
  16. return 0;
  17. if (s[i] > '2')
  18. return s[j] == '0' ? 0 : 1;
  19. if (s[i] == '2' && s[j] > '6')
  20. return 1;
  21. if (s[j] == '0')
  22. return 1;
  23. return 2;
  24. }
  25. if (s[i] > '2')
  26. return dp(s, i + 1, j);
  27. if (s[i] == '2')
  28. {
  29. if (s[i + 1] == '0')
  30. return dp(s, i + 2, j);
  31. else if (s[i + 1] < '7')
  32. return dp(s, i + 1, j) + dp(s, i + 2, j);
  33. else
  34. return dp(s, i + 1, j);
  35. }
  36. if (s[i] == '0')
  37. return 0;
  38. if (s[i + 1] == '0')
  39. return dp(s, i + 2, j);
  40. return dp(s, i + 1, j) + dp(s, i + 2, j);
  41. }
  42. int numDecodings(string s)
  43. {
  44. return dp(s, 0, s.size() - 1);
  45. }
  46. };
  47. int main()
  48. {
  49. Solution s;
  50. cout << s.numDecodings("12") << endl;
  51. cout << s.numDecodings("226") << endl;
  52. cout << s.numDecodings("0") << endl;
  53. cout << s.numDecodings("06") << endl;
  54. return 0;
  55. }

代码4:  

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. class Solution {
  4. public:
  5. int numDecodings(string s) {
  6. int n = s.size();
  7. vector<int> f(n + 1);
  8. f[0] = 1;
  9. for (int i = 1; i <= n; ++i) {
  10. if (s[i - 1] != '0') {
  11. f[i] += f[i - 1];
  12. }
  13. if (i > 1 && s[i - 2] != '0' && ((s[i - 2] - '0') * 10 + (s[i - 1] - '0') <= 26)) {
  14. f[i] += f[i - 2];
  15. }
  16. }
  17. return f[n];
  18. }
  19. };
  20. int main()
  21. {
  22. Solution s;
  23. cout << s.numDecodings("12") << endl;
  24. cout << s.numDecodings("226") << endl;
  25. cout << s.numDecodings("0") << endl;
  26. cout << s.numDecodings("06") << endl;
  27. return 0;
  28. }

代码5:  

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. class Solution
  4. {
  5. public:
  6. int numDecodings(string s)
  7. {
  8. if (s.empty() || s[0] == '0')
  9. return 0;
  10. vector<int> dp(s.size() + 1, 0);
  11. dp[0] = 1;
  12. for (int i = 1; i < dp.size(); ++i)
  13. {
  14. dp[i] = (s[i - 1] == '0') ? 0 : dp[i - 1];
  15. if (i > 1 && (s[i - 2] == '1' || (s[i - 2] >= '2' && s[i - 1] <= '6')))
  16. dp[i] += dp[i - 2];
  17. }
  18. return dp[s.size()];
  19. }
  20. };
  21. int main()
  22. {
  23. Solution s;
  24. cout << s.numDecodings("12") << endl;
  25. cout << s.numDecodings("226") << endl;
  26. cout << s.numDecodings("0") << endl;
  27. cout << s.numDecodings("06") << endl;
  28. return 0;
  29. }

代码6:  

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. class Solution
  4. {
  5. public:
  6. int numDecodings(string s) {
  7. if (s.empty() || s[0] == '0') {
  8. return 0;
  9. }
  10. vector<int> dp(s.size() + 1, 1);
  11. for (int i = 2; i < dp.size(); ++i){
  12. dp[i] = ((s[i-1] == '0') ? 0 : dp[i-1]);
  13. if (s[i-2] == '1' || (s[i-2] == '2' && s[i-1] <= '6')){
  14. dp[i] += dp[i-2];
  15. }
  16. }
  17. return dp.back();
  18. }
  19. };
  20. int main()
  21. {
  22. Solution s;
  23. cout << s.numDecodings("12") << endl;
  24. cout << s.numDecodings("226") << endl;
  25. cout << s.numDecodings("0") << endl;
  26. cout << s.numDecodings("06") << endl;
  27. return 0;
  28. }

前:​https://hannyang.blog.csdn.net/article/details/129287197​

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/码创造者/article/detail/804981
推荐阅读
相关标签
  

闽ICP备14008679号