如何让百度k掉网站,北京网址,江苏专业网站制作公司,wordpress 多媒体管理93. 复原 IP 地址--分割
题目
有效 IP 地址 正好由四个整数#xff08;每个整数位于 0 到 255 之间组成#xff0c;且不能含有前导 0#xff09;#xff0c;整数之间用 . 分隔。
例如#xff1a;0.1.2.201 和 192.168.1.1 是 有效 IP 地址每个整数位于 0 到 255 之间组成且不能含有前导 0整数之间用 . 分隔。
例如0.1.2.201 和 192.168.1.1 是 有效 IP 地址但是 0.011.255.245、192.168.1.312 和 192.1681.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]提示
1 s.length 20s 仅由数字组成
题目解析 主函数 restoreIpAddresses 初始化输入字符串 str。调用 backtrace 方法从索引0开始递归生成所有可能的IP地址组合。 回溯函数 backtrace 如果 path存储当前路径的IP段中正好有4段且字符串已完全处理完 将路径拼接成IP地址加入结果列表 result。如果超过4段或字符串处理完但不足4段则直接返回。遍历字符串从当前位置 start 开始切分长度为1到3的子串 检查子串是否是有效IP段用 isValid 函数。如果有效加入路径并继续递归。递归完成后回溯将最后一个加入的段移除。 有效性检查 isValid 检查一个子串是否为合法IP段 长度为1时直接合法。长度大于1时不能以0开头且必须在0~255范围内。
class Solution {ListString result new ArrayList();ListString path new LinkedList();String str;// 递归回溯方法public void backtrace(int start) {// 如果路径已经有4个段并且已经处理完字符串则记录结果if (path.size() 4 start str.length()) {StringBuilder end new StringBuilder();for (int i 0; i path.size(); i) {end.append(path.get(i));if (i ! path.size() - 1) {end.append(.);}}result.add(end.toString());return;}// 如果路径长度大于4段或者已经到达字符串末尾停止递归if (path.size() 4 || start str.length()) {return;}// 尝试从当前位置切分1到3位长度的子字符串for (int i start 1; i Math.min(start 3, str.length()); i) {String segment str.substring(start, i);// 检查段的有效性if (isValid(segment)) {path.add(segment);backtrace(i); // 递归调用处理下一个段path.remove(path.size() - 1); // 回溯去掉当前段}}}// 检查一个字符串是否是有效的IP段private boolean isValid(String segment) {// 不能以0开头的多位数字且必须在0到255之间if (segment.length() 1 segment.charAt(0) 0) {return false;}int num Integer.parseInt(segment);return num 0 num 255;}public ListString restoreIpAddresses(String s) {str s;backtrace(0); // 从字符串的第一个字符开始return result;}
}78. 子集
题目
给你一个整数数组 nums 数组中的元素 互不相同 。返回该数组所有可能的子集幂集。
解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。 示例 1
输入nums [1,2,3]
输出[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]示例 2
输入nums [0]
输出[[],[0]]提示
1 nums.length 10-10 nums[i] 10nums 中的所有元素 互不相同
题目解析
以示例中nums [1,2,3]为例把求子集抽象为树型结构如下 从图中红线部分可以看出遍历这个树的时候把所有节点都记录下来就是要求的子集集合。
这道题就是一道非常标准的回溯法遍历得出结果集的题目
没什么好说的直接看代码
class Solution {ListListInteger resultnew ArrayList();ListIntegerpath new LinkedList();public void backtrace(int[]nums,int start){result.add(new ArrayList(path));if(startnums.length){return;}for(int istart;inums.length;i){path.add(nums[i]);backtrace(nums,i1);path.removeLast();}}public ListListInteger subsets(int[] nums) {backtrace(nums,0);return result;}
}
90. 子集 II
题目
给你一个整数数组 nums 其中可能包含重复元素请你返回该数组所有可能的 子集幂集。
解集 不能 包含重复的子集。返回的解集中子集可以按 任意顺序 排列。 示例 1
输入nums [1,2,2]
输出[[],[1],[1,2],[1,2,2],[2],[2,2]]示例 2
输入nums [0]
输出[[],[0]]
题目解析
大体思路和上一题相同但是多了一个去重的步骤
具体可以看我之前的文章的第二题所用的方法用一个标记数组在树层进行去重
算法训练第二十二天|39. 组合总和 40. 组合总和 II 131. 分割回文串-CSDN博客
Java代码如下
class Solution {ListListInteger resultnew ArrayList();ListIntegerpath new LinkedList();boolean []used;public void backtrace(int[]nums,int start){result.add(new ArrayList(path));if(startnums.length){return;}for(int istart;inums.length;i){if(i0nums[i]nums[i-1]used[i-1]false){continue;}used[i]true;path.add(nums[i]);backtrace(nums,i1);used[i]false;path.removeLast();}}public ListListInteger subsetsWithDup(int[] nums) {usednew boolean[nums.length];Arrays.fill(used,false);Arrays.sort(nums);backtrace(nums,0);return result;}
}
