• 回溯难题（算法村第十八关黄金挑战）

    复原 IP 地址

    93. 复原 IP 地址 - 力扣（LeetCode）

    有效 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 '.' 分隔。

    • 例如："0.1.2.201" 和 "192.168.1.1" 是 有效 IP 地址，但是 "0.011.255.245"、"192.168.1.312" 和 "192.168@1.1" 是 无效 IP 地址。

    给定一个只包含数字的字符串 s ，用以表示一个 IP 地址，返回所有可能的有效 IP 地址，这些地址可以通过在 s 中插入 '.' 来形成。你 不能 重新排序或删除 s 中的任何数字。你可以按 任何 顺序返回答案。

    示例 1：

    输入：s = "25525511135"
输出：["255.255.11.135","255.255.111.35"]

    • 1
    • 2

    示例 2：

    输入：s = "0000"
输出：["0.0.0.0"]

    • 1
    • 2

    示例 3：

    输入：s = "101023"
输出：["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"]

    • 1
    • 2

    提示：

    • 1 <= s.length <= 20
    • s 仅由数字组成

    解

    IP地址只有四段，所以将分割的段数 == 4作为终止条件。考虑到构造IP地址时还要手动给添加三个小数点，所以我们用变量pointCount来表示小数点数量，pointCount == 3说明字符串分成了4段了。

    List<String> addressList = new ArrayList<>();

public List<String> restoreIpAddresses(String s)
{
    if(s.length() < 4 || s.length() > 12)
        return addressList;

    backTracing(s, 0, 0);
    return addressList;
}

//判断索引在[start,end]之间的字符能否构造有效的IP的地址
public boolean isValid(String s, int start, int end)
{
    //避免数组越界
    if (start > s.length() - 1)
        return false;

    //含有前导零
    if (s.charAt(start) == '0' && start != end)
        return false;

    //四位数及以上
    if (end - start >= 3)
        return false;

    int num = 0;
    for (int i = start; i <= end; i++)
            num = num * 10 + s.charAt(i) - '0';

    return num <= 255;
}

/**
 * @param pointCount  . 的个数
 */
