代码随想录-Day28

93. 复原 IP 地址

有效 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”]
示例 2:

输入:s = “0000”
输出:[“0.0.0.0”]
示例 3:

输入:s = “101023”
输出:[“1.0.10.23”,“1.0.102.3”,“10.1.0.23”,“10.10.2.3”,“101.0.2.3”]

class Solution {
    static final int SEG_COUNT = 4;
    List<String> ans = new ArrayList<String>();
    int[] segments = new int[SEG_COUNT];

    public List<String> restoreIpAddresses(String s) {
        segments = new int[SEG_COUNT];
        dfs(s, 0, 0);
        return ans;
    }

    public void dfs(String s, int segId, int segStart) {
        // 如果找到了 4 段 IP 地址并且遍历完了字符串,那么就是一种答案
        if (segId == SEG_COUNT) {
            if (segStart == s.length()) {
                StringBuffer ipAddr = new StringBuffer();
                for (int i = 0; i < SEG_COUNT; ++i) {
                    ipAddr.append(segments[i]);
                    if (i != SEG_COUNT - 1) {
                        ipAddr.append('.');
                    }
                }
                ans.add(ipAddr.toString());
            }
            return;
        }

        // 如果还没有找到 4 段 IP 地址就已经遍历完了字符串,那么提前回溯
        if (segStart == s.length()) {
            return;
        }

        // 由于不能有前导零,如果当前数字为 0,那么这一段 IP 地址只能为 0
        if (s.charAt(segStart) == '0') {
            segments[segId] = 0;
            dfs(s, segId + 1, segStart + 1);
            return;
        }

        // 一般情况,枚举每一种可能性并递归
        int addr = 0;
        for (int segEnd = segStart; segEnd < s.length(); ++segEnd) {
            addr = addr * 10 + (s.charAt(segEnd) - '0');
            if (addr > 0 && addr <= 0xFF) {
                segments[segId] = addr;
                dfs(s, segId + 1, segEnd + 1);
            } else {
                break;
            }
        }
    }
}

这段代码是一个 Java 函数,用于解决“恢复 IP 地址”问题。给定一个字符串 s,它只包含数字字符,该函数尝试恢复它并返回所有可能的有效 IPv4 地址。IPv4 地址由四个整数(每个整数位于 0 到 255 之间,包括 0 和 255)组成,中间用 ‘.’ 分隔。

解决方案概述:

  • 类成员变量:

    • static final int SEG_COUNT = 4;:定义了一个常量,表示 IP 地址的段数。
    • List<String> ans = new ArrayList<String>();:用于存储所有可能的 IP 地址结果。
    • int[] segments = new int[SEG_COUNT];:用于记录当前正在构建的 IP 地址的四段数值。
  • 主要函数:

    • public List<String> restoreIpAddresses(String s):入口函数,初始化 segments 数组,并调用 dfs 函数开始深度优先搜索。
  • dfs 函数 (public void dfs(String s, int segId, int segStart)):

    • 终止条件:
      • 当已经找到 4 段地址 (segId == SEG_COUNT) 并且字符串遍历完 (segStart == s.length()),说明找到了一个有效 IP,将其添加到结果列表 ans 中。
      • 如果没达到 4 段但字符串已经遍历完,直接返回,因为无法构成有效 IP。
    • 特殊处理:
      • 遇到字符 ‘0’ 作为新段的开始,该段只能为 0,直接递归进入下一段。
    • 一般情况遍历:
      • 从当前位置 segStart 开始,逐步尝试形成一个合法的数字(0-255),并递归进入下一段的构建。若形成的数字不合法(超出范围),则停止当前段的扩展,回溯到上一步。

此算法通过深度优先搜索来尝试构建 IP 地址的所有可能组合,同时利用剪枝策略减少无效的搜索路径,比如遇到 ‘0’ 时直接确定该段为 0,以及检查数字是否超出了 IP 地址段的合法范围。

在这段代码中,segments[i] 是一个整数数组,用来保存当前正在构建的 IP 地址的每个段。

