有没学做早餐的网站,采购管理,百度升级最新版本,高端大气的广告公司名字一、LeetCode93. 复原 IP 地址
题目链接#xff1a;93. 复原 IP 地址
题目描述#xff1a;
有效 IP 地址 正好由四个整数#xff08;每个整数位于 0 到 255 之间组成#xff0c;且不能含有前导 0#xff09;#xff0c;整数之间用 . 分隔。
例如#xff1a;0.…一、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.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 仅由数字组成
算法分析
利用递归纵向遍历字符串中合理的四个子串。
然后for循环遍历每个合理子串0~255的整数不含前导0。
代码如下
class Solution {ListStringresult 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 ListString 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] 10nums 中的所有元素 互不相同
算法分析
每次递归要先收集子集以防漏掉。
然后横向遍历数组将数组的元素依次放入路径递归回溯。
代码如下
class Solution {ListListIntegerresult new ArrayList();//收集所有子集LinkedListIntegerpath 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 ListListInteger 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 {ListListIntegerresult new ArrayList();//存放所有合理子集LinkedListIntegerpath 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 ListListInteger subsetsWithDup(int[] nums) {len nums.length;Arrays.sort(nums);backTravel(nums, 0);return result;}
}
总结
遇到复杂的题时千万不要慌仔细读题一步一步来大胆尝试。
