本文主要是介绍LeetCode算法题解(回溯)|LeetCode93. 复原 IP 地址、LeetCode78. 子集、LeetCode90. 子集 II,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
一、LeetCode93. 复原 IP 地址
题目链接: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"]
提示:
1 <= s.length <= 20
s
仅由数字组成
算法分析:
利用递归纵向遍历字符串中合理的四个子串。
然后for循环遍历每个合理子串(0~255的整数,不含前导0)。
代码如下:
class Solution {List<String>result = new ArrayList<>();//用来存放所有结果int len;//字符串的长度public void backTravel(String a, int index, int count, String path) {if(count == 4) {//整数的个数等于4个时if(path.length() == len + 3) {//该组合的长度等于字符串的长度加上三个'.'的长度时,放入结果集result.add(path);}return;}for(int i = index; i < len; i++) {if(i == index && a.charAt(i) == '0') {//如果字串长度为一且为"0",0单独为一个整数if(path.length() == 0) {count++;backTravel(a, i + 1, count, path + "0");}else {count++;backTravel(a, i + 1, count, path + ".0");}}else if(i - index <= 2 && Integer.parseInt(a.substring(index, i + 1)) <= 255){//如果字串在合理的范围,递归if(path.length() == 0) backTravel(a, i + 1, count + 1, path + a.substring(index, i + 1));else backTravel(a, i + 1, count + 1, path + "." + a.substring(index, i + 1));}else break;//不在合理范围跳出循环}}public List<String> restoreIpAddresses(String s) {len = s.length();backTravel(s, 0, 0,"");return result;}
}
二、LeetCode78. 子集
题目链接: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] <= 10
nums
中的所有元素 互不相同
算法分析:
每次递归要先收集子集,以防漏掉。
然后横向遍历数组,将数组的元素依次放入路径,递归,回溯。
代码如下:
class Solution {List<List<Integer>>result = new ArrayList<>();//收集所有子集LinkedList<Integer>path = new LinkedList<>();//遍历所有子集int len;//数组长度public void backTravel(int[] nums, int index) {result.add(new LinkedList<>(path));//每次递归先收集子集,防止漏掉if(index == len) return;//终止条件for(int i = index; i < len; i++) {//横向遍历数组path.add(nums[i]);backTravel(nums, i + 1);//递归path.removeLast();//回溯}}public List<List<Integer>> subsets(int[] nums) {len = nums.length;backTravel(nums, 0);return result;}
}
三、LeetCode90. 子集 II
题目链接: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
算法分析:
这道题的做法跟上道题很类似,只不过为了避免重复的子集出现,我们需要先对数组进行排序,让相同的元素放在一起,然后再遍历元素的时候进行枝剪(每层递归处理到相同元素时,只处理一次,避免相同元素出现在同一位置从而出现重复)。
代码如下:
class Solution {List<List<Integer>>result = new ArrayList<>();//存放所有合理子集LinkedList<Integer>path = new LinkedList<>();//搜索所有合理子集int len;public void backTravel(int[] nums, int index) {result.add(new LinkedList<>(path));//先放子集if(index == len) return;for(int i = index; i < len; i++) {if(i > index && nums[i] == nums[i - 1]) continue;//枝剪相同元素出现在同一位置path.add(nums[i]);backTravel(nums, i + 1);path.removeLast();}}public List<List<Integer>> subsetsWithDup(int[] nums) {len = nums.length;Arrays.sort(nums);backTravel(nums, 0);return result;}
}
总结
遇到复杂的题时千万不要慌,仔细读题,一步一步来,大胆尝试。
这篇关于LeetCode算法题解(回溯)|LeetCode93. 复原 IP 地址、LeetCode78. 子集、LeetCode90. 子集 II的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!