详细解释:

  • segments 数组的定义:

    int[] segments = new int[SEG_COUNT];
    

    segments 是一个长度为 4 的数组,因为一个有效的 IP 地址由 4 段组成,每段之间用点(.)隔开。

  • segments 的用途:
    segments 用来临时保存正在递归构建的 IP 地址的每一段。递归过程中,segments 的每个元素将依次保存每一段的值。

  • 递归中的赋值:

    segments[segId] = addr;
    

    在递归函数 dfs 中,每次确定了一段 IP 地址的值后,将该值保存到 segments 中对应的位置。

  • 完整 IP 地址的构建:

    if (segId == SEG_COUNT) {
        if (segStart == s.length()) {
            StringBuffer ipAddr = new StringBuffer();
            for (int i = 0; i < SEG_COUNT; ++i) {
                ipAddr.append(segments[i]);
                if (i != SEG_COUNT - 1) {
                    ipAddr.append('.');
                }
            }
            ans.add(ipAddr.toString());
        }
        return;
    }
    

    当找到 4 段有效的 IP 地址(segId == SEG_COUNT)且已经遍历完字符串时(segStart == s.length()),将 segments 数组中的值拼接成一个完整的 IP 地址字符串,并添加到 ans 列表中。

示例

假设输入字符串 s = "25525511135",在递归的某个阶段,segments 可能会保存如下值:

  • segments[0] = 255
  • segments[1] = 255
  • segments[2] = 111
  • segments[3] = 35

最终 segments 会被构建为 ["255", "255", "111", "35"],并拼接成 IP 地址 "255.255.111.35"

总结

segments 是一个临时存储数组,用来保存当前正在构建的 IP 地址的每个段的值。递归过程中,每确定一个段的值,就将其保存到 segments 中对应的位置,并在找到完整的 4 段有效 IP 地址后,拼接成字符串形式并添加到结果列表 ans 中。

for (int segEnd = segStart; segEnd < s.length(); ++segEnd) {
            addr = addr * 10 + (s.charAt(segEnd) - '0');
            if (addr > 0 && addr <= 0xFF) {
                segments[segId] = addr;
                dfs(s, segId + 1, segEnd + 1);
            } else {
                break;
            }
        }
}

这段代码是 IP 地址分段的核心部分,通过递归构建 IP 地址的每一段。我们逐个字符地构建当前段的数值,并在有效范围内递归地继续处理剩余的字符串。

