国际贸易网站哪家好,网站制作在哪里比较好,最简单的网站开发软件,网站如何做访客统计Day 20 总结
自己实现中遇到哪些困难 一句话讲明白问题分类 组合问题和分割问题都是收集树的叶子节点#xff0c;子集问题是找树的所有节点#xff01;切割字符串问题回顾 昨天的切割回文子串#xff0c;和今天的切割ip地址#xff0c;都是需要将字符串拆分成 n 份。只不过…Day 20 总结
自己实现中遇到哪些困难 一句话讲明白问题分类 组合问题和分割问题都是收集树的叶子节点子集问题是找树的所有节点切割字符串问题回顾 昨天的切割回文子串和今天的切割ip地址都是需要将字符串拆分成 n 份。只不过每一小份的长度不定切完当前这一小份再交给下层去切割剩余部分。今日收获记录一下自己的学习时间 17:30 - 19:00
93.复原IP地址
题目链接/文章讲解代码随想录
题目链接https://leetcode.cn/problems/restore-ip-addresses/
题目描述
有效 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 中的任何数字。你可以按 任何 顺序返回答案。
实现思路
将字符串分隔成四个部分并且每个部分都是有效的数字0-255。
1.字符串分隔一定是从前向后进行切割先切割一个数字出来然后再对剩下的字符串再次进行切割。然后要检查当前切割出来的字符串是不是合格的如果前面都切不出来合格的字符串后面的切割也没有意义直接结束该分支的搜索。找到了一个合适的字符串就传递到下层一次再剩余字符串中继续切割。当前层切割的字符串长度慢慢递增。
2.检查切割的结果到达搜索树的结尾时要确保整个字符串已经切割完了并且切割成了四个部分。排除不符合条件的分支并把切割完的字符串收集到结果集合中。
回溯模板
代码实现
class Solution {public ListString results new ArrayList();public ListString path new ArrayList();public ListString restoreIpAddresses(String s) {backtrack(s, 0);return results;}// 参数// 返回值:public void backtrack(String s, int startIndex) {// 终止条件if (path.size() 4) {return;} if (startIndex s.length() path.size() 4) {StringBuffer ipAddr new StringBuffer();for (int i0; i4; i) {ipAddr.append(path.get(i));if (i 3) {ipAddr.append(.);}}results.add(ipAddr.toString());}// 回溯单层搜索过程for (int istartIndex; is.length(); i){if (!isValid(s, startIndex, i1)) {continue;}path.add(s.substring(startIndex, i1));backtrack(s, i1);path.remove(path.size()-1);}}public boolean isValid(String s, int start, int end) {if (end - start 3) {return false;}if (s.charAt(start) 0) {if (end - start 1) {return false;}}if (end - start 2) {if (s.charAt(start) 0) {return false;}if (Integer.parseInt(s.substring(start,end)) 255) {return false;}}return true;}
}// 实现方案2
class Solution {ListInteger path new ArrayList();ListString results new ArrayList();char[] arr;public ListString restoreIpAddresses(String s) {arr s.toCharArray();backtrack(0);return results;}public void backtrack(int startIdx) {if (path.size() 4 || startIdx arr.length) return;if (startIdx arr.length path.size() 4) {String s ;for (Integer i : path) s si.;results.add(s.substring(0,s.length()-1));}for (int istartIdx; iarr.length; i) {int num getNum(startIdx, i);if (num -1) return;path.add(num);backtrack(i1);path.remove(path.size()-1);}}public int getNum(int start, int end) {// 小于四位数if (end - start 3) return -1;// 没有前导0if (arr[start] 0) {if (end start) return -1;return 0;}// 1-255int num 0;while (start end) {num num * 10 (int)(arr[start]-0);}if (num 255) return -1;return num;}
}
78.子集
题目链接/文章讲解代码随想录
题目链接https://leetcode.cn/problems/subsets/
题目描述
给你一个整数数组 nums 数组中的元素 互不相同 。返回该数组所有可能的子集幂集。解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
实现思路
收集搜索树上的所有节点。
回溯模板
代码实现
class Solution {// 全局变量免去参数传递ListListInteger results new ArrayList();ListInteger path new ArrayList();int[] nums;public ListListInteger subsets(int[] nums) {this.nums nums;results.add(new ArrayList(path)); // 空集backtrace(0);return results;}public void backtrace(int startIdx) {// 到达底搜索树底层向上返回if (startIdx nums.length) return;for (int istartIdx; inums.length; i) {path.add(nums[i]);results.add(new ArrayList(path)); // 收集所有情况backtrace(i1);path.remove(path.size()-1);}}
}
