公司网站制作与维护,上海外贸市场有哪些,企业宽带 做网站,如何修改wordpress93.复原IP地址
有效 IP 地址 正好由四个整数#xff08;每个整数位于 0 到 255 之间组成#xff0c;且不能含有前导 0#xff09;#xff0c;整数之间用 . 分隔。
例如#xff1a;0.1.2.201 和 192.168.1.1 是 有效 IP 地址#xff0c;但是 每个整数位于 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.length 20s 仅由数字组成
思路
常规思路回溯需要加上判断是否有前导0、单串子串大于等于0且小于等于255的判断
class Solution {ListString resnew ArrayList();int[] segmentsnew int[4];public ListString restoreIpAddresses(String s) {if(s.length()12||s.length()4){return res;}dfs(s,0,0);return res;}public void dfs(String s,int id,int begin){if(id4){if(begins.length()){StringBuffer sbnew StringBuffer();for(int i0;i4;i){sb.append(segments[i]);if(i!3){sb.append(.);}}res.add(sb.toString());}return;}if(begins.length()){return;}if(s.charAt(begin)0){segments[id]0;dfs(s,id1,begin1);return;}int temp0;for(int ibegin;is.length();i){temptemp*10(s.charAt(i)-0);if(temp0temp0xFF){segments[id]temp;dfs(s,id1,i1);}else {break;}}}} 78.子集
给你一个整数数组 nums 数组中的元素 互不相同 。返回该数组所有可能的
子集
幂集。
解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。 提示
1 nums.length 10-10 nums[i] 10nums 中的所有元素 互不相同
思路
两种方法一种递归法另一种迭代法即将数组每一位是否在数组中存为0或1这样只要遍历0到1n即可遍历所有情况
递归法
class Solution {ListListInteger resnew ArrayList();ListInteger pathnew ArrayList();public ListListInteger subsets(int[] nums) {dfs(0,nums);return res;}private void dfs(int cur,int[] nums){if(curnums.length){ListInteger ansnew ArrayList(path);res.add(new ArrayList(ans));return;}path.add(nums[cur]);dfs(cur1,nums);path.remove(path.size()-1);dfs(cur1,nums);}}
迭代法
class Solution {ListListInteger resnew ArrayList();ListInteger pathnew ArrayList();public ListListInteger subsets(int[] nums) {int nnums.length;for(int mask0;mask(1n);mask){path.clear();for (int i0;in;i){if ((mask (1 i)) ! 0) {path.add(nums[i]);}}res.add(new ArrayList(path));}return res;}}
总结
常规题型。