代码逻辑详细解释

  1. 循环构建当前段的值:

    for (int segEnd = segStart; segEnd < s.length(); ++segEnd) {
        addr = addr * 10 + (s.charAt(segEnd) - '0');
    
    • segEndsegStart 开始,逐个字符地遍历字符串 s
    • addr = addr * 10 + (s.charAt(segEnd) - '0');:通过逐个字符地构建当前段的值。例如,字符串 “255” 会被逐个字符地转换为整数 255。
  2. 检查当前段的值是否有效:

    if (addr > 0 && addr <= 0xFF) {
    
    • 检查构建的当前段 addr 是否在有效范围内,即 1 到 255(0xFF 为十六进制 255)。注意,这里排除了值为 0 的段,因为 IP 地址段不能有前导零(除了单独的 “0”)。
  3. 保存当前段的值并递归:

    segments[segId] = addr;
    dfs(s, segId + 1, segEnd + 1);
    
    • 将当前段的值保存到 segments 数组的 segId 位置。
    • 递归调用 dfs 函数,处理下一个段。新的 segId 加 1,segStart 更新为 segEnd + 1
  4. 提前终止循环:

    } else {
        break;
    }
    
    • 如果当前段的值不在有效范围内,提前终止循环,因为继续添加字符会使得当前段的值更加无效。

示例

假设字符串 s 为 “25525511135”:

  • 开始时 segId = 0segStart = 0
  • 循环构建段值时:
    • segEnd = 0addr = 2
    • segEnd = 1addr = 25
    • segEnd = 2addr = 255(有效,继续递归)

递归调用 dfs

  • 新的 segId = 1segStart = 3,处理剩余字符串 “25511135”。

递归会继续这个过程,最终找到所有可能的 IP 地址。

总结

  • 目的: 逐个字符地构建当前段的数值,并在有效范围内递归处理剩余字符串。
  • 细节:
    • 使用 for 循环逐个字符构建段值。
    • 通过 if 语句检查段值是否有效。
    • 保存有效的段值到 segments 数组中。
    • 递归处理下一段。
    • 遇到无效段值时,提前终止循环。

78. 子集

给你一个整数数组 nums ,数组中的元素 互不相同 。返回该数组所有可能的子集(幂集)。

解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
示例 1:

输入:nums = [1,2,3]
输出:[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
示例 2:

输入:nums = [0]
输出:[[],[0]]
在这里插入图片描述

class Solution {
    List<List<Integer>> result = new ArrayList<>();// 存放符合条件结果的集合
    LinkedList<Integer> path = new LinkedList<>();// 用来存放符合条件结果
    public List<List<Integer>> subsets(int[] nums) {
        subsetsHelper(nums, 0);
        return result;
    }

    private void subsetsHelper(int[] nums, int startIndex){
        result.add(new ArrayList<>(path));//「遍历这个树的时候,把所有节点都记录下来,就是要求的子集集合」。
        if (startIndex >= nums.length){ //终止条件可不加
            return;
        }
        for (int i = startIndex; i < nums.length; i++){
            path.add(nums[i]);
            subsetsHelper(nums, i + 1);
            path.removeLast();
        }
    }
}

这段代码是一个 Java 程序,用于实现求解给定整数数组 nums 的所有可能子集(幂集)。子集包括空集和数组本身,且数组中的元素可以无限制重复被选择。程序采用了回溯算法来高效地生成所有子集。

代码解析

  • 类成员变量:

    • List<List<Integer>> result:用于存储所有满足条件的子集结果。
    • LinkedList<Integer> path:用于暂存当前递归路径上的元素,即当前正在构建的子集。
  • 主要方法 subsets(int[] nums):

    • 输入参数:nums,一个整数数组。
    • 此方法首先调用辅助函数 subsetsHelper(nums, 0) 来开始回溯过程。
    • 最终返回结果列表 result,其中包含了 nums 的所有子集。
  • 辅助函数 subsetsHelper(int[] nums, int startIndex):

    • 参数nums 是输入数组,startIndex 表示当前递归层级应开始考虑的数组下标。
    • 终止条件:虽然注释中提到“终止条件可不加”,但实际上递归总是会自然终止,当 startIndex 大于等于数组长度时,递归会自然结束,因为不再有新的元素可以加入子集中。
    • 逻辑
      • 首先,将当前的 path 添加到结果列表 result 中,即使 path 为空,也代表一个有效的子集——空集。
      • 然后,遍历 nums 数组中从 startIndex 开始的每个元素,将当前元素加入到 path 中,然后递归调用 subsetsHelper(nums, i + 1),进入下一层递归继续添加元素。
      • 递归调用返回后,通过 path.removeLast() 移除最后一次添加的元素,回溯到上一层,尝试数组中的下一个元素(或不选择任何元素继续递归),从而构建出所有可能的子集。

示例说明

假设输入数组 nums = [1, 2, 3],该程序将生成以下子集:

  1. 空集 []
  2. [1]
  3. [1, 2]
  4. [1, 2, 3]
  5. [1, 3]
  6. [2]
  7. [2, 3]
  8. [3]

最终,result 将包含这全部 8 个子集。

90. 子集 II

给你一个整数数组 nums ,其中可能包含重复元素,请你返回该数组所有可能的 子集(幂集)。

解集 不能 包含重复的子集。返回的解集中,子集可以按 任意顺序 排列。

示例 1:

输入:nums = [1,2,2]
输出:[[],[1],[1,2],[1,2,2],[2],[2,2]]
示例 2:

输入:nums = [0]
输出:[[],[0]]
在这里插入图片描述

// 使用used数组
class Solution {
   List<List<Integer>> result = new ArrayList<>();// 存放符合条件结果的集合
   LinkedList<Integer> path = new LinkedList<>();// 用来存放符合条件结果
   boolean[] used;
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        if (nums.length == 0){
            result.add(path);
            return result;
        }
        Arrays.sort(nums);
        used = new boolean[nums.length];
        subsetsWithDupHelper(nums, 0);
        return result;
    }
    
    private void subsetsWithDupHelper(int[] nums, int startIndex){
        result.add(new ArrayList<>(path));
        if (startIndex >= nums.length){
            return;
        }
        for (int i = startIndex; i < nums.length; i++){
            if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]){
                continue;
            }
            path.add(nums[i]);
            used[i] = true;
            subsetsWithDupHelper(nums, i + 1);
            path.removeLast();
            used[i] = false;
        }
    }
}

这段代码是对前一个代码段的修改,用于解决含有重复元素的数组子集问题。这里使用了used布尔数组来跟踪每个元素是否在当前子集中被使用过,以避免产生重复的子集。下面是这个修改版代码的解析:

修改点概述

  • 引入了used数组,用于标记数组nums中的元素是否在当前递归路径中已被选用,以处理重复值的问题。
  • 在生成子集之前,先对输入数组nums进行了排序,这是为了确保重复元素相邻,从而便于去重处理。
  • 在递归函数subsetsWithDupHelper中,增加了一个判断条件,用于跳过重复元素的重复使用情况,即如果当前元素与前一个元素相同且前一个元素未被使用过,则跳过本次循环的剩余部分。

