• 力扣--动态规划/深度优先算法/回溯算法93.复原IP地址


    这题主要用了动态规划和回溯算法。

    1. 动态规划数组初始化(DP数组):

      • 首先,创建一个二维数组dp,用于记录字符串中哪些部分是合法的IP地址。
      • 对字符串进行遍历,同时考虑每个可能的IP地址部分(每部分由1到3个字符组成,对应0-255),并根据IPv4地址的规则进行判断,更新dp数组。
    2. 深度优先搜索(DFS):

      • 定义DFS函数,用于递归生成合法的IPv4地址。该函数采用回溯法,遍历每一部分可能的范围,将符合条件的部分添加到当前路径中。
      • 如果已经形成四个部分且遍历到字符串末尾,将路径转为字符串,并加入结果集。
      • 否则,继续递归生成下一部分。
      • 在生成下一部分之前,将路径中的当前部分标记为一个点号('.'),以区分IPv4地址的各个部分。
    3. 返回结果:

      • 在主函数restoreIpAddresses中,首先初始化dp数组,然后调用DFS函数,开始生成合法的IPv4地址。
      • 最后,返回生成的IPv4地址结果集。
    1. class Solution {
    2. vector result; // 存储结果的容器
    3. vector<char> path; // 存储当前路径的容器
    4. // 深度优先搜索函数,用于生成合法的IPv4地址
    5. void dfs(vectorbool>>& dp, string s, int start, int num) {
    6. num++;
    7. if (num >= 5) // 如果已经有四个部分了,结束递归
    8. return;
    9. // 遍历当前部分的可能范围
    10. for (int i = start; i - start <= 2 && i < s.size(); i++) {
    11. if (dp[start][i] == true) {
    12. // 将当前部分加入路径
    13. for (int j = start; j <= i; j++)
    14. path.push_back(s[j]);
    15. // 如果已经是最后一部分且遍历到字符串末尾,将路径转为字符串加入结果集
    16. if (i == s.size() - 1 && num == 4) {
    17. string str;
    18. str.assign(path.begin(), path.end());
    19. result.push_back(str);
    20. }
    21. // 否则,继续递归生成下一部分
    22. else {
    23. path.push_back('.');
    24. dfs(dp, s, i + 1, num);
    25. path.pop_back();
    26. }
    27. // 回溯,将当前部分从路径中移除
    28. for (int j = start; j <= i; j++)
    29. path.pop_back();
    30. }
    31. }
    32. return;
    33. }
    34. public:
    35. // 主函数,生成合法IPv4地址的入口
    36. vector restoreIpAddresses(string s) {
    37. int n = s.size();
    38. // dp数组用于记录字符串中哪些部分是合法的
    39. vectorbool>> dp(n, vector<bool>(n, false));
    40. // 遍历字符串,初始化dp数组
    41. for (int i = 0; i < n; i++) {
    42. for (int j = i; j <= i + 2 && j < n; j++) {
    43. if (i == j)
    44. dp[i][j] = true;
    45. else if (i == j - 1) {
    46. if (s[i] == '0')
    47. dp[i][j] = false;
    48. else
    49. dp[i][j] = true;
    50. } else {
    51. if (s[i] == '0' || s[i] >= '3')
    52. dp[i][j] = false;
    53. else if (s[i] == '1')
    54. dp[i][j] = true;
    55. else {
    56. if (s[i + 1] <= '4' || (s[i + 1] == '5' && s[j] <= '5'))
    57. dp[i][j] = true;
    58. }
    59. }
    60. }
    61. }
    62. // 调用深度优先搜索函数,开始生成合法IPv4地址
    63. dfs(dp, s, 0, 0);
    64. // 返回最终结果
    65. return result;
    66. }
    67. };

  • 相关阅读:
    3、shell脚本观察MySQL进程状态
    C语言实现五子棋游戏
    树递归技巧
    跑在笔记本里的大语言模型 - GPT4All
    Java基于springboot+vue的汽车饰品销售购物商城系统 前后端分离
    新建热门题材跟踪表,捕捉节后主线行情——股票量化分析工具QTYX-V2.7.1
    【刷题记录15】Java工程师丨腾讯面试真题(3)
    23种设计模式
    全网最牛,Pytest自动化测试框架-Fixture测试夹具详解(撸码实例)
    数字电路逻辑 之 逻辑与逻辑运算
  • 原文地址:https://blog.csdn.net/weixin_73865269/article/details/136634504