public void backTracing(String s, int startIndex, int pointCount)
{
    //若已经分成四段
    if (pointCount == 3)
    {
        //若最后一段有效，则记录一个有效IP地址
        if (isValid(s, startIndex, s.length() - 1))
            addressList.add(s);

        return;
    }

    //分段不足则继续分
    for (int i = startIndex; i < s.length(); i++)
    {
        if (isValid(s, startIndex, i))
        {
            //用截取、拼接的方法插入 .
            s = s.substring(0, i + 1) + "." + s.substring(i + 1);
            pointCount++;

            //插入 . 后，字符串 s 中下一个数字的索引为 i + 2。
            //不用担心越界，因为 s 的长度也变大了
            backTracing(s, i + 2, pointCount);

            //撤回 .
            s = s.substring(0, i + 1) + s.substring(i + 2);
            pointCount--;
        }
        else //若中间有一段无效，那后面的都不用看了
            break;
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69

    电话号码的字母组合

    17. 电话号码的字母组合 - 力扣（LeetCode）

    给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。

    给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

    img

    示例 1：

    输入：digits = "23"
输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]

    • 1
    • 2

    示例 2：

    输入：digits = ""
输出：[]

    • 1
    • 2

    示例 3：

    输入：digits = "2"
输出：["a","b","c"]

    • 1
    • 2

    提示：

    • 0 <= digits.length <= 4
    • digits[i] 是范围 ['2', '9'] 的一个数字。

    图解思路

    在这里插入图片描述

    代码实现

    List<String> combinationList = new ArrayList<>();
String digits;

//数字到字母的映射
String[] map = {"", "", "abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};

//更高效的字符串拼接类型
StringBuilder combination = new StringBuilder();

public List<String> letterCombinations(String digits)
{
    if(digits.isEmpty())
        return combinationList;

    this.digits = digits;
    backTracing(0);

    return combinationList;
}

/**
 * @param numIndex digits中数字 num 的索引
 */
public void  backTracing(int numIndex)
{
    if (numIndex > digits.length() - 1)
    {
        combinationList.add(combination.toString());
        return;
    }

    //求 num 所映射的字符串
    String str = map[digits.charAt(numIndex) - '0'];

    for (int i = 0; i < str.length(); i++)
    {
        //从 str 中依次选取单个字符
        combination.append(str.charAt(i));
        //从 digits 中选择下一个数字
        backTracing(numIndex + 1);
        //撤销组合中最后一个字符，循环再试（换本层 str 的下一个字符）
        combination.deleteCharAt(combination.length() - 1);
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44

    括号生成

    22. 括号生成 - 力扣（LeetCode）

    数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。

    示例 1：

    输入：n = 3
输出：["((()))","(()())","(())()","()(())","()()()"]

    • 1
    • 2

    示例 2：

    输入：n = 1
输出：["()"]

    • 1
    • 2

    提示：

    • 1 <= n <= 8

    深搜，做减法

    public List<String> generateParenthesis(int n)
{
    //特判
    if (n == 0)
        return null;

    //结果集
    ArrayList<String> res = new ArrayList<>();

    //深搜，找出全部有效括号组合
    DFS(res, n, n, "");

    return res;
}

/**
 * @param res 结果集
 * @param left 左括号还能用几个
 * @param right 右括号还能用几个
 * @param curStr 当前递归所得到的字符串
 */
public static void DFS(List<String> res, int left, int right, String curStr)
{
    //左右括号都用完了；将一种组合添加到结果集
    if (left == 0 && right == 0)
    {
        res.add(curStr);
        return;
    }

    //若左括号剩余数量大于右括号剩余数量，则“剪枝”（不再进行这种错误模式的括号组合）。
    if (left > right)
        return;

    //若还剩余左括号，则使用左括号
    if (left > 0)
        DFS(res, left - 1, right, curStr + "(" );

    //若还剩余右括号，则使用右括号
    if (right > 0)
        DFS(res, left, right - 1, curStr +")" );
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42

    深搜，做加法

    public List<String> generateParenthesis_2(int n)
{
    //特判
    if (n == 0)
        return null;

    //结果集
    ArrayList<String> res = new ArrayList<String>();

    //深搜,寻找全部有效括号组合
    DFS_2(res, 0, 0, "", n);

    return res;
}

/**
 * @param res 结果集
 * @param left 左括号使用了几个
 * @param right 右括号使用使用了几个
 * @param curStr 当前递归所得到的字符串
 * @param n 题目所给的括号生成对数
 */
public static void DFS_2(List<String> res, int left, int right, String curStr, int n)
{
    //递归终止；将一种组合添加到结果集
    if (left == n && right == n)
    {
        res.add(curStr);
        return;
    }

    //若左括号使用数量小于右括号使用数量，则“剪枝”（不再进行这种错误模式的括号组合）
    if (left < right)
        return;

    //若还剩余左括号，则使用左括号
    if (left < n)
        DFS_2(res, left + 1, right, curStr + "(", n);

    //若还剩余右括号，则使用右括号
    if (right < n)
        DFS_2(res, left, right + 1, curStr +")", n);
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43

    广搜

    class Node
{
    String curStr;
    int left;   //左括号还剩几个没用
    int right; //右括号还剩几个没用

    public Node(String curStr, int left, int right)
    {
        this.curStr = curStr;
        this.left = left;
        this.right = right;
    }
}

public List<String> generateParenthesis_3(int n)
{
    //特判，否则n==0时下面的算法会返回""
    if(n == 0)
        return null;

    //结果集
    ArrayList<String> res = new ArrayList<String>();

    ArrayDeque<Node> queue = new ArrayDeque<>();
    //初始结点入队
    queue.offer(new Node("", n, n));

    while (!queue.isEmpty())
    {
        //队头元素出队
        Node curNode = queue.poll();

        //生成了一组有效括号
        if(curNode.left == 0 && curNode.right == 0)
            res.add(curNode.curStr);

        //若还剩余左括号，则使用左括号
        if (curNode.left > 0)
            queue.offer(new Node(curNode.curStr + "(", curNode.left - 1, curNode.right));

        //若还剩余右括号，且左括号剩余数少于右括号剩余数，则使用右括号
        if (curNode.right > 0 && curNode.left < curNode.right)
            queue.offer(new Node(curNode.curStr + ")", curNode.left, curNode.right - 1));
    }

    return res;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
  • 相关阅读:
    Google测试之道读后感
    2023 年江西省职业院校技能大赛软件测试（高职组）赛项样题
    华为云GaussDB打造金融行业坚实数据底座，共创数字金融新未来
    事务的隔离级别
    LTE(4G) RRC 移动性
    【Flutter】Android原生WebView（非Flutter WebView）与FlutterWeb交互
    设计模式---单例模式
    【Token】JWT使用Token进行登录
    flutter 中最详细的继承，多态，接口讲解
    轻量化动态编译库 Natasha v8.0 正式发布！
  • 原文地址：https://blog.csdn.net/cjj2543107638/article/details/136430837