代码解析

  • 初始化:在subsetsWithDup方法中,首先检查输入数组是否为空,若为空则直接返回包含空集的结果列表。接着,对数组进行排序,并初始化used数组。

  • 递归逻辑调整

    • 在遍历循环中,新增条件if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) continue;,这行代码的目的是避免重复添加相同的子集。当遇到重复数值且前一个相同数值未被使用时,跳过当前迭代,因为这个情况下的子集已经在上一个相同数值被使用时计算过了。
    • 对于每个遍历到的元素,先将其添加到path中,并标记used[i]true,然后递归调用进入下一层;递归返回后,从path中移除当前元素,并将used[i]重置为false,准备探索下一个元素或结束当前层的循环。

示例说明

假设输入数组 nums = [1, 2, 2],此程序将正确生成不包含重复子集的结果列表,如:

  1. []
  2. [1]
  3. [1, 2]
  4. [1, 2, 2]
  5. [2]
  6. [2, 2]

这样,每个子集都是唯一的,尽管输入数组中有重复的元素。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/694524.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

业务扩张阶段

和之前相比就是服务器的数量增多了 业务系统增多了 每个业务的用户也在增多 采购费用和电费挺多 选课系统一年只用几次&#xff0c;平时不用太浪费服务器的资源&#xff0c;那么怎么才能提高服务器资源的利用率呢 在一个服务器上部署多个不同的业务系统能行吗 不太行&…

TransformerFAM:革新深度学习的新型注意力机制

深度学习领域的一项突破性技术——Transformer架构&#xff0c;已经彻底改变了我们处理序列数据的方式。然而&#xff0c;Transformer在处理长序列数据时面临的二次复杂度问题&#xff0c;限制了其在某些应用场景下的潜力。针对这一挑战&#xff0c;研究者们提出了一种名为Tran…

Qwen2大模型微调入门实战(完整代码)

Qwen2是通义千问团队的开源大语言模型&#xff0c;由阿里云通义实验室研发。以Qwen2作为基座大模型&#xff0c;通过指令微调的方式实现高准确率的文本分类&#xff0c;是学习大语言模型微调的入门任务。 指令微调是一种通过在由&#xff08;指令&#xff0c;输出&#xff09;对…

使用vite从0开始搭建vue项目

使用Vite从0开始创建vue项目 第一步&#xff1a;创建项目目录 mkdir vue-demo -创建目录 cd vue-demo --进入项目 npm init -y --生成package.json文件 第二步&#xff1a;安装vite、typescript--ts、vue、vitejs/plugin-vue--对单文件组件、热重载、生产优化的支持 pnpm…

【Python】探索 One-Class SVM:异常检测的利器

我已经从你的 全世界路过 像一颗流星 划过命运 的天空 很多话忍住了 不能说出口 珍藏在 我的心中 只留下一些回忆 &#x1f3b5; 牛奶咖啡《从你的全世界路过》 在数据科学和机器学习领域&#xff0c;异常检测&#xff08;Anomaly Detection&#xff09;是…

工业通讯现场中关于EtherCAT转TCPIP网关的现场应用

在当今工业自动化的浪潮中&#xff0c;EtherCAT技术以其高效、实时的特性成为了众多制造业的首选。然而&#xff0c;随着工业互联网的发展&#xff0c;对于数据的远程访问和云平台集成的需求日益增长&#xff0c;这就需要将EtherCAT协议转化为更为通用的TCP/IP协议。于是开疆智…

【MMU】——MMU 权限控制

文章目录 权限控制内存访问权限内存类型XN execute neverDomain 权限控制 内存访问权限 内存类型 TEX C B bit 控制信息 XN execute never 不可执行区域&#xff0c;例如设备地址空间通常标记为不可执行区域&#xff0c;如果有指令预取访问了该空间&#xff0c;就会触发指令…

CVE-2022-4230

CVE-2022-4230 漏洞介绍 WP Statistics WordPress 插件13.2.9之前的版本不会转义参数&#xff0c;这可能允许经过身份验证的用户执行 SQL 注入攻击。默认情况下&#xff0c;具有管理选项功能 (admin) 的用户可以使用受影响的功能&#xff0c;但是该插件有一个设置允许低权限用…

快速入门Linux及使用VSCode远程连接Linux服务器

在当前的技术环境中&#xff0c;Linux操作系统因其强大的功能和灵活性而广受欢迎。无论你是开发人员、系统管理员还是技术爱好者&#xff0c;学习Linux都是提升技术技能的重要一步。本文将介绍如何快速入门Linux&#xff0c;并使用Visual Studio Code&#xff08;VSCode&#x…

