直播网站建设需要什么软件,网站建设系统服务,厦门seo顾问屈兴东,网站建设300元文章目录 93. 复原 IP 地址解题思路源码 78. 子集解题思路源码 90. 子集 II解题思路源码 93. 复原 IP 地址
有效 IP 地址 正好由四个整数#xff08;每个整数位于 0 到 255 之间组成#xff0c;且不能含有前导 0#xff09;#xff0c;整数之间用 ‘.’ 分隔。
例如… 文章目录 93. 复原 IP 地址解题思路源码 78. 子集解题思路源码 90. 子集 II解题思路源码 93. 复原 IP 地址
有效 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 仅由数字组成
解题思路
也是切割问题的一种跟之前的分割回文串差不多思路用回溯搜索法找出所有可能
源码
class Solution {ListString result new ArrayList();public ListString restoreIpAddresses(String s) {if (s.length() 12) return result; backTrack(s, 0, 0);return result;}private void backTrack(String s, int startIndex, int pointNum) {if (pointNum 3) {if (isValid(s,startIndex,s.length()-1)) {result.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); pointNum;backTrack(s, i 2, pointNum);pointNum--;s s.substring(0, i 1) s.substring(i 2);} else {break;}}}private Boolean isValid(String s, int start, int end) {if (start end) {return false;}if (s.charAt(start) 0 start ! end) { return false;}int num 0;for (int i start; i end; i) {if (s.charAt(i) 9 || s.charAt(i) 0) { return false;}num num * 10 (s.charAt(i) - 0);if (num 255) { return false;}}return true;}
}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 中的所有元素 互不相同
解题思路
如果把 子集问题、组合问题、分割问题都抽象为一棵树的话那么组合问题和分割问题都是收集树的叶子节点而子集问题是找树的所有节点
其实子集也是一种组合问题因为它的集合是无序的子集{1,2} 和 子集{2,1}是一样的。
那么既然是无序取过的元素不会重复取写回溯算法的时候for就要从startIndex开始而不是从0开始
求排列问题的时候就要从0开始因为集合是有序的{1, 2} 和{2, 1}是两个集合排列问题我们后续的文章就会讲到的。
以示例中nums [1,2,3]为例把求子集抽象为树型结构如下
源码
class Solution {ListListInteger result new ArrayList();LinkedListInteger path new LinkedList();public ListListInteger 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();}}
}90. 子集 II
给你一个整数数组 nums 其中可能包含重复元素请你返回该数组所有可能的 子集 幂集。
解集 不能 包含重复的子集。返回的解集中子集可以按 任意顺序 排列。
示例 1
输入nums [1,2,2]输出[[],[1],[1,2],[1,2,2],[2],[2,2]]
示例 2
输入nums [0]输出[[],[0]]
提示
1 nums.length 10-10 nums[i] 10
解题思路
这道题目和78.子集区别就是集合里有重复元素了而且求取的子集要去重。
那么关于回溯算法中的去重问题在40.组合总和II 中已经详细讲解过了和本题是一个套路。
源码
class Solution {ListListInteger result new ArrayList();LinkedListInteger path new LinkedList();boolean[] used;public ListListInteger 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;}}
}
