网站开发属于什么费用,在线建设网站制作,扬州专业手机网站开发,网站要做几个备案93. 复原IP地址
题目描述
给定一个只包含数字的字符串 s#xff0c;复原它并返回所有可能的有效 IP 地址格式。
一个有效的 IP 地址 由四个整数部分组成#xff0c;每部分的取值范围是 0-255#xff0c;每个部分不能包含前导零。
解题思路
这道题目要求我们将一个数字字…93. 复原IP地址
题目描述
给定一个只包含数字的字符串 s复原它并返回所有可能的有效 IP 地址格式。
一个有效的 IP 地址 由四个整数部分组成每部分的取值范围是 0-255每个部分不能包含前导零。
解题思路
这道题目要求我们将一个数字字符串分割成四个有效的 IP 地址部分。可以使用回溯算法来解决这个问题。回溯法可以帮助我们遍历所有可能的分割方式然后验证每个分割是否符合有效 IP 地址的规则。
关键点
回溯法从字符串的起始位置开始递归地尝试分割出每一部分每一部分必须是一个有效的数字并且不能超过 255。有效 IP 地址的条件 每部分数字的范围是 0 到 255。每部分不能有前导零除非部分的值是 “0”。最终结果必须包含四个部分。 分割条件每次递归时检查当前子串是否符合条件。如果符合条件递归继续处理剩余的部分。
步骤
分割字符串从字符串的起始位置开始分割每次分割出一个子串检查该子串是否有效。递归处理如果当前部分有效递归处理剩余的部分直到分割出四个部分。回溯每当分割出一个有效部分后恢复状态继续尝试其他可能的分割方式。结束条件当分割出四个部分且整个字符串处理完毕时将该分割方式保存到结果列表中。
代码实现
class Solution {ListString result new ArrayList();public ListString restoreIpAddresses(String s) {if(s.length()12)return result;treebuilding(s,0,0);return result;}public void treebuilding(String s,int startIndex,int pointSum) {if(pointSum3){if(check(s,startIndex,s.length()-1)){result.add(s);}return;}for(int istartIndex;is.length();i){if(check(s,startIndex,i)){s s.substring(0,i1).s.substring(i1);pointSum;treebuilding(s,i2,pointSum);pointSum--;s s.substring(0,i1)s.substring(i2);}else {break;}}}public boolean check(String s,int start,int end) {if(startend){return false;}if(s.charAt(start) 0 start!end){return false;}int num 0;for(int i start;iend;i){if(s.charAt(i)9 || s.charAt(i) 0){return false;}num num*10(s.charAt(i)-0);if(num255){return false;}}return true;}
}78. 子集
题目描述
给定一组不含重复元素的整数数组 nums返回该数组所有可能的子集幂集。
说明
解集不能包含重复的子集。
解题思路
这道题目要求我们找到数组 nums 的所有可能子集。由于子集的数量为 2^n其中 n 是数组的长度因此可以使用回溯算法生成所有可能的子集。
关键点
回溯法通过回溯法可以在每一层递归中选择或不选择当前元素来生成所有的子集。子集生成每次递归时都会向当前路径中添加一个新的元素同时递归生成后续的子集。每次递归结束后都会移除当前元素以尝试其他可能性。路径管理使用一个 path 列表来存储当前子集的元素并在递归过程中进行更新。
步骤
从空子集开始逐渐向路径中添加元素形成一个新的子集。对于每个元素可以选择加入子集或不加入子集。递归处理每个可能的选择直到遍历完所有元素。每次递归时加入当前路径到结果集 result 中最终返回所有的子集。
代码实现
class Solution {ListListInteger result new ArrayList();LinkedListInteger path new LinkedList();public ListListInteger subsets(int[] nums) {treebuilding(nums,0);return result;}public void treebuilding(int[] nums,int startIndex) {result.add(new ArrayList(path));if(startIndexnums.length){return;}for(int i startIndex;inums.length;i){path.add(nums[i]);treebuilding(nums,i1);path.removeLast();}}
}90. 子集 II
题目描述
给定一个可能包含重复元素的整数数组 nums返回该数组所有可能的子集幂集。
说明
解集不能包含重复的子集。
解题思路
这道题目与第78题“子集”非常相似但有一个额外的挑战——数组可能包含重复元素因此我们需要确保生成的子集不会重复。为了处理这个问题使用 used 数组来避免重复元素的选择。
关键点
回溯法和第78题一样我们使用回溯法生成所有的子集。区别在于这里我们需要处理重复元素确保不产生重复的子集。重复元素的处理为了避免重复的子集我们在回溯过程中通过 used 数组来标记已经被使用过的元素。当遇到重复元素时只有当前一个相同元素已经被选择过时才能选择当前元素。排序我们首先对 nums 数组进行排序这样相同的元素会被放在一起方便我们在回溯过程中跳过重复的元素。
used 数组的作用
used 数组是用来标记当前元素是否已经被使用过以确保我们在回溯的过程中不会选择重复的元素。特别地used 数组的作用如下
标记已经使用的元素在每次递归中如果我们选择了一个元素就通过将 used[i] 设置为 true 来标记这个元素已经被使用。然后递归处理后续的元素。跳过重复元素当我们遇到重复元素时used 数组能够确保我们跳过那些“重复的”分支。具体来说在遍历过程中如果当前元素 nums[i] 和前一个元素 nums[i-1] 相等并且前一个元素没有被选过即 used[i-1] false则跳过当前元素 nums[i]防止重复子集的生成。
解决重复子集的核心
排序对数组进行排序使得相同的元素相邻。这样在回溯过程中当遇到重复元素时可以判断它是否已经被处理过。跳过重复元素通过 used 数组来标记每个元素是否被使用过。如果当前元素和前一个元素相同并且前一个元素没有被使用过则跳过当前元素这样可以避免在同一层递归中重复使用相同的元素。
步骤
排序首先对数组进行排序使得相同的元素相邻便于跳过重复元素。回溯法递归地生成所有子集每次选择一个元素加入当前子集。跳过重复元素在遍历元素时如果当前元素与前一个元素相同并且前一个元素没有被选择则跳过当前元素避免产生重复子集。
代码实现
class Solution {ListListInteger result new ArrayList();LinkedListInteger path new LinkedListInteger();boolean[] used;public ListListInteger subsetsWithDup(int[] nums) {if(nums.length0){result.add(path);return result;}Arrays.sort(nums);used new boolean[nums.length];treebuilding(nums,0);return result;}public void treebuilding(int[] nums,int startIndex){result.add(new ArrayList(path));if(startIndexnums.length){return;}for(int i startIndex;inums.length;i){if(i!0 nums[i] nums[i-1] !used[i-1]){continue;}path.add(nums[i]);used[i] true;treebuilding(nums,i1);used[i] false;path.removeLast();}}
}