【RAG入门教程03】Langchian框架-文档加载

Langchain 使用文档加载器从各种来源获取信息并准备处理。这些加载器充当数据连接器&#xff0c;获取信息并将其转换为 Langchain 可以理解的格式。 LangChain 中有几十个文档加载器&#xff0c;可以在这查看https://python.langchain.com/v0.2/docs/integrations/document_lo…

王学岗鸿蒙开发(北向)——————(七、八)ArkUi的各种装饰器

arts包含如下&#xff1a;1&#xff0c;装饰器 &#xff1b;2&#xff0c;组件的描述(build函数)&#xff1b;3&#xff0c;自定义组件(Component修饰的),是可复用的单元&#xff1b;4&#xff0c;系统的组件(鸿蒙官方提供)&#xff1b;等 装饰器的作用:装饰类、变量、方法、结…

著名AI人工智能社会学家唐兴通谈数字社会学网络社会学主要矛盾与数字空间社会网络社会的基本议题与全球海外最新热点与关注社会结构社会分工数字财富数字游民数字经济

如果人工智能解决了一切&#xff0c;人类会做什么&#xff1f; 这个问题的背后是人工智能时代的社会主要矛盾会是什么&#xff1f;那么整个社会的大的分工体系就会围绕主要矛盾开展。 《人工智能社会主要矛盾》 在农业社会&#xff0c;主要矛盾是人口增长和土地资源之间的关…

这家叉车AGV巨头2024年一季度销售4075万~

导语 大家好&#xff0c;我是社长&#xff0c;老K。专注分享智能制造和智能仓储物流等内容。 新书《智能物流系统构成与技术实践》人俱乐部 一、BALYO公司概览 BALYO&#xff0c;这家来自法国的仓储机器人公司&#xff0c;自2006年成立以来&#xff0c;一直致力于为全球客户提供…

LabVIEW 与组态软件在自动化系统中的应用比较与选择

LabVIEW 确实在非标单机设备、测试和测量系统中有着广泛的应用&#xff0c;特别是在科研、教育、实验室和小型自动化设备中表现突出。然而&#xff0c;LabVIEW 也具备一定的扩展能力&#xff0c;可以用于更复杂和大型的自动化系统。以下是对 LabVIEW 与组态软件在不同应用场景中…

嵌入式单片机产品微波炉拆解分享

在厨房电器中,微波炉可以说是最具技术含量的电器,它的工作原理不像其他电器那样一眼就能看个明白,于是拆解了一个微波炉,分析内部电路。 微波炉的结构 微波炉由箱体、磁控管、变压器、高压电容器、高压二极管、散热风扇、转盘装置及一系列控制保护开关组成,大多数微波炉还…

【详细的Kylin使用心得,什么是Kylin?】

&#x1f308;个人主页: 程序员不想敲代码啊 &#x1f3c6;CSDN优质创作者&#xff0c;CSDN实力新星&#xff0c;CSDN博客专家 &#x1f44d;点赞⭐评论⭐收藏 &#x1f91d;希望本文对您有所裨益&#xff0c;如有不足之处&#xff0c;欢迎在评论区提出指正&#xff0c;让我们共…

【JAVASE】面向对象编程综合案例--------模仿电影信息系统

需求&#xff1a; &#xff08;1&#xff09;展示系统中的全部电影&#xff08;每部电影展示&#xff1a;名称、价格&#xff09; &#xff08;2&#xff09;允许用户根据电影编号&#xff08;ID&#xff09;查询出某个电影的详细信息。 目标&#xff1a;使用所学的面向对象…

报表或者BI的价值在哪?这是十几年的问题啦!

对&#xff0c;问题已经十几年了&#xff0c;答案也应该普世都懂了吧&#xff0c;但非常遗憾&#xff0c;答案没有问题普及的广。看似简单&#xff0c;但也难说清楚&#xff0c;不同的人&#xff0c;总会有不同的看法。 为什么要解释这个并不新鲜的问题&#xff1f; 因为有人问…

计网总结☞网络层

.................................................. 思维导图 ........................................................... 【Wan口和Lan口】 WAN口&#xff08;Wide Area Network port&#xff09;&#xff1a; 1)用于连接外部网络&#xff0c;如互联…

Java面向对象-[封装、继承、多态、权限修饰符]

Java面向对象-封装、继承、权限修饰符 一、封装1、案例12、案例2 二、继承1、案例12、总结 三、多态1、案例 四、权限修饰符1、private2、default3、protected4、public 一、封装 1、案例1 package com.msp_oop;public class Girl {private int age;public int getAge() {ret…