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。
- 当已经找到 4 段地址 (
- 特殊处理:
- 遇到字符 ‘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 地址的每一段。我们逐个字符地构建当前段的数值,并在有效范围内递归地继续处理剩余的字符串。
代码逻辑详细解释
-
循环构建当前段的值:
for (int segEnd = segStart; segEnd < s.length(); ++segEnd) { addr = addr * 10 + (s.charAt(segEnd) - '0');
segEnd
从segStart
开始,逐个字符地遍历字符串s
。addr = addr * 10 + (s.charAt(segEnd) - '0');
:通过逐个字符地构建当前段的值。例如,字符串 “255” 会被逐个字符地转换为整数 255。
-
检查当前段的值是否有效:
if (addr > 0 && addr <= 0xFF) {
- 检查构建的当前段
addr
是否在有效范围内,即 1 到 255(0xFF 为十六进制 255)。注意,这里排除了值为 0 的段,因为 IP 地址段不能有前导零(除了单独的 “0”)。
- 检查构建的当前段
-
保存当前段的值并递归:
segments[segId] = addr; dfs(s, segId + 1, segEnd + 1);
- 将当前段的值保存到
segments
数组的segId
位置。 - 递归调用
dfs
函数,处理下一个段。新的segId
加 1,segStart
更新为segEnd + 1
。
- 将当前段的值保存到
-
提前终止循环:
} else { break; }
- 如果当前段的值不在有效范围内,提前终止循环,因为继续添加字符会使得当前段的值更加无效。
示例
假设字符串 s
为 “25525511135”:
- 开始时
segId = 0
,segStart = 0
。 - 循环构建段值时:
segEnd = 0
,addr = 2
segEnd = 1
,addr = 25
segEnd = 2
,addr = 255
(有效,继续递归)
递归调用 dfs
:
- 新的
segId = 1
,segStart = 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]
- [1, 2]
- [1, 2, 3]
- [1, 3]
- [2]
- [2, 3]
- [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]
- [1, 2]
- [1, 2, 2]
- [2]
- [2, 2]
这样,每个子集都是唯一的,尽管输入数组中有重复的元素。