前言

题目比较简单，基本都是LC的原题。这个也太不像B站的难度了

数字字符串转化成IP地址

现在有一个只包含数字的字符串，将该字符串转化成IP地址的形式，返回所有可能的情况。

示例1

输入

“25525511135”

输出

["255.255.11.135"255.255.111.35"]

思路与代码

第一题是力扣原题，这个计算器的实现使用了双端队列（Deque）来处理表达式中的括号和符号，遵循了基本的算术规则，而且处理了可能出现的空格。

class Solution {
    public int calculate(String s) {
        Deque<Integer> ops = new LinkedList<Integer>();
        ops.push(1);
        int sign = 1;

        int ret = 0;
        int n = s.length();
        int i = 0;
        while (i < n) {
            if (s.charAt(i) == ' ') {
                i++;
            } else if (s.charAt(i) == '+') {
                sign = ops.peek();
                i++;
            } else if (s.charAt(i) == '-') {
                sign = -ops.peek();
                i++;
            } else if (s.charAt(i) == '(') {
                ops.push(sign);
                i++;
            } else if (s.charAt(i) == ')') {
                ops.pop();
                i++;
            } else {
                long num = 0;
                while (i < n && Character.isDigit(s.charAt(i))) {
                    num = num * 10 + s.charAt(i) - '0';
                    i++;
                }
                ret += sign * num;
            }
        }
        return ret;
    }
}

手搓计算器

给你一个字符串表达式s，请你实现一个基本计算器来计算并返回它的值。注意不允许使用任何将字符串作为数学表达式计算的内置函数，比如 eval0。

运算符仅包含+、1、(、)

示例1

输入

“1+1”

输出

2

思路与代码

IP地址由四个十进制数组成，每个十进制数位于0到255之间，并由三个点分隔。例如，172.16.254.1是一个合法的IP地址。但不所有四个数字都是必需的，例如，0.0.0.0和255.255.255.255都是合法的IP地址。

现在，让我们解释代码的核心思想：

1. 筛选条件：

• 如果s的长度小于4或大于12，直接返回。因为合法的IP地址最短长度是4（0.0.0.0），最长长度是12（255.255.255.255）。

2. 回溯法（Backtracking）：

• 使用递归的方式尝试所有可能的组合来构建IP地址。
• backtrack函数是这个逻辑的核心，它通过添加或删除部分子字符串来尝试构建IP地址。
• 它以s的当前索引idx为参数，并检查每一个可能的IP地址段。

3. IP地址段的检查：

• tmp的长度大于1并且以0开头（例如01，010）是不合法的。
• tmp转换成整数后大于255是不合法的。
• ip的大小超过4（因为IP地址只有四段）是不合法的。
• 使用substring方法从s中提取子字符串tmp。
• 有几个检查以确保子字符串tmp是合法的IP地址段：
• 如果上述检查都通过，那么tmp被添加到ip列表中，并递归地进入下一步。

4. 结束条件：

• 如果我们到达了s的末尾并且ip列表的大小为4，那么我们找到了一个合法的IP地址组合。此时，ip列表的内容被加入到res结果列表中。

5. 其他逻辑：

• getList方法主要用于返回结果。它先调用restoreIpAddresses方法，然后将结果转换为字符串数组，移除所有null项（虽然这里似乎不可能有null项，removeIf(item -> item == null)可能是多余的）。

import java.util.ArrayList;
import java.util.List;

class C {

    List<String> res = new ArrayList<>();
    List<String> ip = new ArrayList<>(7);

    public String[] getList(String s) {
        List<String> strings = restoreIpAddresses(s);
        strings.removeIf(item -> item == null);

        String[] ss= new String[strings.size()];
        for (int i = 0;i<strings.size();i++){
            ss[i] = strings.get(i);
        }
        return ss;
    }


    public List<String> restoreIpAddresses(String s) {
        if (s.length() < 4 || s.length() > 12) {
            return res;
        }
        backtrack(s, 0);
        return res;
    }

    private void backtrack(String s, int idx) {
        if (idx == s.length()) {
            if (ip.size() == 4) {
                res.add(String.join(".", ip));
            }
            return;
        }
        for (int i = idx; i < s.length(); ++i) {
            String tmp = s.substring(idx, i + 1);
            if ((tmp.length() > 1 && tmp.startsWith("0")) || Integer.parseInt(tmp) > 255 || ip.size() >= 4) {
                return;
            }
            ip.add(tmp);
            backtrack(s, i + 1);
            ip.remove(ip.size() - 1);
        }
    }
}